From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from shards.monkeyblade.net (shards.monkeyblade.net [198.137.202.13]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by huchra.bufferbloat.net (Postfix) with ESMTPS id 8E60E2006AA for ; Sat, 12 May 2012 12:55:04 -0700 (PDT) Received: from localhost (cpe-66-108-118-54.nyc.res.rr.com [66.108.118.54]) (authenticated bits=0) by shards.monkeyblade.net (8.14.4/8.14.4) with ESMTP id q4CJqxlJ030926 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=NO); Sat, 12 May 2012 12:53:00 -0700 Date: Sat, 12 May 2012 15:52:59 -0400 (EDT) Message-Id: <20120512.155259.1178343836887150194.davem@davemloft.net> To: eric.dumazet@gmail.com From: David Miller In-Reply-To: <1336829533.31653.1108.camel@edumazet-glaptop> References: <1336829533.31653.1108.camel@edumazet-glaptop> X-Mailer: Mew version 6.5 on Emacs 24.0.95 / Mule 6.0 (HANACHIRUSATO) Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Greylist: Sender succeeded SMTP AUTH, not delayed by milter-greylist-4.2.6 (shards.monkeyblade.net [198.137.202.13]); Sat, 12 May 2012 12:53:01 -0700 (PDT) X-Mailman-Approved-At: Sat, 12 May 2012 13:11:55 -0700 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 19:55:04 -0000 From: Eric Dumazet Date: Sat, 12 May 2012 15:32:13 +0200 > From: Eric Dumazet > > As Van pointed out, interval/sqrt(count) can be implemented using > multiplies only. > > http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots > > This patch implements the Newton method and reciprocal divide. > > Total cost is 15 cycles instead of 120 on my Corei5 machine (64bit > kernel). > > There is a small 'error' for count values < 5, but we don't really care. > > I reuse a hole in struct codel_vars : > - pack the dropping boolean into one bit > - use 31bit to store the reciprocal value of sqrt(count). > > Suggested-by: Van Jacobson > Signed-off-by: Eric Dumazet Applied but I never like that bitfield sharing for real integers. GCC makes a complete mess of it as it extracts and inserts the integer value into that bit field. You are guarenteed to get better code if you do this by hand in a full u32. Either that or just bite the bullet and use a completely seperate field, maybe we'll need more boolean states later.