www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.intrinsic and bit arrays

reply Munchgreeble bigfoot.com writes:
Wow. I am practically watering at the mouth. I've just discovered std.intrinsic
Only the other day a colleague and I were debating what the best way was to find
a bit in a bit array. Both of us lamenting that despite the fact that this
problem comes up time and again in embedded code, you almost always end up doing
a linear search - terribly inefficient when most processors have a dedicated
instruction.

Imagine my delight when just now I discovered D gives you access to the
dedicated CPU instruction to do just that. I'm over the moon =)

One thing I wasn't clear on though, how do these functions relate to bit arrays?
Bit arrays seem like the obvious thing to use as arguments here - is it possible
to use them instead? I was kind of hoping that bit arrays would provide a layer
of abstraction on top of this stuff, whilst still allowing bit level operations.
E.g. it would be nice to be able to do the below, instead of having to declare
"bits" and "moreBits" as ints.

bit[32] bits;
bit[32] moreBits;
:
blah; 
:
bits = bits ^ moreBits;

but I can live without bit arrays if needs be - it would just have been a nice
to have.

Thanks =)

Munch
Nov 22 2005
next sibling parent reply Sean Kelly <sean f4.ca> writes:
Munchgreeble bigfoot.com wrote:

 
 One thing I wasn't clear on though, how do these functions relate to bit
arrays?
 Bit arrays seem like the obvious thing to use as arguments here - is it
possible
 to use them instead? I was kind of hoping that bit arrays would provide a layer
 of abstraction on top of this stuff, whilst still allowing bit level
operations.
 E.g. it would be nice to be able to do the below, instead of having to declare
 "bits" and "moreBits" as ints.



It's not an answer, but you can accomplish quite a bit via slicing and 
clever casting if you're willing to live some terrifying code:

void main() {
     uint x = 99;
     bit[] b = cast(bit[])(cast(bit*)&x)[0..(x.sizeof*8)];
     printf( "%u\n", b.length );
     uint y = cast(uint)*&b[0];
     printf( "%u\n", x );
     printf( "%u\n", y );
     for( int i = 7; i >= 0; --i )
         printf( "%.*s", b[i] ? "1" : "0" );
     printf( "\n" );
}


Sean
Nov 22 2005
parent reply Munchgreeble <"a" b.com \"munchgreeble xATx bigfoot xDOTx com\"> writes:
Wow, now that's what I call casting =) It would have taken me quite a 
long time to almost get to that stage, give up and post to the 
newsgroup, so thanks - much appreciated.

It's not pretty I'll grant you, but you can usually encapsulate that 
stuff and cover it with comments, so I'm happy - thanks.

One thing I'm not clear on - does the slicing cost anything at run time? 
I'm guessing not since all the limits are calculable at compile time?

Regards

Munch

Sean Kelly wrote:


 Munchgreeble bigfoot.com wrote:
 

 One thing I wasn't clear on though, how do these functions relate to 
 bit arrays?
 Bit arrays seem like the obvious thing to use as arguments here - is 
 it possible
 to use them instead? I was kind of hoping that bit arrays would 
 provide a layer
 of abstraction on top of this stuff, whilst still allowing bit level 
 operations.



 It's not an answer, but you can accomplish quite a bit via slicing and 
 clever casting if you're willing to live some terrifying code:
 
 void main() {
     uint x = 99;
     bit[] b = cast(bit[])(cast(bit*)&x)[0..(x.sizeof*8)];
     printf( "%u\n", b.length );
     uint y = cast(uint)*&b[0];
     printf( "%u\n", x );
     printf( "%u\n", y );
     for( int i = 7; i >= 0; --i )
         printf( "%.*s", b[i] ? "1" : "0" );
     printf( "\n" );
 }
 
 
 Sean
Nov 23 2005
parent Sean Kelly <sean f4.ca> writes:
Munchgreeble wrote:

 Wow, now that's what I call casting =) It would have taken me quite a 
 long time to almost get to that stage, give up and post to the 
 newsgroup, so thanks - much appreciated.
 
 It's not pretty I'll grant you, but you can usually encapsulate that 
 stuff and cover it with comments, so I'm happy - thanks.
 
 One thing I'm not clear on - does the slicing cost anything at run time? 
 I'm guessing not since all the limits are calculable at compile time?



I suppose it depends how good the optimizer is.  Might be worth 
compiling with -O and looking at the output.


