Patchwork [1,of,2] revlog: efficient implementation of 'descendant'

mail settings
Submitter Paul Morelle
Date June 21, 2018, 2:24 p.m.
Message ID <8d20b1b4b6a0297e7f96.1529591068@belenos.localdomain>
Download mbox | patch
Permalink /patch/32362/
State New
Headers show


Paul Morelle - June 21, 2018, 2:24 p.m.
# HG changeset patch
# User Boris Feld <>
# Date 1529584327 -3600
#      Thu Jun 21 13:32:07 2018 +0100
# Node ID 8d20b1b4b6a0297e7f9640d285b15a5d6647369e
# Parent  a0e185f104541858a0b049e1fb67c4d113930a9a
# EXP-Topic descendant
# Available At
#              hg pull -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/
--- a/mercurial/	Fri Feb 02 14:21:04 2018 -0800
+++ b/mercurial/	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"""