codel: use Newton method instead of sqrt() and divides

As Van pointed out, interval/sqrt(count) can be implemented using
multiplies only.

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Iterative_methods_for_reciprocal_square_roots

This patch implements the Newton method and reciprocal divide.

Total cost is 15 cycles instead of 120 on my Corei5 machine (64bit
kernel).

There is a small 'error' for count values < 5, but we don't really care.

I reuse a hole in struct codel_vars :
 - pack the dropping boolean into one bit
 - use 31bit to store the reciprocal value of sqrt(count).

Suggested-by: Van Jacobson <[email protected]>
Signed-off-by: Eric Dumazet <[email protected]>
Cc: Dave Taht <[email protected]>
Cc: Kathleen Nichols <[email protected]>
Cc: Tom Herbert <[email protected]>
Cc: Matt Mathis <[email protected]>
Cc: Yuchung Cheng <[email protected]>
Cc: Nandita Dukkipati <[email protected]>
Cc: Stephen Hemminger <[email protected]>
Signed-off-by: David S. Miller <[email protected]>

0 files changed, 0 insertions, 0 deletions