Re: diff to speed up fdalloc using two-level bitmaps

On Wed, Oct 29, 2003 at 01:59:13AM -0500, Niels Provos wrote:
> On Tue, Oct 28, 2003 at 11:25:59AM -0500, Niels Provos wrote:
> > It could need some fine tuning
> > 
> >  http://www.citi.umich.edu/u/provos/benchmark/netbsd-fdalloc-zoom.jpg
> > 
> > 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;
> }

One caveat is, if the argument word is passed as 0, the result of
bsfl is undefined (i.e., unpredictable). So there's needed additional
code to check if it's 0. 

BTW, how about making ffs(9) inline as well? Calling overhead seems
to be quite high on i386...

Jun-Young

-- 
Bang Jun-Young <[email protected]>