Re: [aqm] avoiding the sqrt

[Mikael Abrahamsson <[e-mail]>]

On Mon, 10 Aug 2015, Jeff Weeks wrote:

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

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: [e-mail]