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

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

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

> From: Henrique Ferreiro <hferreiro@igalia.com>
>
> Diffing the working tree against a commit with a pathspec can take
> time quadratic in the size of the index when the pathspec matches a
> subtree whose entries are the first entries of the index.  Fix it by
> having next_cache_entry() record how far it scanned in cache_bottom,
> so repeated calls no longer rescan the growing prefix of
> already-unpacked entries.  On a Chromium checkout (~500k index
> entries),
>
> 	git diff HEAD -- .agents/OWNERS
>
> took about 8 minutes before this change and 0.07 seconds after it.
> The same diff without the commit, without the pathspec, or with
> --cached was already instant.
>
> Add p0009-diff-pathspec.sh, which builds a 10,000-entry index whose
> first path lives in a subtree (100,000 entries under --long-tests),
> to guard against the regression.  Comparing v2.55.0 with this change
> using GIT_TEST_LONG=t:
>
> Test                            v2.55.0           HEAD
> ------------------------------------------------------------------------
> 0009.2: diff pathspec subtree   7.16(7.12+0.01)   0.02(0.01+0.00) -99.7%
>
> Signed-off-by: Henrique Ferreiro <hferreiro@igalia.com>
> ---
>     unpack-trees: avoid quadratic index scan in next_cache_entry()
>     
>     Changes since v1: adjust the synthetic index size based on the EXPENSIVE
>     prerequisite.

Thanks.