[PATCH 4 of 6] revlog: add functions that use ancestor.lazyancestorset
Siddharth Agarwal
sid0 at fb.com
Fri Dec 14 13:35:54 CST 2012
# HG changeset patch
# User Siddharth Agarwal <sid0 at fb.com>
# Date 1355510978 28800
# Node ID 530ebaedf4047fbcddef10d98dbb0fb0e68dc7a5
# Parent 74b0e1f732cf868681ace3e2bc44d5eb54e1729a
revlog: add functions that use ancestor.lazyancestorset
In a linear repository with over 400,000 commits, hg perfancestorset takes
0.80 seconds no matter how far behind we're looking. With this patch, hg
perfancestorset -- X takes:
Rev X Time
-1 0.00s
-4000 0.01s
-20000 0.04s
-80000 0.17s
-200000 0.43s
-300000 0.69s
0 0.88s
Thus, for revisions close to tip, we're up to several orders of magnitude
faster. At 0 we're around 10% slower.
diff -r 74b0e1f732cf -r 530ebaedf404 contrib/perf.py
--- a/contrib/perf.py Fri Dec 14 11:31:23 2012 -0800
+++ b/contrib/perf.py Fri Dec 14 10:49:38 2012 -0800
@@ -82,7 +82,7 @@
revs = repo.revs(revset)
heads = repo.changelog.headrevs()
def d():
- s = set(repo.changelog.ancestors(heads))
+ s = repo.changelog.ancestorset(heads)
for rev in revs:
rev in s
timer(d)
diff -r 74b0e1f732cf -r 530ebaedf404 mercurial/revlog.py
--- a/mercurial/revlog.py Fri Dec 14 11:31:23 2012 -0800
+++ b/mercurial/revlog.py Fri Dec 14 10:49:38 2012 -0800
@@ -369,6 +369,21 @@
for rev in self.ancestors(revs, stoprev):
yield rev
+ def ancestorset(self, revs, stoprev=0):
+ """Return an object that resembles the set of ancestors of revs.
+
+ The only operation currently supported is membership (in). The set is
+ computed lazily starting from tip and working in descending rev
+ order."""
+ return ancestor.lazyancestorset(revs, self.parentrevs, False,
+ stoprev=stoprev)
+
+ def incancestorset(self, revs, stoprev=0):
+ """Identical to ancestorset() except it also generates the revisions,
+ 'revs'"""
+ return ancestor.lazyancestorset(revs, self.parentrevs, True,
+ stoprev=stoprev)
+
def descendants(self, revs):
"""Generate the descendants of 'revs' in revision order.
More information about the Mercurial-devel
mailing list