[Xen-devel] [OSSTEST PATCH 08/10] cs-bisection-step: Fix memoisation of search_compute_length_at

[Ian Jackson <ian.jackson@xxxxxxxxxxxxx>]

There was a half-implemented memoisation.  Memoisation is necessary
because otherwise the algorithm is exponential in the commit history
depth (with base equal to the commit parent fanout).

Sort this out:
 * Break out the actual computation into a ne
   search_compute_length_at_intern
 * Deleting the individual memo assignments, which incidentally
   means we no longer miss an (unimportant) one.
 * Actually having the new memoising function search_compute_length_at
   check $n->{LengthAt} (this is the bugfix).

Signed-off-by: Ian Jackson <Ian.Jackson@xxxxxxxxxxxxx>
---
 cs-bisection-step |   12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

diff --git a/cs-bisection-step b/cs-bisection-step
index 90111ff..57ecac4 100755
--- a/cs-bisection-step
+++ b/cs-bisection-step
@@ -639,8 +639,10 @@ sub consolidateresults () {
 our @interesting_lengths;
 
 sub search_compute_length_at ($);
-sub search_compute_length_at ($) {
+
+sub search_compute_length_at_intern ($) {
     my ($n) = @_;
+
     print DEBUG "CLA $n->{Rtuple} ";
     if (!relevant($n)) {
         print DEBUG "X (irrelevant)\n";
@@ -652,7 +654,6 @@ sub search_compute_length_at ($) {
         if ($n->{Result} ne 'pass') {
             search_compute_length_below($n);
         }
-        $n->{LengthAt}= 0;
         return 0;
     }
     my $res= 1;
@@ -662,10 +663,15 @@ sub search_compute_length_at ($) {
         next if $t eq 'X';
         $res += $t;
     }
-    $n->{LengthAt}= $res;
     return $res;
 }
 
+sub search_compute_length_at ($) {
+    my ($n) = @_;
+    return $n->{LengthAt} if exists $n->{LengthAt};
+    return $n->{LengthAt} = search_compute_length_at_intern($n);
+}
+
 sub search_compute_length_below ($) {
     my ($base) = @_;
     return if $base->{UninterestingFailure};
-- 
1.7.10.4


_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel