Re: [PATCH] unpack-trees: fix accidentally quadratic behavior
From: Junio C Hamano <hidden>
Date: 2016-06-15 23:07:50
David Turner [off-list ref] 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 <redacted> ---
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.
quoted hunk
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)