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

PATCH Superseded Henrique Ferreiro via GitGitGadget 3 participants 7 messages Jul 7 – Jul 8

lore

Share & tools

lore

Henrique Ferreiro via GitGitGadget

author

2026-07-07 21:01 UTC #0 lore raw

PATCH 1/1 unpack-trees: avoid quadratic index scan in next_cache_entry()

From: Henrique Ferreiro <[email protected]>

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 <[email protected]>

---
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

t/perf/p0009-diff-pathspec.sh new file +27 -0

new file mode 100755
index 0000000000..0f1dccfbb4
@@ -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

unpack-trees.c +3 -1

index b42020f16b..ed9fef453a 100644
@@ -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

Signature · 1 line

gitgitgadget

Junio C Hamano

2026-07-07 21:30 UTC #1 lore raw

"Henrique Ferreiro via GitGitGadget" <[email protected]>

Quoted 5 lines · writes:

unpack-trees.c +0 -0
index b42020f16b..ed9fef453a 100644

unpack-trees.c static struct cache_entry *next_cache_entry(struct unpack_trees_options *o) · line 678

Quoted 9 lines

unpack-trees.c +3 -1

@@ -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++;

Nice spotting.

Does this trick work correctly even when a path's sorting order differs between the index and tree objects, which is precisely why .cache_bottom was introduced, to allow backward scanning while bounding the lookback distance?

Quoted 12 lines

unpack-trees.c +0 -0
 	}
 	return NULL;
t/perf/p0009-diff-pathspec.sh new file +2 -0
new file mode 100755
index 0000000000..0f1dccfbb4
@@ -0,0 +1,27 @@
+#!/bin/sh
+

t/perf/p0009-diff-pathspec.sh line 12

Quoted 10 lines

t/perf/p0009-diff-pathspec.sh new file +10 -0

+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 &&

You will probably want to mimic how t/perf/p4209-pickaxe.sh helps testers by adjusting the count based on how the EXPENSIVE prerequisite is configured.

Quoted 5 lines

t/perf/p0009-diff-pathspec.sh new file +5 -0

+	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 &&

t/perf/p0009-diff-pathspec.sh line 27

Quoted 10 lines

t/perf/p0009-diff-pathspec.sh new file +10 -0

+	git commit -q -m initial &&
+	mkdir -p aaa &&
+	echo content >aaa/file
+'
+
+test_perf 'diff pathspec subtree' '
+	git diff HEAD -- aaa/file
+'
+
+test_done

Thanks.

Henrique Ferreiro

2026-07-08 18:31 UTC #2 lore raw

Quoted 19 lines · Junio C Hamano

"Henrique Ferreiro via GitGitGadget" <[email protected]>
Quoted 5 lines · writes:
unpack-trees.c +0 -0
index b42020f16b..ed9fef453a 100644
unpack-trees.c static struct cache_entry *next_cache_entry(struct unpack_trees_options *o) · line 678
Quoted 9 lines
unpack-trees.c +3 -1
@@ -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++;
Nice spotting.

Quoted 4 lines

Does this trick work correctly even when a path's sorting order differs between the index and tree objects, which is precisely why .cache_bottom was introduced, to allow backward scanning while bounding the lookback distance?

IIUC, .cache_bottom points at the first entry that needs to be processed. With this change, that still holds true even when entries are processed out of index order. find_cache_pos() also advances cache_bottom past unpacked entries since e53e6b4433 (unpack-trees: Make index lookahead less pessimal, 2010-06-10).

Quoted 42 lines

Quoted 12 lines
unpack-trees.c +0 -0
  	}
  	return NULL;
