Patchwork D6506: revlog: speed up isancestor

login
register
mail settings
Submitter phabricator
Date June 10, 2019, 6:33 p.m.
Message ID <differential-rev-PHID-DREV-zykhzfnxylauwfjf7ben-req@phab.mercurial-scm.org>
Download mbox | patch
Permalink /patch/40411/
State Superseded
Headers show

Comments

phabricator - June 10, 2019, 6:33 p.m.
valentin.gatienbaron created this revision.
Herald added a reviewer: indygreg.
Herald added a subscriber: mercurial-devel.
Herald added a reviewer: hg-reviewers.

REVISION SUMMARY
  Currently, it is implemented on top of commonancestorsheads.
  Implement it on top of reachableroots instead, as reachableroots could
  stop walking the graph much sooner than commonancestorsheads.
  
  Measuring repo.changelog.isancestorrev on two revisions in a private repository:
  before: ! wall 0.005175 comb 0.010000 user 0.010000 sys 0.000000 (best of 550)
  after : ! wall 0.000072 comb 0.000000 user 0.000000 sys 0.000000 (best of 36199)
  
  When hg does this kind of operations 1500 times in pull ->
  bookmarks.comparebookmarks -> bookmarks.validdest, that's 11s that
  drop from the --profile output.

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D6506

AFFECTED FILES
  mercurial/changelog.py
  mercurial/dagop.py
  mercurial/revlog.py

CHANGE DETAILS




To: valentin.gatienbaron, indygreg, #hg-reviewers
Cc: mercurial-devel

Patch

diff --git a/mercurial/revlog.py b/mercurial/revlog.py
--- a/mercurial/revlog.py
+++ b/mercurial/revlog.py
@@ -1216,14 +1216,25 @@ 
         A revision is considered an ancestor of itself.
 
         The implementation of this is trivial but the use of
-        commonancestorsheads is not."""
+        reachableroots is not."""
         if a == nullrev:
             return True
         elif a == b:
             return True
         elif a > b:
             return False
-        return a in self._commonancestorsheads(a, b)
+        return bool(self.reachableroots(a, [b], [a], includepath=False))
+
+    def reachableroots(self, minroot, heads, roots, includepath=False):
+        """return (heads(::<roots> and <roots>::<heads>))
+
+        If includepath is True, return (<roots>::<heads>)."""
+        try:
+            return self.index.reachableroots2(minroot, heads, roots,
+                                              includepath)
+        except AttributeError:
+            return dagop._reachablerootspure(self.parentrevs,
+                                             minroot, roots, heads, includepath)
 
     def ancestor(self, a, b):
         """calculate the "best" common ancestor of nodes a and b"""
diff --git a/mercurial/dagop.py b/mercurial/dagop.py
--- a/mercurial/dagop.py
+++ b/mercurial/dagop.py
@@ -259,11 +259,10 @@ 
                 yield rev
                 break
 
-def _reachablerootspure(repo, minroot, roots, heads, includepath):
-    """See reachableroots"""
+def _reachablerootspure(pfunc, minroot, roots, heads, includepath):
+    """See revlog.reachableroots"""
     if not roots:
         return []
-    parentrevs = repo.changelog.parentrevs
     roots = set(roots)
     visit = list(heads)
     reachable = set()
@@ -280,7 +279,7 @@ 
             reached(rev)
             if not includepath:
                 continue
-        parents = parentrevs(rev)
+        parents = pfunc(rev)
         seen[rev] = parents
         for parent in parents:
             if parent >= minroot and parent not in seen:
@@ -296,18 +295,13 @@ 
     return reachable
 
 def reachableroots(repo, roots, heads, includepath=False):
-    """return (heads(::<roots> and <roots>::<heads>))
-
-    If includepath is True, return (<roots>::<heads>)."""
+    """See revlog.reachableroots"""
     if not roots:
         return baseset()
     minroot = roots.min()
     roots = list(roots)
     heads = list(heads)
-    try:
-        revs = repo.changelog.reachableroots(minroot, heads, roots, includepath)
-    except AttributeError:
-        revs = _reachablerootspure(repo, minroot, roots, heads, includepath)
+    revs = repo.changelog.reachableroots(minroot, heads, roots, includepath)
     revs = baseset(revs)
     revs.sort()
     return revs
diff --git a/mercurial/changelog.py b/mercurial/changelog.py
--- a/mercurial/changelog.py
+++ b/mercurial/changelog.py
@@ -420,9 +420,6 @@ 
             if i not in self.filteredrevs:
                 yield i
 
-    def reachableroots(self, minroot, heads, roots, includepath=False):
-        return self.index.reachableroots2(minroot, heads, roots, includepath)
-
     def _checknofilteredinrevs(self, revs):
         """raise the appropriate error if 'revs' contains a filtered revision