[PATCH 2 of 2] [WIP] parsers: use base-16 trie for faster node->rev mapping

[Matt Mackall]

On Tue, 2012-03-27 at 22:23 -0400, Greg Ward wrote:
> On 27 March 2012, Matt Mackall said:
> > On Mon, 2012-03-26 at 21:34 -0400, Greg Ward wrote:
> > > Anyways, I got some results this time. I measured elapsed time and
> > > peak memory with 
> > > 
> > >   /usr/bin/time -f "%E s elapsed, %M kB max"
> > > 
> > > on each command. For each test, I ran it 5 times and reported the
> > > shortest runtime along with the peak memory from that run. (Sometimes
> > > that was the smallest peak memory, sometimes not. The variance in peak
> > > memory usage was pretty small though.)
> > 
> > Can you post the time for running 'hg version' as well as some repo
> > statistics?
> 
>   $ /usr/bin/time -f "%E s elapsed, %M kB max" ./hg version
>   Mercurial Distributed SCM (version 2.1.1+49-5854b39086d0)
>   (see http://mercurial.selenic.com for more information)
>   
>   Copyright (C) 2005-2012 Matt Mackall and others
>   This is free software; see the source for copying conditions. There is NO
>   warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
>   0:00.31 s elapsed, 6140 kB max
> 
> That's with both of Bryan's patches applied, not that it should matter.
> 
> I did mention this is an old, slow laptop, right? (1.4 GHz Pentium M,
> 1.5 GB of RAM, slow IDE disk. Software: Arch Linux, kernel
> 3.2.12-1-ARCH, glibc 2.15, python 2.7.2.)
> 
> Repo stats:
>   128k changesets
>    25k files in current checkout
>    45k files in all of history (hg manifest --all)
> 
>   repo size:
>     ~980 MB according to "du -sh .hg/store"
>     ~540 MB according to "tar -cf - .hg/store | wc -c"
>     ~270 MB of that is 00manifest.d
>             (I'm using generaldelta on newer clones, but haven't
> 	    gotten around to recloning everything)
> 
> > Also, please check out contrib/perf.py.
> 
> D'ohh! Forgot all about it. I have used it before, but blanked last
> night.
> 
> Here are some results:
> 
> perfheads:
>   unpatched: wall 0.120259 comb 0.120000 user 0.120000 sys 0.000000 (best of 76)
>   patched:   wall 0.241573 comb 0.240000 user 0.240000 sys 0.000000 (best of 41)

Yes, this is definitely slower, but turns out to be 2x faster when you
include the index load/parse time.

> perflog:
>   unpatched: wall 63.324580 comb 60.710000 user 59.600000 sys 1.110000 (best of 3)
>   patched:   wall 65.194923 comb 64.070000 user 63.040000 sys 1.030000 (best of 3)

Hmm, I get slightly faster log results.

> perfindex:
>   unpatched: wall 0.180053 comb 0.170000 user 0.150000 sys 0.020000 (best of 52)
>   patched:   wall 0.021411 comb 0.020000 user 0.000000 sys 0.020000 (best of 139)
> 
> perfrevlog .hg/store/00changelog.i:
>   unpatched: wall 0.609125 comb 0.610000 user 0.540000 sys 0.070000 (best of 14)
>   patched:   wall 0.276779 comb 0.290000 user 0.220000 sys 0.070000 (best of 36)
> 
> perfrevlog .hg/store/00manifest.i:
>   unpatched: wall 24.790400 comb 23.620000 user 21.070000 sys 2.550000 (best of 3)
>   patched:   wall 24.157500 comb 23.670000 user 21.220000 sys 2.450000 (best of 3)
> 
> And now, if you'll excuse me, the Committee for Prevention of Abuse to
> Elderly Laptops is banging on my front door. I'd better go answer it
> before the CPU fan on this thing melts.
> 
>         Greg


-- 
Mathematics is the supreme nostalgia of our time.