From: Junio C Hamano <gitster@pobox.com>
Date: Wed, 08 Jul 2026 19:16:23 GMT
Subject: Re: [PATCH] unpack-trees: avoid quadratic index scan in next_cache_entry()
Message-ID: <xmqqzf01thq0.fsf@gitster.g>
In-Reply-To: <4c0a31e9-9b20-46c8-8f1f-0fda34515270@igalia.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
>>> +'