[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