unpack-trees: avoid quadratic index scan in next_cache_entry()#2353
unpack-trees: avoid quadratic index scan in next_cache_entry()#2353hferreiro wants to merge 1 commit into
Conversation
|
/preview |
|
Preview email sent as pull.2353.git.git.1783457006207.gitgitgadget@gmail.com |
|
/submit |
|
Submitted as pull.2353.git.git.1783458106037.gitgitgadget@gmail.com To fetch this version into To fetch this version to local tag |
|
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. |
|
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. |
|
User |
|
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>
cc1aaf0 to
c8f1ca3
Compare
|
/preview |
|
Preview email sent as pull.2353.v2.git.git.1783546738840.gitgitgadget@gmail.com |
|
/submit |
|
Submitted as pull.2353.v2.git.git.1783546933992.gitgitgadget@gmail.com To fetch this version into To fetch this version to local tag |
|
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
>>>> +' |
|
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. |
|
This branch is now known as |
|
This patch series was integrated into seen via 29bf20e. |
|
There was a status update in the "New Topics" section about the branch 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
left a comment
There was a problem hiding this comment.
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:
- Pathspec-limited tree walk +
switch_cache_bottom/restore_cache_bottomrewindscache_bottomonto already-CE_UNPACKEDearly entries (non---cachedonly — matches the “--cachedwas already fast” claim). mark_ce_used()only advancescache_bottomwhen the marked entry iscache[cache_bottom].- 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. |
There was a problem hiding this comment.
[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 |
There was a problem hiding this comment.
[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).
| struct cache_entry *ce = index->cache[pos]; | ||
| if (!(ce->ce_flags & CE_UNPACKED)) | ||
| if (!(ce->ce_flags & CE_UNPACKED)) { | ||
| o->internal.cache_bottom = pos; |
There was a problem hiding this comment.
[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;| if (!(ce->ce_flags & CE_UNPACKED)) | ||
| if (!(ce->ce_flags & CE_UNPACKED)) { | ||
| o->internal.cache_bottom = pos; | ||
| return ce; |
There was a problem hiding this comment.
[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.
|
This patch series was integrated into next via 744f1ae. |
|
There was a status update in the "Cooking" section about the branch 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> |
|
There was a status update in the "Cooking" section about the branch 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> |
Changes since v1: adjust the synthetic index size based on the EXPENSIVE prerequisite.
cc: Henrique Ferreiro hferreiro@igalia.com