[PATCH] obsolete: fix n^2 marker computation behavior

Augie Fackler raf at durin42.com
Fri Feb 5 15:40:05 UTC 2016


On Thu, Feb 04, 2016 at 03:41:18PM -0800, Durham Goode wrote:
> # HG changeset patch
> # User Durham Goode <durham at 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 at mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel



More information about the Mercurial-devel mailing list