[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