t/perf/p0009-diff-pathspec.sh new file +2 -0
new file mode 100755
index 0000000000..0f1dccfbb4
@@ -0,0 +1,27 @@
+#!/bin/sh
+
t/perf/p0009-diff-pathspec.sh line 12
Quoted 10 lines
t/perf/p0009-diff-pathspec.sh new file +10 -0
+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 &&
You will probably want to mimic how t/perf/p4209-pickaxe.sh helps testers by adjusting the count based on how the EXPENSIVE prerequisite is configured.
Quoted 5 lines
t/perf/p0009-diff-pathspec.sh new file +5 -0
+	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 &&
t/perf/p0009-diff-pathspec.sh line 27
Quoted 10 lines
t/perf/p0009-diff-pathspec.sh new file +10 -0
+	git commit -q -m initial &&
+	mkdir -p aaa &&
+	echo content >aaa/file
+'
+
+test_perf 'diff pathspec subtree' '
+	git diff HEAD -- aaa/file
+'
+
+test_done
Thanks.

Junio C Hamano

2026-07-08 19:16 UTC #3 lore raw

Quoted 25 lines · Henrique Ferreiro

Quoted 19 lines · Junio C Hamano
"Henrique Ferreiro via GitGitGadget" <[email protected]>
Quoted 5 lines · writes:
unpack-trees.c +0 -0
index b42020f16b..ed9fef453a 100644
unpack-trees.c static struct cache_entry *next_cache_entry(struct unpack_trees_options *o) · line 678
Quoted 9 lines
unpack-trees.c +3 -1
@@ -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++;
Nice spotting.
Quoted 4 lines
Does this trick work correctly even when a path's sorting order differs between the index and tree objects, which is precisely why .cache_bottom was introduced, to allow backward scanning while bounding the lookback distance?

Quoted 5 lines

IIUC, .cache_bottom points at the first entry that needs to be processed. With this change, that still holds true even when entries are processed out of index order. find_cache_pos() also advances cache_bottom past unpacked entries since e53e6b4433 (unpack-trees: Make index lookahead less pessimal, 2010-06-10).

That sounds sensible.

Quoted 14 lines

t/perf/p0009-diff-pathspec.sh new file +8 -0

new file mode 100755
index 0000000000..0f1dccfbb4
@@ -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
+

Quoted 8 lines

Quoted 8 lines
t/perf/p0009-diff-pathspec.sh line 12
Quoted 4 lines
t/perf/p0009-diff-pathspec.sh new file +4 -0
+# The entries exist only in the index, which is enough to
+# exercise the index scan.
+test_expect_success 'setup' '
+	count=100000 &&
You will probably want to mimic how t/perf/p4209-pickaxe.sh helps testers by adjusting the count based on how the EXPENSIVE prerequisite is configured.

I think this comment still needs addressing, though.

Thanks.

Quoted 9 lines

t/perf/p0009-diff-pathspec.sh new file +9 -0

+	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
+'

Henrique Ferreiro

2026-07-08 21:40 UTC #4 lore raw

Quoted 54 lines · Junio C Hamano

Quoted 24 lines · Henrique Ferreiro
Quoted 19 lines · Junio C Hamano
"Henrique Ferreiro via GitGitGadget" <[email protected]>
Quoted 5 lines · writes:
unpack-trees.c +0 -0
index b42020f16b..ed9fef453a 100644
unpack-trees.c static struct cache_entry *next_cache_entry(struct unpack_trees_options *o) · line 678
Quoted 9 lines
unpack-trees.c +3 -1
@@ -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++;
Nice spotting.
Quoted 4 lines
Does this trick work correctly even when a path's sorting order differs between the index and tree objects, which is precisely why .cache_bottom was introduced, to allow backward scanning while bounding the lookback distance?
Quoted 5 lines
IIUC, .cache_bottom points at the first entry that needs to be processed. With this change, that still holds true even when entries are processed out of index order. find_cache_pos() also advances cache_bottom past unpacked entries since e53e6b4433 (unpack-trees: Make index lookahead less pessimal, 2010-06-10).
That sounds sensible.
Quoted 13 lines
Quoted 13 lines
Quoted 13 lines
t/perf/p0009-diff-pathspec.sh new file +7 -0
new file mode 100755
index 0000000000..0f1dccfbb4
@@ -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
Quoted 8 lines
Quoted 8 lines
t/perf/p0009-diff-pathspec.sh line 12
Quoted 5 lines
t/perf/p0009-diff-pathspec.sh new file +5 -0
+
+# The entries exist only in the index, which is enough to
+# exercise the index scan.
+test_expect_success 'setup' '
+	count=100000 &&
You will probably want to mimic how t/perf/p4209-pickaxe.sh helps testers by adjusting the count based on how the EXPENSIVE prerequisite is configured.

