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 B6DE3201AF6 for ; Sat, 12 May 2012 14:48:50 -0700 (PDT) Received: by wibhn6 with SMTP id hn6so1189888wib.10 for ; Sat, 12 May 2012 14:48:48 -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=H1OWB88LsQvusqDGZ1MLddSGZgy/0C+0YrzNIfzSff4=; b=oI7Q9IFc9k6TZGTorGId1IckraF6Ulr2rnVALk56q9aM2dzB7Zs65M2qje1rarBaKW Er7lzVZoxRJED0YudKzVK5YncovRvp4FLPO426D/97WXZtuJ6Eu8fsMdLuVao0bqv0NH Et8/4Ssm4K9W6JFgnZLnenSlgYBauVhvvmUaSPKNao9m3denDHAkJpoHRzpiRCyoAdIc zIw3JB676yHyzTZbvxG9mbfgma0jtH/BXEphOIVaxIUas92l2Us5iv58EmBV+jIO8vy+ YzmovM7UeSbWiZJUrY3xaXiAhZWxlX+DZRbkxrLTVSWZ9tKCmdUKmatm40RTePIEgsBt VsMg== Received: by 10.180.78.233 with SMTP id e9mr6975095wix.5.1336859328366; Sat, 12 May 2012 14:48:48 -0700 (PDT) Received: from [172.28.131.74] ([74.125.122.49]) by mx.google.com with ESMTPS id r2sm34729380wif.7.2012.05.12.14.48.45 (version=SSLv3 cipher=OTHER); Sat, 12 May 2012 14:48:46 -0700 (PDT) From: Eric Dumazet To: David Miller In-Reply-To: <20120512.164513.1156706853054390966.davem@davemloft.net> References: <1336829533.31653.1108.camel@edumazet-glaptop> <20120512.155259.1178343836887150194.davem@davemloft.net> <1336855256.31653.1329.camel@edumazet-glaptop> <20120512.164513.1156706853054390966.davem@davemloft.net> Content-Type: text/plain; charset="UTF-8" Date: Sat, 12 May 2012 23:48:44 +0200 Message-ID: <1336859324.31653.1385.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: Sat, 12 May 2012 21:48:51 -0000 On Sat, 2012-05-12 at 16:45 -0400, David Miller wrote: > From: Eric Dumazet > Date: Sat, 12 May 2012 22:40:56 +0200 > > > 24 bit of precision for the reciprocal value is more than enough (Van > > suggested 16 bits in fact), so we have actually room for 7 bits if > > needed. > > Using a u16 would also work for me. I tried it but it gives noticeable errors for count > 16000, and no speed gain. count=16525 scale=0 sqrt(scaled_count)=2056 reciprocal(sq)=1fe0200 Newton=235 interval/sqrt(16525) = 777909 (float compute) 778210 (integer approx) 777926 (int_sqrt_div) 862121 (Newton approx) And if a flow is really agressive, count can grow above 10^6 > > > By the way, gcc on x86 generates nice "and 0xfffffffe,%eax" instruction > > for (vars->rec_inv_sqrt << 1). > > Yeah but what do stores of ->rec_inv_sqrt look like? The load is "shr %edi" as in : and the store an "or %ecx,%esi" 5f2: 8b 72 08 mov 0x8(%rdx),%esi 5f5: 44 8b 02 mov (%rdx),%r8d 5f8: 89 f7 mov %esi,%edi 5fa: 41 83 c0 01 add $0x1,%r8d vars->count + 1 5fe: 83 e6 01 and $0x1,%esi vars->dropping in esi 601: d1 ef shr %edi 603: 44 89 02 mov %r8d,(%rdx) vars->count++; 606: 45 89 c0 mov %r8d,%r8d 609: 89 ff mov %edi,%edi 60b: 48 89 f9 mov %rdi,%rcx 60e: 48 0f af cf imul %rdi,%rcx 612: 48 c1 e9 1f shr $0x1f,%rcx 616: 49 0f af c8 imul %r8,%rcx 61a: 49 b8 00 00 00 80 01 mov $0x180000000,%r8 621: 00 00 00 624: 49 29 c8 sub %rcx,%r8 627: 4c 89 c1 mov %r8,%rcx 62a: 48 0f af cf imul %rdi,%rcx 62e: 48 c1 e9 20 shr $0x20,%rcx 632: 01 c9 add %ecx,%ecx 634: 09 ce or %ecx,%esi combine the two fields 636: 89 72 08 mov %esi,0x8(%rdx) final store Using 24bits generates roughly same code. (constants are different)