# [PATCH] unpack-trees: fix accidentally quadratic behavior 6 messages from 2016-01-21 to 2016-01-21. Participants: David Turner, Junio C Hamano. Thread: https://gitlist.dev/t/41232 ## David Turner, 2016-01-21 04:05 Subject: [PATCH] unpack-trees: fix accidentally quadratic behavior Message-ID: <1453349156-12553-1-git-send-email-dturner@twopensource.com> URL: https://gitlist.dev/e/1453349156-12553-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 | 19 ++++++++++++++++++- 1 file changed, 18 insertions(+), 1 deletion(-) diff --git a/unpack-trees.c b/unpack-trees.c index 5f541c2..b18a611 100644 --- a/unpack-trees.c +++ b/unpack-trees.c @@ -695,8 +695,25 @@ 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) { + 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; + } ce_name = ce->name + pfxlen; ce_slash = strchr(ce_name, '/'); if (ce_slash) -- 2.4.2.749.g730654d-twtrsrc ``` ## Junio C Hamano, 2016-01-21 04:58 Subject: Re: [PATCH] unpack-trees: fix accidentally quadratic behavior Message-ID: URL: https://gitlist.dev/e/xmqq60ynzfyq.fsf%40gitster.mtv.corp.google.com In-Reply-To: <1453349156-12553-1-git-send-email-dturner@twopensource.com> ``` David Turner 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 > --- 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. > unpack-trees.c | 19 ++++++++++++++++++- > 1 file changed, 18 insertions(+), 1 deletion(-) > > diff --git a/unpack-trees.c b/unpack-trees.c > index 5f541c2..b18a611 100644 > --- a/unpack-trees.c > +++ b/unpack-trees.c > @@ -695,8 +695,25 @@ 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) { > + 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; > + } > ce_name = ce->name + pfxlen; > ce_slash = strchr(ce_name, '/'); > if (ce_slash) ``` ## David Turner, 2016-01-21 19:09 Subject: Re: [PATCH] unpack-trees: fix accidentally quadratic behavior Message-ID: <1453403398.16226.40.camel@twopensource.com> URL: https://gitlist.dev/e/1453403398.16226.40.camel%40twopensource.com In-Reply-To: ``` On Wed, 2016-01-20 at 20:58 -0800, Junio C Hamano wrote: > David Turner 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 > > --- > > 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. ``` ## Junio C Hamano, 2016-01-21 19:51 Subject: Re: [PATCH] unpack-trees: fix accidentally quadratic behavior Message-ID: URL: https://gitlist.dev/e/xmqqpowuyall.fsf%40gitster.mtv.corp.google.com In-Reply-To: <1453403398.16226.40.camel@twopensource.com> ``` David Turner writes: > On Wed, 2016-01-20 at 20:58 -0800, Junio C Hamano wrote: >> David Turner 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 >> > --- >> >> 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? > The tests all pass, so this should be good. Please don't ever say that again. The existing tests do not cover all corner cases, and they fundamentally cannot cover the corner cases future changes may introduce. Saying "Even test X breaks, so it is clearly broken. Why did you send it out without testing?" is OK, though. ``` ## David Turner, 2016-01-21 20:59 Subject: Re: [PATCH] unpack-trees: fix accidentally quadratic behavior Message-ID: <1453409984.16226.46.camel@twopensource.com> URL: https://gitlist.dev/e/1453409984.16226.46.camel%40twopensource.com In-Reply-To: ``` On Thu, 2016-01-21 at 11:51 -0800, Junio C Hamano wrote: > David Turner writes: > > > On Wed, 2016-01-20 at 20:58 -0800, Junio C Hamano wrote: > > > David Turner 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 > > > > --- > > > > > > 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. ``` ## Junio C Hamano, 2016-01-21 21:06 Subject: Re: [PATCH] unpack-trees: fix accidentally quadratic behavior Message-ID: URL: https://gitlist.dev/e/xmqqbn8ey75h.fsf%40gitster.mtv.corp.google.com In-Reply-To: <1453409984.16226.46.camel@twopensource.com> ``` David Turner writes: >> 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? Very reasonable. I was mostly afraid of leaving the loop prematurely and giving a wrong answer to the caller. ```