Patchwork obsolete: fix n^2 marker computation behavior

login
register
mail settings
Submitter Durham Goode
Date Feb. 4, 2016, 11:41 p.m.
Message ID <29aeb1f85fbc10053e69.1454629278@dev8486.prn1.facebook.com>
Download mbox | patch
Permalink /patch/12987/
State Superseded
Commit 48e1a641765d541a4bdc3f36b69cb3f5974040af
Headers show

Comments

Durham Goode - Feb. 4, 2016, 11:41 p.m.
# HG changeset patch
# User Durham Goode <durham@fb.com>
# Date 1454629084 28800
#      Thu Feb 04 15:38:04 2016 -0800
# Node ID 29aeb1f85fbc10053e697d406ce7ae93901f7e0e
# Parent  01a5143cd25f285f8c745a92986cd7186bb32c90
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.
Augie Fackler - Feb. 5, 2016, 3:40 p.m.
On Thu, Feb 04, 2016 at 03:41:18PM -0800, Durham Goode wrote:
> # HG changeset patch
> # User Durham Goode <durham@fb.com>
> # Date 1454629084 28800
> #      Thu Feb 04 15:38:04 2016 -0800
> # Node ID 29aeb1f85fbc10053e697d406ce7ae93901f7e0e
> # Parent  01a5143cd25f285f8c745a92986cd7186bb32c90
> obsolete: fix n^2 marker computation behavior

Queued this, thanks.

>
> 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
> @@ -1225,6 +1225,7 @@ def createmarkers(repo, relations, flag=
>          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 @@ def createmarkers(repo, relations, flag=
>                  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()
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel

Patch

diff --git a/mercurial/obsolete.py b/mercurial/obsolete.py
--- a/mercurial/obsolete.py
+++ b/mercurial/obsolete.py
@@ -1225,6 +1225,7 @@  def createmarkers(repo, relations, flag=
         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 @@  def createmarkers(repo, relations, flag=
                 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()