Re: [PATCH] unpack-trees: fix accidentally quadratic behavior

[David Turner <dturner@twopensource.com>]

On Thu, 2016-01-21 at 11:51 -0800, Junio C Hamano wrote:
> David Turner <dturner@twopensource.com> writes:
> 
> > On Wed, 2016-01-20 at 20:58 -0800, Junio C Hamano wrote:
> > > David Turner <dturner@twopensource.com> writes:
> > > 
> > > > While unpacking trees (e.g. during git checkout), when we hit a
> > > > cache
> > > > entry that's past and outside our path, we cut off iteration.
> > > > 
> > > > This provides about a 45% speedup on git checkout between
> > > > master
> > > > and
> > > > master^20000 on Twitter's monorepo.  Speedup in general will
> > > > depend
> > > > on
> > > > repostitory structure, number of changes, and packfile packing
> > > > decisions.
> > > > 
> > > > Signed-off-by: David Turner <dturner@twopensource.com>
> > > > ---
> > > 
> > > I haven't thought things through, but does this get fooled by the
> > > somewhat strange ordering rules of tree entries (i.e. a subtree
> > > sorts as if its name is suffixed with a '/' in a tree object)?
> > > 
> > > Other than that, I like this.  "We know the list is sorted, and
> > > after seeing this entry we know there is nothing that will match"
> > > is
> > > an obvious optimization that we already use elsewhere.
> > > 
> > > Thanks.
> > 
> > I think this is correct, because we first do the more complicated
> > check
> > (ce_in_traverse_path), and only check the ordering once that has
> > failed.  
> 
> But the patch does this:
> 
> > +			if (info->prev && info->traverse_path) {
> > +				int prefix_cmp = strncmp(ce->name,
> > info->traverse_path, info->pathlen);
> > +				if (prefix_cmp > 0)
> > +					break;
> > +				else if (prefix_cmp == 0 &&
> > +					 ce_namelen(ce) >= info
> > ->pathlen &&
> > +					 strcmp(ce->name + info
> > ->pathlen,
> > +						 info->name.path)
> > > 0) {
> > +					break;
> > +				}
> > +			}
> >  			continue;
> 
> The first break is correct, but I am not sure about the "else if"
> part.  Shouldn't it be doing something similar to the logic to "keep
> looking" that talks about "t-i", "t" and "t/a" at the end of the
> loop?

Rather than doing more complicated logic, let's just do the first
check; it seems about as fast for our repo, and I think will usually be
so.  does that seem reasonable to you?

> > The tests all pass, so this should be good.
> 
> Please don't ever say that again.  

OK.