Re: [aqm] avoiding the sqrt
Dave Taht <dave.taht@gmail.com> Wed, 19 August 2015 00:24 UTC
Return-Path: <dave.taht@gmail.com>
X-Original-To: aqm@ietfa.amsl.com
Delivered-To: aqm@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A869B1A1A6C for <aqm@ietfa.amsl.com>; Tue, 18 Aug 2015 17:24:43 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.434
X-Spam-Level: *
X-Spam-Status: No, score=1.434 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, FRT_FUCK2=3.434, SPF_PASS=-0.001] autolearn=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id T0l59lihOlk3 for <aqm@ietfa.amsl.com>; Tue, 18 Aug 2015 17:24:42 -0700 (PDT)
Received: from mail-ob0-x235.google.com (mail-ob0-x235.google.com [IPv6:2607:f8b0:4003:c01::235]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id AFDC41A1A14 for <aqm@ietf.org>; Tue, 18 Aug 2015 17:24:41 -0700 (PDT)
Received: by obbhe7 with SMTP id he7so155608312obb.0 for <aqm@ietf.org>; Tue, 18 Aug 2015 17:24:41 -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=RJ2SEBw0M5vLqWjTP//tJssRfxOT4QTN1oEzHXIMkok=; b=z4qAsHOYTNxHetNfvT5izZwDW1yQC7gspLsj65NAB9rFPYcynTb5fDDBuWTTjmat/z eRDNXdINeVVnm2/Lm3JnClXLvLsKDBSEF0AkUiSGVSqyWmX8QliKrJRGeWRSEdXlhZaM fgbCXG4vmZG+E30WI7pisnKs2Qd2DP5D+cz1yBEGgkgWQFeow4wZk7wStrKvrloOB59q bB6vWLKPppTyOG4TGKj+R6JeMn9E7cNa7anv8MFiumcinxDe7ZPtoKDIE8rPIRBIEkhq +hkB+NkVE/7MMqwx5caWTpIk3S+h+zg3Qesr2Ucn4nr0YRizaoHPyrEdPS+NHZj6sZev dESQ==
MIME-Version: 1.0
X-Received: by 10.182.79.232 with SMTP id m8mr8138877obx.25.1439943881138; Tue, 18 Aug 2015 17:24:41 -0700 (PDT)
Received: by 10.202.108.12 with HTTP; Tue, 18 Aug 2015 17:24:41 -0700 (PDT)
In-Reply-To: <CAPRuP3nT6vnmSK9oCyGbVDAPfjuQKKnt_cHKKydHKsAL0DgYow@mail.gmail.com>
References: <274D3A0FA900FD47AA6B56991AAA32FDC53BAA3F@wtl-exchp-1.sandvine.com> <7A2801D5E40DD64A85E38DF22117852C70AF58FE@wdc1exchmbxp05.hq.corp.viasat.com> <274D3A0FA900FD47AA6B56991AAA32FDC53BB02B@wtl-exchp-1.sandvine.com> <CAPRuP3nT6vnmSK9oCyGbVDAPfjuQKKnt_cHKKydHKsAL0DgYow@mail.gmail.com>
Date: Tue, 18 Aug 2015 17:24:41 -0700
Message-ID: <CAA93jw62gty42PX=TuMvf_2iFMrNB7aXK-uFXgpYLAwzRk8HzQ@mail.gmail.com>
From: Dave Taht <dave.taht@gmail.com>
To: Andrew Mcgregor <andrewmcgr@google.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <http://mailarchive.ietf.org/arch/msg/aqm/M8mybpA6qfN7Xts1pr3I7uLw5BQ>
Cc: "Agarwal, Anil" <Anil.Agarwal@viasat.com>, Jeff Weeks <jweeks@sandvine.com>, "aqm@ietf.org" <aqm@ietf.org>
Subject: Re: [aqm] avoiding the sqrt
X-BeenThere: aqm@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "Discussion list for active queue management and flow isolation." <aqm.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/aqm>, <mailto:aqm-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/aqm/>
List-Post: <mailto:aqm@ietf.org>
List-Help: <mailto:aqm-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/aqm>, <mailto:aqm-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 19 Aug 2015 00:24:43 -0000
On Tue, Aug 18, 2015 at 4:26 PM, Andrew Mcgregor <andrewmcgr@google.com> wrote: > Memory access on modern CPUs is astonishingly expensive as well, so the > pendulum is well over on the 'just calculate it' side; only in very low-end > embedded devices would there be any benefit to a lookup table (for > perspective, a Raspberry Pi probably loses from the lookup table, and that's > a $35 device; the common MIPS chips found in home routers are very likely > about even on the two approaches, although I admit I have not benchmarked > them). The reasons to do tables these days are 1) if the calculation would > touch a lot more memory (for example, Minstrel rate table construction) or > 2) if it is very hard to do accurately in integer arithmetic (Jonathan's > case here). Accuracy here means two things, btw. One is the right number obtained... the other is that the newton sqrt estimation method does not run well in reverse. I can certainly see compiling the cache out (and doing more serious profiling of cake in the near future, in general) - but at the moment we are just making sure the code is as correct, and as big an advance on the current state of the art (3 tiers of htb + fq_codel in the sqm-scripts) as possible. There will probably be many optimization opportunities - some of which, like hashing and locking improvements in upcoming linux-en are pretty important also. Jonathon has got a technical overview of cake in a pretty good state now, that document is at: http://www.bufferbloat.net/projects/codel/wiki/CakeTechnical > On 11 August 2015 at 23:05, Jeff Weeks <jweeks@sandvine.com> wrote: >> >> Indeed, the microsec granularity means the lookup table would be quite >> large, or would need to use a reduced index into a smaller table. >> After looking at modern cycle counts for integer multiply, I'm realizing >> that they're not nearly as expensive as I remember them to be, so the Linux >> implementation's approach is likely more efficient. >> >> --Jeff >> ________________________________________ >> From: Agarwal, Anil [Anil.Agarwal@viasat.com] >> Sent: Monday, August 10, 2015 2:38 PM >> To: Jeff Weeks; aqm@ietf.org >> Subject: RE: avoiding the sqrt >> >> Jeff, >> >> Did you mean - >> pre-calculate a set of interval/sqrt(count) for some range of count -- >> probably (1..interval^2), >> and for any count > interval^2, the next interval can just be set to >> t+1 >> >> Also, interval is generally kept in microseconds, hence a nominal value >> for interval is 100000. >> >> The current Codel Linux implementation of 1/sqrt(count) uses 4 >> multiplications. >> >> Anil >> >> -----Original Message----- >> From: aqm [mailto:aqm-bounces@ietf.org] On Behalf Of Jeff Weeks >> Sent: Monday, August 10, 2015 12:18 PM >> To: aqm@ietf.org >> Subject: [aqm] avoiding the sqrt >> >> The CoDel control_law is defined as 't + interval/sqrt(count)' >> >> The sample implementation >> (https://urldefense.proofpoint.com/v2/url?u=http-3A__queue.acm.org_appendices_codel.html&d=BQICAg&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=Mwm2-08h6DG8dG8A8i_FAQ9gIL67_jeiZA_pVQpEnIU&s=dMb61gcX82gBDxDv3nIAN4_lJma52tJT57lEdcXrVko&e= >> ) suggests that sqrt(count) can be calculated using only integer >> multiplication, but I'm wondering if it even needs to be calculated. >> >> Would it not be more efficient to pre-calculate a set of 1/sqrt(count) for >> some range -- probably (1..interval), and for any count > interval, the >> next interval can just be set to t+1. >> >> Is there any reason to not use this approach (assuming sufficient memory >> exists, of course)? >> >> --Jeff >> >> ________________________________ >> /dev/jeff_weeks.x2936 >> Sandvine Incorporated >> >> _______________________________________________ >> aqm mailing list >> aqm@ietf.org >> >> https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_aqm&d=BQICAg&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=Mwm2-08h6DG8dG8A8i_FAQ9gIL67_jeiZA_pVQpEnIU&s=guSznYIkwKsTZpoAOLCaLdhlKa4GUMNrO7mu4sv3nMM&e= >> >> _______________________________________________ >> aqm mailing list >> aqm@ietf.org >> https://www.ietf.org/mailman/listinfo/aqm > > > > > -- > Andrew McGregor | SRE | andrewmcgr@google.com | +61 4 1071 2221 > > _______________________________________________ > aqm mailing list > aqm@ietf.org > https://www.ietf.org/mailman/listinfo/aqm > -- Dave Täht worldwide bufferbloat report: http://www.dslreports.com/speedtest/results/bufferbloat And: What will it take to vastly improve wifi for everyone? https://plus.google.com/u/0/explore/makewififast
- [aqm] avoiding the sqrt Jeff Weeks
- Re: [aqm] avoiding the sqrt Mikael Abrahamsson
- Re: [aqm] avoiding the sqrt Jonathan Morton
- Re: [aqm] avoiding the sqrt Agarwal, Anil
- Re: [aqm] avoiding the sqrt Jeff Weeks
- Re: [aqm] avoiding the sqrt Andrew Mcgregor
- Re: [aqm] avoiding the sqrt Dave Taht