Sean
Dec 03 2005
prev sibling next sibling parent reply "Regan Heath" <regan netwin.co.nz> writes:
On Tue, 22 Nov 2005 22:34:41 +0000 (UTC), <Munchgreeble bigfoot.com> wrote:

 Wow. I am practically watering at the mouth. I've just discovered  
 std.intrinsic
 Only the other day a colleague and I were debating what the best way was  
 to find
 a bit in a bit array. Both of us lamenting that despite the fact that  
 this
 problem comes up time and again in embedded code, you almost always end  
 up doing
 a linear search - terribly inefficient when most processors have a  
 dedicated
 instruction.

 Imagine my delight when just now I discovered D gives you access to the
 dedicated CPU instruction to do just that. I'm over the moon =)

 One thing I wasn't clear on though, how do these functions relate to bit  
 arrays?
 Bit arrays seem like the obvious thing to use as arguments here - is it  
 possible
 to use them instead?



There are numerous posts on how bit arrays in D work, it seems people have  
a love/hate relationship with them, try a search you'll see what I mean.


 bit[32] bits;
 bit[32] moreBits;
 :
 blah;
 :
 bits = bits ^ moreBits;



I believe that once we get array operations the line above will be  
possible.

Regan
Nov 22 2005
parent reply Munchgreeble <"a" b.com \"munchgreeble xATx bigfoot xDOTx com\"> writes:
Regan Heath wrote:


 On Tue, 22 Nov 2005 22:34:41 +0000 (UTC), <Munchgreeble bigfoot.com> wrote:
 

 One thing I wasn't clear on though, how do these functions relate to 
 bit  arrays?
 Bit arrays seem like the obvious thing to use as arguments here - is 
 it  possible
 to use them instead?



 
 There are numerous posts on how bit arrays in D work, it seems people 
 have  a love/hate relationship with them, try a search you'll see what I 
 mean.



Thanks - a quick search for "bit array" was very informative. Actually I 
have to say that the archives are a mine of information. Everybody here 
in the newsgroup is so helpful and actually seems to dish out useful 
stuff. What a great place to be =)


 

 bit[32] bits;
 bit[32] moreBits;
 :
 blah;
 :
 bits = bits ^ moreBits;



 
 I believe that once we get array operations the line above will be  
 possible.



Ah yes - OK. Array operations sound great =) What I'm wondering is will 
the compiler (be able to) optimise such operations on bit arrays so that 
you don't end up with 32 separate XORs going on in the compiled code. 
Similarly, doing + on two bit arrays should just do a bitwise OR on each 
of the elements and multiply should turn into bitwise AND. I guess this 
is the kind of thing that's do-able?

Cheers

Munch
Nov 23 2005
parent "Regan Heath" <regan netwin.co.nz> writes:
On Wed, 23 Nov 2005 13:34:00 +0000, Munchgreeble <"a" b.com "munchgreeble  
xATx bigfoot xDOTx com"> wrote:

 bit[32] bits;
 bit[32] moreBits;
 :
 blah;
 :
 bits = bits ^ moreBits;



 possible.



 Ah yes - OK. Array operations sound great =) What I'm wondering is will  
 the compiler (be able to) optimise such operations on bit arrays so that  
 you don't end up with 32 separate XORs going on in the compiled code.  
 Similarly, doing + on two bit arrays should just do a bitwise OR on each  
 of the elements and multiply should turn into bitwise AND. I guess this  
 is the kind of thing that's do-able?



I suspect so. In which case I think we just "wait and see". I don't think  
optimisations like those are high on the priority list, compared to other  
things. I suspect that they and things like them will eventually get done,  
if we give Walter the time and space to do them in.

Regan
Nov 23 2005
prev sibling next sibling parent reply Derek Parnell <derek psych.ward> writes:
On Tue, 22 Nov 2005 22:34:41 +0000 (UTC), Munchgreeble bigfoot.com wrote:


 Wow. I am practically watering at the mouth. I've just discovered std.intrinsic



I didn't realize it existed either. It's just what I needed too. I'd
written a routine to read UTF text but needed to cater for endian-ness and
bswap() is perfect for it. I'd done it the slow way with temporary
variables :)

-- 
Derek
(skype: derek.j.parnell)
Melbourne, Australia
23/11/2005 11:40:52 AM
Nov 22 2005
parent Ben Hinkle <Ben_member pathlink.com> writes:
In article <1202ie2xfdynb.1jhc1jr4s9zi2$.dlg 40tude.net>, Derek Parnell says...

On Tue, 22 Nov 2005 22:34:41 +0000 (UTC), Munchgreeble bigfoot.com wrote:


 Wow. I am practically watering at the mouth. I've just discovered std.intrinsic



I didn't realize it existed either. It's just what I needed too. I'd
written a routine to read UTF text but needed to cater for endian-ness and
bswap() is perfect for it. I'd done it the slow way with temporary
variables :)



