[Codel] fp sqrt vis int sqrt?

[Dave Taht]

On Fri, May 4, 2012 at 11:50 AM, Eric Dumazet <eric.dumazet at gmail.com> wrote:
> On Fri, 2012-05-04 at 11:39 -0700, Dave Taht wrote:
>> Heh. I'd only gotten as far as
>>
>> #include <stdio.h>
>> #include <math.h>
>> main() {
>>
>>
>>
>>
>>
>> before your mail arrived.
>
> Yep, so maybe we can use a precomputed table of 25 values (100 bytes),
> using the reciprocal trick to get precise integer approximation.
>
> (interval/sqrt(count)).
>
> So that control_law() has no multiply or divide to do, just a lookup in
> the array.
>
> Then for count values >= 25, either we can afford an error less than 20%
> using the q->sqrt_count maintained in // with q->count, either we
> compute the reciprocal each time we change q->count.

We end up with cumulative error and we are trying to match in inverse
tcp's behavior on the flip side, over a variety of RTTs and bandwidths
ranging from nearly 0 to 10GigE....

table[sch->len] in size doesn't bother me much. Except that I'd hoped
to get away with ~ infinite queue length and not bother with that.

More noise presumably helps with randomization down to some point to
where we fall below kernel time granularity.

> (cost : one divide + int_sqrt() call )
> plus one multiply in control_law()
>
> Not sure we need to be ultra precise.

I'd like to toss these concepts back over the wall to kathie to simulate.

I think seeing the oscillation in queue length with just int_sqrt vs
fp sqrt would be fun too, but I'm weird that way.

Late this evening I'll have time to incorporate the progress so far
today (thx for the cleanups and help!!!) and I'll try to get another
patch out late tonight. Unless you beat me to it.

About the only thing left bugging me is the netlink interface.


-- 
Dave Täht
SKYPE: davetaht
US Tel: 1-239-829-5608
http://www.bufferbloat.net