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

From: David Turner <dturner@twopensource.com>
Date: Jan 21, 2016, 23:24 UTC
Message-ID: <1453418660.16226.53.camel@twopensource.com>
In-Reply-To: <20160121213056.GA6664@sigill.intra.peff.net>

On Thu, 2016-01-21 at 16:30 -0500, Jeff King wrote:

Show 24 quoted lines

> On Thu, Jan 21, 2016 at 04:11:48PM -0500, David Turner wrote:
> 
> > 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.
> 
> I feel like I'm missing the explanation of the quadratic part. From
> looking at the patch, my guess is:
> 
>   1. We're doing a linear walk in a data structure (a "struct
>      index_state").
> 
>   2. For each element, we look it up in another structure
>      ("struct traverse_info") with a linear search.
> 
>      That leaves us at O(m*n), but if we assume both are on the same
>      order of magnitude, that's quadratic.

No, I think, it's the opposite order: we're doing a linear walk over the incoming tree and for each entry, we're calling find_cache_pos. find_cache_pos was doing a linear walk over struct index_state. But the same algorithmic complexity holds.

Show 7 quoted lines

>   3. The fix works by knowing that once a lookup in (2) fails once,
> it's
>      likely to fail for all the remainder, and we short-cut that case
>      and skip out of (1) completely.
> 
> But that makes me wonder. Aren't we still quadratic in the case that
> ce_in_traverse_path() returns true?

I think that doesn't happen very often, because it requires that the paths match up.

Show 9 quoted lines

> If so, would we benefit from either:
> 
>   a. Improving the complexity of ce_in_traverse_path, to say O(log
> n),
>      which would give us O(n log n) for the whole operation in all
>      cases?
> 
>   b. If both lists are already sorted, maybe doing a list-merge to
>      compare them in O(2n) time?

(b) appears to be now (roughly) what we're now doing.

> I'm fairly ignorant of this part of the code, so there's probably a
> good
> reason why my suggestion is unworkable.

I am also quite ignorant of this part of the code; I just looked at perf and did some simple counting.