lkml.org 
[lkml]   [2003]   [May]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: [RFC][PATCH] Faster generic_fls
Date
On May 2, Daniel Phillips wrote:
> On Friday 02 May 2003 02:10, Willy Tarreau wrote:
> > At first, I thought you had coded an FFS instead of an FLS. But I
> > realized it's valid, and is fast because one half of the numbers tested
> > will not even take one iteration.
>
> Aha, and duh. At 1 million iterations, my binary search clobbers the shift
> version by a factor of four. At 2**31 iterations, my version also wins, by
> 20%.
>
> I should note that the iterations parameter to my benchmark program is
> deeply flawed, since it changes the nature of the input set, not just the
> number of iterations. Fortunately, all tests I've done have been with
> 2**32 iterations, giving a perfectly uniform distribution of input values.

That is what I posted in my first message in this thread... The shift
algorithm only works fine for uniform distributed input values... But here is
a version that behaves better for small values, too. I don't think it will
reach the tree version but it should be much better that the old version!

int fls_shift(int x)
{
int bit;

if(x & 0xFFFF0000) {
bit = 32;

while(x > 0) {
--bit;
x <<= 1;
}
} else {
bit = 0;

while(x) {
++bit;
x >>= 1;
}
}

return bit;
}

For me this version even speeds up the uniform distributed benchmark...

> For uniformly distributed inputs the simple shift loop does well, but for
> calculating floor(log2(x)) it's much worse than the fancier alternatives.
> I suspect typical usage leans more to the latter than the former.

If this is the case the tree version will surely be the best!

But I think this topic is not worth any further work as this is not used very
often... So this version will be my last one!

But this was a good example how suited algorithms can speed up benchmarks ;-)

> Regards,
>
> Daniel

Best regards
Thomas[unhandled content-type:application/pgp-signature]
\
 
 \ /
  Last update: 2005-03-22 13:35    [W:0.063 / U:1.240 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site