diff options
| author | Gerrit Renker <gerrit@erg.abdn.ac.uk> | 2006-12-03 14:53:27 -0200 |
|---|---|---|
| committer | Arnaldo Carvalho de Melo <acme@mandriva.com> | 2006-12-03 14:53:27 -0200 |
| commit | 2bbf29acd8f7adcf161de7e5d891b4095687a59f (patch) | |
| tree | 955b15fa3bcdee1f879949d8639c5e9d5b82e84e | |
| parent | 44158306d756c88272c8faf243ca68897498e219 (diff) | |
[DCCP] tfrc: Binary search for reverse TFRC lookup
This replaces the linear search algorithm for reverse lookup with
binary search.
It has the advantage of better scalability: O(log2(N)) instead of O(N).
This means that the average number of iterations is reduced from 250
(linear search if each value appears equally likely) down to at most 9.
Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
Acked-by: Ian McDonald <ian.mcdonald@jandi.co.nz>
Signed-off-by: Arnaldo Carvalho de Melo <acme@mandriva.com>
| -rw-r--r-- | net/dccp/ccids/lib/tfrc_equation.c | 38 |
1 files changed, 24 insertions, 14 deletions
diff --git a/net/dccp/ccids/lib/tfrc_equation.c b/net/dccp/ccids/lib/tfrc_equation.c index 0a4a3d2feba5..ddac2c511e2f 100644 --- a/net/dccp/ccids/lib/tfrc_equation.c +++ b/net/dccp/ccids/lib/tfrc_equation.c @@ -594,6 +594,21 @@ static const u32 tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE][2] = { { 243315981, 271305 } }; +/* return largest index i such that fval <= lookup[i][small] */ +static inline u32 tfrc_binsearch(u32 fval, u8 small) +{ + u32 try, low = 0, high = TFRC_CALC_X_ARRSIZE - 1; + + while (low < high) { + try = (low + high) / 2; + if (fval <= tfrc_calc_x_lookup[try][small]) + high = try; + else + low = try + 1; + } + return high; +} + /** * tfrc_calc_x - Calculate the send rate as per section 3.1 of RFC3448 * @@ -656,8 +671,7 @@ EXPORT_SYMBOL_GPL(tfrc_calc_x); */ u32 tfrc_calc_x_reverse_lookup(u32 fvalue) { - int ctr = 0; - int small; + int index; if (fvalue == 0) /* f(p) = 0 whenever p = 0 */ return 0; @@ -672,18 +686,14 @@ u32 tfrc_calc_x_reverse_lookup(u32 fvalue) return 1000000; } - if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1]) - small = 1; - else - small = 0; - - while (fvalue > tfrc_calc_x_lookup[ctr][small]) - ctr++; - - if (small) - return (ctr + 1) * TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE; - else - return (ctr + 1) * 1000000 / TFRC_CALC_X_ARRSIZE; + if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1]) { + index = tfrc_binsearch(fvalue, 1); + return (index + 1) * TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE; + } + + /* else ... it must be in the coarse-grained column */ + index = tfrc_binsearch(fvalue, 0); + return (index + 1) * 1000000 / TFRC_CALC_X_ARRSIZE; } EXPORT_SYMBOL_GPL(tfrc_calc_x_reverse_lookup); |