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 B6D5F200B29 for ; Fri, 4 May 2012 10:44:29 -0700 (PDT) Received: by wgbfa7 with SMTP id fa7so2401945wgb.28 for ; Fri, 04 May 2012 10:44:27 -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=0BjKb3Cun8KW63+mdANlk5PYeQFSDnibQL0yzxwvC50=; b=Y8QJrvfU1davPqpe8+uCrWRrZjEd7G9hnihi7TyIef8KDQc17OkXUjwHijEs8yEpr9 29Bl1qAk0CEu5MORWdJGToqDf/DEd9zSQn6bNWHKe+NlrQwW07jsrvmWyrWMeixEDtoo QY3fGE3LCR2V2Er0ah/KuJPQ6J/s8w3fwr+ttniDFvlBq4O3EECCcypA1+lIp6SOAQHm Hf6X+u2aEZ5ndQ61gtm4DXUW7d8LarnJrCwXzjEfEPmSFakAdkUSKmZ8rJjNzft+yG4Y 8qgsNMTxsHAWCwHCzVidsJii/1XT0oIggwpRoNHkNi2ysSSOS1ko/6pHf2siVumnEL68 iBhw== MIME-Version: 1.0 Received: by 10.180.105.69 with SMTP id gk5mr17124465wib.3.1336153463997; Fri, 04 May 2012 10:44:23 -0700 (PDT) Received: by 10.223.112.66 with HTTP; Fri, 4 May 2012 10:44:23 -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:44:23 -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:44:30 -0000 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 wr= ote: >>> 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 lo= op. > > 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 > > 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 --=20 Dave T=E4ht SKYPE: davetaht US Tel: 1-239-829-5608 http://www.bufferbloat.net