unpack-trees: avoid quadratic index scan in next_cache_entry()

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>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

0 files changed, 0 insertions, 0 deletions