From patchwork Tue Feb 23 13:19:22 2016
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: [STABLE] obsolete: fix n^2 marker computation behavior
From: Pierre-Yves David <pierre-yves.david@ens-lyon.org>
X-Patchwork-Id: 13311
Message-Id: <61be787ee62ea5910b0e.1456233562@marginatus.alto.octopoid.net>
To: mercurial-devel@mercurial-scm.org
Cc: Pierre-Yves David <pierre-yves.david@ens-lyon.org>
Date: Tue, 23 Feb 2016 14:19:22 +0100

# 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.

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: