From patchwork Thu Feb 20 18:36:33 2014
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: [4,of,4,RFC] cmdutil: implemented new lazy increasingwindows
From: Lucas Moscovicz <lmoscovicz@fb.com>
X-Patchwork-Id: 3729
Message-Id: <3513f022f0a8ff7ce8e3.1392921393@dev1037.prn2.facebook.com>
To: mercurial-devel@selenic.com
Date: Thu, 20 Feb 2014 10:36:33 -0800

# HG changeset patch
# User Lucas Moscovicz <lmoscovicz@fb.com>
# Date 1392330432 28800
#      Thu Feb 13 14:27:12 2014 -0800
# Node ID 3513f022f0a8ff7ce8e394c1f8f33728940d3fed
# Parent  44ca956d656db4e57add5e815dfd0aaaec57c6b9
cmdutil: implemented new lazy increasingwindows

Now log can work in a lazy way and get results as soon as they are processed.

Performance Benchmarking:

$ time hg log -l1 -qr "branch(default)"
0:9117c6561b0b

real  0m2.303s
user  0m2.252s
sys 0m0.048s

$ time ./hg log -l1 -qr "branch(default)"
0:9117c6561b0b

real  0m0.238s
user  0m0.199s
sys 0m0.037s

diff --git a/mercurial/cmdutil.py b/mercurial/cmdutil.py
--- a/mercurial/cmdutil.py
+++ b/mercurial/cmdutil.py
@@ -995,19 +995,11 @@
 
     raise util.Abort(_("revision matching date not found"))
 
-def increasingwindows(start, end, windowsize=8, sizelimit=512):
-    if start < end:
-        while start < end:
-            yield start, min(windowsize, end - start)
-            start += windowsize
-            if windowsize < sizelimit:
-                windowsize *= 2
-    else:
-        while start > end:
-            yield start, min(windowsize, start - end - 1)
-            start -= windowsize
-            if windowsize < sizelimit:
-                windowsize *= 2
+def increasingwindows(windowsize=8, sizelimit=512):
+    while True:
+        yield windowsize
+        if windowsize < sizelimit:
+            windowsize *= 2
 
 class FileWalkError(Exception):
     pass
@@ -1140,7 +1132,6 @@
     slowpath = match.anypats() or (match.files() and opts.get('removed'))
     fncache = {}
     change = repo.changectx
-    revs = revset.baseset(revs)
 
     # First step is to fill wanted, the set of revisions that we want to yield.
     # When it does not induce extra cost, we also fill fncache for revisions in
@@ -1149,7 +1140,7 @@
 
     if not slowpath and not match.files():
         # No files, no patterns.  Display all revs.
-        wanted = set(revs)
+        wanted = revs
 
     if not slowpath and match.files():
         # We only have to read through the filelog to find wanted revisions
@@ -1253,13 +1244,6 @@
             if ff.match(x):
                 wanted.discard(x)
 
-    # Choose a small initial window if we will probably only visit a
-    # few commits.
-    limit = loglimit(opts)
-    windowsize = 8
-    if limit:
-        windowsize = min(limit, windowsize)
-
     # Now that wanted is correctly initialized, we can iterate over the
     # revision range, yielding only revisions in wanted.
     def iterate():
@@ -1271,8 +1255,18 @@
             def want(rev):
                 return rev in wanted
 
-        for i, window in increasingwindows(0, len(revs), windowsize):
-            nrevs = [rev for rev in revs[i:i + window] if want(rev)]
+        it = iter(revs)
+        stopiteration = False
+        for windowsize in increasingwindows():
+            nrevs = []
+            for i in xrange(windowsize):
+                try:
+                    rev = it.next()
+                    if want(rev):
+                        nrevs.append(rev)
+                except (StopIteration):
+                    stopiteration = True
+                    break
             for rev in sorted(nrevs):
                 fns = fncache.get(rev)
                 ctx = change(rev)
@@ -1285,6 +1279,10 @@
                 prepare(ctx, fns)
             for rev in nrevs:
                 yield change(rev)
+
+            if stopiteration:
+                break
+
     return iterate()
 
 def _makegraphfilematcher(repo, pats, followfirst):