[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

**To**:**tech-userlevel%netbsd.org@localhost****Subject**:**Re: 64-bit masks****From**:**christos%astron.com@localhost (Christos Zoulas)**- Date: Mon, 30 Nov 2009 02:05:29 +0000 (UTC)

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

**Follow-Ups**:**Re: 64-bit masks***From:*Sad Clouds

**References**:**64-bit masks***From:*Sad Clouds

**Re: 64-bit masks***From:*Robert Elz

**Re: 64-bit masks***From:*Sad Clouds

- Prev by Date:
**Re: 64-bit masks** - Next by Date:
**Re: 64-bit masks** - Previous by Thread:
**Re: 64-bit masks** - Next by Thread:
**Re: 64-bit masks** - Indexes: