obsolete: fix n^2 marker computation behavior stable
authorDurham Goode <durham@fb.com>
Thu, 04 Feb 2016 15:38:04 -0800
branchstable
changeset 28390 48e1a641765d
parent 28389 9ab45fbe045e
child 28449 3072ce740945
child 28517 95163ababeb8
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.
mercurial/obsolete.py
--- a/mercurial/obsolete.py	Tue Mar 08 17:26:12 2016 +0000
+++ b/mercurial/obsolete.py	Thu Feb 04 15:38:04 2016 -0800
@@ -1225,6 +1225,7 @@
         metadata['user'] = repo.ui.username()
     tr = repo.transaction('add-obsolescence-marker')
     try:
+        markerargs = []
         for rel in relations:
             prec = rel[0]
             sucs = rel[1]
@@ -1243,6 +1244,15 @@
                 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()