threads / patch / 41232

patchunpack-trees: fix accidentally quadratic behavior

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

## tl;dr

6 messages between Jan 21, 2016 and Jan 21, 2016. Diffs are folded; open one to read it.

replies: 5people: 2as markdown or json

David Turner· Jan 21, 2016, 04:05 UTC · lore

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>
---
 unpack-trees.c | 19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)
Show changes to unpack-trees.c +18 −1
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· Jan 21, 2016, 04:58 UTC · re: David Turner · lore

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

David Turner <dturner@twopensource.com> writes:
Show 10 quoted lines
> 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.
Show 34 quoted lines
>  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· Jan 21, 2016, 19:09 UTC · re: Junio C Hamano · lore

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

On Wed, 2016-01-20 at 20:58 -0800, Junio C Hamano wrote:
Show 25 quoted lines
> 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.

Junio C Hamano· Jan 21, 2016, 19:51 UTC · re: David Turner · lore

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

David Turner <dturner@twopensource.com> writes:
Show 30 quoted lines
> 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.  
But the patch does this:
Show 12 quoted lines
> +			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· Jan 21, 2016, 20:59 UTC · re: Junio C Hamano · lore

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

On Thu, 2016-01-21 at 11:51 -0800, Junio C Hamano wrote:
Show 60 quoted lines
> David Turner <dturner@twopensource.com> writes:
> 
> > 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.  
> 
> 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· Jan 21, 2016, 21:06 UTC · re: David Turner · lore

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

David Turner <dturner@twopensource.com> writes:
Show 8 quoted lines
>> 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.

← back to recent threads