[PATCH 1 of 2] revlog: efficient implementation of 'descendant'

Paul Morelle paul.morelle at octobus.net
Thu Jun 21 14:24:28 UTC 2018


# HG changeset patch
# User Boris Feld <boris.feld at octobus.net>
# Date 1529584327 -3600
#      Thu Jun 21 13:32:07 2018 +0100
# Node ID 8d20b1b4b6a0297e7f9640d285b15a5d6647369e
# Parent  a0e185f104541858a0b049e1fb67c4d113930a9a
# EXP-Topic descendant
# Available At https://bitbucket.org/octobus/mercurial-devel/
#              hg pull https://bitbucket.org/octobus/mercurial-devel/ -r 8d20b1b4b6a0
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, while it is quite
instantaneous to walk ancestors.

As self.ancestors returns a lazyancestors instance, calling __contains__ still
considers the other bound as a ceiling limit for the research.

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

diff -r a0e185f10454 -r 8d20b1b4b6a0 mercurial/revlog.py
--- a/mercurial/revlog.py	Fri Feb 02 14:21:04 2018 -0800
+++ b/mercurial/revlog.py	Thu Jun 21 13:32:07 2018 +0100
@@ -1378,12 +1378,7 @@
     def descendant(self, start, end):
         if start == nullrev:
             return True
-        for i in self.descendants([start]):
-            if i == end:
-                return True
-            elif i > end:
-                break
-        return False
+        return start in self.ancestors([end])
 
     def commonancestorsheads(self, a, b):
         """calculate all the heads of the common ancestors of nodes a and b"""


More information about the Mercurial-devel mailing list