Skip to content

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

Open
hferreiro wants to merge 1 commit into
git:masterfrom
hferreiro:unpack-trees-quadratic-scan
Open

unpack-trees: avoid quadratic index scan in next_cache_entry()#2353
hferreiro wants to merge 1 commit into
git:masterfrom
hferreiro:unpack-trees-quadratic-scan

Conversation

@hferreiro

@hferreiro hferreiro commented Jul 7, 2026

Copy link
Copy Markdown

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

cc: Henrique Ferreiro hferreiro@igalia.com

@hferreiro

Copy link
Copy Markdown
Author

/preview

@gitgitgadget-git

Copy link
Copy Markdown

Preview email sent as pull.2353.git.git.1783457006207.gitgitgadget@gmail.com

@hferreiro

Copy link
Copy Markdown
Author

/submit

@gitgitgadget-git

Copy link
Copy Markdown

Submitted as pull.2353.git.git.1783458106037.gitgitgadget@gmail.com

To fetch this version into FETCH_HEAD:

git fetch https://github.com/gitgitgadget/git/ pr-git-2353/hferreiro/unpack-trees-quadratic-scan-v1

To fetch this version to local tag pr-git-2353/hferreiro/unpack-trees-quadratic-scan-v1:

git fetch --no-tags https://github.com/gitgitgadget/git/ tag pr-git-2353/hferreiro/unpack-trees-quadratic-scan-v1

@gitgitgadget-git

Copy link
Copy Markdown

Junio C Hamano wrote on the Git mailing list (how to reply to this email):

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

@gitgitgadget-git

Copy link
Copy Markdown

Henrique Ferreiro wrote on the Git mailing list (how to reply to this email):

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.

@gitgitgadget-git

Copy link
Copy Markdown

User Henrique Ferreiro <hferreiro@igalia.com> has been added to the cc: list.

@gitgitgadget-git

Copy link
Copy Markdown

Junio C Hamano wrote on the Git mailing list (how to reply to this email):

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

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>
@hferreiro hferreiro force-pushed the unpack-trees-quadratic-scan branch from cc1aaf0 to c8f1ca3 Compare July 8, 2026 21:36
@hferreiro

Copy link
Copy Markdown
Author

/preview

@gitgitgadget-git

Copy link
Copy Markdown

Preview email sent as pull.2353.v2.git.git.1783546738840.gitgitgadget@gmail.com

@hferreiro

Copy link
Copy Markdown
Author

/submit

@gitgitgadget-git

Copy link
Copy Markdown

Submitted as pull.2353.v2.git.git.1783546933992.gitgitgadget@gmail.com

To fetch this version into FETCH_HEAD:

git fetch https://github.com/gitgitgadget/git/ pr-git-2353/hferreiro/unpack-trees-quadratic-scan-v2

To fetch this version to local tag pr-git-2353/hferreiro/unpack-trees-quadratic-scan-v2:

git fetch --no-tags https://github.com/gitgitgadget/git/ tag pr-git-2353/hferreiro/unpack-trees-quadratic-scan-v2

@gitgitgadget-git

Copy link
Copy Markdown

Henrique Ferreiro wrote on the Git mailing list (how to reply to this email):

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

@gitgitgadget-git

Copy link
Copy Markdown

Junio C Hamano wrote on the Git mailing list (how to reply to this email):

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

@gitgitgadget-git

Copy link
Copy Markdown

This branch is now known as hf/unpack-trees-quadratic-scan.

@gitgitgadget-git

Copy link
Copy Markdown

This patch series was integrated into seen via 29bf20e.

@gitgitgadget-git gitgitgadget-git Bot added the seen label Jul 9, 2026
@gitgitgadget-git

Copy link
Copy Markdown

There was a status update in the "New Topics" section about the branch hf/unpack-trees-quadratic-scan on the Git mailing list:

The cache-scanning loop in 'next_cache_entry()' has been optimized
to avoid rescanning already-unpacked index entries, preventing a
quadratic performance slow-down when diffing the working tree
against a commit with a pathspec matching early index entries.

Will merge to 'next'?
cf. <xmqqpl0xqh3n.fsf@gitster.g>
source: <pull.2353.v2.git.git.1783546933992.gitgitgadget@gmail.com>

@abhisharma30 abhisharma30 left a comment

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Review summary

Thanks for the clear diagnosis and the huge win (Chromium-scale index: minutes → tens of ms). I walked next_cache_entry() / mark_ce_used() / switch_cache_bottom / restore_cache_bottom and the leftover drain loop, and also had a second pass focused on the perf test.

Verdict: looks correct and ready to land (matches Junio’s “sounds sensible” / “Will merge to 'next'?” thread). Residual notes below are non-blocking.

Algorithm

