[Codel] fp sqrt vis int sqrt?

[Dave Taht]

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.

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