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

[Jun Wu]

Excerpts from Pierre-Yves David's message of 2016-11-02 00:29:45 +0100:
> 
> 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.

I'd prefer commenting on details directly. Things like "this is a complex
issue, you should try to do more homework before trying to solve it" are
useful to new people, while not very helpful to me, who had some experience
here. I think you can save your time by simplifying most part of this email
to:

  - Could you include runtime data for the Mozilla graft case?
  - Could you include runtime data for pure and pypy?
  - How do you think about a C implementation for lazyancestors?

> 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.

I think I fully understand what the current _adjustlinkrev code is doing and
why it is the form today.

Instead of running tests blindly, I'd like to measure things more
scientifically, like analyzing the code flow, the time complexity etc.
For this patch, if C code works, it should be faster in all cases. Reasons:

  - If _ancestrycontext exists, the code path is the same for both the new
    and the old code, so there should be no difference. This covers cases
    where copies.py sets _ancestrycontext explicitly.
  - If _ancestrycontext does not exist, "memberanc" will be created on the
    fly by "_adjustlinkrev" and dropped when returning. Therefore no state
    about which ancestor revisions are already visited is stored. It's
    walking from _descendantrev or self.rev each time. The C code is doing a
    same stateless thing but is 10-100x faster.

I can update the commit message to include the above reasons.

As I'm lacking of time, probably like everyone else here, I'd defend my time
to be used on something more meaningful (than unnecessary tests here). So I
can end up completing more things here, which is a good thing.

That said, pure / pypy is a valid concern. The problem is, is
"ancestor.commonancestorsheads" slower than "ancestor.lazyancestors"?
I will answer this question later.

> 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.

I was aware of issue4537 and issue4514 before writing the series. I did
run the commands commented by Mathias on issue4514.

> 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.

This is a valid concern.

> 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.

I had considered. It's not very compelling now because it is complex
(re-inventing heapq and memory management can be painful), requires extra
time to complete, while the current C code seems to be good enough even for
internal big repos.

I'd note that I think the C code may have room to improve. And if we are
going to add some "state" to speed up testing ancestors, I think it should
be done globally, i.e. on the C index object. So the state is private to the
C code and the Python code just calls index.isancestor, without knowing
about the details. As the changelog is shared globally and it may be a waste
of memory to have separated states for each fctx.
 
> > 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)
> > https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel 
>