From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-we0-f171.google.com (mail-we0-f171.google.com [74.125.82.171]) (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 173D1200B29 for ; Fri, 4 May 2012 10:46:31 -0700 (PDT) Received: by wejx9 with SMTP id x9so3578357wej.16 for ; Fri, 04 May 2012 10:46:30 -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=rcfySti+4FzwVsvzmss/iEWYSxS7aKxB9X4vTfMkau8=; b=EkN6B3o54Ad3tMi0LuBPQWW6EokCveB3NW3uE3UDdUb7lBh7nR7GOYhLnZyGe+OWDg gRhLq4/74dAtr+s96aYAI45QnhzoVNKFu9vkdS+PYeHYTjiVNf+iGBxJ1HDLeNb3+doO HtLxilC3lsgv98+wIAzJUtWTsdVTo6CEzq99C3BUix6/IjDcV77d6BJQe8gabZdaS3Da g1r1DKYfXHgDRB/pFmxDjqoYZAn+cucG9D+vyiG+FCcO7JxFG4jBZguOAoYpLusxHrEf kv3i625EhyomVjtXCYVBG98XmrFwNi7+VZ4dsO0m5TBWbldzCjG0KPc43LA3+QBx7RGn 8K1w== MIME-Version: 1.0 Received: by 10.216.141.134 with SMTP id g6mr2009589wej.12.1336153589756; Fri, 04 May 2012 10:46:29 -0700 (PDT) Received: by 10.223.112.66 with HTTP; Fri, 4 May 2012 10:46:29 -0700 (PDT) In-Reply-To: References: <4FA3F248.3070101@freedesktop.org> <4FA3F50D.7080406@freedesktop.org> <1336146993.3752.354.camel@edumazet-glaptop> Date: Fri, 4 May 2012 10:46:29 -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 17:46:32 -0000 On Fri, May 4, 2012 at 10:44 AM, Dave Taht wrote: > On Fri, May 4, 2012 at 10:43 AM, Dave Taht wrote: >> On Fri, May 4, 2012 at 10:23 AM, Dave Taht wrote: >>> On Fri, May 4, 2012 at 8:56 AM, Eric Dumazet w= rote: >>>> On Fri, 2012-05-04 at 11:26 -0400, Jim Gettys wrote: >>>> >>>>> >>>>> I suspect there are fully integer implementations kicking around... >>>>> It's just that x86 finally got fast enough FP that doing one multiply= in >>>>> floating point beat the alternative. >>>> >>>> Anyway we dont need to compute sqrt() at all. >>>> >>>> This can be done easily when we do the q->count++, if we hold in >>>> q->sqrt_count the estimated value of sqrt(count) >>>> >>>> Ie replace : >>>> >>>> q->count++; >>>> >>>> by: >>>> >>>> q->count++; >>>> n =3D q->sqrt_count + 1; >>>> if (n * n <=3D q->count) >>>> =A0 =A0 =A0 =A0q->sqrt_count =3D n; >>>> >>>> A multiply is an acceptable cost. >>>> >>>> >>>> Of course, you need to reset sqrt_count to 1 when count is reset to 1 >>> >>> Except that the cumulative drop probability is very different when you >>> apply a series of times of integer vs floating point sqrt calculations >>> into the mix. >>> >>> I can do up a graph, and may (it helps to visualize things), however >>> if you look at the first four in the series, you get the net >>> effect of a 5th and nearly a 6th term by the time you get to the 4th >>> expansion of the series done with a fp sqrt vs integer sqrt. >>> >>> 10000000+ =A07071067+ =A05773502+5000000 >>> 27844569 >>> >>> 10000000+10000000+10000000+5000000 >>> 35000000 >>> >>> so with fp you end up with a much tighter and more responsive control l= oop. >> >> To be mildly more clear, by the time integer sqrt codel would have >> dropped 4 packets, fp codel would have nearly dropped 6. >> >> 27844569+4472135+4472135 >> 36788839 And I goofed on the copy/paste math. (all the more reason for me to code this up and graph it) 27844569+4472135+4082482 36399186 >> >> That's assuming a 100ms target, which by observation over the > ^^^^^^^^^^^^^^^^^^^^interval > > past >> year is not what a typical tcp stream is like anymore, it's closer to >> 50ms, particularly for elephants and cdns, less in many cases. >> >> >>> >>> In looking over the (lack of) compiler support for fp in the kernel, >>> it seems simplest to load up a table from userspace for the >>> interval/sqrt(count) calculation. >>> >>> Not that I netlink and I are friendly at the moment. >>> >>> And I would have liked to been able to to fiddle with target (for >>> wireless) on the fly as a function of (active_stations), with interval >>> slaved to minstrel's idea of everything. >>> >>> /me goes to look at gcc's implementation >>>> >>>> >>> >>> >>> >>> -- >>> Dave T=E4ht >>> SKYPE: davetaht >>> US Tel: 1-239-829-5608 >>> http://www.bufferbloat.net >> >> >> >> -- >> Dave T=E4ht >> SKYPE: davetaht >> US Tel: 1-239-829-5608 >> http://www.bufferbloat.net > > > > -- > Dave T=E4ht > SKYPE: davetaht > US Tel: 1-239-829-5608 > http://www.bufferbloat.net --=20 Dave T=E4ht SKYPE: davetaht US Tel: 1-239-829-5608 http://www.bufferbloat.net