Re: Set up for better tree diff optimizations

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Mar 21, 2007, 18:21 UTC
Message-ID: <Pine.LNX.4.64.0703211110050.6730@woody.linux-foundation.org>
In-Reply-To: <7vslby1qvw.fsf@assigned-by-dhcp.cox.net>

On Wed, 21 Mar 2007, Junio C Hamano wrote:

> 
> As always, you are right and enlightened others with your
> superiour intelligence enough to produce code for you so that
> you do not have to write yourself ;-).

What can I say? It's a gift. I write _just_ enough code so that others get intrigued and encouraged to do the rest. Then I step in, and take all the glory.

> Would something like this suit your taste?

This looks fine, although the reason I didn't get it done myself is that I have this nagging feeling that there must be some clever way to make it even faster. I hated having to do the "strncmp()" early, when it's not always needed.

But like your patch, I could never come up with a way to *both* do the "don't strncmp() if you don't have to" *and* do the "nothing further will be interesting any more" optimization..

That said, your numbers are pretty convincing:

> The "rev-list org.eclipse.debug.ui/" test that took 16-17
> seconds takes 9 seconds with this patch.  Running with a
> diffrent pathspec "org.apache.ant/" obviously makes it go a lot
> faster (15sec vs 7sec).

Yeah, and conversely, a pathspec at the end of the list of paths will make it less of an optimization. But in general it shouldn't ever be a loss except for the rather rare case of asking for a path at the end of a tree, and then the loss should be pretty small (ie it's the result of doing a few strncmp's that we used to be able to skip).

Considering that the win on _average_ is in the 50% range (and your numbers back that up), it's definitely worth it.

		Linus