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 BD1A7200B29 for ; Fri, 4 May 2012 10:23:05 -0700 (PDT) Received: by wgbfa7 with SMTP id fa7so2387037wgb.28 for ; Fri, 04 May 2012 10:23:03 -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=tiPGL34H4x8bvuOkPlT78caaKmJ1X2t1D9YQb0aC/vQ=; b=Wa+b51g2urO2asUX38y4YzBztGP2Dltov0T2STVbr6rd4K7+Bo/zlRhbyDIpgbLGdv YPNHggpOcEh61+G8nWWO3O/RspsFK+VGqixm5RiLHI3kHSPqzYAF0w+o/rdA7UokGYhE jsIuv4pebs83hiNu66EweUp/ZEzcAD/Cbu0yrFQMICvispz7V3GaliNAoxRsbcyY7INt srM89gQJ1FrtJ9rpxIK8QoQEwjAN4HzT+lWFaOK3sbVXid65TwH+nl+C2gl3F1+YgpgG g330vWdVdSoZjuJATymOZTwkw4QJGX1beT8voKg1BNwpJ6rhF6HrxYOWw+FrL81LFtQb gfKQ== MIME-Version: 1.0 Received: by 10.216.142.226 with SMTP id i76mr4579019wej.28.1336152181548; Fri, 04 May 2012 10:23:01 -0700 (PDT) Received: by 10.223.112.66 with HTTP; Fri, 4 May 2012 10:23:01 -0700 (PDT) In-Reply-To: <1336146993.3752.354.camel@edumazet-glaptop> References: <4FA3F248.3070101@freedesktop.org> <4FA3F50D.7080406@freedesktop.org> <1336146993.3752.354.camel@edumazet-glaptop> Date: Fri, 4 May 2012 10:23:01 -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:23:06 -0000 On Fri, May 4, 2012 at 8:56 AM, Eric Dumazet wrote= : > 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+ 7071067+ 5773502+5000000 27844569 10000000+10000000+10000000+5000000 35000000 so with fp you end up with a much tighter and more responsive control loop. 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 > > --=20 Dave T=E4ht SKYPE: davetaht US Tel: 1-239-829-5608 http://www.bufferbloat.net