Patchwork [STABLE] revset: force immediate revset evaluation for roots() (issue4313)

login
register
mail settings
Submitter Gregory Szorc
Date July 24, 2014, 2:09 a.m.
Message ID <da352529e4b1b99c313b.1406167790@gps-mbp.local>
Download mbox | patch
Permalink /patch/5194/
State Changes Requested
Headers show

Comments

Gregory Szorc - July 24, 2014, 2:09 a.m.
# HG changeset patch
# User Gregory Szorc <gregory.szorc@gmail.com>
# Date 1406167462 25200
#      Wed Jul 23 19:04:22 2014 -0700
# Branch stable
# Node ID da352529e4b1b99c313b77058d259535b96b9f2f
# Parent  54ff2789d75e0662a536b3da61ca25c07436966b
revset: force immediate revset evaluation for roots() (issue4313)

Lazy revsets make roots() extremely slow for large inputs. The
underlying reason is that baseset.__sub__ creates a lazyset and the
subsequent evaluation of that lazyset results in back-and-forth
evaluation between the 2 sets, leading to an explosion of function
evaluations and drastic slowdown. This is possibly a regression
from dd716807fd23.

On the author's machine, this slowdown manifested during evaluation of
'roots(%ln::)' in phases.retractboundary after unbundling the Firefox
repository. Using `time hg unbundle firefox.hg` as a benchmark:

Before: 8:00
After:  4:28
Delta: -3:32

For reference, the subset and cs baseset instances impacted by this
change were of lengths 193634 and 193627, respectively.

The proper fix for this issue is to make baseset.__sub__ more intelligent.
However, the patch author is not super familiar with this code, would like
a fix for a bad performance regression to make the next stable release,
is concerned about a related change in dd716807fd23 and unintended
consequences of changing baseset.__sub__ and believes that this
targeted approach is the safest for right now.
Pierre-Yves David - July 24, 2014, 9:39 a.m.
On 07/24/2014 04:09 AM, Gregory Szorc wrote:
> # HG changeset patch
> # User Gregory Szorc <gregory.szorc@gmail.com>
> # Date 1406167462 25200
> #      Wed Jul 23 19:04:22 2014 -0700
> # Branch stable
> # Node ID da352529e4b1b99c313b77058d259535b96b9f2f
> # Parent  54ff2789d75e0662a536b3da61ca25c07436966b
> revset: force immediate revset evaluation for roots() (issue4313)
>
> Lazy revsets make roots() extremely slow for large inputs. The
> underlying reason is that baseset.__sub__ creates a lazyset and the
> subsequent evaluation of that lazyset results in back-and-forth
> evaluation between the 2 sets, leading to an explosion of function
> evaluations and drastic slowdown. This is possibly a regression
> from dd716807fd23.
>
> On the author's machine, this slowdown manifested during evaluation of
> 'roots(%ln::)' in phases.retractboundary after unbundling the Firefox
> repository. Using `time hg unbundle firefox.hg` as a benchmark:
>
> Before: 8:00
> After:  4:28
> Delta: -3:32

Please have a look at contrib/revsetbenchmarks.{py,txt}

Such regression should be added to the benchmark list (if not already 
present) and output in your changeset description should be extract from 
the script run.

