diff hgext/hbisect.py @ 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.

--- 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)