From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wi0-f175.google.com (mail-wi0-f175.google.com [209.85.212.175]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id A265721F09E for ; Sun, 13 May 2012 00:23:31 -0700 (PDT) Received: by wibhn6 with SMTP id hn6so1336494wib.10 for ; Sun, 13 May 2012 00:23:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=subject:from:to:cc:in-reply-to:references:content-type:date :message-id:mime-version:x-mailer:content-transfer-encoding; bh=f/4+1aRXcAvY+7IzVakiBRMcejt0hzwH08ciZxEe+iU=; b=yMwWJ61CcQxL2/kfjwby93uAsHr23WoXDHJdcOLfD6Vat/6Ol+SjIGjs9I2M/50V8U 1k1Xqc0i2DH5pRo7qNixKCn4I+jVetVD/pFBIY2kSuoDNTCKp/2rZ6T+4vIDAEOwAKhp O4d/eAm7Y2myTMQCC4NTuHl6dcZZDyKT9jO94cdxHZner354uBBTmvKW+cKAGtyGBb1P aha8A+D4zR0g/D1ZHO+ZS+mvrDDlRlQfuYQvYithUI6ojRhK643ba7cvt5M0uCzYr/UF SooFbBTv+BGZLAg/04dTBgqiFNMoumMbdkGFSBzf4SRMeKs8P/AxPbiMwczwe3pcShup BqBg== Received: by 10.180.100.230 with SMTP id fb6mr10031239wib.3.1336893808986; Sun, 13 May 2012 00:23:28 -0700 (PDT) Received: from [172.28.131.74] ([74.125.122.49]) by mx.google.com with ESMTPS id g10sm16354068wiw.0.2012.05.13.00.23.25 (version=SSLv3 cipher=OTHER); Sun, 13 May 2012 00:23:27 -0700 (PDT) From: Eric Dumazet To: David Miller In-Reply-To: <20120512.175217.1632102067268101115.davem@davemloft.net> References: <1336855256.31653.1329.camel@edumazet-glaptop> <20120512.164513.1156706853054390966.davem@davemloft.net> <1336859324.31653.1385.camel@edumazet-glaptop> <20120512.175217.1632102067268101115.davem@davemloft.net> Content-Type: text/plain; charset="UTF-8" Date: Sun, 13 May 2012 09:23:23 +0200 Message-ID: <1336893803.8512.43.camel@edumazet-glaptop> Mime-Version: 1.0 X-Mailer: Evolution 2.28.3 Content-Transfer-Encoding: 7bit Cc: dave.taht@bufferbloat.net, nanditad@google.com, netdev@vger.kernel.org, codel@lists.bufferbloat.net, ycheng@google.com, shemminger@vyatta.com, mattmathis@google.com Subject: Re: [Codel] [PATCH net-next] codel: use Newton method instead of sqrt() and divides X-BeenThere: codel@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: CoDel AQM discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 13 May 2012 07:23:32 -0000 From: Eric Dumazet On Sat, 2012-05-12 at 17:52 -0400, David Miller wrote: > Ok, fair enough. Oh well, I sent my mail too late. The error made no sense after a good night. Also, when Van says something, you can be fairly sure its right, and if it's not, then you didn't understand what Van said ;) 16bit precision is OK, once the maths are correctly done in the userland program I wrote yesterday... count=16525, precision=16 bits, sqrt(scaled_count)=4113, reciprocal(sq)=1fde240, Newton=1fd0000 interval/sqrt(16525) = 777909 (float compute) // (u32)(interval/sqrt(count)) 778020 (integer approx) // reciprocal_divide(interval, rec) 777926 (int_sqrt_div) // int_sqrt_div(interval, count) 776672 (Newton approx) // reciprocal_divide(interval, previnv << shift) count=9889134, precision=16 bits, sqrt(scaled_count)=50315, reciprocal(sq)=14d720, Newton=140000 interval/sqrt(9889134) = 31799 (float compute) 31799 (integer approx) 31799 (int_sqrt_div) 30517 (Newton approx) And kernel code using u16 : 6a1: 0f b7 72 0a movzwl 0xa(%rdx),%esi 6a5: 8b 3a mov (%rdx),%edi 6a7: 83 c7 01 add $0x1,%edi 6aa: c1 e6 10 shl $0x10,%esi 6ad: 89 3a mov %edi,(%rdx) vars->count++ 6af: 89 ff mov %edi,%edi 6b1: 89 f6 mov %esi,%esi 6b3: 48 89 f1 mov %rsi,%rcx 6b6: 48 0f af ce imul %rsi,%rcx 6ba: 48 c1 e9 20 shr $0x20,%rcx 6be: 48 0f af cf imul %rdi,%rcx 6c2: 48 bf 00 00 00 00 03 mov $0x300000000,%rdi 6c9: 00 00 00 6cc: 48 29 cf sub %rcx,%rdi 6cf: 48 89 f9 mov %rdi,%rcx 6d2: 48 c1 e9 02 shr $0x2,%rcx 6d6: 48 0f af ce imul %rsi,%rcx 6da: 48 c1 e9 2f shr $0x2f,%rcx 6de: 66 89 4a 0a mov %cx,0xa(%rdx) Fell free to add following cleanup patch, if you like it ;) Thanks [PATCH net-next] codel: use u16 field instead of 31bits for rec_inv_sqrt David pointed out gcc might generate poor code with 31bit fields. Using u16 is more than enough and permits a better code output. Also make the code intent more readable using constants, fixed point arithmetic not being trivial for everybody. Suggested-by: David Miller Signed-off-by: Eric Dumazet --- include/net/codel.h | 25 +++++++++++++++---------- 1 file changed, 15 insertions(+), 10 deletions(-) diff --git a/include/net/codel.h b/include/net/codel.h index bd8747c..7546517 100644 --- a/include/net/codel.h +++ b/include/net/codel.h @@ -133,13 +133,17 @@ struct codel_params { struct codel_vars { u32 count; u32 lastcount; - bool dropping:1; - u32 rec_inv_sqrt:31; + bool dropping; + u16 rec_inv_sqrt; codel_time_t first_above_time; codel_time_t drop_next; codel_time_t ldelay; }; +#define REC_INV_SQRT_BITS (8 * sizeof(u16)) /* or sizeof_in_bits(rec_inv_sqrt) */ +/* needed shift to get a Q0.32 number from rec_inv_sqrt */ +#define REC_INV_SQRT_SHIFT (32 - REC_INV_SQRT_BITS) + /** * struct codel_stats - contains codel shared variables and stats * @maxpacket: largest packet we've seen so far @@ -173,17 +177,18 @@ static void codel_stats_init(struct codel_stats *stats) * http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots * new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2) * - * Here, invsqrt is a fixed point number (< 1.0), 31bit mantissa) + * Here, invsqrt is a fixed point number (< 1.0), 32bit mantissa, aka Q0.32 */ static void codel_Newton_step(struct codel_vars *vars) { - u32 invsqrt = vars->rec_inv_sqrt; - u32 invsqrt2 = ((u64)invsqrt * invsqrt) >> 31; - u64 val = (3LL << 31) - ((u64)vars->count * invsqrt2); + u32 invsqrt = ((u32)vars->rec_inv_sqrt) << REC_INV_SQRT_SHIFT; + u32 invsqrt2 = ((u64)invsqrt * invsqrt) >> 32; + u64 val = (3LL << 32) - ((u64)vars->count * invsqrt2); - val = (val * invsqrt) >> 32; + val >>= 2; /* avoid overflow in following multiply */ + val = (val * invsqrt) >> (32 - 2 + 1); - vars->rec_inv_sqrt = val; + vars->rec_inv_sqrt = val >> REC_INV_SQRT_SHIFT; } /* @@ -195,7 +200,7 @@ static codel_time_t codel_control_law(codel_time_t t, codel_time_t interval, u32 rec_inv_sqrt) { - return t + reciprocal_divide(interval, rec_inv_sqrt << 1); + return t + reciprocal_divide(interval, rec_inv_sqrt << REC_INV_SQRT_SHIFT); } @@ -326,7 +331,7 @@ static struct sk_buff *codel_dequeue(struct Qdisc *sch, codel_Newton_step(vars); } else { vars->count = 1; - vars->rec_inv_sqrt = 0x7fffffff; + vars->rec_inv_sqrt = ~0U >> REC_INV_SQRT_SHIFT; } vars->lastcount = vars->count; vars->drop_next = codel_control_law(now, params->interval,