Patchwork [STABLE] obsolete: fix n^2 marker computation behavior

login
register
mail settings
Submitter Pierre-Yves David
Date Feb. 23, 2016, 1:19 p.m.
Message ID <61be787ee62ea5910b0e.1456233562@marginatus.alto.octopoid.net>
Download mbox | patch
Permalink /patch/13311/
State Accepted
Commit 48e1a641765d541a4bdc3f36b69cb3f5974040af
Delegated to: Matt Mackall
Headers show

Comments

Pierre-Yves David - Feb. 23, 2016, 1:19 p.m.
# HG changeset patch
# User Durham Goode <durham@fb.com>
# Date 1454629084 28800
#      Thu Feb 04 15:38:04 2016 -0800
# Branch stable
# Node ID 61be787ee62ea5910b0e55b5b5743079fbea1457
# Parent  1bcb4f34b9f91a2e330966182f691664fbada1bc
# Available At http://hg.netv6.net/marmoute-wip/mercurial/
#              hg pull http://hg.netv6.net/marmoute-wip/mercurial/ -r 61be787ee62e
obsolete: fix n^2 marker computation behavior

Previously, if you ran obsolete.createmarkers with a bunch of markers that did
not have successors (like when you do a prune), it encountered a n^2 computation
behavior because the loop would read the changelog (to get ctx.parents()), then
add a marker, in a loop.  Adding a marker invalidated the computehidden cache,
and reading the changelog recomputed it.

This resulted in pruning 150 commits taking 150+ seconds in a large repo.

The fix is to break the reading part of the loop to be separate from the writing
part.
Pierre-Yves David - Feb. 23, 2016, 1:54 p.m.
On 02/23/2016 02:19 PM, Pierre-Yves David wrote:
> # HG changeset patch
> # User Durham Goode <durham@fb.com>
> # Date 1454629084 28800
> #      Thu Feb 04 15:38:04 2016 -0800
> # Branch stable
> # Node ID 61be787ee62ea5910b0e55b5b5743079fbea1457
> # Parent  1bcb4f34b9f91a2e330966182f691664fbada1bc
> # Available At http://hg.netv6.net/marmoute-wip/mercurial/
> #              hg pull http://hg.netv6.net/marmoute-wip/mercurial/ -r 61be787ee62e
> obsolete: fix n^2 marker computation behavior

This is a grafting on stable of a change from durham currently on 
default. This is hitting people in the wild and the change is small 
enough for stable in my opinion.
Augie Fackler - Feb. 23, 2016, 6:05 p.m.
On Tue, Feb 23, 2016 at 02:54:52PM +0100, Pierre-Yves David wrote:
>
>
> On 02/23/2016 02:19 PM, Pierre-Yves David wrote:
> ># HG changeset patch
> ># User Durham Goode <durham@fb.com>
> ># Date 1454629084 28800
> >#      Thu Feb 04 15:38:04 2016 -0800
> ># Branch stable
> ># Node ID 61be787ee62ea5910b0e55b5b5743079fbea1457
> ># Parent  1bcb4f34b9f91a2e330966182f691664fbada1bc
> ># Available At http://hg.netv6.net/marmoute-wip/mercurial/
> >#              hg pull http://hg.netv6.net/marmoute-wip/mercurial/ -r 61be787ee62e
> >obsolete: fix n^2 marker computation behavior
>
> This is a grafting on stable of a change from durham currently on default.
> This is hitting people in the wild and the change is small enough for stable
> in my opinion.

I concur, but I'll leave that to mpm (cc'd) to decide.

