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)