Messages in this thread | | | From | Thomas Schlichter <> | Subject | Re: [RFC][PATCH] Faster generic_fls | Date | Fri, 2 May 2003 01:27:16 +0200 |
| |
On May 1, Willy TARREAU wrote: > On Thu, May 01, 2003 at 10:53:21PM +0800, hugang wrote: > > Here is test in my machine, The faster is still table. > > because, as Falk said, the tests are incremental and the branch prediction > works very well. I proposed a simple scrambling function based on bswap. > Please consider this function : > > f(i) = i ^ htonl(i) ^ htonl(i<<7) > > It returns such values : > > 0x00000001 => 0x81000001 > 0x00000002 => 0x02010002 > 0x00000003 => 0x83010003 > 0x00000004 => 0x04020004 > 0x00000005 => 0x85020005 > 0x00000006 => 0x06030006 > 0x00000007 => 0x87030007 > 0x00000008 => 0x08040008 > 0x00000009 => 0x89040009 > 0x0000000a => 0x0a05000a > 0x0000000b => 0x8b05000b > > etc... > > As you see, high bits move fast enough to shot a predictor. > > The tree function as well as Daniel's "new" resist better to non linear > suites. BTW, the latest changes I did show that the convergence should be > between Daniel's function and mine, because there are common concepts. I > noticed that the expression used in Daniel's function is too complex for > gcc to optimize it well enough. In my case, gcc 3.2.3 coded too many jumps > instead of conditional moves. I saw that playing with -mbranch-cost changes > the code. A mix between the two is used here (and listed after). It's still > not optimial, reading the code, because there's always one useless jump and > move. But in the worst case, it gives exactly the same result as Daniel's. > But in other cases, it is even slightly faster. Honnestly, now it's just a > matter of taste. Daniel's easier to read, mine produces smaller code. This > time, it's faster than others Athlon, Alpha and Sparc. I Don't know about > the PentiumIII nor the P4. > > Here are the results on Athlon, gcc-3.2.3, then Alpha and Sparc.
~~ snip~~
Here are some results with the scrambling function on AMD K6-III 450MHz, gcc-2.95.3:
fls_old (generic_fls from linux 2.5.68): real 3m52.960s user 3m42.080s sys 0m0.348s
fls_bsrl: real 4m39.040s user 4m25.532s sys 0m0.401s
fls_table: real 4m59.622s user 4m45.511s sys 0m0.469s
fls_tree: real 3m3.986s user 2m55.236s sys 0m0.272s
fls_shift: real 2m58.765s user 2m50.092s sys 0m0.278s
So for me the table version seems to be the slowest one. The BSRL instruction on the K6-III seems to be very slow, too. The tree and my shift version are faster than the original version here...
That someone else can test my fls_shift version I'll provide it here again: static inline int fls_shift(int x) { int bit = 32; while(x > 0) { --bit; x <<= 1; }
return x ? bit : 0; }
> Willy
Thomas[unhandled content-type:application/pgp-signature] | |