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

[Henrique Ferreiro <hferreiro@igalia.com>]

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