FWIW, std.stream.EndianStream could save you some trouble. It uses bswap, too.
Check out std.stream.EndianStream.fixBO (where BO stands for byte-order not
body-odour) for an endian-fixing routine that works for more than just 32 bits
words.
Nov 22 2005
prev sibling parent reply Tiago Gasiba <tiago.gasiba gmail.com> writes:
Munchgreeble bigfoot.com schrieb:


 Wow. I am practically watering at the mouth. I've just discovered
 std.intrinsic Only the other day a colleague and I were debating what the
 best way was to find a bit in a bit array. Both of us lamenting that
 despite the fact that this problem comes up time and again in embedded
 code, you almost always end up doing a linear search - terribly
 inefficient when most processors have a dedicated instruction.
 
 Imagine my delight when just now I discovered D gives you access to the
 dedicated CPU instruction to do just that. I'm over the moon =)
 



Wow!!! Me too! I'm speechless... Amazing! Thanks for posting this message -
you've opened my eyes! :)
Now (forgive my ignorance) I feel that I must ask the following:
If there are functions to find/set/reset bits, is there any function to count
bits?

For example, how can I do this efficiently:

  ulong  x = 0x1234;  // whatever...
  bitcount(x) -> 5;   // there are 5 ones in x

Thanks,
Tiago

-- 
Tiago Gasiba (M.Sc.) - http://www.gasiba.de
Everything should be made as simple as possible, but not simpler.
Nov 23 2005
parent reply Don Clugston <dac nospam.com.au> writes:
Tiago Gasiba wrote:

 Munchgreeble bigfoot.com schrieb:
 
 

Wow. I am practically watering at the mouth. I've just discovered
std.intrinsic Only the other day a colleague and I were debating what the
best way was to find a bit in a bit array. Both of us lamenting that
despite the fact that this problem comes up time and again in embedded
code, you almost always end up doing a linear search - terribly
inefficient when most processors have a dedicated instruction.

Imagine my delight when just now I discovered D gives you access to the
dedicated CPU instruction to do just that. I'm over the moon =)



 
 Wow!!! Me too! I'm speechless... Amazing! Thanks for posting this message -
you've opened my eyes! :)
 Now (forgive my ignorance) I feel that I must ask the following:
 If there are functions to find/set/reset bits, is there any function to count
bits?
 
 For example, how can I do this efficiently:
 
   ulong  x = 0x1234;  // whatever...
   bitcount(x) -> 5;   // there are 5 ones in x



That should be a standard function too. There's no instrinsic for it, 
though, because x86 has no instruction for that (some other CPUs do, 
though, it's typically called "population count" or POPC -- stupid name, 
bitcount is much better).

You add neighbouring bits, then add neighbouring pairs, nibbles, bytes, 
and words:

// Calculates the number of set bits in a 32-bit integer.
int bitcount(uint x)
{
// add neighbouring bits. Each bit is 0 or 1.
x = ((x&0xAAAAAAAA)>>1) +(x&0x55555555);
// now each two bits of x is a number 00,01 or 10.
// now add neighbouring pairs
x = ((x&0xCCCCCCCC)>>2) + (x&0x33333333);
// now each nibble holds 0000-0100. Adding them wont
// overflow any more, so we don't need to mask any more
// Now add the nibbles
x += (x>>4);
// each byte is a number from 00000000 to 00001000.
// now add the bytes
x += (x>>8);
// now add the words
x += (x>>16);
return x;
}

Nifty, eh? On paper, it doesn't look as fast as a table lookup, but it 
adds 4 bytes at once, and it has no cache problems, so in real problems 
it should be faster. (Note that if you do a simple speed test, a table 
lookup will look deceptively good because the table will stay in the 
cache. You need to profile a realistic program).

I did not make it up, I read it on a newsgroup long ago. But I recreated 
it from memory, so it's completely public domain.

I have a few of these bit functions (all in C++), I should convert them 
to D and submit them to Phobos. Especially since they even have unit 
tests -- a rarity for my C++ code :-)
Nov 23 2005
parent reply Don Clugston <dac nospam.com.au> writes:
Don Clugston wrote:

 
 I have a few of these bit functions (all in C++), I should convert them 
 to D and submit them to Phobos. Especially since they even have unit 
 tests -- a rarity for my C++ code :-)



I just put them into MathExtra on dsource.org. Not that they belong 
there, but anyway...
Nov 23 2005
parent Munchgreeble <"a" b.com \"munchgreeble xATx bigfoot xDOTx com\"> writes:
Great! And thanks for posting the algorithm - I must confess I've always 
used a 16-bit wide table lookup for bit counting.

Cheers

Munch

Don Clugston wrote:


 Don Clugston wrote:
 

 I have a few of these bit functions (all in C++), I should convert 
 them to D and submit them to Phobos. Especially since they even have 
 unit tests -- a rarity for my C++ code :-)



 
 I just put them into MathExtra on dsource.org. Not that they belong 
 there, but anyway...
Nov 23 2005