lkml.org 
[lkml]   [2007]   [Mar]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    Subject[PATCH 2/2] tcp: cubic optimization
    Use willy's work in optimizing cube root by having table for small values.

    Signed-off-by: Stephen Hemminger <shemminger@linux-foundation.org>

    --- net-2.6.22.orig/net/ipv4/tcp_cubic.c 2007-03-21 12:57:11.000000000 -0700
    +++ net-2.6.22/net/ipv4/tcp_cubic.c 2007-03-21 13:04:59.000000000 -0700
    @@ -91,23 +91,51 @@
    tcp_sk(sk)->snd_ssthresh = initial_ssthresh;
    }

    -/*
    - * calculate the cubic root of x using Newton-Raphson
    +/* calculate the cubic root of x using a table lookup followed by one
    + * Newton-Raphson iteration.
    + * Avg err ~= 0.195%
    */
    static u32 cubic_root(u64 a)
    {
    - u32 x;
    -
    - /* Initial estimate is based on:
    - * cbrt(x) = exp(log(x) / 3)
    + u32 x, b, shift;
    + /*
    + * cbrt(x) MSB values for x MSB values in [0..63].
    + * Precomputed then refined by hand - Willy Tarreau
    + *
    + * For x in [0..63],
    + * v = cbrt(x << 18) - 1
    + * cbrt(x) = (v[x] + 10) >> 6
    */
    - x = 1u << (fls64(a)/3);
    + static const u8 v[] = {
    + /* 0x00 */ 0, 54, 54, 54, 118, 118, 118, 118,
    + /* 0x08 */ 123, 129, 134, 138, 143, 147, 151, 156,
    + /* 0x10 */ 157, 161, 164, 168, 170, 173, 176, 179,
    + /* 0x18 */ 181, 185, 187, 190, 192, 194, 197, 199,
    + /* 0x20 */ 200, 202, 204, 206, 209, 211, 213, 215,
    + /* 0x28 */ 217, 219, 221, 222, 224, 225, 227, 229,
    + /* 0x30 */ 231, 232, 234, 236, 237, 239, 240, 242,
    + /* 0x38 */ 244, 245, 246, 248, 250, 251, 252, 254,
    + };
    +
    + b = fls64(a);
    + if (b < 7) {
    + /* a in [0..63] */
    + return ((u32)v[(u32)a] + 35) >> 6;
    + }
    +
    + b = ((b * 84) >> 8) - 1;
    + shift = (a >> (b * 3));

    - /* converges to 32 bits in 3 iterations */
    - x = (2 * x + (u32)div64_64(a, (u64)x*(u64)x)) / 3;
    - x = (2 * x + (u32)div64_64(a, (u64)x*(u64)x)) / 3;
    - x = (2 * x + (u32)div64_64(a, (u64)x*(u64)x)) / 3;
    + x = ((u32)(((u32)v[shift] + 10) << b)) >> 6;

    + /*
    + * Newton-Raphson iteration
    + * 2
    + * x = ( 2 * x + a / x ) / 3
    + * k+1 k k
    + */
    + x = (2 * x + (u32)div64_64(a, (u64)x * (u64)(x - 1)));
    + x = ((x * 341) >> 10);
    return x;
    }


    --
    Stephen Hemminger <shemminger@linux-foundation.org>
    -
    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: 2007-03-21 21:25    [W:0.025 / U:37.504 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site