Messages in this thread | ![/](/images/icornerl.gif) | | From | Thomas Schlichter <> | Subject | Re: [RFC][PATCH] Faster generic_fls | Date | Fri, 2 May 2003 03:47:37 +0200 |
| |
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] | ![\](/images/icornerr.gif) |