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.026 / U:90.356 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site