Patchwork [3,of,4] revlog: efficient implementation of 'descendant'

mail settings
Submitter Paul Morelle
Date July 1, 2018, 6:38 a.m.
Message ID <5ea9c5d20ecc1aac2aec.1530427121@belenos.localdomain>
Download mbox | patch
Permalink /patch/32536/
State Accepted
Headers show


Paul Morelle - July 1, 2018, 6:38 a.m.
# HG changeset patch
# User Boris Feld <>
# Date 1529622320 -3600
#      Fri Jun 22 00:05:20 2018 +0100
# Node ID 5ea9c5d20ecc1aac2aecdd4c0902b3cd470b04d5
# Parent  494f5f95311e3b36a01cca745e52f536c3977a5c
# EXP-Topic descendant
# Available At
#              hg pull -r 5ea9c5d20ecc
revlog: efficient implementation of 'descendant'

Iterating over descendants is costly, because there are no "parent -> children"
pointers. Walking the other way around is much more efficient, especially on
large repositories, where descendant walks can cost seconds. And the other hand,
common ancestors code follows links in the right direction and has a compiled

In real life usage, this saved up to 80s during some pull operations, where
descendant test happens in extension code.


diff -r 494f5f95311e -r 5ea9c5d20ecc mercurial/
--- a/mercurial/	Thu Jun 21 23:56:51 2018 +0100
+++ b/mercurial/	Fri Jun 22 00:05:20 2018 +0100
@@ -1376,16 +1376,14 @@ 
         return c
     def descendant(self, start, end):
+        """True if revision 'end' is an descendant of revision 'start'
+        A revision is considered as a descendant of itself."""
         if start == nullrev:
             return True
         elif start == end:
             return True
-        for i in self.descendants([start]):
-            if i == end:
-                return True
-            elif i > end:
-                break
-        return False
+        return start in self._commonancestorsheads(start, end)
     def commonancestorsheads(self, a, b):
         """calculate all the heads of the common ancestors of nodes a and b"""