summaryrefslogtreecommitdiffstats
path: root/net/sched/sch_fq_codel.c
diff options
context:
space:
mode:
authorEric Dumazet <edumazet@google.com>2012-05-12 03:32:13 +0000
committerDavid S. Miller <davem@davemloft.net>2012-05-12 15:50:49 -0400
commit536edd67109df5e0cdb2c4ee759e9bade7976367 (patch)
treeb253ee5ce32fdc37346120c9ebbfd1f187ad6b95 /net/sched/sch_fq_codel.c
parent470f16c83ce5e481d50cb6da076e836b6219a57c (diff)
downloadlinux-536edd67109df5e0cdb2c4ee759e9bade7976367.tar.bz2
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 <van@pollere.net> Signed-off-by: Eric Dumazet <edumazet@google.com> Cc: Dave Taht <dave.taht@bufferbloat.net> Cc: Kathleen Nichols <nichols@pollere.com> Cc: Tom Herbert <therbert@google.com> Cc: Matt Mathis <mattmathis@google.com> Cc: Yuchung Cheng <ycheng@google.com> Cc: Nandita Dukkipati <nanditad@google.com> Cc: Stephen Hemminger <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net/sched/sch_fq_codel.c')
0 files changed, 0 insertions, 0 deletions