ancestor.missingancestors: don't discard from basesvisit
We only actually care about whether revsvisit is empty, so we can let
basesvisit grow to arbitrary size.
It turns out that this actually helps performance. For a large repo with
hundreds of thousands of commits, hg perfrevset 'only(0, tip)' (basically the
worst case, involving a full DAG traversal) goes from 1.63 seconds to 1.50. hg
perfrevset 'only(tip, 0)' remains unchanged at 1.98 seconds.
--- a/mercurial/ancestor.py Sat Nov 15 10:55:34 2014 -0800
+++ b/mercurial/ancestor.py Fri Nov 14 11:33:52 2014 -0800
@@ -155,20 +155,19 @@
start = max(max(revsvisit), max(basesvisit))
bothvisit = revsvisit.intersection(basesvisit)
revsvisit.difference_update(bothvisit)
- basesvisit.difference_update(bothvisit)
# At this point, we hold the invariants that:
# - revsvisit is the set of nodes we know are an ancestor of at least one
# of the nodes in revs
# - basesvisit is the same for bases
# - bothvisit is the set of nodes we know are ancestors of at least one of
- # the nodes in revs and one of the nodes in bases
- # - a node may be in none or one, but not more, of revsvisit, basesvisit
- # and bothvisit at any given time
+ # the nodes in revs and one of the nodes in bases, and that are smaller
+ # than curr. bothvisit and revsvisit are mutually exclusive, but bothvisit
+ # is a subset of basesvisit.
# Now we walk down in reverse topo order, adding parents of nodes already
- # visited to the sets while maintaining the invariants. When a node is
- # found in both revsvisit and basesvisit, it is removed from them and
- # added to bothvisit instead. When revsvisit becomes empty, there are no
- # more ancestors of revs that aren't also ancestors of bases, so exit.
+ # visited to the sets while maintaining the invariants. When a node is found
+ # in both revsvisit and basesvisit, it is removed from revsvisit and added
+ # to bothvisit. When revsvisit becomes empty, there are no more ancestors of
+ # revs that aren't also ancestors of bases, so exit.
missing = []
for curr in xrange(start, nullrev, -1):
@@ -177,18 +176,17 @@
if curr in bothvisit:
bothvisit.remove(curr)
- # curr's parents might have made it into revsvisit or basesvisit
- # through another path
+ # curr's parents might have made it into revsvisit through another
+ # path
for p in pfunc(curr):
revsvisit.discard(p)
- basesvisit.discard(p)
+ basesvisit.add(p)
bothvisit.add(p)
continue
- # curr will never be in both revsvisit and basesvisit, since if it
- # were it'd have been pushed to bothvisit
if curr in revsvisit:
missing.append(curr)
+ revsvisit.remove(curr)
thisvisit = revsvisit
othervisit = basesvisit
elif curr in basesvisit:
@@ -198,7 +196,6 @@
# not an ancestor of revs or bases: ignore
continue
- thisvisit.remove(curr)
for p in pfunc(curr):
if p == nullrev:
pass
@@ -206,7 +203,7 @@
# p is implicitly in thisvisit. This means p is or should be
# in bothvisit
revsvisit.discard(p)
- basesvisit.discard(p)
+ basesvisit.add(p)
bothvisit.add(p)
else:
# visit later