Re: inotify daemon speedup for git [POC/HACK]

[Avery Pennarun <apenwarr@gmail.com>]

On Tue, Jul 27, 2010 at 8:00 PM, Shawn O. Pearce <spearce@spearce.org> wrote:
> Avery Pennarun <apenwarr@gmail.com> wrote:
>> While we're here, it's probably worth mentioning that git's index file
>> format (which stores a sequential list of full paths in alphabetical
>> order, instead of an actual hierarchy) does become a bottleneck when
>> you actually have a huge number of files in your repo (like literally
>> a million).  You can't actually binary search through the index!  The
>> current implementation of submodules allows you to dodge that
>> scalability problem since you end up with multiple smaller index
>> files.  Anyway, that's fixable too.
>
> Yes.
>
> More than once I've been tempted to rewrite the on-disk (and I guess
> in-memory) format of the index.  And then I remember how painful that
> stuff is in either C git.git or JGit, and I back away slowly.  :-)
>
> Ideally the index is organized the same way the trees are, but
> you still can't do a really good binary search because of the
> ass-backwards name sorting rule for trees.  But for performance
> reasons you still want to keep the entire index in a single file,
> an index per directory (aka SVN/CVS) is too slow for the common
> case of <30k files.

Really?  What's wrong with the name sorting rule?  I kind of like it.

bup's current index - after I abandoned my clone of the git one since
it was too slow with insane numbers of files - is very fast for reads
and in-place updates using mmap.

Essentially, it's a tree, starting from the outermost leafs and
leading toward the entry at the very end of the file, which is the
root.  (The idea of doing it backwards was that I could write the file
sequentially.  In retrospect, that was probably an unnecessarily
brain-bending waste of time and the root should have been the first
entry instead.)

For speed, the bup index can just mark entries as deleted using a flag
rather than actually rewriting the whole indexfile.  Unfortunately, I
failed to make it sufficiently flexible to *add* new entries without
needing to rewrite the whole thing.  In bup, that's a big deal
(especially since python is kind of slow and there are typically >1
million files in the index).  In git, it's maybe not so bad; after
all, the current implementation rewrites the index *every* time and
nobody notices.

Anyway, the code for it isn't too hairy, in case you want to steal some ideas:
http://github.com/apenwarr/bup/blob/master/lib/bup/index.py

(Disclaimer: I say this after actually spending a couple of late
nights pulling my hair out over it.  So I'm not so hairy anymore
either, but that doesn't prove much.)

I've considered just tossing the whole thing and using sqlite instead.
 Eventually I'll do it as a benchmark to see what happens.  My past
experiments with sqlite have demonstrated that its performance is
rather mind boggling (> 100k rows inserted per second as long as you
prepare() your SQL statements).  Reading from the index would be fast,
adding entries would be much faster than presently, but I'm not sure
about mass updates.  For bup sqlite would be okay, though I doubt git
wants to take on a whole sqlite dependency.  Then again, you never
know.

Have fun,

Avery