[PATCH] phase: improve retractboundary perf

[Martin von Zweigbergk]

On Sat, Nov 7, 2015 at 4:13 PM Durham Goode <durham at fb.com> wrote:

> # HG changeset patch
> # User Durham Goode <durham at fb.com>
> # Date 1446941509 28800
> #      Sat Nov 07 16:11:49 2015 -0800
> # Node ID 60db725e6c3d79385908a948ce5620419c22ac51
> # Parent  3b5d30cbbf1132be2325c5362a156038bdc84e2c
> phase: improve retractboundary perf
>
> The existing retractboundary implementation computed the new boundary by
> walking
> all descendants of all existing roots and computing the new roots. This is
> O(commits since first root), which on long repos can be hundreds of
> thousands of
> commits.
>
> The new algorithm only updates roots that are greater than the new root
> locations. For common operations like commit on a repo with the earliest
> root
> several hundred thousand commits ago, this makes retractboundary go from
> 1 second to 0.008 seconds.
>

Nice, I'm pushing this to the clowncopter.


>
> I tested it by running the test suite with both implementations and
> checking
> that the root results were always the identical.
>
> diff --git a/mercurial/phases.py b/mercurial/phases.py
> --- a/mercurial/phases.py
> +++ b/mercurial/phases.py
> @@ -308,9 +308,19 @@ class phasecache(object):
>                  raise error.Abort(_('cannot change null revision phase'))
>              currentroots = currentroots.copy()
>              currentroots.update(newroots)
> -            ctxs = repo.set('roots(%ln::)', currentroots)
> -            currentroots.intersection_update(ctx.node() for ctx in ctxs)
> -            self._updateroots(targetphase, currentroots, tr)
> +
> +            # Only compute new roots for revs above the roots that are
> being
> +            # retracted.
> +            minnewroot = min(repo[n].rev() for n in newroots)
> +            aboveroots = [n for n in currentroots
> +                          if repo[n].rev() >= minnewroot]
> +            updatedroots = repo.set('roots(%ln::)', aboveroots)
> +
> +            finalroots = set(n for n in currentroots if repo[n].rev() <
> +                             minnewroot)
>

This is almost the same as for "aboveroots", but Python doesn't seem to
have a "partition" function, and even though creating the contexts may be a
little expensive, I guess it's rare that more than a few roots are involved.


> +            finalroots.update(ctx.node() for ctx in updatedroots)
> +
> +            self._updateroots(targetphase, finalroots, tr)
>          repo.invalidatevolatilesets()
>
>      def filterunknown(self, repo):
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel at selenic.com
> https://selenic.com/mailman/listinfo/mercurial-devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://selenic.com/pipermail/mercurial-devel/attachments/20151109/f4f842b2/attachment.html>