Re: [PATCH] unpack-trees: fix accidentally quadratic behavior
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Jan 21, 2016, 04:58 UTC
- Message-ID
- <xmqq60ynzfyq.fsf@gitster.mtv.corp.google.com>
- In-Reply-To
- <1453349156-12553-1-git-send-email-dturner@twopensource.com>
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)