[Codel] fp sqrt vis int sqrt?

[Jim Gettys]

On 05/04/2012 11:19 AM, Dave Taht wrote:
> 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!

I don't think that is the "original", which predates quake by a lot
according to the article.
>
> 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...

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