>
> --
> Pierre-Yves David
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Pierre-Yves David - March 7, 2016, 3:10 p.m.
On 02/23/2016 07:05 PM, Augie Fackler wrote:
> On Tue, Feb 23, 2016 at 02:54:52PM +0100, Pierre-Yves David wrote:
>>
>>
>> On 02/23/2016 02:19 PM, Pierre-Yves David wrote:
>>> # HG changeset patch
>>> # User Durham Goode <durham@fb.com>
>>> # Date 1454629084 28800
>>> #      Thu Feb 04 15:38:04 2016 -0800
>>> # Branch stable
>>> # Node ID 61be787ee62ea5910b0e55b5b5743079fbea1457
>>> # Parent  1bcb4f34b9f91a2e330966182f691664fbada1bc
>>> # Available At http://hg.netv6.net/marmoute-wip/mercurial/
>>> #              hg pull http://hg.netv6.net/marmoute-wip/mercurial/ -r 61be787ee62e
>>> obsolete: fix n^2 marker computation behavior
>>
>> This is a grafting on stable of a change from durham currently on default.
>> This is hitting people in the wild and the change is small enough for stable
>> in my opinion.
>
> I concur, but I'll leave that to mpm (cc'd) to decide.

Gentle ping.
Matt Mackall - March 9, 2016, 11:25 p.m.
On Mon, 2016-03-07 at 16:10 +0100, Pierre-Yves David wrote:
> 
> On 02/23/2016 07:05 PM, Augie Fackler wrote:
> > On Tue, Feb 23, 2016 at 02:54:52PM +0100, Pierre-Yves David wrote:
> > > 
> > > 
> > > On 02/23/2016 02:19 PM, Pierre-Yves David wrote:
> > > > # HG changeset patch
> > > > # User Durham Goode <durham@fb.com>
> > > > # Date 1454629084 28800
> > > > #      Thu Feb 04 15:38:04 2016 -0800
> > > > # Branch stable
> > > > # Node ID 61be787ee62ea5910b0e55b5b5743079fbea1457
> > > > # Parent  1bcb4f34b9f91a2e330966182f691664fbada1bc
> > > > # Available At http://hg.netv6.net/marmoute-wip/mercurial/
> > > > #              hg pull http://hg.netv6.net/marmoute-wip/mercurial/ -r
> > > > 61be787ee62e
> > > > obsolete: fix n^2 marker computation behavior
> > > 
> > > This is a grafting on stable of a change from durham currently on default.
> > > This is hitting people in the wild and the change is small enough for
> > > stable
> > > in my opinion.
> > 
> > I concur, but I'll leave that to mpm (cc'd) to decide.
> 
> Gentle ping.

The duplicate summary caused this to be swallowed by my "have I already dealt
with this?" tools.

For future reference, I think avoidable quadratic (or worse!) behavior is fair
to consider an outright bug and appropriate for stable, especially if we see it
manifest in 100s+ overhead.

What I don't like to see on stable is performance tweaking with small constant
factors. A 2x speed-up is awesome.. but not worth risking regression on stable
for.

I've manually grafted this here, thanks.

Patch

diff --git a/mercurial/obsolete.py b/mercurial/obsolete.py
--- a/mercurial/obsolete.py
+++ b/mercurial/obsolete.py
@@ -1223,10 +1223,11 @@  def createmarkers(repo, relations, flag=
         metadata = {}
     if 'user' not in metadata:
         metadata['user'] = repo.ui.username()
     tr = repo.transaction('add-obsolescence-marker')
     try:
+        markerargs = []
         for rel in relations:
             prec = rel[0]
             sucs = rel[1]
             localmetadata = metadata.copy()
             if 2 < len(rel):
@@ -1241,10 +1242,19 @@  def createmarkers(repo, relations, flag=
             npare = None
             if not nsucs:
                 npare = tuple(p.node() for p in prec.parents())
             if nprec in nsucs:
                 raise error.Abort("changeset %s cannot obsolete itself" % prec)
+
+            # Creating the marker causes the hidden cache to become invalid,
+            # which causes recomputation when we ask for prec.parents() above.
+            # Resulting in n^2 behavior.  So let's prepare all of the args
+            # first, then create the markers.
+            markerargs.append((nprec, nsucs, npare, localmetadata))
+
+        for args in markerargs:
+            nprec, nsucs, npare, localmetadata = args
             repo.obsstore.create(tr, nprec, nsucs, flag, parents=npare,
                                  date=date, metadata=localmetadata)
             repo.filteredrevcache.clear()
         tr.close()
     finally: