Re: [RFC][PATCH] Faster generic_fls

[hugang]

On Thu, 1 May 2003 17:54:28 +0200
Thomas Schlichter <[e-mail]> wrote:

> Hi,
> 
> On March 1, hugang wrote:
> > On Thu, 1 May 2003 15:52:04 +0200
> >
> > Willy TARREAU <[e-mail]> wrote:
> > >  However, I have good news for you, the table code is 15% faster than my
> > > tree on an Alpha EV6 ;-)
> > >  It may be because gcc can use different tricks on this arch.
> > >
> > >  Cheers
> > >  Willy
> >
> > However, The most code changed has increase a little peformance, Do we
> > really need it?
> >
> > Here is test in my machine, The faster is still table.
> 
> I think the table version is so fast as a normal distribution of numbers is 
> tested. With this distribution half of the occuring values have the MSB set, 
> one quarter the next significant bit and so on...
> 
> The tree version is approximately equally fast for every number, but the table 
> version is fast if a very significant bit is set and slow if  a less 
> significant bit is set...
> 
> If small values occour more often than big ones the tree version should be 
> preferred, else following version may be very fast, too.
> 
> static inline int fls_shift(int x)
> {
> 	int bit = 32;
>  
> 	while(x > 0) {
> 		--bit;
> 		x <<= 1;
> 	}
> 
> 	return x ? bit : 0;
> }
> 

Yes, The shift is very faster than other. Here is a test in P4 1.6G.

model name      : Intel(R) Pentium(R) 4 Mobile CPU 1.60GHz
Reading specs from /usr/lib/gcc-lib/i386-linux/2.95.4/specs
gcc version 2.95.4 20011002 (Debian prerelease)
==== -Wall -Wstrict-prototypes -Wno-trigraphs -O2 -fno-strict-aliasing -fno-common -fomit-frame-pointer -pipe -mpreferred-stack-boundary=2 -march=i686 ====
test_fls.c: In function `fls_tree_fls':
test_fls.c:85: warning: type defaults to `int' in declaration of `t'
4294967295 iterations of nil... checksum = 4294967295

real    0m21.698s
user    0m21.650s
sys     0m0.000s
4294967295 iterations of table... checksum = 4294967265

real    0m41.581s
user    0m41.500s
sys     0m0.000s
4294967295 iterations of tree... checksum = 4294967265

real    1m1.173s
user    1m1.040s
sys     0m0.000s
4294967295 iterations of shift... checksum = 4294967265

real    0m22.050s
user    0m22.000s
sys     0m0.010s

-- 
Hu Gang / Steve
Email        : [e-mail], [e-mail]
GPG FinePrint: 4099 3F1D AE01 1817 68F7  D499 A6C2 C418 86C8 610E
ICQ#         : 205800361
Registered Linux User : 204016