: Binary search for reverse TFRC lookup
PATCH 3/3 : Binary search for reverse TFRC lookup
[DCCP]: 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 <[email protected]>
--- net/dccp/ccids/lib/tfrc_equation.c | 36 ++++++++++++++++++++++-------------- 1 file changed, 22 insertions(+), 14 deletions(-)
net/dccp/ccids/lib/tfrc_equation.c +22 -14
@@ -626,6 +626,21 @@ u32 tfrc_calc_x(u16 s, u32 R, u32 p)EXPORT_SYMBOL_GPL (tfrc_calc_x); +/* return largest index i such that fval <= lookup[i][small] */ +static inline u32 tfrc_binsearch (u32 fval,int 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_reverse_lookup - try to find p given f(p) * @fvalue: function value to match, scaled by 1000000
@@ -634,8 +649,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 <=> p = 0 */ return 0 ;
@@ -650,19 +664,13 @@ u32 tfrc_calc_x_reverse_lookup(u32 fvalureturn 1000000 ; } -if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE -1 ][1 ]) - small =1 ; -else - small =0 ; - +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 ; + } -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 ; + index =tfrc_binsearch (fvalue,0 ); +return (index +1 ) *1000000 /TFRC_CALC_X_ARRSIZE ; }EXPORT_SYMBOL_GPL (tfrc_calc_x_reverse_lookup);