>
> For reference, the subset and cs baseset instances impacted by this
> change were of lengths 193634 and 193627, respectively.
>
> The proper fix for this issue is to make baseset.__sub__ more intelligent.
> However, the patch author is not super familiar with this code, would like
> a fix for a bad performance regression to make the next stable release,
> is concerned about a related change in dd716807fd23 and unintended
> consequences of changing baseset.__sub__ and believes that this
> targeted approach is the safest for right now.
>
> diff --git a/mercurial/revset.py b/mercurial/revset.py
> --- a/mercurial/revset.py
> +++ b/mercurial/revset.py
> @@ -1474,9 +1474,13 @@ def roots(repo, subset, x):
>       """
>       s = getset(repo, spanset(repo), x).set()
>       subset = baseset([r for r in s if r in subset.set()])
>       cs = _children(repo, subset, s)
> -    return subset - cs
> +    # This casting was added for performance reasons because __sub__ on 2
> +    # baseset will create lazyset and the subsequent evaluation appears to
> +    # be O(n^2). This hack should be removed if baseset.__sub__ gains the
> +    # smarts to react intelligently to 2 baseset instances.
> +    return baseset(subset.set() - cs.set())
>
>   def secret(repo, subset, x):
>       """``secret()``
>       Changeset in secret phase."""
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@selenic.com
> http://selenic.com/mailman/listinfo/mercurial-devel
>
Matt Mackall - July 25, 2014, 3:04 a.m.
On Wed, 2014-07-23 at 19:09 -0700, Gregory Szorc wrote:
> This is possibly a regression
> from dd716807fd23.

You said the magic word to make me actually care about this during a
code freeze.. but then didn't take the crucial step of measuring the
regression.
Gregory Szorc - July 25, 2014, 5:15 a.m.
On 7/24/14, 8:04 PM, Matt Mackall wrote:
> On Wed, 2014-07-23 at 19:09 -0700, Gregory Szorc wrote:
>> This is possibly a regression
>> from dd716807fd23.
>
> You said the magic word to make me actually care about this during a
> code freeze.. but then didn't take the crucial step of measuring the
> regression.

There are some numbers in the v2 patch I sent today. I didn't explicitly 
mention dd716807fd23's numbers in the commit though. Here are 
dd716807fd23^, dd716807fd23, and my v2 patch for the hg repo:

revset #6: roots(0::tip)
0) wall 0.078206 comb 0.070000 user 0.070000 sys 0.000000 (best of 100)
1) wall 2.841311 comb 2.840000 user 2.840000 sys 0.000000 (best of 4)
2) wall 0.078800 comb 0.080000 user 0.080000 sys 0.000000 (best of 100)

revset #23: roots((0:tip)::)
0) wall 0.154665 comb 0.160000 user 0.160000 sys 0.000000 (best of 62)
1) wall 2.872686 comb 2.870000 user 2.870000 sys 0.000000 (best of 4)
2) wall 0.155815 comb 0.160000 user 0.160000 sys 0.000000 (best of 61)

And here they are for mozilla-central:

revset #6: roots(0::tip)
0) wall 0.669493 comb 0.670000 user 0.660000 sys 0.010000 (best of 15)
1) wall 301.787656 comb 301.770000 user 301.670000 sys 0.100000 (best of 3)
2) wall 0.672837 comb 0.680000 user 0.670000 sys 0.010000 (best of 15)

revset #23: roots((0:tip)::)
0) wall 1.246024 comb 1.250000 user 1.230000 sys 0.020000 (best of 8)
1) wall 218.167173 comb 218.170000 user 218.080000 sys 0.090000 (best of 3)
2) wall 1.229971 comb 1.230000 user 1.210000 sys 0.020000 (best of 8)
Pierre-Yves David - July 25, 2014, 12:39 p.m.
On 07/25/2014 07:15 AM, Gregory Szorc wrote:
> On 7/24/14, 8:04 PM, Matt Mackall wrote:
>> On Wed, 2014-07-23 at 19:09 -0700, Gregory Szorc wrote:
>>> This is possibly a regression
>>> from dd716807fd23.
>>
>> You said the magic word to make me actually care about this during a
>> code freeze.. but then didn't take the crucial step of measuring the
>> regression.
>
> There are some numbers in the v2 patch I sent today. I didn't explicitly
> mention dd716807fd23's numbers in the commit though. Here are
> dd716807fd23^, dd716807fd23, and my v2 patch for the hg repo:
>
> revset #6: roots(0::tip)
> 0) wall 0.078206 comb 0.070000 user 0.070000 sys 0.000000 (best of 100)
> 1) wall 2.841311 comb 2.840000 user 2.840000 sys 0.000000 (best of 4)
> 2) wall 0.078800 comb 0.080000 user 0.080000 sys 0.000000 (best of 100)
>
> revset #23: roots((0:tip)::)
> 0) wall 0.154665 comb 0.160000 user 0.160000 sys 0.000000 (best of 62)
> 1) wall 2.872686 comb 2.870000 user 2.870000 sys 0.000000 (best of 4)
> 2) wall 0.155815 comb 0.160000 user 0.160000 sys 0.000000 (best of 61)
>
> And here they are for mozilla-central:
>
> revset #6: roots(0::tip)
> 0) wall 0.669493 comb 0.670000 user 0.660000 sys 0.010000 (best of 15)
> 1) wall 301.787656 comb 301.770000 user 301.670000 sys 0.100000 (best of 3)
> 2) wall 0.672837 comb 0.680000 user 0.670000 sys 0.010000 (best of 15)
>
> revset #23: roots((0:tip)::)
> 0) wall 1.246024 comb 1.250000 user 1.230000 sys 0.020000 (best of 8)
> 1) wall 218.167173 comb 218.170000 user 218.080000 sys 0.090000 (best of 3)
> 2) wall 1.229971 comb 1.230000 user 1.210000 sys 0.020000 (best of 8)

Having the 3 line in the patches descriptions would be nice. This can 
probably be added by the queuer instead of spamming the list with a V3.

I assume you also checked that your patches does not introduce 
significant regression in any other entries of the revset benchmark file.
Gregory Szorc - July 25, 2014, 2:02 p.m.
On Jul 25, 2014, at 5:39, Pierre-Yves David <pierre-yves.david@ens-lyon.org> wrote:
> 
> 
> 
>> On 07/25/2014 07:15 AM, Gregory Szorc wrote:
>>> On 7/24/14, 8:04 PM, Matt Mackall wrote:
>>>> On Wed, 2014-07-23 at 19:09 -0700, Gregory Szorc wrote:
>>>> This is possibly a regression
>>>> from dd716807fd23.
>>> 
>>> You said the magic word to make me actually care about this during a
>>> code freeze.. but then didn't take the crucial step of measuring the
>>> regression.
>> 
>> There are some numbers in the v2 patch I sent today. I didn't explicitly
>> mention dd716807fd23's numbers in the commit though. Here are
>> dd716807fd23^, dd716807fd23, and my v2 patch for the hg repo:
>> 
>> revset #6: roots(0::tip)
>> 0) wall 0.078206 comb 0.070000 user 0.070000 sys 0.000000 (best of 100)
>> 1) wall 2.841311 comb 2.840000 user 2.840000 sys 0.000000 (best of 4)
>> 2) wall 0.078800 comb 0.080000 user 0.080000 sys 0.000000 (best of 100)
>> 
>> revset #23: roots((0:tip)::)
>> 0) wall 0.154665 comb 0.160000 user 0.160000 sys 0.000000 (best of 62)
>> 1) wall 2.872686 comb 2.870000 user 2.870000 sys 0.000000 (best of 4)
>> 2) wall 0.155815 comb 0.160000 user 0.160000 sys 0.000000 (best of 61)
>> 
>> And here they are for mozilla-central:
>> 
>> revset #6: roots(0::tip)
>> 0) wall 0.669493 comb 0.670000 user 0.660000 sys 0.010000 (best of 15)
>> 1) wall 301.787656 comb 301.770000 user 301.670000 sys 0.100000 (best of 3)
>> 2) wall 0.672837 comb 0.680000 user 0.670000 sys 0.010000 (best of 15)
>> 
>> revset #23: roots((0:tip)::)
>> 0) wall 1.246024 comb 1.250000 user 1.230000 sys 0.020000 (best of 8)
>> 1) wall 218.167173 comb 218.170000 user 218.080000 sys 0.090000 (best of 3)
>> 2) wall 1.229971 comb 1.230000 user 1.210000 sys 0.020000 (best of 8)
> 
> Having the 3 line in the patches descriptions would be nice. This can probably be added by the queuer instead of spamming the list with a V3.
> 
> I assume you also checked that your patches does not introduce significant regression in any other entries of the revset benchmark file.

Yes, no new regressions.
Matt Mackall - July 25, 2014, 5:13 p.m.
On Thu, 2014-07-24 at 22:15 -0700, Gregory Szorc wrote:
> On 7/24/14, 8:04 PM, Matt Mackall wrote:
> > On Wed, 2014-07-23 at 19:09 -0700, Gregory Szorc wrote:
> >> This is possibly a regression
> >> from dd716807fd23.
> >
> > You said the magic word to make me actually care about this during a
> > code freeze.. but then didn't take the crucial step of measuring the
> > regression.
> 
> There are some numbers in the v2 patch I sent today. I didn't explicitly 
> mention dd716807fd23's numbers in the commit though. Here are 
> dd716807fd23^, dd716807fd23, and my v2 patch for the hg repo:
> 
> revset #6: roots(0::tip)
> 0) wall 0.078206 comb 0.070000 user 0.070000 sys 0.000000 (best of 100)
> 1) wall 2.841311 comb 2.840000 user 2.840000 sys 0.000000 (best of 4)
> 2) wall 0.078800 comb 0.080000 user 0.080000 sys 0.000000 (best of 100)

Not sure how I missed that when I ran the benchmarks. Sigh.

> revset #23: roots((0:tip)::)
> 0) wall 1.246024 comb 1.250000 user 1.230000 sys 0.020000 (best of 8)
> 1) wall 218.167173 comb 218.170000 user 218.080000 sys 0.090000 (best of 3)
> 2) wall 1.229971 comb 1.230000 user 1.210000 sys 0.020000 (best of 8)

Yowtch. I was working under the assumption that baseset.__contains__
would be a cached set like lazyset, but instead it's list.__contains__.
Something to fix post-3.1.

Patch

diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -1474,9 +1474,13 @@  def roots(repo, subset, x):
     """
     s = getset(repo, spanset(repo), x).set()
     subset = baseset([r for r in s if r in subset.set()])
     cs = _children(repo, subset, s)
-    return subset - cs
+    # This casting was added for performance reasons because __sub__ on 2
+    # baseset will create lazyset and the subsequent evaluation appears to
+    # be O(n^2). This hack should be removed if baseset.__sub__ gains the
+    # smarts to react intelligently to 2 baseset instances.
+    return baseset(subset.set() - cs.set())
 
 def secret(repo, subset, x):
     """``secret()``
     Changeset in secret phase."""