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 Friday 02 May 2003 02:10, Willy Tarreau wrote:
    > At first, I thought you had coded an FFS instead of an FLS. But I realized
    > it's valid, and is fast because one half of the numbers tested will not even
    > take one iteration.

    Aha, and duh. At 1 million iterations, my binary search clobbers the shift
    version by a factor of four. At 2**31 iterations, my version also wins, by
    20%.

    I should note that the iterations parameter to my benchmark program is deeply
    flawed, since it changes the nature of the input set, not just the number of
    iterations. Fortunately, all tests I've done have been with 2**32
    iterations, giving a perfectly uniform distribution of input values.

    For uniformly distributed inputs the simple shift loop does well, but for
    calculating floor(log2(x)) it's much worse than the fancier alternatives. I
    suspect typical usage leans more to the latter than the former.

    Regards,

    Daniel
    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-03-22 13:35    [W:2.901 / U:0.004 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site