Subject: [aqm] avoiding the sqrt

From: Jeff Weeks <[email-masked]>
Date: Mon, 10 Aug 2015 16:18:26 +0000

The CoDel control_law is defined as 't + interval/sqrt(count)'

The sample implementation (http://queue.acm.org/appendices/codel.html) 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

---

From: Mikael Abrahamsson <[email-masked]>
Date: Mon, 10 Aug 2015 19:17:06 +0200 (CEST)

> Is there any reason to not use this approach (assuming sufficient memory exists, of course)?

I think this should be left up to individual implementation. I have some 
experience from assembler programming on the C64 and Amiga in the 80ties, 
and back then it was common to have these kinds of lookup tables because 
memory accesses were "cheap" and calculations were "expensive". I don't 
know if this is still the case in modern hardware, it might even be that 
it's cheaper to do sqrt on an internal register compared to doing memory 
access to relatively slow DRAM (if the lookup table isn't kept in cache) 
to fetch some data from a precalculated lookup table.

-- 
Mikael Abrahamsson    email: [email-masked]

---

From: Jonathan Morton <[email-masked]>
Date: Mon, 10 Aug 2015 20:18:09 +0300

The version of codel that cake uses does indeed use such a lookup table for
1..15.  This was for accuracy rather than performance reasons.

- Jonathan Morton

---

From: "Agarwal, Anil" <[email-masked]>
Date: Mon, 10 Aug 2015 18:38:17 +0000

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:[email-masked]] On Behalf Of Jeff Weeks
Sent: Monday, August 10, 2015 12:18 PM
To: [email-masked]
Subject: [aqm] avoiding the sqrt

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.

--Jeff

_______________________________________________
aqm mailing list
[email-masked]
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=

---

From: Jeff Weeks <[email-masked]>
Date: Tue, 11 Aug 2015 13:05:55 +0000

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 [[email-masked]]
Sent: Monday, August 10, 2015 2:38 PM
To: Jeff Weeks; [email-masked]
Subject: RE: avoiding the sqrt

Jeff,

Did you mean -

Anil

-----Original Message-----
From: aqm [mailto:[email-masked]] On Behalf Of Jeff Weeks
Sent: Monday, August 10, 2015 12:18 PM
To: [email-masked]
Subject: [aqm] avoiding the sqrt

--Jeff

---

From: Andrew Mcgregor <[email-masked]>
Date: Wed, 19 Aug 2015 09:26:36 +1000

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).

On 11 August 2015 at 23:05, Jeff Weeks <[email-masked]> 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
> 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.
>
> https://www.ietf.org/mailman/listinfo/aqm
>

-- 
Andrew McGregor | SRE | [email-masked] | +61 4 1071 2221

---

From: Dave Taht <[email-masked]>
Date: Tue, 18 Aug 2015 17:24:41 -0700

On Tue, Aug 18, 2015 at 4:26 PM, Andrew Mcgregor <[email-masked]> wrote:
> 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

>> 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=

-- 
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