Re: [PATCH] unpack-trees: avoid quadratic index scan in next_cache_entry()
Henrique Ferreiro <hferreiro@igalia.com> writes:
Show 24 quoted lines
> 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?Show 5 quoted 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).
Show 22 quoted lines
>>> 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.
Show 9 quoted lines
>>> + 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 <gitster@pobox.com>