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 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]
\
 
 \ /
  Last update: 2005-03-22 13:35    [W:0.104 / U:0.592 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site