[PATCH 2 of 5] adjustlinkrev: use C implementation to test ancestor if possible

[Pierre-Yves David]

On 11/01/2016 09:51 AM, Jun Wu wrote:
> # HG changeset patch
> # User Jun Wu <quark at fb.com>
> # Date 1477989396 0
> #      Tue Nov 01 08:36:36 2016 +0000
> # Node ID 93e073edc7f673d76d1113f5830ec46210707c25
> # Parent  ac063914b3a3c01f1d7ed253c73113903fccb7a9
> # Available At https://bitbucket.org/quark-zju/hg-draft
> #              hg pull https://bitbucket.org/quark-zju/hg-draft -r 93e073edc7f6
> adjustlinkrev: use C implementation to test ancestor if possible
>
> The C ancestors implementation is about 10-100x faster than the Python
> lazyancestors implementation (and it has room to improve: 1. we only need
> isancestor, not common ancestor; 2. we can shrink revs[p:q] to a single
> ranged revision if all(revs[i].parentrevs() == [i-1] for i in range(p,q)),
> the state of known ranged revisions can be stored in the C index object).
>
> In the real world, the following command:
>
>   HGRCPATH=/dev/null hg log -f mercurial/c*.py -T '{rev}\n' > /dev/null
>
> Takes 2.3 to 2.5 seconds user-space CPU time before the patch,
>   and 1.7 to 1.9 after.

There is an history of introducing large performance regression while 
touching that code. That explain a bit its complexity, for example there 
is case were we carry the direct parent in _descendantrev and adjust 
linkrev as we go while there is some case where we just set the top most 
revision in _descendantrev and adjust link on demand much later. These 
serve different purposes for different top level use case.

The multiple cases we found should be available on the tracked and the 
changesets touching this should be quite well documented with for 
example details on the operation and repository used for timing. 
Unfortunatly as we do not have a formal benchmark suite, they have not 
been recorded more formally. I greatly recommend your dig all that out 
before proceeding (As you've already started doing so in your reply).
For example, the changeset you point out, 9372180b8c9b, is fixing an 
issue that was not visible on the Mercurial repository but was affecting 
the Mozilla repository dramatically.

It probably make sense to build a proper list of all problematic case, 
link them to benchmark and record timing for these operation on all 
milestone (pre-adjust, with-current-adjust, with-your-change). Having 
such list would help use being confident in the direction we will move in.


All this performance related work need also to be measure in term of 
impact of user of the pure code, including with pypy.

That said, Have you consider just writing a C version of the 
lazy-ancestors code? It would probably provide similar speed up while 
proving useful for many other part of the code.

> diff --git a/mercurial/context.py b/mercurial/context.py
> --- a/mercurial/context.py
> +++ b/mercurial/context.py
> @@ -838,9 +838,14 @@ class basefilectx(object):
>          else:
>              revs = [srcrev]
> +        # check if this linkrev is an ancestor of srcrev
>          if memberanc is None:
> -            memberanc = iteranc = cl.ancestors(revs, lkr,
> -                                               inclusive=inclusive)
> -        # check if this linkrev is an ancestor of srcrev
> -        if lkr not in memberanc:
> +            # cl.isancestor is backed by C code, faster than cl.ancestors
> +            if any(cl.isancestor(lkr, r) for r in revs):
> +                return lkr
> +        else:
> +            if lkr in memberanc:
> +                return lkr
> +        # fallback to walk through the changelog
> +        if True:
>              if iteranc is None:
>                  iteranc = cl.ancestors(revs, lkr, inclusive=inclusive)
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel at mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel

-- 
Pierre-Yves David