{"thread":{"id":"65946","subject":"[PATCH] unpack-trees: avoid quadratic index scan in next_cache_entry()","startedAt":"2026-07-07T21:01:48Z","lastAt":"2026-07-08T21:58:07Z","messageCount":7,"participants":["Henrique Ferreiro via GitGitGadget","Junio C Hamano","Henrique Ferreiro"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"547404","messageId":"pull.2353.git.git.1783458106037.gitgitgadget@gmail.com","threadId":"65946","inReplyTo":null,"subject":"[PATCH] unpack-trees: avoid quadratic index scan in next_cache_entry()","fromName":"Henrique Ferreiro via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-07-07T21:01:45Z","receivedAt":"2026-07-07T21:01:48Z","isPatch":true,"body":"From: Henrique Ferreiro \n\nDiffing the working tree against a commit with a pathspec can take\ntime quadratic in the size of the index when the pathspec matches a\nsubtree whose entries are the first entries of the index. Fix it by\nhaving next_cache_entry() record how far it scanned in cache_bottom,\nso repeated calls no longer rescan the growing prefix of\nalready-unpacked entries. On a Chromium checkout (~500k index\nentries),\n\n\tgit diff HEAD -- .agents/OWNERS\n\ntook about 8 minutes before this change and 0.07 seconds after it.\nThe same diff without the commit, without the pathspec, or with\n--cached was already instant.\n\nAdd p0009-diff-pathspec.sh, which builds a 100,000-entry index whose\nfirst path lives in a subtree, to guard against the regression.\nComparing v2.55.0 with this change:\n\nTest v2.55.0 HEAD\n------------------------------------------------------------------------\n0009.2: diff pathspec subtree 7.16(7.12+0.01) 0.02(0.01+0.00) -99.7%\n\nSigned-off-by: Henrique Ferreiro \n---\n unpack-trees: avoid quadratic index scan in next_cache_entry()\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2353%2Fhferreiro%2Funpack-trees-quadratic-scan-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2353/hferreiro/unpack-trees-quadratic-scan-v1\nPull-Request: https://github.com/git/git/pull/2353\n\n t/perf/p0009-diff-pathspec.sh | 27 +++++++++++++++++++++++++++\n unpack-trees.c | 4 +++-\n 2 files changed, 30 insertions(+), 1 deletion(-)\n create mode 100755 t/perf/p0009-diff-pathspec.sh\n\ndiff --git a/t/perf/p0009-diff-pathspec.sh b/t/perf/p0009-diff-pathspec.sh\nnew file mode 100755\nindex 0000000000..0f1dccfbb4\n--- /dev/null\n+++ b/t/perf/p0009-diff-pathspec.sh\n@@ -0,0 +1,27 @@\n+#!/bin/sh\n+\n+test_description='Tests performance of diffing the working tree with a pathspec'\n+\n+. ./perf-lib.sh\n+\n+test_perf_fresh_repo\n+\n+# The entries exist only in the index, which is enough to\n+# exercise the index scan.\n+test_expect_success 'setup' '\n+\tcount=100000 &&\n+\tblob=$(echo content | git hash-object -w --stdin) &&\n+\t{\n+\t\tprintf \"100644 $blob\\taaa/file\\n\" &&\n+\t\tprintf \"100644 $blob\\tf%s\\n\" $(test_seq $count)\n+\t} | git update-index --index-info &&\n+\tgit commit -q -m initial &&\n+\tmkdir -p aaa &&\n+\techo content >aaa/file\n+'\n+\n+test_perf 'diff pathspec subtree' '\n+\tgit diff HEAD -- aaa/file\n+'\n+\n+test_done\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex b42020f16b..ed9fef453a 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -671,8 +671,10 @@ static struct cache_entry *next_cache_entry(struct unpack_trees_options *o)\n \n \twhile (pos < index->cache_nr) {\n \t\tstruct cache_entry *ce = index->cache[pos];\n-\t\tif (!(ce->ce_flags & CE_UNPACKED))\n+\t\tif (!(ce->ce_flags & CE_UNPACKED)) {\n+\t\t\to->internal.cache_bottom = pos;\n \t\t\treturn ce;\n+\t\t}\n \t\tpos++;\n \t}\n \treturn NULL;\n\nbase-commit: e9019fcafe0040228b8631c30f97ae1adb61bcdc\n-- \ngitgitgadget\n"},{"id":"547406","messageId":"xmqqv7aqzdvq.fsf@gitster.g","threadId":"65946","inReplyTo":"pull.2353.git.git.1783458106037.gitgitgadget@gmail.com","subject":"Re: [PATCH] unpack-trees: avoid quadratic index scan in next_cache_entry()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-07-07T21:30:33Z","receivedAt":"2026-07-07T21:30:36Z","isPatch":true,"body":"\"Henrique Ferreiro via GitGitGadget\" \nwrites:\n\n> diff --git a/unpack-trees.c b/unpack-trees.c\n> index b42020f16b..ed9fef453a 100644\n> --- a/unpack-trees.c\n> +++ b/unpack-trees.c\n> @@ -671,8 +671,10 @@ static struct cache_entry *next_cache_entry(struct unpack_trees_options *o)\n> \n> \twhile (pos < index->cache_nr) {\n> \t\tstruct cache_entry *ce = index->cache[pos];\n> -\t\tif (!(ce->ce_flags & CE_UNPACKED))\n> +\t\tif (!(ce->ce_flags & CE_UNPACKED)) {\n> +\t\t\to->internal.cache_bottom = pos;\n> \t\t\treturn ce;\n> +\t\t}\n> \t\tpos++;\n\nNice spotting.\n\nDoes this trick work correctly even when a path's sorting order\ndiffers between the index and tree objects, which is precisely why\n.cache_bottom was introduced, to allow backward scanning while\nbounding the lookback distance?\n\n> \t}\n> \treturn NULL;\n\n\n> diff --git a/t/perf/p0009-diff-pathspec.sh b/t/perf/p0009-diff-pathspec.sh\n> new file mode 100755\n> index 0000000000..0f1dccfbb4\n> --- /dev/null\n> +++ b/t/perf/p0009-diff-pathspec.sh\n> @@ -0,0 +1,27 @@\n> +#!/bin/sh\n> +\n> +test_description='Tests performance of diffing the working tree with a pathspec'\n> +\n> +. ./perf-lib.sh\n> +\n> +test_perf_fresh_repo\n> +\n> +# The entries exist only in the index, which is enough to\n> +# exercise the index scan.\n> +test_expect_success 'setup' '\n> +\tcount=100000 &&\n\nYou will probably want to mimic how t/perf/p4209-pickaxe.sh helps\ntesters by adjusting the count based on how the EXPENSIVE\nprerequisite is configured.\n\n> +\tblob=$(echo content | git hash-object -w --stdin) &&\n> +\t{\n> +\t\tprintf \"100644 $blob\\taaa/file\\n\" &&\n> +\t\tprintf \"100644 $blob\\tf%s\\n\" $(test_seq $count)\n> +\t} | git update-index --index-info &&\n> +\tgit commit -q -m initial &&\n> +\tmkdir -p aaa &&\n> +\techo content >aaa/file\n> +'\n> +\n> +test_perf 'diff pathspec subtree' '\n> +\tgit diff HEAD -- aaa/file\n> +'\n> +\n> +test_done\n\nThanks.\n"},{"id":"547525","messageId":"4c0a31e9-9b20-46c8-8f1f-0fda34515270@igalia.com","threadId":"65946","inReplyTo":"xmqqv7aqzdvq.fsf@gitster.g","subject":"Re: [PATCH] unpack-trees: avoid quadratic index scan in next_cache_entry()","fromName":"Henrique Ferreiro","fromEmail":"hferreiro@igalia.com","sentAt":"2026-07-08T18:31:35Z","receivedAt":"2026-07-08T18:31:44Z","isPatch":true,"body":"\nOn 07/07/2026 23:30, Junio C Hamano wrote:\n> \"Henrique Ferreiro via GitGitGadget\" \n> writes:\n>\n>> diff --git a/unpack-trees.c b/unpack-trees.c\n>> index b42020f16b..ed9fef453a 100644\n>> --- a/unpack-trees.c\n>> +++ b/unpack-trees.c\n>> @@ -671,8 +671,10 @@ static struct cache_entry *next_cache_entry(struct unpack_trees_options *o)\n>> \n>> \twhile (pos < index->cache_nr) {\n>> \t\tstruct cache_entry *ce = index->cache[pos];\n>> -\t\tif (!(ce->ce_flags & CE_UNPACKED))\n>> +\t\tif (!(ce->ce_flags & CE_UNPACKED)) {\n>> +\t\t\to->internal.cache_bottom = pos;\n>> \t\t\treturn ce;\n>> +\t\t}\n>> \t\tpos++;\n> Nice spotting.\n>\n> Does this trick work correctly even when a path's sorting order\n> differs between the index and tree objects, which is precisely why\n> .cache_bottom was introduced, to allow backward scanning while\n> bounding the lookback distance?\nIIUC, .cache_bottom points at the first entry that needs to be \nprocessed. With this change, that still holds true even when entries are \nprocessed out of index order. find_cache_pos() also advances \ncache_bottom past unpacked entries since e53e6b4433 (unpack-trees: Make \nindex lookahead less pessimal, 2010-06-10).\n>\n>> \t}\n>> \treturn NULL;\n>\n>> diff --git a/t/perf/p0009-diff-pathspec.sh b/t/perf/p0009-diff-pathspec.sh\n>> new file mode 100755\n>> index 0000000000..0f1dccfbb4\n>> --- /dev/null\n>> +++ b/t/perf/p0009-diff-pathspec.sh\n>> @@ -0,0 +1,27 @@\n>> +#!/bin/sh\n>> +\n>> +test_description='Tests performance of diffing the working tree with a pathspec'\n>> +\n>> +. ./perf-lib.sh\n>> +\n>> +test_perf_fresh_repo\n>> +\n>> +# The entries exist only in the index, which is enough to\n>> +# exercise the index scan.\n>> +test_expect_success 'setup' '\n>> +\tcount=100000 &&\n> You will probably want to mimic how t/perf/p4209-pickaxe.sh helps\n> testers by adjusting the count based on how the EXPENSIVE\n> prerequisite is configured.\n>\n>> +\tblob=$(echo content | git hash-object -w --stdin) &&\n>> +\t{\n>> +\t\tprintf \"100644 $blob\\taaa/file\\n\" &&\n>> +\t\tprintf \"100644 $blob\\tf%s\\n\" $(test_seq $count)\n>> +\t} | git update-index --index-info &&\n>> +\tgit commit -q -m initial &&\n>> +\tmkdir -p aaa &&\n>> +\techo content >aaa/file\n>> +'\n>> +\n>> +test_perf 'diff pathspec subtree' '\n>> +\tgit diff HEAD -- aaa/file\n>> +'\n>> +\n>> +test_done\n> Thanks.\n"},{"id":"547526","messageId":"xmqqzf01thq0.fsf@gitster.g","threadId":"65946","inReplyTo":"4c0a31e9-9b20-46c8-8f1f-0fda34515270@igalia.com","subject":"Re: [PATCH] unpack-trees: avoid quadratic index scan in next_cache_entry()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-07-08T19:16:23Z","receivedAt":"2026-07-08T19:16:26Z","isPatch":true,"body":"Henrique Ferreiro writes:\n\n> On 07/07/2026 23:30, Junio C Hamano wrote:\n>> \"Henrique Ferreiro via GitGitGadget\" \n>> writes:\n>>\n>>> diff --git a/unpack-trees.c b/unpack-trees.c\n>>> index b42020f16b..ed9fef453a 100644\n>>> --- a/unpack-trees.c\n>>> +++ b/unpack-trees.c\n>>> @@ -671,8 +671,10 @@ static struct cache_entry *next_cache_entry(struct unpack_trees_options *o)\n>>> \n>>> \twhile (pos < index->cache_nr) {\n>>> \t\tstruct cache_entry *ce = index->cache[pos];\n>>> -\t\tif (!(ce->ce_flags & CE_UNPACKED))\n>>> +\t\tif (!(ce->ce_flags & CE_UNPACKED)) {\n>>> +\t\t\to->internal.cache_bottom = pos;\n>>> \t\t\treturn ce;\n>>> +\t\t}\n>>> \t\tpos++;\n>> Nice spotting.\n>>\n>> Does this trick work correctly even when a path's sorting order\n>> differs between the index and tree objects, which is precisely why\n>> .cache_bottom was introduced, to allow backward scanning while\n>> bounding the lookback distance?\n\n> IIUC, .cache_bottom points at the first entry that needs to be \n> processed. With this change, that still holds true even when entries are \n> processed out of index order. find_cache_pos() also advances \n> cache_bottom past unpacked entries since e53e6b4433 (unpack-trees: Make \n> index lookahead less pessimal, 2010-06-10).\n\nThat sounds sensible.\n\n>>> diff --git a/t/perf/p0009-diff-pathspec.sh b/t/perf/p0009-diff-pathspec.sh\n>>> new file mode 100755\n>>> index 0000000000..0f1dccfbb4\n>>> --- /dev/null\n>>> +++ b/t/perf/p0009-diff-pathspec.sh\n>>> @@ -0,0 +1,27 @@\n>>> +#!/bin/sh\n>>> +\n>>> +test_description='Tests performance of diffing the working tree with a pathspec'\n>>> +\n>>> +. ./perf-lib.sh\n>>> +\n>>> +test_perf_fresh_repo\n>>> +\n>>> +# The entries exist only in the index, which is enough to\n>>> +# exercise the index scan.\n>>> +test_expect_success 'setup' '\n>>> +\tcount=100000 &&\n>>\n>> You will probably want to mimic how t/perf/p4209-pickaxe.sh helps\n>> testers by adjusting the count based on how the EXPENSIVE\n>> prerequisite is configured.\n\nI think this comment still needs addressing, though.\n\nThanks.\n\n>>> +\tblob=$(echo content | git hash-object -w --stdin) &&\n>>> +\t{\n>>> +\t\tprintf \"100644 $blob\\taaa/file\\n\" &&\n>>> +\t\tprintf \"100644 $blob\\tf%s\\n\" $(test_seq $count)\n>>> +\t} | git update-index --index-info &&\n>>> +\tgit commit -q -m initial &&\n>>> +\tmkdir -p aaa &&\n>>> +\techo content >aaa/file\n>>> +'\n"},{"id":"547536","messageId":"c3bd7389-4650-4e5d-a579-8dcb90ea3c47@igalia.com","threadId":"65946","inReplyTo":"xmqqzf01thq0.fsf@gitster.g","subject":"Re: [PATCH] unpack-trees: avoid quadratic index scan in next_cache_entry()","fromName":"Henrique Ferreiro","fromEmail":"hferreiro@igalia.com","sentAt":"2026-07-08T21:40:40Z","receivedAt":"2026-07-08T21:40:55Z","isPatch":true,"body":"\nOn 08/07/2026 21:16, Junio C Hamano wrote:\n> Henrique Ferreiro writes:\n>\n>> On 07/07/2026 23:30, Junio C Hamano wrote:\n>>> \"Henrique Ferreiro via GitGitGadget\" \n>>> writes:\n>>>\n>>>> diff --git a/unpack-trees.c b/unpack-trees.c\n>>>> index b42020f16b..ed9fef453a 100644\n>>>> --- a/unpack-trees.c\n>>>> +++ b/unpack-trees.c\n>>>> @@ -671,8 +671,10 @@ static struct cache_entry *next_cache_entry(struct unpack_trees_options *o)\n>>>> \n>>>> \twhile (pos < index->cache_nr) {\n>>>> \t\tstruct cache_entry *ce = index->cache[pos];\n>>>> -\t\tif (!(ce->ce_flags & CE_UNPACKED))\n>>>> +\t\tif (!(ce->ce_flags & CE_UNPACKED)) {\n>>>> +\t\t\to->internal.cache_bottom = pos;\n>>>> \t\t\treturn ce;\n>>>> +\t\t}\n>>>> \t\tpos++;\n>>> Nice spotting.\n>>>\n>>> Does this trick work correctly even when a path's sorting order\n>>> differs between the index and tree objects, which is precisely why\n>>> .cache_bottom was introduced, to allow backward scanning while\n>>> bounding the lookback distance?\n>> IIUC, .cache_bottom points at the first entry that needs to be\n>> processed. With this change, that still holds true even when entries are\n>> processed out of index order. find_cache_pos() also advances\n>> cache_bottom past unpacked entries since e53e6b4433 (unpack-trees: Make\n>> index lookahead less pessimal, 2010-06-10).\n> That sounds sensible.\n>\n>>>> diff --git a/t/perf/p0009-diff-pathspec.sh b/t/perf/p0009-diff-pathspec.sh\n>>>> new file mode 100755\n>>>> index 0000000000..0f1dccfbb4\n>>>> --- /dev/null\n>>>> +++ b/t/perf/p0009-diff-pathspec.sh\n>>>> @@ -0,0 +1,27 @@\n>>>> +#!/bin/sh\n>>>> +\n>>>> +test_description='Tests performance of diffing the working tree with a pathspec'\n>>>> +\n>>>> +. ./perf-lib.sh\n>>>> +\n>>>> +test_perf_fresh_repo\n>>>> +\n>>>> +# The entries exist only in the index, which is enough to\n>>>> +# exercise the index scan.\n>>>> +test_expect_success 'setup' '\n>>>> +\tcount=100000 &&\n>>> You will probably want to mimic how t/perf/p4209-pickaxe.sh helps\n>>> testers by adjusting the count based on how the EXPENSIVE\n>>> prerequisite is configured.\n> I think this comment still needs addressing, though.\n>\n> Thanks.\n\nSure. I've just sent v2 with those changes. Note that I used an initial \ncount of 1000, otherwise the improvement is not noticeable.\n\n\n>>>> +\tblob=$(echo content | git hash-object -w --stdin) &&\n>>>> +\t{\n>>>> +\t\tprintf \"100644 $blob\\taaa/file\\n\" &&\n>>>> +\t\tprintf \"100644 $blob\\tf%s\\n\" $(test_seq $count)\n>>>> +\t} | git update-index --index-info &&\n>>>> +\tgit commit -q -m initial &&\n>>>> +\tmkdir -p aaa &&\n>>>> +\techo content >aaa/file\n>>>> +'\n"},{"id":"547537","messageId":"pull.2353.v2.git.git.1783546933992.gitgitgadget@gmail.com","threadId":"65946","inReplyTo":"pull.2353.git.git.1783458106037.gitgitgadget@gmail.com","subject":"[PATCH v2] unpack-trees: avoid quadratic index scan in next_cache_entry()","fromName":"Henrique Ferreiro via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-07-08T21:42:13Z","receivedAt":"2026-07-08T21:42:16Z","isPatch":true,"body":"From: Henrique Ferreiro \n\nDiffing the working tree against a commit with a pathspec can take\ntime quadratic in the size of the index when the pathspec matches a\nsubtree whose entries are the first entries of the index. Fix it by\nhaving next_cache_entry() record how far it scanned in cache_bottom,\nso repeated calls no longer rescan the growing prefix of\nalready-unpacked entries. On a Chromium checkout (~500k index\nentries),\n\n\tgit diff HEAD -- .agents/OWNERS\n\ntook about 8 minutes before this change and 0.07 seconds after it.\nThe same diff without the commit, without the pathspec, or with\n--cached was already instant.\n\nAdd p0009-diff-pathspec.sh, which builds a 10,000-entry index whose\nfirst path lives in a subtree (100,000 entries under --long-tests),\nto guard against the regression. Comparing v2.55.0 with this change\nusing GIT_TEST_LONG=t:\n\nTest v2.55.0 HEAD\n------------------------------------------------------------------------\n0009.2: diff pathspec subtree 7.16(7.12+0.01) 0.02(0.01+0.00) -99.7%\n\nSigned-off-by: Henrique Ferreiro \n---\n unpack-trees: avoid quadratic index scan in next_cache_entry()\n \n Changes since v1: adjust the synthetic index size based on the EXPENSIVE\n prerequisite.\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2353%2Fhferreiro%2Funpack-trees-quadratic-scan-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2353/hferreiro/unpack-trees-quadratic-scan-v2\nPull-Request: https://github.com/git/git/pull/2353\n\nRange-diff vs v1:\n\n 1: cc1aaf01cf ! 1: c8f1ca389d unpack-trees: avoid quadratic index scan in next_cache_entry()\n @@ Commit message\n The same diff without the commit, without the pathspec, or with\n --cached was already instant.\n \n - Add p0009-diff-pathspec.sh, which builds a 100,000-entry index whose\n - first path lives in a subtree, to guard against the regression.\n - Comparing v2.55.0 with this change:\n + Add p0009-diff-pathspec.sh, which builds a 10,000-entry index whose\n + first path lives in a subtree (100,000 entries under --long-tests),\n + to guard against the regression. Comparing v2.55.0 with this change\n + using GIT_TEST_LONG=t:\n \n Test v2.55.0 HEAD\n ------------------------------------------------------------------------\n @@ t/perf/p0009-diff-pathspec.sh (new)\n +\n +test_perf_fresh_repo\n +\n ++count=10000\n ++if test_have_prereq EXPENSIVE\n ++then\n ++\tcount=100000\n ++fi\n ++\n +# The entries exist only in the index, which is enough to\n +# exercise the index scan.\n +test_expect_success 'setup' '\n -+\tcount=100000 &&\n +\tblob=$(echo content | git hash-object -w --stdin) &&\n +\t{\n +\t\tprintf \"100644 $blob\\taaa/file\\n\" &&\n\n\n t/perf/p0009-diff-pathspec.sh | 32 ++++++++++++++++++++++++++++++++\n unpack-trees.c | 4 +++-\n 2 files changed, 35 insertions(+), 1 deletion(-)\n create mode 100755 t/perf/p0009-diff-pathspec.sh\n\ndiff --git a/t/perf/p0009-diff-pathspec.sh b/t/perf/p0009-diff-pathspec.sh\nnew file mode 100755\nindex 0000000000..6079db52c2\n--- /dev/null\n+++ b/t/perf/p0009-diff-pathspec.sh\n@@ -0,0 +1,32 @@\n+#!/bin/sh\n+\n+test_description='Tests performance of diffing the working tree with a pathspec'\n+\n+. ./perf-lib.sh\n+\n+test_perf_fresh_repo\n+\n+count=10000\n+if test_have_prereq EXPENSIVE\n+then\n+\tcount=100000\n+fi\n+\n+# The entries exist only in the index, which is enough to\n+# exercise the index scan.\n+test_expect_success 'setup' '\n+\tblob=$(echo content | git hash-object -w --stdin) &&\n+\t{\n+\t\tprintf \"100644 $blob\\taaa/file\\n\" &&\n+\t\tprintf \"100644 $blob\\tf%s\\n\" $(test_seq $count)\n+\t} | git update-index --index-info &&\n+\tgit commit -q -m initial &&\n+\tmkdir -p aaa &&\n+\techo content >aaa/file\n+'\n+\n+test_perf 'diff pathspec subtree' '\n+\tgit diff HEAD -- aaa/file\n+'\n+\n+test_done\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex b42020f16b..ed9fef453a 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -671,8 +671,10 @@ static struct cache_entry *next_cache_entry(struct unpack_trees_options *o)\n \n \twhile (pos < index->cache_nr) {\n \t\tstruct cache_entry *ce = index->cache[pos];\n-\t\tif (!(ce->ce_flags & CE_UNPACKED))\n+\t\tif (!(ce->ce_flags & CE_UNPACKED)) {\n+\t\t\to->internal.cache_bottom = pos;\n \t\t\treturn ce;\n+\t\t}\n \t\tpos++;\n \t}\n \treturn NULL;\n\nbase-commit: e9019fcafe0040228b8631c30f97ae1adb61bcdc\n-- \ngitgitgadget\n"},{"id":"547538","messageId":"xmqqpl0xqh3n.fsf@gitster.g","threadId":"65946","inReplyTo":"pull.2353.v2.git.git.1783546933992.gitgitgadget@gmail.com","subject":"Re: [PATCH v2] unpack-trees: avoid quadratic index scan in next_cache_entry()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-07-08T21:58:04Z","receivedAt":"2026-07-08T21:58:07Z","isPatch":true,"body":"\"Henrique Ferreiro via GitGitGadget\" \nwrites:\n\n> From: Henrique Ferreiro \n>\n> Diffing the working tree against a commit with a pathspec can take\n> time quadratic in the size of the index when the pathspec matches a\n> subtree whose entries are the first entries of the index. Fix it by\n> having next_cache_entry() record how far it scanned in cache_bottom,\n> so repeated calls no longer rescan the growing prefix of\n> already-unpacked entries. On a Chromium checkout (~500k index\n> entries),\n>\n> \tgit diff HEAD -- .agents/OWNERS\n>\n> took about 8 minutes before this change and 0.07 seconds after it.\n> The same diff without the commit, without the pathspec, or with\n> --cached was already instant.\n>\n> Add p0009-diff-pathspec.sh, which builds a 10,000-entry index whose\n> first path lives in a subtree (100,000 entries under --long-tests),\n> to guard against the regression. Comparing v2.55.0 with this change\n> using GIT_TEST_LONG=t:\n>\n> Test v2.55.0 HEAD\n> ------------------------------------------------------------------------\n> 0009.2: diff pathspec subtree 7.16(7.12+0.01) 0.02(0.01+0.00) -99.7%\n>\n> Signed-off-by: Henrique Ferreiro \n> ---\n> unpack-trees: avoid quadratic index scan in next_cache_entry()\n> \n> Changes since v1: adjust the synthetic index size based on the EXPENSIVE\n> prerequisite.\n\nThanks.\n"}]}