[PATCH] unpack-trees: avoid quadratic index scan in next_cache_entry()

["Henrique Ferreiro via GitGitGadget" <gitgitgadget@gmail.com>]

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

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