Re: Set up for better tree diff optimizations

Linus Torvalds [off-list ref] writes:

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

quoted

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

I briefly tried match[0] < path[0] as a compromise, but it did
not fly well with the eclipse example for obvious reasons ;-).

quoted

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

We _could_ check never_interesting first and if it is already
dropped then defer strncmp() and check the pathlen > matchlen
comparison first.