[Codel] fp sqrt vis int sqrt?

[Dave Taht]

On Fri, May 4, 2012 at 10:43 AM, Dave Taht <dave.taht at gmail.com> wrote:
> 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
^^^^^^^^^^^^^^^^^^^^interval

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



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