Patchwork [1,of,4] revset: changed ancestors revset to return lazy generators

login
register
mail settings
Submitter Lucas Moscovicz
Date March 6, 2014, 11:19 p.m.
Message ID <279a4c4a90edea64fccb.1394147956@dev1037.prn2.facebook.com>
Download mbox | patch
Permalink /patch/3882/
State Accepted
Commit 13c0327eeb6f4a8d44c940295025ebe14759165c
Headers show

Comments

Lucas Moscovicz - March 6, 2014, 11:19 p.m.
# HG changeset patch
# User Lucas Moscovicz <lmoscovicz@fb.com>
# Date 1391797922 28800
#      Fri Feb 07 10:32:02 2014 -0800
# Node ID 279a4c4a90edea64fccb932519aee0e43bf1605f
# Parent  b04f4e319df23fc242161f7df8c6182989501433
revset: changed ancestors revset to return lazy generators

This will not improve revsets like "::tip" but will do when that gets
intersected or substracted with another revset.

Performance Benchmarking:

$ time hg log -qr "draft() and ::tip"
...

real  0m3.961s
user  0m3.640s
sys 0m0.313s

$ time ./hg log -qr "draft() and ::tip"
...

real  0m1.080s
user  0m0.987s
sys 0m0.083s

Patch

diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -8,6 +8,7 @@ 
 import re
 import parser, util, error, discovery, hbisect, phases
 import node
+import heapq
 import match as matchmod
 import ancestor as ancestormod
 from i18n import _
@@ -20,14 +21,24 @@ 
     """Like revlog.ancestors(), but supports followfirst."""
     cut = followfirst and 1 or None
     cl = repo.changelog
-    visit = util.deque(revs)
+
+    # Implementation to be changed in later patches based on revs order.
+    h = list(revs)
+    for i in xrange(len(h)):
+        h[i] = -h[i]
+    heapq.heapify(h)
     seen = set([node.nullrev])
-    while visit:
-        for parent in cl.parentrevs(visit.popleft())[:cut]:
-            if parent not in seen:
-                visit.append(parent)
-                seen.add(parent)
-                yield parent
+    def iterate():
+        while h:
+            current = -heapq.heappop(h)
+            if current not in seen:
+                seen.add(current)
+                yield current
+                for parent in cl.parentrevs(current)[:cut]:
+                    if parent != node.nullrev:
+                        heapq.heappush(h, -parent)
+
+    return descgeneratorset(iterate())
 
 def _revdescendants(repo, revs, followfirst):
     """Like revlog.descendants() but supports followfirst."""
@@ -312,7 +323,7 @@ 
     args = getset(repo, spanset(repo), x)
     if not args:
         return baseset([])
-    s = set(_revancestors(repo, args, followfirst)) | set(args)
+    s = _revancestors(repo, args, followfirst)
     return subset.filter(lambda r: r in s)
 
 def ancestors(repo, subset, x):
@@ -784,7 +795,7 @@ 
         else:
             return baseset([])
     else:
-        s = set(_revancestors(repo, [c.rev()], followfirst)) | set([c.rev()])
+        s = _revancestors(repo, baseset([c.rev()]), followfirst)
 
     return subset.filter(lambda r: r in s)