Patchwork [5,of,7] dagop: compute depth in revancestors() generator

login
register
mail settings
Submitter Yuya Nishihara
Date June 22, 2017, 3:52 p.m.
Message ID <59abcdd7c59336a5314e.1498146738@mimosa>
Download mbox | patch
Permalink /patch/21616/
State Accepted
Headers show

Comments

Yuya Nishihara - June 22, 2017, 3:52 p.m.
# HG changeset patch
# User Yuya Nishihara <yuya@tcha.org>
# Date 1497712308 -32400
#      Sun Jun 18 00:11:48 2017 +0900
# Node ID 59abcdd7c59336a5314ec9b4b95075874c0d838f
# Parent  3b2bded55cfab4dd13079cbf1d0354c1462d5c18
dagop: compute depth in revancestors() generator

Surprisingly, this makes revset benchmark slightly faster. I don't know why,
but it appears that wrapping -inputrev by tuple is the key. So I decided to
just enable depth computation by default.

  # reverse(ancestors(tip)) using hg repo
  1) 0.081051
  2) 0.075408
via Mercurial-devel - June 23, 2017, 5:23 p.m.
On Thu, Jun 22, 2017 at 8:52 AM, Yuya Nishihara <yuya@tcha.org> wrote:
> # HG changeset patch
> # User Yuya Nishihara <yuya@tcha.org>
> # Date 1497712308 -32400
> #      Sun Jun 18 00:11:48 2017 +0900
> # Node ID 59abcdd7c59336a5314ec9b4b95075874c0d838f
> # Parent  3b2bded55cfab4dd13079cbf1d0354c1462d5c18
> dagop: compute depth in revancestors() generator
>
> Surprisingly, this makes revset benchmark slightly faster. I don't know why,
> but it appears that wrapping -inputrev by tuple is the key.

I've heard something about gc and container types. Could it be that
the references don't get decremented to 0 in the new version (until gc
happens)? Just a thought.

> So I decided to
> just enable depth computation by default.
>
>   # reverse(ancestors(tip)) using hg repo
>   1) 0.081051
>   2) 0.075408
>
> diff --git a/mercurial/dagop.py b/mercurial/dagop.py
> --- a/mercurial/dagop.py
> +++ b/mercurial/dagop.py
> @@ -31,30 +31,32 @@ def _genrevancestors(repo, revs, followf
>      # without fully computing the input revs
>      revs.sort(reverse=True)
>      irevs = iter(revs)
> -    pendingheap = []
> +    pendingheap = []  # [(-rev, depth), ...] (i.e. lower depth first)
>
>      inputrev = next(irevs, None)
>      if inputrev is not None:
> -        heapq.heappush(pendingheap, -inputrev)
> +        heapq.heappush(pendingheap, (-inputrev, 0))
>
>      lastrev = None
>      while pendingheap:
> -        currev = -heapq.heappop(pendingheap)
> +        currev, curdepth = heapq.heappop(pendingheap)
> +        currev = -currev
>          if currev == inputrev:
>              inputrev = next(irevs, None)
>              if inputrev is not None:
> -                heapq.heappush(pendingheap, -inputrev)
> +                heapq.heappush(pendingheap, (-inputrev, 0))
>          if currev != lastrev:
>              lastrev = currev
>              yield currev
> +            pdepth = curdepth + 1
>              try:
>                  for prev in cl.parentrevs(currev)[:cut]:
>                      if prev != node.nullrev:
> -                        heapq.heappush(pendingheap, -prev)
> +                        heapq.heappush(pendingheap, (-prev, pdepth))
>              except error.WdirUnsupported:
>                  for pctx in repo[currev].parents()[:cut]:
>                      if pctx.rev() != node.nullrev:
> -                        heapq.heappush(pendingheap, -pctx.rev())
> +                        heapq.heappush(pendingheap, (-pctx.rev(), pdepth))
>
>  def revancestors(repo, revs, followfirst):
>      """Like revlog.ancestors(), but supports followfirst."""
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel

Patch

diff --git a/mercurial/dagop.py b/mercurial/dagop.py
--- a/mercurial/dagop.py
+++ b/mercurial/dagop.py
@@ -31,30 +31,32 @@  def _genrevancestors(repo, revs, followf
     # without fully computing the input revs
     revs.sort(reverse=True)
     irevs = iter(revs)
-    pendingheap = []
+    pendingheap = []  # [(-rev, depth), ...] (i.e. lower depth first)
 
     inputrev = next(irevs, None)
     if inputrev is not None:
-        heapq.heappush(pendingheap, -inputrev)
+        heapq.heappush(pendingheap, (-inputrev, 0))
 
     lastrev = None
     while pendingheap:
-        currev = -heapq.heappop(pendingheap)
+        currev, curdepth = heapq.heappop(pendingheap)
+        currev = -currev
         if currev == inputrev:
             inputrev = next(irevs, None)
             if inputrev is not None:
-                heapq.heappush(pendingheap, -inputrev)
+                heapq.heappush(pendingheap, (-inputrev, 0))
         if currev != lastrev:
             lastrev = currev
             yield currev
+            pdepth = curdepth + 1
             try:
                 for prev in cl.parentrevs(currev)[:cut]:
                     if prev != node.nullrev:
-                        heapq.heappush(pendingheap, -prev)
+                        heapq.heappush(pendingheap, (-prev, pdepth))
             except error.WdirUnsupported:
                 for pctx in repo[currev].parents()[:cut]:
                     if pctx.rev() != node.nullrev:
-                        heapq.heappush(pendingheap, -pctx.rev())
+                        heapq.heappush(pendingheap, (-pctx.rev(), pdepth))
 
 def revancestors(repo, revs, followfirst):
     """Like revlog.ancestors(), but supports followfirst."""