From: Dave Taht <dave.taht@gmail.com>
To: Eric Dumazet <eric.dumazet@gmail.com>
Cc: codel@lists.bufferbloat.net
Subject: Re: [Codel] fp sqrt vis int sqrt?
Date: Fri, 4 May 2012 10:44:23 -0700 [thread overview]
Message-ID: <CAA93jw6SLTBV7dd-NE-k-f5PqvU7XocsQC=koDu8M03ocBgrmQ@mail.gmail.com> (raw)
In-Reply-To: <CAA93jw6uf+EnoEPGWA5tS7kY7C8j4E7knL+OmWy8niCceQvvRQ@mail.gmail.com>
On Fri, May 4, 2012 at 10:43 AM, Dave Taht <dave.taht@gmail.com> wrote:
> On Fri, May 4, 2012 at 10:23 AM, Dave Taht <dave.taht@gmail.com> wrote:
>> On Fri, May 4, 2012 at 8:56 AM, Eric Dumazet <eric.dumazet@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
next prev parent reply other threads:[~2012-05-04 17:44 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-05-04 15:11 Dave Taht
2012-05-04 15:14 ` Jim Gettys
2012-05-04 15:19 ` Dave Taht
2012-05-04 15:26 ` Jim Gettys
2012-05-04 15:56 ` Eric Dumazet
2012-05-04 17:23 ` Dave Taht
2012-05-04 17:43 ` Dave Taht
2012-05-04 17:44 ` Dave Taht [this message]
2012-05-04 17:46 ` Dave Taht
2012-05-04 23:42 ` Kathleen Nichols
2012-05-05 0:01 ` Dave Taht
2012-05-04 17:47 ` Eric Dumazet
2012-05-04 18:26 ` Eric Dumazet
2012-05-04 18:39 ` Dave Taht
2012-05-04 18:50 ` Eric Dumazet
2012-05-04 19:04 ` Dave Taht
2012-05-04 19:16 ` Eric Dumazet
2012-05-05 8:14 ` Eric Dumazet
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://lists.bufferbloat.net/postorius/lists/codel.lists.bufferbloat.net/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAA93jw6SLTBV7dd-NE-k-f5PqvU7XocsQC=koDu8M03ocBgrmQ@mail.gmail.com' \
--to=dave.taht@gmail.com \
--cc=codel@lists.bufferbloat.net \
--cc=eric.dumazet@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox