Re: git and larger trees, not so fast?

On Thu, 9 Aug 2007, Linus Torvalds wrote:

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