Re: [aqm] avoiding the sqrt

[Andrew Mcgregor <[e-mail]>]

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