[patch 0/5] [PATCH CFT] more revlog experiments

[Matt Mackall]

On Sat, Mar 18, 2006 at 07:05:31PM -0500, Chris Mason wrote:
> Hello everyone,
> 
> Here's my latest set of revlog changes.  The index format has changed
> slightly from the last time (sorry, repos from my last patch won't be
> readable), and overall this one is faster.

This packing stuff is interesting, but I have some reservations.

Things that I've noticed:

a) breaks hg log foo.c (we no longer have file level indices)
b) breaks hg debugindex .hg/data/foo.c.i (poking around at the
   internals gets much harder)
c) introduces an arbitrarily large multiplier (files per directory)
   into all single file operations (like breaking a hardlink)
d) adds a bunch of new complexity to be performant

Point (c) is the worst, and it means it's hard to consider this scheme
as a default. And (d) means this will likely prove hard to maintain as
an option.

I'd really like to understand where the performance gains are coming
from. You've claimed it's mostly due to reducing seeks by reducing
filesystem metadata, but I'm a bit skeptical.

Considering the kernel repo, which has something like 17k files in
1.7k directories. This gives us an average 10 files per directory or
20 files in the hg repo (.i and .d). On ext3, inodes are 128 bytes by
default, so we can fit 32 in a 4k disk block. Similarly, assuming the
average filename is less than 100 bytes, we should have no problem
fitting a directory's worth of filenames in a single block of
directory data.

Assuming the operating system reads and caches inodes and
directory data at least a block at a time, we shouldn't see a huge
seek win here. And if we do, perhaps we can mitigate it by pre-opening
a directory's worth of files at checkout time. So what's going on?

As to space savings, this falls into three components:

a) block slop elimination

An average 4k per file (2k each for .i and .d). As history grows, this
overhead shrinks proportionally. 

b) metadata elimination

2 * (inode size + directory entry length) per file. But directory
entries are "free" for any directory that's not larger than 1 block
(which will be the norm). And inode size is typically 128-256 bytes.
So this whole category is relatively negligible compared to (a).

c) delta-parent optimization

I think the benchmarks showed this wasn't a huge win by itself and I
have some concerns about its worst-case seek behavior.


At any rate, I'd like to see the revlogng bits by themselves. That
part is uncontroversial and getting it in sooner means it can be made
the default sooner.

-- 
Mathematics is the supreme nostalgia of our time.