Re: 64-bit masks

[christos%astron.com@localhost (Christos Zoulas)]

In article <op.u36j5hpo8u90ff@localhost>,
Sad Clouds  <cryintothebluesky%googlemail.com@localhost> wrote:
>-=-=-=-=-=-
>
>On Fri, 27 Nov 2009 16:00:43 -0000, Robert Elz <kre%munnari.oz.au@localhost> 
>wrote:
>
>> Whether this is really an appropriate algorithm depends on just what you
>> need to know all the free objects for - if you just want to find the  
>> first
>> free object, there are easier (faster) ways, but if you really need to
>> find all of them, this might be OK.
>
>Hi, well I really need to find the first free object, not all the free  
>objects at once. The faster I can do it, the better. I looked at ffs()  
>function to find first set bit, but it operates on integers, which I think  
>might be problematic because:
>
>1. On different platforms integer could be 16, 32, or even 64-bits wide
>2. If I need to keep track of 64 or more objects, I would need an array of  
>integers. Calling ffs() function several times might slow things down. But  
>if ffs() is implemented via fast assembly instruction, I guess it should  
>be OK.
>
>It also needs to be portable to at least BSD, Linux and Solaris.
>
>My code assumes bit 1 is busy, and bit 0 is free. So I came up with the  
>following function (attached) to look for the first unset (0) bit. If  
>anyone knows faster algorithms, I'd be interested to know.
>
>PS. I ran a quick benchmark on Sparc Solaris, a loop of 10_000_000  
>iterations calling ffs() on 32-bit int, and a loop for my function on  
>64-bit int.
>
>/opt/SUNWspro/bin/cc -xO3 find_bit.c
>
>This is my function:
>rom@ultra10 ptime ./a.out
>
>real        0.561
>user        0.542
>sys         0.009
>
>This is Solaris ffs():
>rom@ultra10 ptime ./a.out
>
>real        0.680
>user        0.626
>sys         0.009
>
>
>I suppose it's a good start.
>-=-=-=-=-=-
>
>
>/*
>ffu_bit - find first unset bit
>
>Return:
> index of first unset bit (0 to 63)
> -1 if there were no unset bits
>
>Pre:
> bit_str is a 64-bit unsigned integer
>
>Post:
> none
>
>The function uses binary search algorithm to find 8-bit byte inside a 64-bit
>integer, which contains an unset bit.
>
>The function divides 64-bit integer into two 32-bit halves. It then divides
>each 32-bit half into two 16-bit halves. Each of the 16-bit halves is then
>divided into two 8-bit halves.

How does the ffs64() from <sys/bitops.h> do?

christos