[lkml]   [2003]   [May]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: [RFC][PATCH] Faster generic_fls
    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,

    fls_old (generic_fls from linux 2.5.68):
    real 3m52.960s
    user 3m42.080s
    sys 0m0.348s

    real 4m39.040s
    user 4m25.532s
    sys 0m0.401s

    real 4m59.622s
    user 4m45.511s
    sys 0m0.469s

    real 3m3.986s
    user 2m55.236s
    sys 0m0.272s

    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) {
    x <<= 1;

    return x ? bit : 0;

    > Willy

    Thomas[unhandled content-type:application/pgp-signature]
     \ /
      Last update: 2005-03-22 13:35    [W:0.024 / U:90.708 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site