The quadratic path is real:

  1. Pathspec-limited tree walk + switch_cache_bottom / restore_cache_bottom rewinds cache_bottom onto already-CE_UNPACKED early entries (non---cached only — matches the “--cached was already fast” claim).
  2. mark_ce_used() only advances cache_bottom when the marked entry is cache[cache_bottom].
  3. The leftover loop then calls next_cache_entry() for each remaining index entry; without recording progress, each call rescans a growing unpacked prefix → O(n²).

Setting o->internal.cache_bottom = pos when returning the first non-unpacked entry restores the invariant “bottom is a safe restart point for the next scan” and is consistent with how find_cache_pos() already slides the bottom past unpacked entries. Tree-vs-index order (Junio’s question) is handled: out-of-order marks leave holes, but the first not-yet-unpacked entry at/after the previous bottom is still the correct resume point.

Historical note worth remembering

cache_bottom has been correctness-sensitive before (f2a454e0a5 / 99430aa12c sparse-index history). This change is small and in the right direction, but it is not “just a micro-optim”. Existing ambient sparse/pathspec tests don’t construct this exact layout; the new perf script is the primary guard.

Process

Already in seen as hf/unpack-trees-quadratic-scan. EXPENSIVE sizing feedback from v1 is addressed in v2.

fi

# The entries exist only in the index, which is enough to
# exercise the index scan.

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

[nit] Comment says entries “exist only in the index”, but the setup git commits them into HEAD as well. Only the worktree is sparse (only aaa/file is checked out). The bulk f* paths still live in the tree + index.

Suggest rephrasing, e.g. that the bulk of the index need not be present in the worktree; what this exercises is the leftover index scan after a pathspec-limited tree walk (the non---cached restore_cache_bottom path).

if test_have_prereq EXPENSIVE
then
count=100000
fi

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

[suggestion] Default count=10000 (100k only under EXPENSIVE) may be a soft signal on noisy machines — O(n²) means 10k is ~100× less work than the 100k numbers in the commit message (~7s → 0.02s).

Not blocking. Optional: bump default a bit, or one-line note in the test description that a clear before/after wants --long-tests / GIT_TEST_LONG=t. The EXPENSIVE split itself is the right pattern (same as p4209-pickaxe.sh).

Comment thread unpack-trees.c
struct cache_entry *ce = index->cache[pos];
if (!(ce->ce_flags & CE_UNPACKED))
if (!(ce->ce_flags & CE_UNPACKED)) {
o->internal.cache_bottom = pos;

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

[nit / optional] When the scan exhausts and returns NULL, cache_bottom is left pointing at the last examined region rather than cache_nr. A subsequent next_cache_entry() would rescan the fully-unpacked prefix again (still O(n) once, not quadratic in the usual leftover-loop pattern).

Not required for this fix — after the leftover loop finishes, mark_all_ce_unused() clears state. Only worth considering if you want the “bottom is past all unpacked” invariant to hold on the empty return as well:

o->internal.cache_bottom = index->cache_nr;
return NULL;

Comment thread unpack-trees.c
if (!(ce->ce_flags & CE_UNPACKED))
if (!(ce->ce_flags & CE_UNPACKED)) {
o->internal.cache_bottom = pos;
return ce;

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

[suggestion — coverage, non-blocking] Pure perf bug ⇒ no functional test that fails without the fix is expected. Given past cache_bottom/sparse correctness churn, a tiny functional case (dir-first path + a few later siblings, git diff HEAD -- aaa/file output check, optionally sparse-index) would be a cheap safety net that “wrong but fast” cannot hide behind p0009 alone.

I would not block landing on that; the algorithm change is small and the perf shape is well chosen.

@gitgitgadget-git

Copy link
Copy Markdown

This patch series was integrated into next via 744f1ae.

@gitgitgadget-git

Copy link
Copy Markdown

There was a status update in the "Cooking" section about the branch hf/unpack-trees-quadratic-scan on the Git mailing list:

The cache-scanning loop in 'next_cache_entry()' has been optimized
to avoid rescanning already-unpacked index entries, preventing a
quadratic performance slow-down when diffing the working tree
against a commit with a pathspec matching early index entries.

Will merge to 'master'.
cf. <xmqqpl0xqh3n.fsf@gitster.g>
source: <pull.2353.v2.git.git.1783546933992.gitgitgadget@gmail.com>

@gitgitgadget-git

Copy link
Copy Markdown

There was a status update in the "Cooking" section about the branch hf/unpack-trees-quadratic-scan on the Git mailing list:

The cache-scanning loop in 'next_cache_entry()' has been optimized
to avoid rescanning already-unpacked index entries, preventing a
quadratic performance slow-down when diffing the working tree
against a commit with a pathspec matching early index entries.

Will merge to 'master'.
cf. <xmqqpl0xqh3n.fsf@gitster.g>
source: <pull.2353.v2.git.git.1783546933992.gitgitgadget@gmail.com>

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants