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

[Junio C Hamano <gitster@pobox.com>]

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