Re: Handling large files with GIT

[Linus Torvalds <torvalds@osdl.org>]

On Mon, 13 Feb 2006, Jeff Garzik wrote:
>
> Linus Torvalds wrote:
> > I've never used maildir layout, but if it is a couple of large _flat_
> > subdirectories,
> 
> That's what it is :/   One directory per mail folder, with each email an
> individual file in that dir.

Ok.

Anyway, I double-checked, and I'm wrong anyway. While the "static 
directories" thing is a huge performance optimization for doing many 
things (diffing trees, file history in git-rev-list, etc etc), for merging 
it doesn't help. We always end up expanding the whole tree.

Which is kind of sad.

It's inevitable in one sense: we do the merge in the index, after all, and 
the index - unlike the tree structures - is a flat file (like the 
"manifest" in mercurial or monotone). It's also represented that way in 
memory. 

However, it is a total and complete waste in other cases.

Thinking more about it, this is also why merging causes all the horrible 
index performance: not only do we (unnecessarily) read the same trees over 
and over again only to collapse them back to stage0 later when they are 
the same, but because we keep the index in a linear format, when we read 
the other trees, we'll have to move things around with memmove() (just the 
pointers, but still).

We'd actually be a _lot_ better off if we split "git-read-tree" up into 
two phases: one that did the recursive tree operation (which can optimize 
the "same tree everywhere" case), and the second stage that actually 
populated the index.

I'll have to think about this. It would be an absolutely _huge_ 
optimization for merging in certain patterns, it just doesn't matter for 
something like the kernel with "just" 18,000 files and not a lot of 
strange merging going on.

In contrast, I can see a mail archive easily having hundreds of thousands 
of individual emails. At which time it's horribly stupid to read them all 
in three times (for a merge - base, origin, new) and do so in a pretty 
inefficient manner.

Ho humm. It doesn't look _hard_ per se, and I think the two-stage 
git-read-tree is actually also what the recursive merge strategy wants 
anyway (it can't use the index - it really just wants to get a list of 
conflict information). So this definitely sounds like the RightThing(tm) 
to do anyway, and it fits the git data structures really well.

So no downsides. Except that this is some rather core code, and you can't 
afford to get it wrong. And the fact that I'm a lazy bastard, of course.

			Linus