From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wg0-f47.google.com (mail-wg0-f47.google.com [74.125.82.47]) (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 38F7D200681 for ; Fri, 4 May 2012 12:04:59 -0700 (PDT) Received: by wgbfa7 with SMTP id fa7so2458495wgb.28 for ; Fri, 04 May 2012 12:04:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=25nhoP0s3qJZTOiat5aFo5bZWdggQ+JEAI+Ri3p7o/Q=; b=iRpSzwh6ppLN3xVVgAgfm3G7o/AOANeag9/+20r1SX5wCrHNJ9m4iEYeJAyQ59BSyr H5bFe0ps7KiBPAG+sU+Vrgk2IwJ3me5ngUYpYB5A92k1Im8ihBorWc/g/EvVn9p/eo30 qHV3/Tbkb4VKkAynON2zPQFRZGhQXp0SQVFjm3dgj4/sbUJC3QMXuodhUCdjEQM/QCkc e/J15sfm5AES+6NMn7AKayiRt3hJ7zbv4zxpyjdBHO4khcadJu+WHt8c1cr7hHuXNXdQ w5Zd0XSPSA2CpPBsRb25HG5PjPVFebWP4I3hkDfcNYsv2tPF68mnkpOJhILC06qrT85o 6ukQ== MIME-Version: 1.0 Received: by 10.180.105.69 with SMTP id gk5mr17728266wib.3.1336158294091; Fri, 04 May 2012 12:04:54 -0700 (PDT) Received: by 10.223.112.66 with HTTP; Fri, 4 May 2012 12:04:54 -0700 (PDT) In-Reply-To: <1336157416.3752.378.camel@edumazet-glaptop> References: <4FA3F248.3070101@freedesktop.org> <4FA3F50D.7080406@freedesktop.org> <1336146993.3752.354.camel@edumazet-glaptop> <1336153652.3752.361.camel@edumazet-glaptop> <1336155996.3752.368.camel@edumazet-glaptop> <1336157416.3752.378.camel@edumazet-glaptop> Date: Fri, 4 May 2012 12:04:54 -0700 Message-ID: From: Dave Taht To: Eric Dumazet Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Cc: codel@lists.bufferbloat.net Subject: Re: [Codel] fp sqrt vis int sqrt? 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: Fri, 04 May 2012 19:04:59 -0000 On Fri, May 4, 2012 at 11:50 AM, Eric Dumazet wrot= e: > On Fri, 2012-05-04 at 11:39 -0700, Dave Taht wrote: >> Heh. I'd only gotten as far as >> >> #include >> #include >> main() { >> >> >> >> >> >> before your mail arrived. > > Yep, so maybe we can use a precomputed table of 25 values (100 bytes), > using the reciprocal trick to get precise integer approximation. > > (interval/sqrt(count)). > > So that control_law() has no multiply or divide to do, just a lookup in > the array. > > Then for count values >=3D 25, either we can afford an error less than 20= % > using the q->sqrt_count maintained in // with q->count, either we > compute the reciprocal each time we change q->count. We end up with cumulative error and we are trying to match in inverse tcp's behavior on the flip side, over a variety of RTTs and bandwidths ranging from nearly 0 to 10GigE.... table[sch->len] in size doesn't bother me much. Except that I'd hoped to get away with ~ infinite queue length and not bother with that. More noise presumably helps with randomization down to some point to where we fall below kernel time granularity. > (cost : one divide + int_sqrt() call ) > plus one multiply in control_law() > > Not sure we need to be ultra precise. I'd like to toss these concepts back over the wall to kathie to simulate. I think seeing the oscillation in queue length with just int_sqrt vs fp sqrt would be fun too, but I'm weird that way. Late this evening I'll have time to incorporate the progress so far today (thx for the cleanups and help!!!) and I'll try to get another patch out late tonight. Unless you beat me to it. About the only thing left bugging me is the netlink interface. --=20 Dave T=E4ht SKYPE: davetaht US Tel: 1-239-829-5608 http://www.bufferbloat.net