Patchwork [3,of,7] revset: inline parents computation to reuse the input argument

login
register
mail settings
Submitter Boris Feld
Date Jan. 15, 2019, 7:33 p.m.
Message ID <da8305b14fd8d61f7943.1547580802@localhost.localdomain>
Download mbox | patch
Permalink /patch/37759/
State Accepted
Headers show

Comments

Boris Feld - Jan. 15, 2019, 7:33 p.m.
# HG changeset patch
# User Boris Feld <boris.feld@octobus.net>
# Date 1547481235 -3600
#      Mon Jan 14 16:53:55 2019 +0100
# Node ID da8305b14fd8d61f7943c0f53480cfbb2358880d
# Parent  0c8eb4ed3b0f0294f2cb2d328ffce70847489be9
# EXP-Topic revset.predicates
# Available At https://bitbucket.org/octobus/mercurial-devel/
#              hg pull https://bitbucket.org/octobus/mercurial-devel/ -r da8305b14fd8
revset: inline parents computation to reuse the input argument

Before this change, using `heads(xxx)` would compute `xxx` multiple time. Once
to select the possible candidates, and once to compute the parent set.

The code used to compute parents is a direct copy past from the `parents`
revset. We expect to replace it quickly in a later changeset. So we did not
bother with extracting a function.

In case where the input set is expensive to compute this provides a
significant performance boost.

(output are from contrib/revsetbenchmarks.py)

revset: heads(matching(tip, "author"))
   plain         min           max           first         last          reverse       rev..rst      rev..ast      sort          sor..rst      sor..ast
0) 15.06746      14.92766      7.335694      15.03092      7.635580      15.04133      7.454806      15.27565      14.97796      14.87607      7.480900
1) 7.529300  49% 7.592152  50% 7.480548      7.544528  50% 7.421248      7.522279  50% 7.484876      7.613154  49% 7.599553  50% 7.561410  50% 7.508990

In other cases, with a faster input set, we still see a (smaller) performance
boost.

revset: heads(all())
   plain         min           max           first         last          reverse       rev..rst      rev..ast      sort          sor..rst      sor..ast
0) 0.038994      0.035981      0.033345      0.035751      0.033569      0.039833      0.033653      0.035428      0.039483      0.035750      0.033657
1) 0.036359  93% 0.032613  90% 0.031479  94% 0.032790  91% 0.030681  91% 0.036456  91% 0.031128  92% 0.032461  91% 0.036276  91% 0.032721  91% 0.031024  92%

revset: heads(-10000:-1)
   plain         min           max           first         last          reverse       rev..rst      rev..ast      sort          sor..rst      sor..ast
0) 0.004184      0.003576      0.003593      0.003628      0.003569      0.004277      0.003590      0.003719      0.004194      0.003659      0.003690
1) 0.003850  92% 0.003267  91% 0.003256  90% 0.003261  89% 0.003204  89% 0.003855  90% 0.003294  91% 0.003164  85% 0.003848  91% 0.003302  90% 0.003296  89%

revset: (-5000:-1000) and heads(-10000:-1)
   plain         min           max           first         last          reverse       rev..rst      rev..ast      sort          sor..rst      sor..ast
0) 0.004730      0.003429      0.003359      0.003391      0.003369      0.004787      0.003418      0.003469      0.004772      0.003445      0.003454
1) 0.004277  90% 0.003430      0.003423      0.003353      0.003340      0.004250  88% 0.003387      0.003385      0.004325  90% 0.003413      0.003373

revset: heads(matching(tip, "author")) and -10000:-1
   plain         min           max           first         last          reverse       rev..rst      rev..ast      sort          sor..rst      sor..ast
0) 8.250275      8.231453      7.508579      8.230028      7.529777      8.358590      7.531636      8.301830      8.137196      8.421402      7.540355
1) 7.474707  90% 7.587345  92% 7.486192      7.548340  91% 7.485288      7.659108  91% 7.485307      7.628890  91% 7.523479  92% 7.558384  89% 7.467524

revset: (-10000:-1) and heads(matching(tip, "author"))
   plain         min           max           first         last          reverse       rev..rst      rev..ast      sort          sor..rst      sor..ast
0) 8.341504      8.315248      7.489414      8.320746      7.548816      8.244137      7.514663      8.281701      8.218862      8.412644      7.456793
1) 7.553704  90% 7.570679  91% 7.391438      7.724237  92% 7.527400      7.570637  91% 7.580622      7.450912  89% 7.556154  91% 7.514726  89% 7.494328
Yuya Nishihara - Jan. 17, 2019, 11:30 a.m.
On Tue, 15 Jan 2019 20:33:22 +0100, Boris Feld wrote:
> # HG changeset patch
> # User Boris Feld <boris.feld@octobus.net>
> # Date 1547481235 -3600
> #      Mon Jan 14 16:53:55 2019 +0100
> # Node ID da8305b14fd8d61f7943c0f53480cfbb2358880d
> # Parent  0c8eb4ed3b0f0294f2cb2d328ffce70847489be9
> # EXP-Topic revset.predicates
> # Available At https://bitbucket.org/octobus/mercurial-devel/
> #              hg pull https://bitbucket.org/octobus/mercurial-devel/ -r da8305b14fd8
> revset: inline parents computation to reuse the input argument

Queued, thanks.

> @@ -1168,9 +1168,18 @@ def heads(repo, subset, x, order):
>      # argument set should never define order
>      if order == defineorder:
>          order = followorder
> -    s = getset(repo, subset, x, order=order)
> -    ps = parents(repo, subset, x)
> -    return s - ps
> +    inputset = getset(repo, fullreposet(repo), x, order=order)

Since we do 'subset &', this can be just order=anyorder, and takeorder=True
can be removed.

> +    return subset & (inputset - ps)

Patch

diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -1168,9 +1168,18 @@  def heads(repo, subset, x, order):
     # argument set should never define order
     if order == defineorder:
         order = followorder
-    s = getset(repo, subset, x, order=order)
-    ps = parents(repo, subset, x)
-    return s - ps
+    inputset = getset(repo, fullreposet(repo), x, order=order)
+    ps = set()
+    cl = repo.changelog
+    up = ps.update
+    parentrevs = cl.parentrevs
+    for r in inputset:
+        try:
+            up(parentrevs(r))
+        except error.WdirUnsupported:
+            up(p.rev() for p in repo[r].parents())
+    ps.discard(node.nullrev)
+    return subset & (inputset - ps)
 
 @predicate('hidden()', safe=True)
 def hidden(repo, subset, x):
diff --git a/tests/test-revset.t b/tests/test-revset.t
--- a/tests/test-revset.t
+++ b/tests/test-revset.t
@@ -1427,12 +1427,10 @@  Test heads
   $ hg debugrevspec -s '9: & heads(all())'
   * set:
   <filteredset
+    <baseset [9]>,
     <filteredset
-      <baseset [9]>,
-      <spanset+ 0:10>>,
-    <not
-      <filteredset
-        <baseset [9]>, set([0, 1, 2, 3, 4, 5, 6, 8])>>>
+      <spanset+ 0:10>,
+      <not set([0, 1, 2, 3, 4, 5, 6, 8])>>>
   9
 
  but should follow the order of the subset