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

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

[Henrique Ferreiro via GitGitGadget]

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

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

[Junio C Hamano]

"Henrique Ferreiro via GitGitGadget" <gitgitgadget@gmail.com>
writes:

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

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?

>  	}
>  	return NULL;


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

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.

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

Thanks.

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

[Henrique Ferreiro]

On 07/07/2026 23:30, Junio C Hamano wrote:
> "Henrique Ferreiro via GitGitGadget" <gitgitgadget@gmail.com>
> writes:
>
>> 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++;
> 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?
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).
>
>>   	}
>>   	return NULL;
>
>> 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 &&
> 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.
>
>> +	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
> Thanks.

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

[Junio C Hamano]

Henrique Ferreiro <hferreiro@igalia.com> writes:

> On 07/07/2026 23:30, Junio C Hamano wrote:
>> "Henrique Ferreiro via GitGitGadget" <gitgitgadget@gmail.com>
>> writes:
>>
>>> 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++;
>> 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?

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

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

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

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

[Henrique Ferreiro]

On 08/07/2026 21:16, Junio C Hamano wrote:
> Henrique Ferreiro <hferreiro@igalia.com> writes:
>
>> On 07/07/2026 23:30, Junio C Hamano wrote:
>>> "Henrique Ferreiro via GitGitGadget" <gitgitgadget@gmail.com>
>>> writes:
>>>
>>>> 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++;
>>> 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?
>> 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.
>
>>>> 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 &&
>>> 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.

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


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

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

[Henrique Ferreiro via GitGitGadget]

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 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 <hferreiro@igalia.com>
---
    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

diff --git a/t/perf/p0009-diff-pathspec.sh b/t/perf/p0009-diff-pathspec.sh
new file mode 100755
index 0000000000..6079db52c2
--- /dev/null
+++ b/t/perf/p0009-diff-pathspec.sh
@@ -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
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

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

[Junio C Hamano]

"Henrique Ferreiro via GitGitGadget" <gitgitgadget@gmail.com>
writes:

> 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 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 <hferreiro@igalia.com>
> ---
>     unpack-trees: avoid quadratic index scan in next_cache_entry()
>     
>     Changes since v1: adjust the synthetic index size based on the EXPENSIVE
>     prerequisite.

Thanks.