merge-slicing: introduce and use "inheritance point" for merge
authorPierre-Yves David <pierre-yves.david@ens-lyon.org>
Fri, 24 Mar 2017 08:16:00 +0100
changeset 2220 0b6745b91d6d
parent 2219 d83bf4773433
child 2221 f61d091d318e
merge-slicing: introduce and use "inheritance point" for merge The first part of the stable sorted list of revision of a merge will shared with the one of others. This means we can reuse subranges computed from that point to compute some of the subranges from the merge. That point is latest point in the stable sorted list where the depth of the revisions match its index (that means all revision earlier in the stable sorted list are its ancestors, no dangling unrelated branches exists). This is a bit expensive to find since we have to walk all the revision, but being able to reuse subranges in all case (not just regular changesets) provide a massive speedup so the cost is worth it.
hgext3rd/evolve/stablerange.py
--- a/hgext3rd/evolve/stablerange.py	Fri Mar 24 08:31:10 2017 +0100
+++ b/hgext3rd/evolve/stablerange.py	Fri Mar 24 08:16:00 2017 +0100
@@ -172,6 +172,11 @@
         self._stablesortprepared = {}
         # caching parent call # as we do so many of them
         self._parentscache = {}
+        # The first part of the stable sorted list of revision of a merge will
+        # shared with the one of others. This means we can reuse subranges
+        # computed from that point to compute some of the subranges from the
+        # merge.
+        self._inheritancecache = {}
 
     def warmup(self, repo, heads):
         """warm the cache up to 'heads'"""
@@ -287,6 +292,37 @@
         revs.extend(reversed(top))
         return revs
 
+    def _inheritancepoint(self, repo, merge):
+        """Find the inheritance point of a Merge
+
+        The first part of the stable sorted list of revision of a merge will shared with
+        the one of others. This means we can reuse subranges computed from that point to
+        compute some of the subranges from the merge.
+
+        That point is latest point in the stable sorted list where the depth of the
+        revisions match its index (that means all revision earlier in the stable sorted
+        list are its ancestors, no dangling unrelated branches exists).
+        """
+        value = self._inheritancecache.get(merge)
+        if value is None:
+            revs = self.revsfromrange(repo, (merge, 0))
+            i = reversed(revs)
+            i.next() # pop the merge
+            expected = len(revs) - 1
+            # Since we do warmup properly, we can expect the cache to be hot
+            # for everythin under the merge we investigate
+            cache = self._depthcache
+            # note: we cannot do a binary search because element under the
+            # inherited point might have mismatching depth because of inner
+            # branching.
+            for rev in i:
+                if cache[rev] == expected:
+                    break
+                expected -= 1
+            value = (expected - 1 , rev)
+            self._inheritancecache[merge] = value
+        return value
+
     @staticmethod
     def _depthmerge(cl, rev, p1, p2, stack, cache):
         # sub method to simplify the main 'depthrev' one
@@ -355,12 +391,16 @@
         rangeid at slicepoint
 
         This function also have the important task to update the revscache of
-        the parent revs if possible and needed"""
-        # is this is a merge, there is not need to prepare the parents.
+        the parent rev s if possible and needed"""
         p1, p2 = self._parents(rangeid[0], repo.changelog.parentrevs)
-        if p2 != nodemod.nullrev:
-            return None
-        reusablerev = p1
+        if p2 == nodemod.nullrev:
+            # regular changesets, we pick the parent
+            reusablerev = p1
+        else:
+            # merge, we try the inheritance point
+            # if it is too low, it will be ditched by the depth check anyway
+            index, reusablerev = self._inheritancepoint(repo, rangeid[0])
+
         # if we reached the slicepoint, no need to go further
         if self.depthrev(repo, reusablerev) <= slicepoint:
             return None
@@ -392,10 +432,12 @@
 
     def _slicesrangeat(self, repo, rangeid, globalindex):
         p1, p2 = self._parents(rangeid[0], repo.changelog.parentrevs)
-        if p2 != nodemod.nullrev:
-            return self._slicesrangeatmerge(repo, rangeid, globalindex)
-
-        reuserev = p1
+        if p2 == nodemod.nullrev:
+            reuserev = p1
+        else:
+            index, reuserev = self._inheritancepoint(repo, rangeid[0])
+            if index < globalindex:
+                return self._slicesrangeatmerge(repo, rangeid, globalindex)
 
         assert reuserev != nodemod.nullrev