[Codel] fp sqrt vis int sqrt?

[Dave Taht]

On Fri, May 4, 2012 at 10:23 AM, Dave Taht <dave.taht at gmail.com> wrote:
> On Fri, May 4, 2012 at 8:56 AM, Eric Dumazet <eric.dumazet at gmail.com> wrote:
>> On Fri, 2012-05-04 at 11:26 -0400, Jim Gettys wrote:
>>
>>>
>>> I suspect there are fully integer implementations kicking around...
>>> It's just that x86 finally got fast enough FP that doing one multiply in
>>> floating point beat the alternative.
>>
>> Anyway we dont need to compute sqrt() at all.
>>
>> This can be done easily when we do the q->count++, if we hold in
>> q->sqrt_count the estimated value of sqrt(count)
>>
>> Ie replace :
>>
>> q->count++;
>>
>> by:
>>
>> q->count++;
>> n = q->sqrt_count + 1;
>> if (n * n <= q->count)
>>        q->sqrt_count = n;
>>
>> A multiply is an acceptable cost.
>>
>>
>> Of course, you need to reset sqrt_count to 1 when count is reset to 1
>
> Except that the cumulative drop probability is very different when you
> apply a series of times of integer vs floating point sqrt calculations
> into the mix.
>
> I can do up a graph, and may (it helps to visualize things), however
> if you look at the first four in the series, you get the net
> effect of a 5th and nearly a 6th term by the time you get to the 4th
> expansion of the series done with a fp sqrt vs integer sqrt.
>
> 10000000+  7071067+  5773502+5000000
> 27844569
>
> 10000000+10000000+10000000+5000000
> 35000000
>
> so with fp you end up with a much tighter and more responsive control loop.

To be mildly more clear, by the time integer sqrt codel would have
dropped 4 packets, fp codel would have nearly dropped 6.

27844569+4472135+4472135
36788839

That's assuming a 100ms target, which by observation over the past
year is not what a typical tcp stream is like anymore, it's closer to
50ms, particularly for elephants and cdns, less in many cases.


>
> In looking over the (lack of) compiler support for fp in the kernel,
> it seems simplest to load up a table from userspace for the
> interval/sqrt(count) calculation.
>
> Not that I netlink and I are friendly at the moment.
>
> And I would have liked to been able to to fiddle with target (for
> wireless) on the fly as a function of (active_stations), with interval
> slaved to minstrel's idea of everything.
>
> /me goes to look at gcc's implementation
>>
>>
>
>
>
> --
> Dave Täht
> SKYPE: davetaht
> US Tel: 1-239-829-5608
> http://www.bufferbloat.net



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