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

From: Henrique Ferreiro <hferreiro@igalia.com>
Date: Jul 8, 2026, 18:31 UTC
Message-ID: <4c0a31e9-9b20-46c8-8f1f-0fda34515270@igalia.com>
In-Reply-To: <xmqqv7aqzdvq.fsf@gitster.g>

On 07/07/2026 23:30, Junio C Hamano wrote:

Show 23 quoted lines

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

Show 42 quoted lines

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