Re: git and larger trees, not so fast?

From: Junio C Hamano <gitster@pobox.com>
Date: Aug 9, 2007, 18:00 UTC
Message-ID: <7vr6mcy4dk.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <alpine.LFD.0.999.0708091015500.25146@woody.linux-foundation.org>

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

Show 8 quoted lines

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