Re: [aqm] avoiding the sqrt

[Dave Taht <[e-mail]>]

On Tue, Aug 18, 2015 at 4:26 PM, Andrew Mcgregor <[e-mail]> 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 <[e-mail]> 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 [[e-mail]]
>> Sent: Monday, August 10, 2015 2:38 PM
>> To: Jeff Weeks; [e-mail]
>> 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:[e-mail]] On Behalf Of Jeff Weeks
>> Sent: Monday, August 10, 2015 12:18 PM
>> To: [e-mail]
>> 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
>> [e-mail]
>>
>> 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
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/aqm
>
>
>
>
> --
> Andrew McGregor | SRE | [e-mail] | [phone]
>
> _______________________________________________
> aqm mailing list
> [e-mail]
> 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