[Codel] fp sqrt vis int sqrt?

[Dave Taht]

On Fri, May 4, 2012 at 8:14 AM, Jim Gettys <jg at freedesktop.org> wrote:
> On 05/04/2012 11:11 AM, Dave Taht wrote:
>> The linux kernel has no floating point in it, so I'd substituted the
>> internal int_sqrt as a substitute,
>> just to get something to work.
>>
>> static inline ktime_t control_law(const struct codel_sched_data *q, ktime_t t)
>> {
>>         return ktime_add_ns(t, q->interval / int_sqrt(q->count));
>> }
>>
>> Often ns2 models use floating point. Having not seen the model I don't
>> know that for sure.
>>
>> The series for an integer sqrt is far more 'chunky' than a fp one.
>>
>> int sqrt 1,2,3,4 = 1 1 1 2
>> fp sqrt 1 2 3 4 = 1 1.4.1 1.73 2
>>
>> and gets even more chunky as you get larger values, eg, sqrt(36
>> through 48) = 6, sqrt(49) = 7
>>
>> So we could precalculate the interval/sqrt(count) using floating point
>> in the control law calculation,
>> early, during qdisc setup, thus neatly avoiding both the divide and
>> sqrt in the control law path.
>>
>> Or we could do fixed point.
>>
>> Kathie: In the sim, in various simulations, what is the dynamic range
>> of count? And is it floating point sqrt?
>>
> The Wikipedia article on fast inverse sqrt is enlightening on computing
> this really fast.
>
> See:
>
> http://en.wikipedia.org/wiki/Fast_inverse_square_root
>
> This has little to do with whether an integer or floating point value is
> better algorithmically.

Neat trick, that.

I'm delighted the wikipedia article kept the fully commented original
code around!

That said, you can't use FP at all without special handling in the
kernel. It's certainly a terrible idea on a hot path...

>                            - Jim



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