diff options
| author | David Turner <dturner@twopensource.com> | 2016-01-22 14:58:43 -0500 |
|---|---|---|
| committer | Junio C Hamano <gitster@pobox.com> | 2016-01-22 13:03:10 -0800 |
| commit | a6720955f19ea10bf9569d04480deed25b1bccf7 (patch) | |
| tree | a1278d3dd1d02f69605e3d123cca6929fa9462a5 | |
| parent | d9c2bd560e1e7a3d4654fb6ef3f9037ad337eb01 (diff) | |
| download | git-dt/unpack-compare-entry-optim.tar.gz | |
unpack-trees: fix accidentally quadratic behaviordt/unpack-compare-entry-optim
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>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
| -rw-r--r-- | unpack-trees.c | 13 |
1 files changed, 12 insertions, 1 deletions
diff --git a/unpack-trees.c b/unpack-trees.c index 5f541c28c6..9f55cc28b9 100644 --- a/unpack-trees.c +++ b/unpack-trees.c @@ -695,8 +695,19 @@ 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->traverse_path) { + if (strncmp(ce->name, info->traverse_path, + info->pathlen) > 0) + break; + } continue; + } ce_name = ce->name + pfxlen; ce_slash = strchr(ce_name, '/'); if (ce_slash) |