Patchwork [3,of,3] cmdutil: implemented new lazy increasingwindows

login
register
mail settings
Submitter Lucas Moscovicz
Date Feb. 22, 2014, 7:19 p.m.
Message ID <dbb13949e05d8c576672.1393096774@dev1037.prn2.facebook.com>
Download mbox | patch
Permalink /patch/3741/
State Accepted
Commit 86cefb15e7b5cbb4c6d99a80942d922e998e1a38
Headers show

Comments

Lucas Moscovicz - Feb. 22, 2014, 7:19 p.m.
# HG changeset patch
# User Lucas Moscovicz <lmoscovicz@fb.com>
# Date 1392330432 28800
#      Thu Feb 13 14:27:12 2014 -0800
# Node ID dbb13949e05d8c576672ea0a49a978048c77ddf7
# Parent  01e0d36c542521cea4569185506909c47df3d129
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
Sean Farley - Feb. 22, 2014, 7:36 p.m.
Lucas Moscovicz <lmoscovicz@fb.com> writes:

> # HG changeset patch
> # User Lucas Moscovicz <lmoscovicz@fb.com>
> # Date 1392330432 28800
> #      Thu Feb 13 14:27:12 2014 -0800
> # Node ID dbb13949e05d8c576672ea0a49a978048c77ddf7
> # Parent  01e0d36c542521cea4569185506909c47df3d129
> 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

I'm really loving all these revset improvements! Unfortunately, I'm
having a hard time following them because there isn't a V2, V3,
etc. flag (i.e. 'hg email --flag V2'). It's not required, of course, but
I think it would help others like me follow along.

> 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
> @@ -1251,14 +1242,7 @@
>          stop = min(revs[0], revs[-1])
>          for x in xrange(rev, stop - 1, -1):
>              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)
> +                wanted = wanted - [x]
>  
>      # Now that wanted is correctly initialized, we can iterate over the
>      # revision range, yielding only revisions in wanted.
> @@ -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):
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@selenic.com
> http://selenic.com/mailman/listinfo/mercurial-devel
Matt Mackall - Feb. 24, 2014, 10:13 p.m.
On Sat, 2014-02-22 at 11:19 -0800, Lucas Moscovicz wrote:
> # HG changeset patch
> # User Lucas Moscovicz <lmoscovicz@fb.com>
> # Date 1392330432 28800
> #      Thu Feb 13 14:27:12 2014 -0800
> # Node ID dbb13949e05d8c576672ea0a49a978048c77ddf7
> # Parent  01e0d36c542521cea4569185506909c47df3d129
> cmdutil: implemented new lazy increasingwindows

These are queued for default, thanks.

Patch

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
@@ -1251,14 +1242,7 @@ 
         stop = min(revs[0], revs[-1])
         for x in xrange(rev, stop - 1, -1):
             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)
+                wanted = wanted - [x]
 
     # Now that wanted is correctly initialized, we can iterate over the
     # revision range, yielding only revisions in wanted.
@@ -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):