From: David Turner <dturner@twopensource.com>
Date: Thu, 21 Jan 2016 19:09:58 GMT
Subject: Re: [PATCH] unpack-trees: fix accidentally quadratic behavior
Message-ID: <1453403398.16226.40.camel@twopensource.com>
In-Reply-To: <xmqq60ynzfyq.fsf@gitster.mtv.corp.google.com>

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.  The tests all pass, so this should be good.