changeset 5772:4c46636eafe5

bisect: skip calculations on candidates with too many ancestors Once an ancestor list has grown past the perfect threshold, all descendants are less optimal. Use a poison dict to avoid pointless operations on their long ancestor lists, thus eliminating most of the work.
author Matt Mackall <mpm@selenic.com>
date Mon, 31 Dec 2007 18:20:34 -0600
parents 9d3f49f52a4a
children 2f6105ab4c54
files hgext/hbisect.py
diffstat 1 files changed, 20 insertions(+), 10 deletions(-) [+]
line wrap: on
line diff
--- a/hgext/hbisect.py	Mon Dec 31 18:20:34 2007 -0600
+++ b/hgext/hbisect.py	Mon Dec 31 18:20:34 2007 -0600
@@ -58,7 +58,12 @@
     # find the best node to test
     best_rev = None
     best_len = -1
+    poison = {}
     for rev in candidates:
+        if rev in poison:
+            for c in children.get(rev, []):
+                poison[c] = True # poison children
+            continue
         l = ancestors[rev]
         ancestors[rev] = None
         if l != None:
@@ -72,21 +77,26 @@
                     a.update(dict.fromkeys(s))
                 a[rev] = None
                 a = a.keys()
+
+            x = len(a) # number of ancestors
+            y = tot - x # number of non-ancestors
+            value = min(x, y) # how good is this test?
+            if value > best_len and rev not in skip:
+                best_len = value
+                best_rev = rev
+                if value == perfect: # found a perfect candidate? quit early
+                    break
+
+            if y < perfect: # all downhill from here?
+                for c in children.get(rev, []):
+                    poison[c] = True # poison children
+                continue
+
             for c in children.get(rev, []):
                 if ancestors[c]:
                     ancestors[c].append(a)
                 else:
                     ancestors[c] = [a]
-            if n in skip:
-                continue
-            a = len(a) # number of ancestors
-            b = tot - a # number of non-ancestors
-            value = min(a, b) # how good is this test?
-            if value > best_len:
-                best_len = value
-                best_rev = rev
-                if value == perfect: # found a perfect candidate? quit early
-                    break
 
     assert best_rev is not None
     best_node = changelog.node(best_rev)