Patchwork [4,of,6] ancestor: optimize _lazyancestorsiter() for contiguous chains

login
register
mail settings
Submitter Yuya Nishihara
Date Sept. 11, 2018, 11:02 p.m.
Message ID <d346926526c0ca1d35b5.1536706929@mimosa>
Download mbox | patch
Permalink /patch/34506/
State Accepted
Headers show

Comments

Yuya Nishihara - Sept. 11, 2018, 11:02 p.m.
# HG changeset patch
# User Yuya Nishihara <yuya@tcha.org>
# Date 1536584339 -32400
#      Mon Sep 10 21:58:59 2018 +0900
# Node ID d346926526c0ca1d35b549d8f47840d123879249
# Parent  acc190466e6d1e6db9bd99024e360b68c3c8d8cb
ancestor: optimize _lazyancestorsiter() for contiguous chains

If there's no revision between p1 and current, p1 must be the next revision
to visit. In this case, we can get around the overhead of heappop/push
operations. Note that this is faster than using heapreplace().

'current - p1 == 1' could be generalized as 'all(r not in seen for r in
xrange(p1, current)', but Python is too slow to do such thing.

Patch

diff --git a/mercurial/ancestor.py b/mercurial/ancestor.py
--- a/mercurial/ancestor.py
+++ b/mercurial/ancestor.py
@@ -283,14 +283,22 @@  def _lazyancestorsiter(parentrevs, initr
                 see(p2)
 
     while visit:
-        current = -nextitem(visit)
+        current = -visit[0]
         if current < stoprev:
             break
         yield current
+        # optimize out heapq operation if p1 is known to be the next highest
+        # revision, which is quite common in linear history.
         p1, p2 = parentrevs(current)
         if p1 not in seen:
-            schedule(visit, -p1)
+            if current - p1 == 1:
+                visit[0] = -p1
+            else:
+                nextitem(visit)
+                schedule(visit, -p1)
             see(p1)
+        else:
+            nextitem(visit)
         if p2 not in seen:
             schedule(visit, -p2)
             see(p2)
diff --git a/tests/test-ancestor.py b/tests/test-ancestor.py
--- a/tests/test-ancestor.py
+++ b/tests/test-ancestor.py
@@ -221,6 +221,10 @@  def test_lazyancestors():
     s = genlazyancestors([11, 13], stoprev=12, inclusive=True)
     printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
 
+    # Contiguous chains: 5->4, 2->1 (where 1 is in seen set), 1->0
+    s = genlazyancestors([10, 1], inclusive=True)
+    printlazyancestors(s, [2, 10, 4, 5, -1, 0, 1])
+
 # The C gca algorithm requires a real repo. These are textual descriptions of
 # DAGs that have been known to be problematic, and, optionally, known pairs
 # of revisions and their expected ancestor list.
diff --git a/tests/test-ancestor.py.out b/tests/test-ancestor.py.out
--- a/tests/test-ancestor.py.out
+++ b/tests/test-ancestor.py.out
@@ -22,3 +22,6 @@  iteration:  [13, 11]
 % lazy ancestor set for [11, 13], stoprev = 12, inclusive = True
 membership: [13]
 iteration:  [13]
+% lazy ancestor set for [10, 1], stoprev = 0, inclusive = True
+membership: [2, 10, 4, 5, 0, 1]
+iteration:  [10, 5, 4, 2, 1, 0]