xrevlog: experimental reimplementation of revlog in C

Matt Mackall mpm at selenic.com
Wed Nov 10 21:29:57 CST 2010


On Wed, 2010-11-10 at 22:01 -0500, Greg Ward wrote:
> On Wed, Nov 10, 2010 at 4:14 PM, Matt Mackall <mpm at selenic.com> wrote:
> > This looks promising. I've speculated that the right way to fix this is
> > by making our parser C extension make an array-like class to replace
> > revlog.index. Not sure it's worth rewriting the rest of revlog in C
> > though.
> 
> My gut instinct says that the core of the problem is the list and dict
> storing the index in both directions: it takes time to parse the
> index, time to build those data structures, and memory to store them.

Well yes and no. Turns out the list building operations are reasonably
fast provided you do two things:

 - preallocate a list of the appropriate size
 - turn off recursive garbage collection on the list

The slowness is largely on the dict side. In particular, it's impossible
in Py2.x at least to preallocate a dict of a given size, so as you
insert 100k entries into a dict, it's going to be grown and rehashed
multiple times, so performance ends up being O(nlog n) with a big
constant factor rather than O(n) with a small one.

There's a second level of slowness that's incurred by having lazyparser
in there too.

> So I think that custom C data structure should serve both purposes.
> The interesting part is mapping node IDs to revnums, which I have
> avoided doing in xrevlog so far.  (Basically it needs a hashtable
> where the hash function is identity.  Seems silly to spend effort
> hashing SHA-1 hashes.)

Indeed. My vision is getting the whole index into memory, then providing
a set of accessors like parentrevs() to get at it without ever
completely unpacking it.

> As for rewriting the rest of revlog in C: oh well, I've gone and done
> it, and now it's out there.  It's ~800 lines plus a stripped down copy
> of your mpatch.c (~500 lines).  And so far it only supports looking up
> revs by revnum, not node ID.

You did the zlib bits too?

> Honestly, I really did this because 1) I wanted to understand revlog
> better and 2) it was a great excuse to learn about mmap().  Success on
> both counts.  I think I need to deal with lookups by node ID before we
> can see about adapting some/all of it into Mercurial.

Hmm, mmap(). Kernel hacker hat on: the conventional wisdom about mmap()
being the fast way to do things is about 15 years out of date. mmap
means mussing about with page tables to avoid copying data from kernel
space to user space, and on modern CPUs (read Pentium and later) that
actually turns out to be _slower than copying the pages in question_ due
to all the cache flushing that's involved in doing page table
manipulations. Worse, since you're not directing the I/O, you're much
more likely to get seeky I/O and miss read-ahead opportunities.

> Anyone know a good hashtable library for C?  ;-)

There's a thin hashtable implementation in bdiff.c that should be plenty
adequate. Hashes should be very nicely distributed, but you'll probably
still need 2n buckets to avoid excessive collisions. Fortunately, each
bucket can simply contain a pointer to the index entry, no need to store
the key in two places.

-- 
Mathematics is the supreme nostalgia of our time.




More information about the Mercurial-devel mailing list