[Codel] fp sqrt vis int sqrt?

[Dave Taht]

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

And I goofed on the copy/paste math. (all the more reason for me to
code this up and graph it)

27844569+4472135+4082482
36399186


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



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