# [PATCH v2] unpack-trees: fix accidentally quadratic behavior 3 messages from 2016-01-21 to 2016-01-21. Participants: David Turner, Jeff King. Thread: https://gitlist.dev/t/41237 ## David Turner, 2016-01-21 21:11 Subject: [PATCH v2] unpack-trees: fix accidentally quadratic behavior Message-ID: <1453410708-23951-1-git-send-email-dturner@twopensource.com> URL: https://gitlist.dev/e/1453410708-23951-1-git-send-email-dturner%40twopensource.com ``` 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 --- unpack-trees.c | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-) diff --git a/unpack-trees.c b/unpack-trees.c index 5f541c2..d8e9685 100644 --- a/unpack-trees.c +++ b/unpack-trees.c @@ -695,8 +695,19 @@ static int find_cache_pos(struct traverse_info *info, ++o->cache_bottom; continue; } - if (!ce_in_traverse_path(ce, info)) + if (!ce_in_traverse_path(ce, info)) { + /* + * Check if we can skip future cache checks + * (because we're already past all possible + * entries in the traverse path). + */ + if (info->prev && info->traverse_path) { + if (strncmp(ce->name, info->traverse_path, + info->pathlen) > 0) + break; + } continue; + } ce_name = ce->name + pfxlen; ce_slash = strchr(ce_name, '/'); if (ce_slash) -- 2.4.2.749.g730654d-twtrsrc ``` ## Jeff King, 2016-01-21 21:30 Subject: Re: [PATCH v2] unpack-trees: fix accidentally quadratic behavior Message-ID: <20160121213056.GA6664@sigill.intra.peff.net> URL: https://gitlist.dev/e/20160121213056.GA6664%40sigill.intra.peff.net In-Reply-To: <1453410708-23951-1-git-send-email-dturner@twopensource.com> ``` 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. 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? 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? I'm fairly ignorant of this part of the code, so there's probably a good reason why my suggestion is unworkable. -Peff ``` ## David Turner, 2016-01-21 23:24 Subject: Re: [PATCH v2] unpack-trees: fix accidentally quadratic behavior Message-ID: <1453418660.16226.53.camel@twopensource.com> URL: https://gitlist.dev/e/1453418660.16226.53.camel%40twopensource.com In-Reply-To: <20160121213056.GA6664@sigill.intra.peff.net> ``` On Thu, 2016-01-21 at 16:30 -0500, Jeff King wrote: > 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. > 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. > 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. ```