Windows people: please help check idea for a new Mercurial repository layout

[Matt Mackall]

On Sat, 2008-06-14 at 23:40 +0200, Dirkjan Ochtman wrote:
> Matt Mackall wrote:
> > Here are the repo layout requirements:
> > 
> > a) does not randomize disk layout (ie hashing)
> > b) avoids case collisions
> > c) uses only ASCII
> > d) handles stupidly long filenames
> > e) avoids filesystem quirks like reserved words and characters
> > f) mostly human-readable (optional)
> > g) reversible (optional)
> > 
> > (a) is important for performance. Filesystems are likely to store
> > sequentially created files in the same directory near each other on
> > disk. Disks and operating systems are likely to cache such data. Thus,
> > always reading and writing files in a consistent order gives the
> > operating system and hardware its best opportunity to optimize layout.
> > Ideally, the store layout should roughly mirror the working dir layout.
> 
> While the last point me be the ideal, it seems to me hashing might not 
> be that bad. We were talking about this with cmason in #mercurial, and 
> from that conversation it seemed to me that, as long as you walk the 
> repository in consistent order (order of creation), it shouldn't really 
> matter what order that is. So it could be some hash, and then you always 
> walk in the order of that hash, and that solves all our problems.

No, it doesn't. You have to think about both ends of the I/O operation.

Let's say you've cloned repo A, which gives you some set of files F that
get stored in random order. To checkout that set of files F, we can
either read them out of the repo in random (pessimal) order, or write
them out to the working directory in random (pessimal) order. In both
cases, we end up seeking like mad. The performance hit is around an
order of magnitude: not something to sneeze at.

(And that's on an FS without decent metadata read-ahead. The difference
will likely be more marked on something like cmason's btrfs.)

If we're clever, we can try reading every file out of the repo into
memory in hash order, then writing them out in directory order. Which
works just fine until you can't fit everything in memory. Then we
discover we weren't so clever after all and we're back to seeking like
mad, even if we're doing fairly large subsets. If our repo is 1G and
we're batching chunks of 100M, we probably still end up seeking over the
entire 1G of input space (or output space) to batch up each chunk.

Mercurial originally used a hashing scheme for its store 3 years ago and
as soon as I moved my Linux test repo from one partition to another,
performance suddenly went to hell because the sort order got pessimized
by rsync alphabetizing things. I tried all sorts of variations on
sorting, batching, etc., but none of them were even close in performance
to the current scheme, namely mirroring the working directory layout and
doing all operations in alphabetical order.

Further, simply cloning or cp'ing generally defragments things rather
than making them worse.

-- 
Mathematics is the supreme nostalgia of our time.