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

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

> +			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;