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

From: Junio C Hamano <gitster@pobox.com>
Date: Jul 7, 2026, 21:30 UTC
Message-ID: <xmqqv7aqzdvq.fsf@gitster.g>
In-Reply-To: <pull.2353.git.git.1783458106037.gitgitgadget@gmail.com>

"Henrique Ferreiro via GitGitGadget" <gitgitgadget@gmail.com> writes:

Show 14 quoted lines

> 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?

>  	}
>  	return NULL;

Show 18 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.

Show 15 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
> +'
> +
> +test_perf 'diff pathspec subtree' '
> +	git diff HEAD -- aaa/file
> +'
> +
> +test_done

Thanks.