revlog: optimize ancestors() to not check filtered revisions for each
authorYuya Nishihara <yuya@tcha.org>
Fri, 12 Oct 2018 06:22:43 +0200
changeset 52729 adbf8ca239e458d8a18aae5a5dc12f8fa030521c
parent 52699 38ac525b44c93fcadb3680d4ded56f1e5a0029b2
child 52730 0ae20d2141ed20f93f1db75ce88c4a6c043d2cda
push id1049
push usergszorc@mozilla.com
push dateFri, 12 Oct 2018 14:22:20 +0000
bugs38093, 40000, 0, 24795, 20000
revlog: optimize ancestors() to not check filtered revisions for each While reviewing the Rust implementation, I noticed iter(ancestors) doesn't need to check filtering state for each parent revision. And doing that appears to have some measurable perf win. $ hg perfancestors -R mercurial (orig) wall 0.038093 comb 0.040000 user 0.040000 sys 0.000000 (best of 100) (this) wall 0.024795 comb 0.020000 user 0.020000 sys 0.000000 (best of 117)
mercurial/revlog.py
--- a/mercurial/revlog.py
+++ b/mercurial/revlog.py
@@ -643,16 +643,19 @@ class revlog(object):
             entry = self.index[rev]
         except IndexError:
             if rev == wdirrev:
                 raise error.WdirUnsupported
             raise
 
         return entry[5], entry[6]
 
+    # fast parentrevs(rev) where rev isn't filtered
+    _uncheckedparentrevs = parentrevs
+
     def node(self, rev):
         try:
             return self.index[rev][7]
         except IndexError:
             if rev == wdirrev:
                 raise error.WdirUnsupported
             raise
 
@@ -742,18 +745,24 @@ class revlog(object):
         return chain, stopped
 
     def ancestors(self, revs, stoprev=0, inclusive=False):
         """Generate the ancestors of 'revs' in reverse topological order.
         Does not generate revs lower than stoprev.
 
         See the documentation for ancestor.lazyancestors for more details."""
 
-        return ancestor.lazyancestors(self.parentrevs, revs, stoprev=stoprev,
-                                      inclusive=inclusive)
+        # first, make sure start revisions aren't filtered
+        revs = list(revs)
+        checkrev = self.node
+        for r in revs:
+            checkrev(r)
+        # and we're sure ancestors aren't filtered as well
+        return ancestor.lazyancestors(self._uncheckedparentrevs, revs,
+                                      stoprev=stoprev, inclusive=inclusive)
 
     def descendants(self, revs):
         return dagop.descendantrevs(revs, self.revs, self.parentrevs)
 
     def findcommonmissing(self, common=None, heads=None):
         """Return a tuple of the ancestors of common and the ancestors of heads
         that are not ancestors of common. In revset terminology, we return the
         tuple: