{"thread":{"id":"63964","subject":"[PATCH] ls-files: conditionally leave index sparse","startedAt":"2025-08-15T16:12:57Z","lastAt":"2025-08-28T15:02:09Z","messageCount":6,"participants":["Derrick Stolee via GitGitGadget","Derrick Stolee","Elijah Newren","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"524260","messageId":"pull.1955.git.1755274373717.gitgitgadget@gmail.com","threadId":"63964","inReplyTo":null,"subject":"[PATCH] ls-files: conditionally leave index sparse","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-08-15T16:12:53Z","receivedAt":"2025-08-15T16:12:57Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee <stolee@gmail.com>\n\nWhen running 'git ls-files' with a pathspec, the index entries get\nfiltered according to that pathspec before iterating over them in\nshow_files().  In 78087097b8 (ls-files: add --sparse option,\n2021-12-22), this iteration was prefixed with a check for the '--sparse'\noption which allows the command to output directory entries; this\ncreated a pre-loop call to ensure_full_index().\n\nHowever, when a user runs 'git ls-files' where the pathspec matches\ndirectories that are recursively matched in the sparse-checkout, there\nare not any sparse directories that match the pathspec so they would not\nbe written to the output. The expansion in this case is just a\nperformance drop for no behavior difference.\n\nReplace this global check to expand the index with a check inside the\nloop for a matched sparse directory. If we see one, then expand the\nindex and continue from the current location. This is safe since the\nprevious entries in the index did not have any sparse directories and\nthus would remain stable in this expansion.\n\nA test in t1092 confirms that this changes the behavior.\n\nSigned-off-by: Derrick Stolee <stolee@gmail.com>\n---\n    ls-files: conditionally leave index sparse\n    \n    Here's a small sparse index performance update based on a user report.\n    \n    Thanks, -Stolee\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1955%2Fderrickstolee%2Fls-files-sparse-index-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1955/derrickstolee/ls-files-sparse-index-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1955\n\n builtin/ls-files.c                       | 13 ++++++++++---\n t/t1092-sparse-checkout-compatibility.sh | 13 +++++++++++++\n 2 files changed, 23 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/ls-files.c b/builtin/ls-files.c\nindex c06a6f33e41..b148607f7a1 100644\n--- a/builtin/ls-files.c\n+++ b/builtin/ls-files.c\n@@ -414,14 +414,21 @@ static void show_files(struct repository *repo, struct dir_struct *dir)\n \tif (!(show_cached || show_stage || show_deleted || show_modified))\n \t\treturn;\n \n-\tif (!show_sparse_dirs)\n-\t\tensure_full_index(repo->index);\n-\n \tfor (i = 0; i < repo->index->cache_nr; i++) {\n \t\tconst struct cache_entry *ce = repo->index->cache[i];\n \t\tstruct stat st;\n \t\tint stat_err;\n \n+\t\tif (S_ISSPARSEDIR(ce->ce_mode) && !show_sparse_dirs) {\n+\t\t\t/*\n+\t\t\t * This is the first time we've hit a sparse dir,\n+\t\t\t * so expansion will leave the first 'i' entries\n+\t\t\t * alone.\n+\t\t\t */\n+\t\t\tensure_full_index(repo->index);\n+\t\t\tce = repo->index->cache[i];\n+\t\t}\n+\n \t\tconstruct_fullname(&fullname, repo, ce);\n \n \t\tif ((dir->flags & DIR_SHOW_IGNORED) &&\ndiff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\nindex d8101139b40..b0f691c151a 100755\n--- a/t/t1092-sparse-checkout-compatibility.sh\n+++ b/t/t1092-sparse-checkout-compatibility.sh\n@@ -1506,6 +1506,8 @@ test_expect_success 'sparse-index is not expanded' '\n \tensure_not_expanded reset --hard &&\n \tensure_not_expanded restore -s rename-out-to-out -- deep/deeper1 &&\n \n+\tensure_not_expanded ls-files deep/deeper1 &&\n+\n \techo >>sparse-index/README.md &&\n \tensure_not_expanded add -A &&\n \techo >>sparse-index/extra.txt &&\n@@ -1607,6 +1609,17 @@ test_expect_success 'describe tested on all' '\n \ttest_all_match git describe --dirty\n '\n \n+test_expect_success 'ls-files filtering and expansion' '\n+\tinit_repos &&\n+\n+\t# This filtering will hit a sparse directory midway\n+\t# through the iteration.\n+\ttest_all_match git ls-files deep &&\n+\n+\t# This pathspec will filter the index to only a sparse\n+\t# directory.\n+\ttest_all_match git ls-files folder1\n+'\n \n test_expect_success 'sparse-index is not expanded: describe' '\n \tinit_repos &&\n\nbase-commit: 724518f3884d8707c5f51428ba98c115818229b8\n-- \ngitgitgadget\n"},{"id":"524977","messageId":"c1f2e7b1-7583-4e1e-8f20-584a7a768286@gmail.com","threadId":"63964","inReplyTo":"pull.1955.git.1755274373717.gitgitgadget@gmail.com","subject":"Re: [PATCH] ls-files: conditionally leave index sparse","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2025-08-26T16:40:31Z","receivedAt":"2025-08-26T16:40:54Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/15/2025 12:12 PM, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee <stolee@gmail.com>\n...\n> Replace this global check to expand the index with a check inside the\n> loop for a matched sparse directory. If we see one, then expand the\n> index and continue from the current location. This is safe since the\n> previous entries in the index did not have any sparse directories and\n> thus would remain stable in this expansion.\n...>     Here's a small sparse index performance update based on a user report.\n\nI know this is small and somewhat niche, but it hasn't had any review\nor been picked up in What's Cooking. Could someone please take a look?\n\nThanks,\n-Stolee\n"},{"id":"524990","messageId":"CABPp-BE-FrvWHiskk3t7ePG9NWmj8E5FaFfxk6JGF4ztYVQt0w@mail.gmail.com","threadId":"63964","inReplyTo":"pull.1955.git.1755274373717.gitgitgadget@gmail.com","subject":"Re: [PATCH] ls-files: conditionally leave index sparse","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-08-26T18:37:08Z","receivedAt":"2025-08-26T18:37:20Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Aug 15, 2025 at 9:13 AM Derrick Stolee via GitGitGadget\n<gitgitgadget@gmail.com> wrote:\n>\n> From: Derrick Stolee <stolee@gmail.com>\n>\n> When running 'git ls-files' with a pathspec, the index entries get\n> filtered according to that pathspec before iterating over them in\n\nWhen I first read this patch, I missed this part of your commit\nmessage and figured there was no possible way your patch could\nactually speed things up.  I verified with your testcase that it\nworked, though, and had to step through a debugger to find out what I\nwas missing.  It's the prune_index() call in cmd_ls_files() that does\nthis -- but only when the pathspecs provided have some common prefix.\nSo, it's not unique to when there's a single pathspec as your commit\nmessage claims, and the pointer to prune_index() may have helped save\nme some head-scratching in review the patch.\n\nPerhaps this could be clarified here (and made more explicit for folks\nlike me that gloss over it), something like\n\nWhen running 'git ls-files' with pathspecs with a common prefix, the\nindex entries get\nfiltered according to that common prefix in prune_index() before\niterating over them in show_files().\n\n> show_files().  In 78087097b8 (ls-files: add --sparse option,\n> 2021-12-22), this iteration was prefixed with a check for the '--sparse'\n> option which allows the command to output directory entries; this\n> created a pre-loop call to ensure_full_index().\n>\n> However, when a user runs 'git ls-files' where the pathspec matches\n> directories that are recursively matched in the sparse-checkout, there\n> are not any sparse directories that match the pathspec so they would not\n> be written to the output. The expansion in this case is just a\n> performance drop for no behavior difference.\n>\n> Replace this global check to expand the index with a check inside the\n> loop for a matched sparse directory. If we see one, then expand the\n> index and continue from the current location. This is safe since the\n> previous entries in the index did not have any sparse directories and\n> thus would remain stable in this expansion.\n>\n> A test in t1092 confirms that this changes the behavior.\n>\n> Signed-off-by: Derrick Stolee <stolee@gmail.com>\n> ---\n>     ls-files: conditionally leave index sparse\n>\n>     Here's a small sparse index performance update based on a user report.\n>\n>     Thanks, -Stolee\n>\n> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1955%2Fderrickstolee%2Fls-files-sparse-index-v1\n> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1955/derrickstolee/ls-files-sparse-index-v1\n> Pull-Request: https://github.com/gitgitgadget/git/pull/1955\n>\n>  builtin/ls-files.c                       | 13 ++++++++++---\n>  t/t1092-sparse-checkout-compatibility.sh | 13 +++++++++++++\n>  2 files changed, 23 insertions(+), 3 deletions(-)\n>\n> diff --git a/builtin/ls-files.c b/builtin/ls-files.c\n> index c06a6f33e41..b148607f7a1 100644\n> --- a/builtin/ls-files.c\n> +++ b/builtin/ls-files.c\n> @@ -414,14 +414,21 @@ static void show_files(struct repository *repo, struct dir_struct *dir)\n>         if (!(show_cached || show_stage || show_deleted || show_modified))\n>                 return;\n>\n> -       if (!show_sparse_dirs)\n> -               ensure_full_index(repo->index);\n> -\n>         for (i = 0; i < repo->index->cache_nr; i++) {\n>                 const struct cache_entry *ce = repo->index->cache[i];\n>                 struct stat st;\n>                 int stat_err;\n>\n> +               if (S_ISSPARSEDIR(ce->ce_mode) && !show_sparse_dirs) {\n> +                       /*\n> +                        * This is the first time we've hit a sparse dir,\n> +                        * so expansion will leave the first 'i' entries\n> +                        * alone.\n> +                        */\n> +                       ensure_full_index(repo->index);\n> +                       ce = repo->index->cache[i];\n> +               }\n\nI see how this is safe.  I didn't understand how it helped performance\nuntil I figured out by stepping through that repo->indexc->cache_nr is\nmuch less than I expected, because of the prune_index() call that\nhappened earlier.\n\n>                 construct_fullname(&fullname, repo, ce);\n>\n>                 if ((dir->flags & DIR_SHOW_IGNORED) &&\n> diff --git a/t/t1092-sparse-checkout-compatibility.sh b/t/t1092-sparse-checkout-compatibility.sh\n> index d8101139b40..b0f691c151a 100755\n> --- a/t/t1092-sparse-checkout-compatibility.sh\n> +++ b/t/t1092-sparse-checkout-compatibility.sh\n> @@ -1506,6 +1506,8 @@ test_expect_success 'sparse-index is not expanded' '\n>         ensure_not_expanded reset --hard &&\n>         ensure_not_expanded restore -s rename-out-to-out -- deep/deeper1 &&\n>\n> +       ensure_not_expanded ls-files deep/deeper1 &&\n> +\n\nThanks, this testcase is exactly what I needed to figure out what I\nwas misunderstanding.\n\n>         echo >>sparse-index/README.md &&\n>         ensure_not_expanded add -A &&\n>         echo >>sparse-index/extra.txt &&\n> @@ -1607,6 +1609,17 @@ test_expect_success 'describe tested on all' '\n>         test_all_match git describe --dirty\n>  '\n>\n> +test_expect_success 'ls-files filtering and expansion' '\n> +       init_repos &&\n> +\n> +       # This filtering will hit a sparse directory midway\n> +       # through the iteration.\n> +       test_all_match git ls-files deep &&\n> +\n> +       # This pathspec will filter the index to only a sparse\n> +       # directory.\n> +       test_all_match git ls-files folder1\n> +'\n\nLooks good.\n"},{"id":"524994","messageId":"xmqqh5xtkiwt.fsf@gitster.g","threadId":"63964","inReplyTo":"pull.1955.git.1755274373717.gitgitgadget@gmail.com","subject":"Re: [PATCH] ls-files: conditionally leave index sparse","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-26T19:00:18Z","receivedAt":"2025-08-26T19:00:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n>  \tfor (i = 0; i < repo->index->cache_nr; i++) {\n>  \t\tconst struct cache_entry *ce = repo->index->cache[i];\n>  \t\tstruct stat st;\n>  \t\tint stat_err;\n>  \n> +\t\tif (S_ISSPARSEDIR(ce->ce_mode) && !show_sparse_dirs) {\n> +\t\t\t/*\n> +\t\t\t * This is the first time we've hit a sparse dir,\n> +\t\t\t * so expansion will leave the first 'i' entries\n> +\t\t\t * alone.\n> +\t\t\t */\n\nIn other words,\n\n (1) we know that the original index entries are sorted\n\n (2) we are looking at a single directory entry that is sparse, say\n     \"D/\", and ensure_full_index() will expand it (and other later\n     entries in the current index).\n\n (3) we assume that the contents of \"D/\" will never sort before the\n     original location where \"D/\" used to sit, iow, we do not have\n     to rewind to the beginning of index->cache[] array and skip\n     what we have already processed.\n\nHaving bitten by the index sort order number of times, I just wanted\nto make sure everybody's assumption is on the same page.\n\n> +\t\t\tensure_full_index(repo->index);\n> +\t\t\tce = repo->index->cache[i];\n\nand there is no need to say \"again\" (redo this round of the loop)\nhere, as grabbing ce was the only thing the loop did, and we just\nreplaced the entry for the originally folded \"D/\" with one for the\nfirst subpath in \"D/\".  Sounds sensible.\n\n"},{"id":"525070","messageId":"5c19f2f4-1d04-424d-9720-6db4342aebdd@gmail.com","threadId":"63964","inReplyTo":"c1f2e7b1-7583-4e1e-8f20-584a7a768286@gmail.com","subject":"Re: [PATCH] ls-files: conditionally leave index sparse","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2025-08-27T19:36:18Z","receivedAt":"2025-08-27T19:36:42Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/26/2025 12:40 PM, Derrick Stolee wrote:\n> On 8/15/2025 12:12 PM, Derrick Stolee via GitGitGadget wrote:\n>> From: Derrick Stolee <stolee@gmail.com>\n> ...\n>> Replace this global check to expand the index with a check inside the\n>> loop for a matched sparse directory. If we see one, then expand the\n>> index and continue from the current location. This is safe since the\n>> previous entries in the index did not have any sparse directories and\n>> thus would remain stable in this expansion.\n> ...>     Here's a small sparse index performance update based on a user report.\n> \n> I know this is small and somewhat niche, but it hasn't had any review\n> or been picked up in What's Cooking. Could someone please take a look?\n\nThanks, Elijah and Junio for reviewing.\n\nBy coincidence, a user reported an issue where the sparse index was\nexpanded during \"git mergetool\" and it was due to a pathspec-focused\nls-files subcommand. So maybe it's less niche than I had thought.\n\nThanks,\n-Stolee\n\n"},{"id":"525113","messageId":"xmqqplcfxzf5.fsf@gitster.g","threadId":"63964","inReplyTo":"5c19f2f4-1d04-424d-9720-6db4342aebdd@gmail.com","subject":"Re: [PATCH] ls-files: conditionally leave index sparse","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-28T15:02:06Z","receivedAt":"2025-08-28T15:02:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n\n> On 8/26/2025 12:40 PM, Derrick Stolee wrote:\n>> On 8/15/2025 12:12 PM, Derrick Stolee via GitGitGadget wrote:\n>>> From: Derrick Stolee <stolee@gmail.com>\n>> ...\n>>> Replace this global check to expand the index with a check inside the\n>>> loop for a matched sparse directory. If we see one, then expand the\n>>> index and continue from the current location. This is safe since the\n>>> previous entries in the index did not have any sparse directories and\n>>> thus would remain stable in this expansion.\n>> ...>     Here's a small sparse index performance update based on a user report.\n>> \n>> I know this is small and somewhat niche, but it hasn't had any review\n>> or been picked up in What's Cooking. Could someone please take a look?\n>\n> Thanks, Elijah and Junio for reviewing.\n>\n> By coincidence, a user reported an issue where the sparse index was\n> expanded during \"git mergetool\" and it was due to a pathspec-focused\n> ls-files subcommand. So maybe it's less niche than I had thought.\n\nI do not speak for others who did not comment on the thread, but the\nreason I did not act on the message was not because I found it niche\nor insignificant.  I simply missed the single message in the sea of\nother threads.\n\nQueued.  Thanks for pinging.\n"}]}