Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx> 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. - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
