A thought for dealing with linkrevs

Matt Mackall mpm at selenic.com
Thu Sep 18 15:53:52 CDT 2014

On Thu, 2014-09-18 at 12:44 -0700, Pierre-Yves David wrote:
> On 09/17/2014 09:08 PM, Matt Mackall wrote:
> > So I've been thinking about the linkrev problem a bit again. I've
> > occasionally suggested we can deduce the possible positions of the
> > missing linkrevs from the shape of the changelog graph as compared to
> > the filelog graph. This turned out to be complicated so it never really
> > went anywhere.
> >
> > I'm now tinkering with the idea of treating the linkrev as a simple
> > hint: "this is one possibility, and any aliases are numerically after
> > it". So if we're interested in following the history of file F from
> > changeset C, we can say:
> >
> > - is F.linkrev an ancestor of C? great, done
> > - otherwise, let's look in that vicinity for changesets touching F
> >
> > Since the usual case for caring about this is log -f or annotate, which
> > incrementally walk back through file history, we can imagine a
> > "corrector" object that knows where we're following from and can correct
> > related linkrevs. We can even imagine this state being automatically
> > shared as we traverse contexts, thus making fctx.linkrev() magically do
> > the right thing.
> >
> > I tried hacking this up, and the below code will incrementally correct
> > all the linkrevs in the 2639 ancestors of mercurial/commands.py in
> > 0.13s, including fixing up a ton of obsolete linkrevs, which seems like
> > a pretty good start. There are probably a bunch of ways it could be
> > faster/smarter.
> This a pretty cool idea. I love how it provide a bounded solution 
> without too much complexity added. Do you have the timing without the 
> linkcorrector to get an idea of the slow down ?

.03s to simply follow the filelog and get linkrevs
.16s to do the above while correcting links

Compared to a full annotate, which is taking around 7s (including 1s of
parsing obsmarkers...), it's pretty manageable. The current version has
an O(revs) component, but it's still much faster than reading the entire

Mathematics is the supreme nostalgia of our time.

More information about the Mercurial-devel mailing list