[PATCH] unpack-trees: fix accidentally quadratic behavior
- From
David Turner <dturner@twopensource.com>
- Date
- Jan 21, 2016, 04:05 UTC
- Message-ID
- <1453349156-12553-1-git-send-email-dturner@twopensource.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 <dturner@twopensource.com> --- 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