From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wg0-f41.google.com (mail-wg0-f41.google.com [74.125.82.41]) (using TLSv1 with cipher RC4-MD5 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id DDCF8200B29 for ; Fri, 4 May 2012 10:43:48 -0700 (PDT) Received: by wgbds1 with SMTP id ds1so1461200wgb.4 for ; Fri, 04 May 2012 10:43:46 -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=6UIcSVTzSRsvpKFZoY1XjsS7G4/Ne0NuB3DwnClAHWw=; b=kJSiW9fB3Ej51Upm95vGTSbrI0gaZdqHPYxhrQ36wr0E819vdaUMiHnHH7/9DmNJ10 JjXbw3IVCRdRY4S/HcUekTCjJ3JEGrWFSTHrqDbt1JKOfX1ietEwSoUpHhJA36Armj0l /80xkbu6ctaUTvAlSkRrJZwB41xVHaPJS7CWCjDzgmIJxHShnR0/TLb6oM8PF8r4ZdqE iRO8eNgcuNO74zWRr5WtlgNtGWEcF5LQpiWaZHxGa3qNgVlJqwQj5BG7qDXB/IxhA37k QG8d1tSbXb/j5kdPNj5zYRPC1D/K0OHwnedzd1Wz2NUAJAvAIBjLRr6lZyLHjSw1HA1p 5xvw== MIME-Version: 1.0 Received: by 10.180.94.7 with SMTP id cy7mr17116665wib.3.1336153426888; Fri, 04 May 2012 10:43:46 -0700 (PDT) Received: by 10.223.112.66 with HTTP; Fri, 4 May 2012 10:43:46 -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:43:46 -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:43:50 -0000 On Fri, May 4, 2012 at 10:23 AM, Dave Taht wrote: > On Fri, May 4, 2012 at 8:56 AM, Eric Dumazet wro= te: >> 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 i= n >>> 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 loo= p. 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 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 --=20 Dave T=E4ht SKYPE: davetaht US Tel: 1-239-829-5608 http://www.bufferbloat.net