[WIP] lazy revlog index parsing

[Matt Mackall]

On Fri, 2012-03-16 at 22:10 -0400, Greg Ward wrote:
> On 14 March 2012, Bryan O'Sullivan said:
> > The current index parser is eager, and does a lot of unnecessary work on
> > large revlogs.
> > 
> > This causes e.g. "hg tip" to take 0.3 seconds on a repo that contains
> > 300,000 commits.
> 
> Argh, you beat me to it. I started hacking around on a readonly pure C
> revlog library as a vacation project a couple of summers ago. It
> stalled when I came back to the real world *sigh*. It's here, for the
> record:
> 
>   http://hg.gerg.ca/xrevlog/
> 
> The good stuff's in
> 
>   http://hg.gerg.ca/xrevlog/file/default/lib/revlog.c
> 
> And now I have to go read up on radix trees... geez it's hard to keep
> up around here. ;-)

For the record, Wikipedia's idea of what a radix tree is is completely
different than mine. Mine is more like this:

https://lwn.net/Articles/175432/

In other words, take a binary tree and make it 16-way. Then given a hash
prefix like "abcde", we do at most 5 steps before we find a tree leaf
node, discover it's not present, or discover it's ambiguous.

-- 
Mathematics is the supreme nostalgia of our time.