Re: git and larger trees, not so fast?

Linus Torvalds [off-list ref] writes:

So this is all O(n**2), which is why we haven't reacted very much - it 
doesn't show up nearly as much with the kernel. Also, with a smaller set 
of files, it would tends to fit in the L2 cache of most competent CPU's. 
So not only is it n**2, you get the cache trashing behaviour too, and 
that, I think, is what really causes it to fall off the cliff edge!

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

One thing to keep in mind is that in your earlier test of "git
write-tree" (or "git commit") followed by "git add a/file"
followed by "git write-tree" is extremely fast because the
last operation optimizes otherwise O(n) behaviour of write-tree
from index extreamely cheap, thanks to cache-tree in the index.

Diffing the index against the tree *should* be instantaneous.

Right now we do not cull the subdirectory that we _know_ are
unchanged in "git diff-index --cached" using cache-tree, but
diffing the index against the tree could be instantaneous.