From: Henrique Ferreiro <hferreiro@igalia.com>
Diffing the working tree against a commit with a pathspec can take time quadratic in the size of the index when the pathspec matches a subtree whose entries are the first entries of the index. Fix it by having next_cache_entry() record how far it scanned in cache_bottom, so repeated calls no longer rescan the growing prefix of already-unpacked entries. On a Chromium checkout (~500k index entries),
git diff HEAD -- .agents/OWNERS
took about 8 minutes before this change and 0.07 seconds after it. The same diff without the commit, without the pathspec, or with --cached was already instant.
Add p0009-diff-pathspec.sh, which builds a 100,000-entry index whose first path lives in a subtree, to guard against the regression. Comparing v2.55.0 with this change:
Test v2.55.0 HEAD ------------------------------------------------------------------------ 0009.2: diff pathspec subtree 7.16(7.12+0.01) 0.02(0.01+0.00) -99.7%
Signed-off-by: Henrique Ferreiro <hferreiro@igalia.com>
---
unpack-trees: avoid quadratic index scan in next_cache_entry()Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2353%2Fhferreiro%2Funpack-trees-quadratic-scan-v1 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2353/hferreiro/unpack-trees-quadratic-scan-v1 Pull-Request: https://github.com/git/git/pull/2353
t/perf/p0009-diff-pathspec.sh | 27 +++++++++++++++++++++++++++ unpack-trees.c | 4 +++- 2 files changed, 30 insertions(+), 1 deletion(-) create mode 100755 t/perf/p0009-diff-pathspec.sh
Show changes to 2 files +30 −1
t/perf/p0009-diff-pathspec.sh, unpack-trees.c
diff --git a/t/perf/p0009-diff-pathspec.sh b/t/perf/p0009-diff-pathspec.sh new file mode 100755 index 0000000000..0f1dccfbb4 --- /dev/null +++ b/t/perf/p0009-diff-pathspec.sh @@ -0,0 +1,27 @@ +#!/bin/sh + +test_description='Tests performance of diffing the working tree with a pathspec' + +. ./perf-lib.sh + +test_perf_fresh_repo + +# The entries exist only in the index, which is enough to +# exercise the index scan. +test_expect_success 'setup' ' + count=100000 && + blob=$(echo content | git hash-object -w --stdin) && + { + printf "100644 $blob\taaa/file\n" && + printf "100644 $blob\tf%s\n" $(test_seq $count) + } | git update-index --index-info && + git commit -q -m initial && + mkdir -p aaa && + echo content >aaa/file +' + +test_perf 'diff pathspec subtree' ' + git diff HEAD -- aaa/file +' + +test_done diff --git a/unpack-trees.c b/unpack-trees.c index b42020f16b..ed9fef453a 100644 --- a/unpack-trees.c +++ b/unpack-trees.c @@ -671,8 +671,10 @@ static struct cache_entry *next_cache_entry(struct unpack_trees_options *o) while (pos < index->cache_nr) { struct cache_entry *ce = index->cache[pos]; - if (!(ce->ce_flags & CE_UNPACKED)) + if (!(ce->ce_flags & CE_UNPACKED)) { + o->internal.cache_bottom = pos; return ce; + } pos++; } return NULL; base-commit: e9019fcafe0040228b8631c30f97ae1adb61bcdc
-- gitgitgadget