Subject: Re: diff to speed up fdalloc using two-level bitmaps
To: Niels Provos <firstname.lastname@example.org>
From: Matt Thomas <email@example.com>
Date: 10/29/2003 00:44:44
On Tuesday, October 28, 2003, at 10:59 PM, Niels Provos wrote:
> On Tue, Oct 28, 2003 at 11:25:59AM -0500, Niels Provos wrote:
>> It could need some fine tuning
>> An inline assembly function for finding the first zero bit in a
>> word would be a great thing to have across architectures.
> The same benchmark with the following inline assembly
> static __inline__ uint32_t ffz(uint32_t word)
> __asm__("bsfl %1,%0"
> :"=r" (word)
> :"r" (~word));
> return word;
> looks much better:
> Now, it is faster than before in all cases. It would be great if we
> could have a
> include file that would define similar inline assembly for all
> architectures or the equivalent C code if there is no instruction
Note that some architectures (like PowerPC) count bits differently
(bit 0 is the "leftmost" bit) and the cntlzw (count leading zeroes
word) count from left to right.
ffs(3) has not implied bit ordering. To use the more efficient
instructions, the bitops must deal with both bit orderings.
Matt Thomas email: firstname.lastname@example.org
3am Software Foundry www: http://3am-software.com/bio/matt/
Cupertino, CA disclaimer: I avow all knowledge of this