Gitweb: http://git.kernel.org/git/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commit;h=7e58886b45bc4a309aeaa8178ef89ff767daaf7f Commit: 7e58886b45bc4a309aeaa8178ef89ff767daaf7f Parent: 22b9a0a3a49ab1a856e0853b3f3dd2abd156bd7c Author: Stephen Hemminger <[EMAIL PROTECTED]> AuthorDate: Thu Mar 22 12:10:58 2007 -0700 Committer: David S. Miller <[EMAIL PROTECTED]> CommitDate: Wed Apr 25 22:27:19 2007 -0700
[TCP]: cubic optimization Use willy's work in optimizing cube root by having table for small values. Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]> Signed-off-by: David S. Miller <[EMAIL PROTECTED]> --- net/ipv4/tcp_cubic.c | 50 +++++++++++++++++++++++++++++++++++++++----------- 1 files changed, 39 insertions(+), 11 deletions(-) diff --git a/net/ipv4/tcp_cubic.c b/net/ipv4/tcp_cubic.c index 0e6cdfe..15c5803 100644 --- a/net/ipv4/tcp_cubic.c +++ b/net/ipv4/tcp_cubic.c @@ -91,23 +91,51 @@ static void bictcp_init(struct sock *sk) 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; } - To unsubscribe from this list: send the line "unsubscribe git-commits-head" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html