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

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.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2353%2Fhferreiro%2Funpack-trees-quadratic-scan-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2353/hferreiro/unpack-trees-quadratic-scan-v2
Pull-Request: https://github.com/git/git/pull/2353

Range-diff vs v1:

 1:  cc1aaf01cf ! 1:  c8f1ca389d unpack-trees: avoid quadratic index scan in next_cache_entry()
     @@ Commit message
          The same diff without the commit, without the pathspec, or with
          --cached was already instant.
      
     -    Add p0009-diff-pathspec.sh, which builds a 100,000-entry index whose
     -    first path lives in a subtree, to guard against the regression.
     -    Comparing v2.55.0 with this change:
     +    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
          ------------------------------------------------------------------------
     @@ t/perf/p0009-diff-pathspec.sh (new)
      +
      +test_perf_fresh_repo
      +
     ++count=10000
     ++if test_have_prereq EXPENSIVE
     ++then
     ++	count=100000
     ++fi
     ++
      +# The entries exist only in the index, which is enough to
      +# exercise the index scan.
      +test_expect_success 'setup' '
     -+	count=100000 &&
      +	blob=$(echo content | git hash-object -w --stdin) &&
      +	{
      +		printf "100644 $blob\taaa/file\n" &&

 t/perf/p0009-diff-pathspec.sh | 32 ++++++++++++++++++++++++++++++++
 unpack-trees.c                |  4 +++-
 2 files changed, 35 insertions(+), 1 deletion(-)
 create mode 100755 t/perf/p0009-diff-pathspec.sh