[PATCH 1 of 7] ancestors: actually iterate over ancestors in topological order (issue5979)

[Yuya Nishihara]

On Sun, 9 Sep 2018 23:36:15 -0700, Martin von Zweigbergk via Mercurial-devel wrote:
> On Fri, Sep 7, 2018 at 8:08 AM Boris Feld <boris.feld at octobus.net> wrote:
> > # HG changeset patch
> > # User Boris Feld <boris.feld at octobus.net>
> > # Date 1536267628 14400
> > #      Thu Sep 06 17:00:28 2018 -0400
> > # Node ID eb80c721aea9715e23dc35cdd119428aa120ea93
> > # Parent  ab452995eafffa69c34e863e4d8c03e163d8f3ad
> > # EXP-Topic issue5979
> > # Available At https://bitbucket.org/octobus/mercurial-devel/
> > #              hg pull https://bitbucket.org/octobus/mercurial-devel/ -r
> > eb80c721aea9
> > ancestors: actually iterate over ancestors in topological order (issue5979)
> >
> > This code previously used a dequeue logic, the first ancestors seen were
> > the
> > first ancestors to be emitted. In branching/merging situations, it can
> > result
> > in ancestors being yielded before their descendants, breaking the object
> > contract.
> >
> > We got affected by this issue while working on the copy tracing code. At
> > about
> > the same time, Axel Hecht <axel at mozilla.com> reported the issue and
> > provided
> > the test case used in this changeset. Thanks Axel.
> >
> > Running `hg perfancestors` does not show a significant difference between
> > the
> > old and the new version.
> >
> 
> In my hg repo, it went from 0.047230 to 0.093331, which is clearly
> significant. Maybe you made a last-minute change that made it slower? Or is
> my repo just different from yours?

I got a similar result. The heapq version is ~2x slower than the original
buggy implementation. It seems I made it to 1-1.5x slowness by optimizing
out heappush/heappop for contiguous cases (i.e. overwrite visit[0] if p1
is known to be the next largest revision.) I'll send the patches if I can
be sure that's correct.