diff options
author | Gerrit Renker <gerrit@erg.abdn.ac.uk> | 2006-12-03 11:53:27 -0500 |
---|---|---|
committer | Arnaldo Carvalho de Melo <acme@mandriva.com> | 2006-12-03 11:53:27 -0500 |
commit | 2bbf29acd8f7adcf161de7e5d891b4095687a59f (patch) | |
tree | 955b15fa3bcdee1f879949d8639c5e9d5b82e84e /net/dccp | |
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>
Diffstat (limited to 'net/dccp')
-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] = { | |||
594 | { 243315981, 271305 } | 594 | { 243315981, 271305 } |
595 | }; | 595 | }; |
596 | 596 | ||
597 | /* return largest index i such that fval <= lookup[i][small] */ | ||
598 | static inline u32 tfrc_binsearch(u32 fval, u8 small) | ||
599 | { | ||
600 | u32 try, low = 0, high = TFRC_CALC_X_ARRSIZE - 1; | ||
601 | |||
602 | while (low < high) { | ||
603 | try = (low + high) / 2; | ||
604 | if (fval <= tfrc_calc_x_lookup[try][small]) | ||
605 | high = try; | ||
606 | else | ||
607 | low = try + 1; | ||
608 | } | ||
609 | return high; | ||
610 | } | ||
611 | |||
597 | /** | 612 | /** |
598 | * tfrc_calc_x - Calculate the send rate as per section 3.1 of RFC3448 | 613 | * tfrc_calc_x - Calculate the send rate as per section 3.1 of RFC3448 |
599 | * | 614 | * |
@@ -656,8 +671,7 @@ EXPORT_SYMBOL_GPL(tfrc_calc_x); | |||
656 | */ | 671 | */ |
657 | u32 tfrc_calc_x_reverse_lookup(u32 fvalue) | 672 | u32 tfrc_calc_x_reverse_lookup(u32 fvalue) |
658 | { | 673 | { |
659 | int ctr = 0; | 674 | int index; |
660 | int small; | ||
661 | 675 | ||
662 | if (fvalue == 0) /* f(p) = 0 whenever p = 0 */ | 676 | if (fvalue == 0) /* f(p) = 0 whenever p = 0 */ |
663 | return 0; | 677 | return 0; |
@@ -672,18 +686,14 @@ u32 tfrc_calc_x_reverse_lookup(u32 fvalue) | |||
672 | return 1000000; | 686 | return 1000000; |
673 | } | 687 | } |
674 | 688 | ||
675 | if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1]) | 689 | if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1]) { |
676 | small = 1; | 690 | index = tfrc_binsearch(fvalue, 1); |
677 | else | 691 | return (index + 1) * TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE; |
678 | small = 0; | 692 | } |
679 | 693 | ||
680 | while (fvalue > tfrc_calc_x_lookup[ctr][small]) | 694 | /* else ... it must be in the coarse-grained column */ |
681 | ctr++; | 695 | index = tfrc_binsearch(fvalue, 0); |
682 | 696 | return (index + 1) * 1000000 / TFRC_CALC_X_ARRSIZE; | |
683 | if (small) | ||
684 | return (ctr + 1) * TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE; | ||
685 | else | ||
686 | return (ctr + 1) * 1000000 / TFRC_CALC_X_ARRSIZE; | ||
687 | } | 697 | } |
688 | 698 | ||
689 | EXPORT_SYMBOL_GPL(tfrc_calc_x_reverse_lookup); | 699 | EXPORT_SYMBOL_GPL(tfrc_calc_x_reverse_lookup); |