Re: git and larger trees, not so fast?

On Thu, 9 Aug 2007, Linus Torvalds wrote:

Gaah. This shouldn't be *that* hard to fix, but I'm not entirely sure I'll 
have time today.

In fact, I'm almost sure I will *not* have time today.

Anyway, the really trivial (and ugly) fix is to handle the cases of adding 
_independent_ stages to the index (which is the case for both "git 
diff-index" and "git read-tree -m") differently: instead of using the 
standard "add_index_entry()", which does all the complex sorting and 
checks that there aren't duplicates, we could do a much simpler one that 
just unconditionally appends to the end of the index.

This works, because when the stages are independent, there can be no index 
clashes (by definition).

Then, after adding all the stages, we could just do a "qsort()" on the 
result, and rather than having an expensive O(n**2) thing, we'd have a 
much nicer and well-behaved (with a smaller constant too) O(n*logn) thing.

I bet it's just ~50 lines of code, it really shouldn't be that hard to do. 
I just won't be able to do it and test it until late tonight or tomorrow, 
I suspect.

Sadly, this is an area that is almost exclusively mine and Junio's. I'd 
love for somebody else to get their feet wet, but doing a

	gitk read-cache.c

shows that few enough people have done anythign really fundamental in this 
file..

			Linus