comparison mercurial/revset.py @ 20894:04e1596d5dbd

revset: improve _descendants performance Previously revset._descendants would iterate over the entire subset (which is often the entire repo) and test if each rev was in the descendants list. This is really slow on large repos (3+ seconds). Now we iterate over the descendants and test if they're in the subset. This affects advancing and retracting the phase boundary (3.5 seconds down to 0.8 seconds, which is even faster than it was in 2.9). Also affects commands that move the phase boundary (commit and rebase, presumably). The new revsetbenchmark indicates an improvement from 0.2 to 0.12 seconds. So future revset changes should be able to notice regressions. I removed a bad test. It was recently added and tested '1:: and reverse(all())', which has an amibiguous output direction. Previously it printed in reverse order, because we iterated over the subset (the reverse part). Now it prints in normal order because we iterate over the 1:: . Since the revset itself doesn't imply an order, I removed the test.
author Durham Goode <durham@fb.com>
date Tue, 25 Mar 2014 14:10:01 -0700
parents 876c17336b4e
children f52e4ca93529
comparison
equal deleted inserted replaced
20893:b5de9dde181c 20894:04e1596d5dbd
659 def _descendants(repo, subset, x, followfirst=False): 659 def _descendants(repo, subset, x, followfirst=False):
660 args = getset(repo, spanset(repo), x) 660 args = getset(repo, spanset(repo), x)
661 if not args: 661 if not args:
662 return baseset([]) 662 return baseset([])
663 s = _revdescendants(repo, args, followfirst) 663 s = _revdescendants(repo, args, followfirst)
664 a = set(args) 664
665 return subset.filter(lambda r: r in s or r in a) 665 # Both sets need to be ascending in order to lazily return the union
666 # in the correct order.
667 args.ascending()
668
669 subsetset = subset.set()
670 result = (orderedlazyset(s, subsetset.__contains__, ascending=True) +
671 orderedlazyset(args, subsetset.__contains__, ascending=True))
672
673 # Wrap result in a lazyset since it's an _addset, which doesn't implement
674 # all the necessary functions to be consumed by callers.
675 return orderedlazyset(result, lambda r: True, ascending=True)
666 676
667 def descendants(repo, subset, x): 677 def descendants(repo, subset, x):
668 """``descendants(set)`` 678 """``descendants(set)``
669 Changesets which are descendants of changesets in set. 679 Changesets which are descendants of changesets in set.
670 """ 680 """