Quoted 3 lines

I think this comment still needs addressing, though.
Thanks.

Sure. I've just sent v2 with those changes. Note that I used an initial count of 1000, otherwise the improvement is not noticeable.

Quoted 9 lines

t/perf/p0009-diff-pathspec.sh new file +9 -0

+	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
+'

Henrique Ferreiro via GitGitGadget

author

2026-07-08 21:42 UTC #5 lore raw

PATCH v2 1/1 unpack-trees: avoid quadratic index scan in next_cache_entry()

In reply to Henrique Ferreiro via GitGitGadget

From: Henrique Ferreiro <[email protected]>

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 10,000-entry index whose first path lives in a subtree (100,000 entries under --long-tests), to guard against the regression. Comparing v2.55.0 with this change using GIT_TEST_LONG=t:

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 <[email protected]>

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

Changes since v1: adjust the synthetic index size based on the EXPENSIVE prerequisite.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2353%2Fhferreiro%2Funpack-trees-quadratic-scan-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2353/hferreiro/unpack-trees-quadratic-scan-v2
Pull-Request: https://github.com/git/git/pull/2353

Range-diff vs v1:

1: cc1aaf01cf ! 1: c8f1ca389d unpack-trees: avoid quadratic index scan in next_cache_entry()
@@ Commit message
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:
+ Add p0009-diff-pathspec.sh, which builds a 10,000-entry index whose
+ first path lives in a subtree (100,000 entries under --long-tests),
+ to guard against the regression. Comparing v2.55.0 with this change
+ using GIT_TEST_LONG=t:

Test v2.55.0 HEAD
------------------------------------------------------------------------
@@ t/perf/p0009-diff-pathspec.sh (new)
+
+test_perf_fresh_repo
+
++count=10000
++if test_have_prereq EXPENSIVE
++then
++ count=100000
++fi
++
+# 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" &&

 t/perf/p0009-diff-pathspec.sh | 32 ++++++++++++++++++++++++++++++++
 unpack-trees.c                |  4 +++-
 2 files changed, 35 insertions(+), 1 deletion(-)
 create mode 100755 t/perf/p0009-diff-pathspec.sh

t/perf/p0009-diff-pathspec.sh new file +32 -0

new file mode 100755
index 0000000000..6079db52c2
@@ -0,0 +1,32 @@
+#!/bin/sh
+
+test_description='Tests performance of diffing the working tree with a pathspec'
+
+. ./perf-lib.sh
+
+test_perf_fresh_repo
+
+count=10000
+if test_have_prereq EXPENSIVE
+then
+	count=100000
+fi
+
+# The entries exist only in the index, which is enough to
+# exercise the index scan.
+test_expect_success 'setup' '
+	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

unpack-trees.c +3 -1

index b42020f16b..ed9fef453a 100644
@@ -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

Signature · 1 line

gitgitgadget

Junio C Hamano

2026-07-08 21:58 UTC #6 lore raw

"Henrique Ferreiro via GitGitGadget" <[email protected]>

Quoted 25 lines · writes:

From: Henrique Ferreiro <[email protected]>
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 10,000-entry index whose first path lives in a subtree (100,000 entries under --long-tests), to guard against the regression. Comparing v2.55.0 with this change using GIT_TEST_LONG=t:
Test v2.55.0 HEAD
------------------------------------------------------------------------
0009.2: diff pathspec subtree 7.16(7.12+0.01) 0.02(0.01+0.00) -99.7%

Quoted 6 lines

Signed-off-by Henrique Ferreiro <[email protected]>
---
unpack-trees: avoid quadratic index scan in next_cache_entry()
Changes since v1: adjust the synthetic index size based on the EXPENSIVE prerequisite.

Thanks.