Linus Torvalds <torvalds@linux-foundation.org> writes:

quoted text
> 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.

quoted text
> 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.


-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html