{"thread":{"id":"58086","subject":"git bug report: 'git add' hangs in a large repo which has sparse-checkout file with large number of patterns in it","startedAt":"2022-06-29T19:11:47Z","lastAt":"2022-07-12T13:00:39Z","messageCount":12,"participants":["Dian Xu","Victoria Dye","Elijah Newren","Konstantin Ryabitsev"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"458120","messageId":"CAKSRnEzMaQEv=3mkNWRpy6+-c0rz=R191iqheCQ2ptXFs1CQgw@mail.gmail.com","threadId":"58086","inReplyTo":null,"subject":"git bug report: 'git add' hangs in a large repo which has sparse-checkout file with large number of patterns in it","fromName":"Dian Xu","fromEmail":"dianxudev@gmail.com","sentAt":"2022-06-29T19:11:31Z","receivedAt":"2022-06-29T19:11:47Z","isPatch":false,"sender":{"key":"dianxudev@gmail.com","avatar":null},"body":"Dear Git developers,\n\nReporting Issue:\n 'git add' hangs in a large repo which has\nsparse-checkout file with large number of patterns in it\n\nFound in:\n Git 2.34.3. Issue occurs after 'audit for interaction\nwith sparse-index' was introduced in add.c\n\nReproduction steps:\n 1. Clone a repo which has e.g. 2 million plus files\n 2. Enable sparse checkout by: git config core.sparsecheckout true\n 3. Create a .git/info/sparse-checkout file with a large\nnumber of patterns, e.g. 16k plus lines\n 4. Run 'git add', which will hang\n\nInvestigations:\n 1. Stack trace:\n add.c: cmd_add\n -> add.c: prune_directory\n -> pathspec.c: add_pathspec_matches_against_index\n -> dir.c: path_in_sparse_checkout_1\n 2. In Git 2.33.3, the loop at pathspec.c line 42 runs\nfast, even when istate->cache_nr is at 2 million\n 3. Since Git 2.34.3, the newly introduced 'audit for\ninteraction with sparse-index' (dir.c line 1459:\npath_in_sparse_checkout_1) decides to loop through 2 million files and\nmatch each one of them against the sparse-checkout patterns\n 4. This hits the O(n^2) problem thus causes 'git add' to\nhang (or ~1.5 hours to finish)\n\nPlease help us take a look at this issue and let us know if you need\nmore information.\n\nThanks,\n\nDian Xu\nMathworks, Inc\n1 Lakeside Campus Drive, Natick, MA 01760\n508-647-3583\n"},{"id":"458135","messageId":"96034b3f-9811-38c1-7afe-c1c9dd243f0e@github.com","threadId":"58086","inReplyTo":"CAKSRnEzMaQEv=3mkNWRpy6+-c0rz=R191iqheCQ2ptXFs1CQgw@mail.gmail.com","subject":"Re: git bug report: 'git add' hangs in a large repo which has sparse-checkout file with large number of patterns in it","fromName":"Victoria Dye","fromEmail":"vdye@github.com","sentAt":"2022-06-29T21:53:37Z","receivedAt":"2022-06-29T21:53:42Z","isPatch":false,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"Dian Xu wrote:\n> Dear Git developers,\n> \n> Reporting Issue:\n> 'git add' hangs in a large repo which has\n> sparse-checkout file with large number of patterns in it\n> \n> Found in:\n> Git 2.34.3. Issue occurs after 'audit for interaction\n> with sparse-index' was introduced in add.c\n> \n> Reproduction steps:\n> 1. Clone a repo which has e.g. 2 million plus files\n> 2. Enable sparse checkout by: git config core.sparsecheckout true\n> 3. Create a .git/info/sparse-checkout file with a large\n> number of patterns, e.g. 16k plus lines\n> 4. Run 'git add', which will hang> \n> Investigations:\n> 1. Stack trace:\n> add.c: cmd_add\n> -> add.c: prune_directory\n> -> pathspec.c: add_pathspec_matches_against_index\n> -> dir.c: path_in_sparse_checkout_1\n> 2. In Git 2.33.3, the loop at pathspec.c line 42 runs\n> fast, even when istate->cache_nr is at 2 million\n> 3. Since Git 2.34.3, the newly introduced 'audit for\n> interaction with sparse-index' (dir.c line 1459:\n> path_in_sparse_checkout_1) decides to loop through 2 million files and\n> match each one of them against the sparse-checkout patterns\n> 4. This hits the O(n^2) problem thus causes 'git add' to\n> hang (or ~1.5 hours to finish)\n\nThanks for the explanation, it helped me narrow down the source to an exact\ncommit (49fdd51a23 (add: skip tracked paths outside sparse-checkout cone,\n2021-09-24)). \n\nYou're correct that the `path_in_sparse_checkout()` check is slow [1].\nHowever, it only runs on files that are not \"hidden\" with the\n`SKIP_WORKTREE` flag. Ideally, if you're using sparse-checkout, this will\nonly be a small subset of your 2 million files. \n\nIn your repro steps, you're adding patterns to a file then immediately\nrunning `git add`. If that reflects how you're usually working with\nsparse-checkout, `SKIP_WORKTREE` likely isn't being applied properly before\nthe `add`. You can check to see whether file(s) have the flag properly\napplied with `git ls-files -t ` - each `SKIP_WORKTREE`\nfile should have an \"S\" next to it. \"H\" indicates that the flag is *not*\napplied.\n\nIf you see that most of the files that *should* be sparse don't have\n`SKIP_WORKTREE` applied, you can run `git sparse-checkout reapply` (make\nsure you don't have any modified files outside the patterns you're\napplying!). The downside is that it'll be as slow as what you're reporting\nfor `git add`, but any subsequent `add` (or reset, status, etc.) should be\nmuch faster.\n\nIf you do all of that but things are still slow, then the way we check\npathspecs in `git add` would need to change (not trivial, but probably not\nimpossible either). At a cursory glance, I can think of a few options for\nthat:\n\n1. Remove the `path_in_sparse_checkout()` check. It's the simplest solution,\n but it means you'd be able to stage files for commit outside the\n sparse-checkout patterns without using the '--sparse' option. I don't\n personally think that's a huge issue, but given that the implementation\n was intentionally changed *away* from this approach, I'd defer to other\n contributors to see if that's an okay change to make.\n2. After every call to `ce_path_match()`, check if all pathspecs are marked\n as `seen` and, if so, return early. This would slow down each individual\n file check and wouldn't help you if a pathspec matches nothing, but\n prevents checking more files once all pathspecs are matched.\n3. Do some heuristic checks on the pathspecs before checking index entries.\n For example, exact file or directory matches could be searched in the\n index. This would still require falling back on the per-file checks if\n not all pathspecs are matched, but makes some typical use-cases much\n faster.\n\nThere are almost certainly other options, and I can dig around `add.c` more\nto see if there's anything I'm missing (although I'd love to hear other\nideas too!). \n\nHopefully this helps!\n- Victoria\n\n[1] `path_in_sparse_checkout()` is significantly faster in cone mode, but\nwith 16k patterns I'm assuming you're not using cone patterns ;)\n\n> \n> Please help us take a look at this issue and let us know if you need\n> more information.\n> \n> Thanks,\n> \n> Dian Xu\n> Mathworks, Inc\n> 1 Lakeside Campus Drive, Natick, MA 01760\n> 508-647-3583\n\n"},{"id":"458154","messageId":"CABPp-BFzGBDqyh0rQK+PULjW14ewoF0AV6OiN9_Zt=dLW+rW+g@mail.gmail.com","threadId":"58086","inReplyTo":"CAKSRnEzMaQEv=3mkNWRpy6+-c0rz=R191iqheCQ2ptXFs1CQgw@mail.gmail.com","subject":"Re: git bug report: 'git add' hangs in a large repo which has sparse-checkout file with large number of patterns in it","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-06-30T03:10:12Z","receivedAt":"2022-06-30T03:10:37Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Jun 29, 2022 at 12:50 PM Dian Xu wrote:\n>\n> Dear Git developers,\n>\n> Reporting Issue:\n> 'git add' hangs in a large repo which has\n> sparse-checkout file with large number of patterns in it\n>\n> Found in:\n> Git 2.34.3. Issue occurs after 'audit for interaction\n> with sparse-index' was introduced in add.c\n>\n> Reproduction steps:\n> 1. Clone a repo which has e.g. 2 million plus files\n> 2. Enable sparse checkout by: git config core.sparsecheckout true\n> 3. Create a .git/info/sparse-checkout file with a large\n> number of patterns, e.g. 16k plus lines\n\nDid you run `git read-tree -mu HEAD` or even `git sparse-checkout\nreapply` after step 3 and before step 4? If not, you've left the\nworking tree out-of-sync with the specified sparsity paths and should\nfix that before running step 4.\n\n> 4. Run 'git add', which will hang\n\nAlternatively to the above, if you really want to add a file and\nignore the fact that it might be outside the sparsity patterns (and\nrisk it later randomly disappearing with checkout/rebase/merge/etc.\ncommands), then you can use `git add --sparse $FILENAME`.\n\n> Investigations:\n> 1. Stack trace:\n> add.c: cmd_add\n> -> add.c: prune_directory\n> -> pathspec.c: add_pathspec_matches_against_index\n> -> dir.c: path_in_sparse_checkout_1\n> 2. In Git 2.33.3, the loop at pathspec.c line 42 runs\n> fast, even when istate->cache_nr is at 2 million\n> 3. Since Git 2.34.3, the newly introduced 'audit for\n> interaction with sparse-index' (dir.c line 1459:\n> path_in_sparse_checkout_1) decides to loop through 2 million files and\n> match each one of them against the sparse-checkout patterns\n> 4. This hits the O(n^2) problem thus causes 'git add' to\n> hang (or ~1.5 hours to finish)\n>\n> Please help us take a look at this issue and let us know if you need\n> more information.\n\nI'm also curious if you can use --cone mode in sparse-checkout. The\nO(N*M) behavior of sparse checkouts in non-cone mode is pretty\nfundamental, and we may need to add additional paths checking the\nsparsity patterns (i.e. more O(N*M) codepaths) to fix various\nuser-observed bugs. Usage of --cone mode drops all of these to a\nlinear cost.\n"},{"id":"458157","messageId":"CABPp-BHv3TSJhnWSF8AjF_nr72vMnOFXZJKoG0juGwjz13TZ=w@mail.gmail.com","threadId":"58086","inReplyTo":"96034b3f-9811-38c1-7afe-c1c9dd243f0e@github.com","subject":"Re: git bug report: 'git add' hangs in a large repo which has sparse-checkout file with large number of patterns in it","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-06-30T04:06:14Z","receivedAt":"2022-06-30T04:06:30Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Jun 29, 2022 at 3:04 PM Victoria Dye wrote:\n>\n> Dian Xu wrote:\n> > Dear Git developers,\n> >\n> > Reporting Issue:\n> > 'git add' hangs in a large repo which has\n> > sparse-checkout file with large number of patterns in it\n> >\n> > Found in:\n> > Git 2.34.3. Issue occurs after 'audit for interaction\n> > with sparse-index' was introduced in add.c\n> >\n> > Reproduction steps:\n> > 1. Clone a repo which has e.g. 2 million plus files\n> > 2. Enable sparse checkout by: git config core.sparsecheckout true\n> > 3. Create a .git/info/sparse-checkout file with a large\n> > number of patterns, e.g. 16k plus lines\n> > 4. Run 'git add', which will hang>\n> > Investigations:\n> > 1. Stack trace:\n> > add.c: cmd_add\n> > -> add.c: prune_directory\n> > -> pathspec.c: add_pathspec_matches_against_index\n> > -> dir.c: path_in_sparse_checkout_1\n> > 2. In Git 2.33.3, the loop at pathspec.c line 42 runs\n> > fast, even when istate->cache_nr is at 2 million\n> > 3. Since Git 2.34.3, the newly introduced 'audit for\n> > interaction with sparse-index' (dir.c line 1459:\n> > path_in_sparse_checkout_1) decides to loop through 2 million files and\n> > match each one of them against the sparse-checkout patterns\n> > 4. This hits the O(n^2) problem thus causes 'git add' to\n> > hang (or ~1.5 hours to finish)\n>\n> Thanks for the explanation, it helped me narrow down the source to an exact\n> commit (49fdd51a23 (add: skip tracked paths outside sparse-checkout cone,\n> 2021-09-24)).\n>\n> You're correct that the `path_in_sparse_checkout()` check is slow [1].\n> However, it only runs on files that are not \"hidden\" with the\n> `SKIP_WORKTREE` flag. Ideally, if you're using sparse-checkout, this will\n> only be a small subset of your 2 million files.\n>\n> In your repro steps, you're adding patterns to a file then immediately\n> running `git add`. If that reflects how you're usually working with\n> sparse-checkout, `SKIP_WORKTREE` likely isn't being applied properly before\n> the `add`. You can check to see whether file(s) have the flag properly\n> applied with `git ls-files -t ` - each `SKIP_WORKTREE`\n> file should have an \"S\" next to it. \"H\" indicates that the flag is *not*\n> applied.\n>\n> If you see that most of the files that *should* be sparse don't have\n> `SKIP_WORKTREE` applied, you can run `git sparse-checkout reapply` (make\n> sure you don't have any modified files outside the patterns you're\n> applying!). The downside is that it'll be as slow as what you're reporting\n> for `git add`, but any subsequent `add` (or reset, status, etc.) should be\n> much faster.\n>\n> If you do all of that but things are still slow, then the way we check\n> pathspecs in `git add` would need to change (not trivial, but probably not\n> impossible either). At a cursory glance, I can think of a few options for\n> that:\n>\n> 1. Remove the `path_in_sparse_checkout()` check. It's the simplest solution,\n> but it means you'd be able to stage files for commit outside the\n> sparse-checkout patterns without using the '--sparse' option. I don't\n> personally think that's a huge issue, but given that the implementation\n> was intentionally changed *away* from this approach, I'd defer to other\n> contributors to see if that's an okay change to make.\n\nI'm strongly against this. This just restores the original bug we\nwere trying to fix, attempts to paper over the fact that non-cone mode\nis fundamentally O(N*M) in one small instance, and sets the precedent\nthat we can't fix further sparse-checkout-based usability bugs because\nit might add performance bottlenecks in additional places given\nnon-cone-mode's fundamental performance design problem. We should\ninstead (in rough priority order)\n\n* encourage people to adopt cone mode\n* discourage people still using non-cone mode from having lots of patterns\n* make sure people aren't misusing things (the lack of a `git\nread-tree -mu HEAD` or `git sparse-checkout reapply` seemed very\nsuspicious)\n* educate people that non-cone mode is just fundamentally slow, among\nother problems, and that the slowness might appear in additional\nplaces in the future as we fix various usability issues.\n* provide workarounds users can adopt if they really want to persist\nwith non-cone mode with lots of patterns (e.g. add \"--sparse\" to their\n\"git add\" commands), though warn them about the possible side effects\nthey'll face (the added files can seemingly randomly disappear in the\nworking tree with future checkout/pull/merge/rebase/reset/etc commands\nif the added files don't match the sparsity patterns).\n* investigate ways to optimize the code to lower the constant in the\nO(N*M) behavior on a case-by-case basis\n\nWe deprecated non-cone mode in v2.37 in part because of this type of\nissue, and I really don't want the see the deprecated side of things\ndictating how commands work for the now-default mode.\n\n> 2. After every call to `ce_path_match()`, check if all pathspecs are marked\n> as `seen` and, if so, return early. This would slow down each individual\n> file check and wouldn't help you if a pathspec matches nothing, but\n> prevents checking more files once all pathspecs are matched.\n\nMight be interesting. Would need some careful measurements and\nattempts to validate how often all pathspecs are matched early in some\nkind of way, because this would definitely slow down some cases and\nspeed others up, but I don't have a good feel for which side happens\nmore frequently in practice.\n\n> 3. Do some heuristic checks on the pathspecs before checking index entries.\n> For example, exact file or directory matches could be searched in the\n> index. This would still require falling back on the per-file checks if\n> not all pathspecs are matched, but makes some typical use-cases much\n> faster.\n\nI'm confused. \"before checking index entries\", you're checking things\n(namely, exact file or directory matches) \"in the index\"?\n\n> There are almost certainly other options, and I can dig around `add.c` more\n> to see if there's anything I'm missing (although I'd love to hear other\n> ideas too!).\n>\n> Hopefully this helps!\n> - Victoria\n>\n> [1] `path_in_sparse_checkout()` is significantly faster in cone mode, but\n> with 16k patterns I'm assuming you're not using cone patterns ;)\n>\n> >\n> > Please help us take a look at this issue and let us know if you need\n> > more information.\n> >\n> > Thanks,\n> >\n> > Dian Xu\n> > Mathworks, Inc\n> > 1 Lakeside Campus Drive, Natick, MA 01760\n> > 508-647-3583\n>\n"},{"id":"458158","messageId":"c5662c60-4a21-be94-8fe0-13c6730292dd@github.com","threadId":"58086","inReplyTo":"CABPp-BHv3TSJhnWSF8AjF_nr72vMnOFXZJKoG0juGwjz13TZ=w@mail.gmail.com","subject":"Re: git bug report: 'git add' hangs in a large repo which has sparse-checkout file with large number of patterns in it","fromName":"Victoria Dye","fromEmail":"vdye@github.com","sentAt":"2022-06-30T05:06:39Z","receivedAt":"2022-06-30T05:06:45Z","isPatch":false,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"Elijah Newren wrote:\n> On Wed, Jun 29, 2022 at 3:04 PM Victoria Dye wrote:\n>>\n>> Dian Xu wrote:\n>>> Dear Git developers,\n>>>\n>>> Reporting Issue:\n>>> 'git add' hangs in a large repo which has\n>>> sparse-checkout file with large number of patterns in it\n>>>\n>>> Found in:\n>>> Git 2.34.3. Issue occurs after 'audit for interaction\n>>> with sparse-index' was introduced in add.c\n>>>\n>>> Reproduction steps:\n>>> 1. Clone a repo which has e.g. 2 million plus files\n>>> 2. Enable sparse checkout by: git config core.sparsecheckout true\n>>> 3. Create a .git/info/sparse-checkout file with a large\n>>> number of patterns, e.g. 16k plus lines\n>>> 4. Run 'git add', which will hang>\n>>> Investigations:\n>>> 1. Stack trace:\n>>> add.c: cmd_add\n>>> -> add.c: prune_directory\n>>> -> pathspec.c: add_pathspec_matches_against_index\n>>> -> dir.c: path_in_sparse_checkout_1\n>>> 2. In Git 2.33.3, the loop at pathspec.c line 42 runs\n>>> fast, even when istate->cache_nr is at 2 million\n>>> 3. Since Git 2.34.3, the newly introduced 'audit for\n>>> interaction with sparse-index' (dir.c line 1459:\n>>> path_in_sparse_checkout_1) decides to loop through 2 million files and\n>>> match each one of them against the sparse-checkout patterns\n>>> 4. This hits the O(n^2) problem thus causes 'git add' to\n>>> hang (or ~1.5 hours to finish)\n>>\n>> Thanks for the explanation, it helped me narrow down the source to an exact\n>> commit (49fdd51a23 (add: skip tracked paths outside sparse-checkout cone,\n>> 2021-09-24)).\n>>\n>> You're correct that the `path_in_sparse_checkout()` check is slow [1].\n>> However, it only runs on files that are not \"hidden\" with the\n>> `SKIP_WORKTREE` flag. Ideally, if you're using sparse-checkout, this will\n>> only be a small subset of your 2 million files.\n>>\n>> In your repro steps, you're adding patterns to a file then immediately\n>> running `git add`. If that reflects how you're usually working with\n>> sparse-checkout, `SKIP_WORKTREE` likely isn't being applied properly before\n>> the `add`. You can check to see whether file(s) have the flag properly\n>> applied with `git ls-files -t ` - each `SKIP_WORKTREE`\n>> file should have an \"S\" next to it. \"H\" indicates that the flag is *not*\n>> applied.\n>>\n>> If you see that most of the files that *should* be sparse don't have\n>> `SKIP_WORKTREE` applied, you can run `git sparse-checkout reapply` (make\n>> sure you don't have any modified files outside the patterns you're\n>> applying!). The downside is that it'll be as slow as what you're reporting\n>> for `git add`, but any subsequent `add` (or reset, status, etc.) should be\n>> much faster.\n>>\n>> If you do all of that but things are still slow, then the way we check\n>> pathspecs in `git add` would need to change (not trivial, but probably not\n>> impossible either). At a cursory glance, I can think of a few options for\n>> that:\n>>\n>> 1. Remove the `path_in_sparse_checkout()` check. It's the simplest solution,\n>> but it means you'd be able to stage files for commit outside the\n>> sparse-checkout patterns without using the '--sparse' option. I don't\n>> personally think that's a huge issue, but given that the implementation\n>> was intentionally changed *away* from this approach, I'd defer to other\n>> contributors to see if that's an okay change to make.\n> \n> I'm strongly against this. This just restores the original bug we\n> were trying to fix, attempts to paper over the fact that non-cone mode\n> is fundamentally O(N*M) in one small instance, and sets the precedent\n> that we can't fix further sparse-checkout-based usability bugs because\n> it might add performance bottlenecks in additional places given\n> non-cone-mode's fundamental performance design problem. We should\n> instead (in rough priority order)\n\nI'm not sure what the bug was - although I can (and should) read through the\nlist archive to find out - but the rest of your point is convincing enough\non its own. Even if we sacrificed correctness for performance in this one\ncase, there are countless other places in the code like it, and changing all\nof them could seriously hurt user experience in other ways.\n\nThanks for your perspective!\n\n> \n> * encourage people to adopt cone mode\n> * discourage people still using non-cone mode from having lots of patterns\n\nWhile I know these are the recommended best practice, I do want to\nacknowledge that switching to cone mode in some repositories is a huge lift\nor otherwise infeasible [1]. While people make that transition (if they even\ncan), I don't think it's unreasonable to look for ways to improve\nperformance in non-cone sparse checkout, especially if those performance\ngains can also be realized in cone mode.\n\n[1] https://lore.kernel.org/git/nycvar.QRO.7.76.6.2205212347060.352@tvgsbejvaqbjf.bet/\n\n> * make sure people aren't misusing things (the lack of a `git\n> read-tree -mu HEAD` or `git sparse-checkout reapply` seemed very\n> suspicious)\n\nA warning if a particular git operation sees a lot of out-of-cone\nnon-`SKIP_WORKTREE` files might help with this (and would be especially\nimpactful for someone working with a sparse index). I'm not sure how to\nquantify \"a lot\", though.\n\n> * educate people that non-cone mode is just fundamentally slow, among\n> other problems, and that the slowness might appear in additional\n> places in the future as we fix various usability issues.\n> * provide workarounds users can adopt if they really want to persist\n> with non-cone mode with lots of patterns (e.g. add \"--sparse\" to their\n> \"git add\" commands), though warn them about the possible side effects\n> they'll face (the added files can seemingly randomly disappear in the\n> working tree with future checkout/pull/merge/rebase/reset/etc commands\n> if the added files don't match the sparsity patterns).\n> * investigate ways to optimize the code to lower the constant in the\n> O(N*M) behavior on a case-by-case basis\n> \n> We deprecated non-cone mode in v2.37 in part because of this type of\n> issue, and I really don't want the see the deprecated side of things\n> dictating how commands work for the now-default mode.\n> \n>> 2. After every call to `ce_path_match()`, check if all pathspecs are marked\n>> as `seen` and, if so, return early. This would slow down each individual\n>> file check and wouldn't help you if a pathspec matches nothing, but\n>> prevents checking more files once all pathspecs are matched.\n> \n> Might be interesting. Would need some careful measurements and\n> attempts to validate how often all pathspecs are matched early in some\n> kind of way, because this would definitely slow down some cases and\n> speed others up, but I don't have a good feel for which side happens\n> more frequently in practice.\n> \n>> 3. Do some heuristic checks on the pathspecs before checking index entries.\n>> For example, exact file or directory matches could be searched in the\n>> index. This would still require falling back on the per-file checks if\n>> not all pathspecs are matched, but makes some typical use-cases much\n>> faster.\n> \n> I'm confused. \"before checking index entries\", you're checking things\n> (namely, exact file or directory matches) \"in the index\"?\n\nSorry, I definitely wasn't clear. I mean \"perform heuristic checks *per\npathspec item* before iterating *per index entry*.\" Pathspecs used in `git\nadd` are (at least in my experience) pretty small, so there could be\nperformance gains if all the items can be marked `seen` without iterating\nover every entry of the index. I was thinking something like\n`pathspec_needs_expanded_index()` in `reset` (4d1cfc1351 (reset: make\n--mixed sparse-aware, 2021-11-29)), but tailored to this particular case.\n\n> \n>> There are almost certainly other options, and I can dig around `add.c` more\n>> to see if there's anything I'm missing (although I'd love to hear other\n>> ideas too!).\n>>\n>> Hopefully this helps!\n>> - Victoria\n>>\n>> [1] `path_in_sparse_checkout()` is significantly faster in cone mode, but\n>> with 16k patterns I'm assuming you're not using cone patterns ;)\n>>\n>>>\n>>> Please help us take a look at this issue and let us know if you need\n>>> more information.\n>>>\n>>> Thanks,\n>>>\n>>> Dian Xu\n>>> Mathworks, Inc\n>>> 1 Lakeside Campus Drive, Natick, MA 01760\n>>> 508-647-3583\n>>\n\n"},{"id":"458331","messageId":"CABPp-BFRHjF7+9T8dGG=ixsezksZUNU7pm29MG2kcLEYwE06Og@mail.gmail.com","threadId":"58086","inReplyTo":"c5662c60-4a21-be94-8fe0-13c6730292dd@github.com","subject":"Re: git bug report: 'git add' hangs in a large repo which has sparse-checkout file with large number of patterns in it","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-07-01T03:42:35Z","receivedAt":"2022-07-01T03:44:34Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Jun 29, 2022 at 10:06 PM Victoria Dye wrote:\n>\n> Elijah Newren wrote:\n> > On Wed, Jun 29, 2022 at 3:04 PM Victoria Dye wrote:\n> >>\n> >> Dian Xu wrote:\n> >>> Dear Git developers,\n> >>>\n> >>> Reporting Issue:\n> >>> 'git add' hangs in a large repo which has\n> >>> sparse-checkout file with large number of patterns in it\n> >>>\n> >>> Found in:\n> >>> Git 2.34.3. Issue occurs after 'audit for interaction\n> >>> with sparse-index' was introduced in add.c\n> >>>\n> >>> Reproduction steps:\n> >>> 1. Clone a repo which has e.g. 2 million plus files\n> >>> 2. Enable sparse checkout by: git config core.sparsecheckout true\n> >>> 3. Create a .git/info/sparse-checkout file with a large\n> >>> number of patterns, e.g. 16k plus lines\n> >>> 4. Run 'git add', which will hang>\n> >>> Investigations:\n> >>> 1. Stack trace:\n> >>> add.c: cmd_add\n> >>> -> add.c: prune_directory\n> >>> -> pathspec.c: add_pathspec_matches_against_index\n> >>> -> dir.c: path_in_sparse_checkout_1\n> >>> 2. In Git 2.33.3, the loop at pathspec.c line 42 runs\n> >>> fast, even when istate->cache_nr is at 2 million\n> >>> 3. Since Git 2.34.3, the newly introduced 'audit for\n> >>> interaction with sparse-index' (dir.c line 1459:\n> >>> path_in_sparse_checkout_1) decides to loop through 2 million files and\n> >>> match each one of them against the sparse-checkout patterns\n> >>> 4. This hits the O(n^2) problem thus causes 'git add' to\n> >>> hang (or ~1.5 hours to finish)\n> >>\n> >> Thanks for the explanation, it helped me narrow down the source to an exact\n> >> commit (49fdd51a23 (add: skip tracked paths outside sparse-checkout cone,\n> >> 2021-09-24)).\n> >>\n> >> You're correct that the `path_in_sparse_checkout()` check is slow [1].\n> >> However, it only runs on files that are not \"hidden\" with the\n> >> `SKIP_WORKTREE` flag. Ideally, if you're using sparse-checkout, this will\n> >> only be a small subset of your 2 million files.\n> >>\n> >> In your repro steps, you're adding patterns to a file then immediately\n> >> running `git add`. If that reflects how you're usually working with\n> >> sparse-checkout, `SKIP_WORKTREE` likely isn't being applied properly before\n> >> the `add`. You can check to see whether file(s) have the flag properly\n> >> applied with `git ls-files -t ` - each `SKIP_WORKTREE`\n> >> file should have an \"S\" next to it. \"H\" indicates that the flag is *not*\n> >> applied.\n> >>\n> >> If you see that most of the files that *should* be sparse don't have\n> >> `SKIP_WORKTREE` applied, you can run `git sparse-checkout reapply` (make\n> >> sure you don't have any modified files outside the patterns you're\n> >> applying!). The downside is that it'll be as slow as what you're reporting\n> >> for `git add`, but any subsequent `add` (or reset, status, etc.) should be\n> >> much faster.\n> >>\n> >> If you do all of that but things are still slow, then the way we check\n> >> pathspecs in `git add` would need to change (not trivial, but probably not\n> >> impossible either). At a cursory glance, I can think of a few options for\n> >> that:\n> >>\n> >> 1. Remove the `path_in_sparse_checkout()` check. It's the simplest solution,\n> >> but it means you'd be able to stage files for commit outside the\n> >> sparse-checkout patterns without using the '--sparse' option. I don't\n> >> personally think that's a huge issue, but given that the implementation\n> >> was intentionally changed *away* from this approach, I'd defer to other\n> >> contributors to see if that's an okay change to make.\n> >\n> > I'm strongly against this. This just restores the original bug we\n> > were trying to fix, attempts to paper over the fact that non-cone mode\n> > is fundamentally O(N*M) in one small instance, and sets the precedent\n> > that we can't fix further sparse-checkout-based usability bugs because\n> > it might add performance bottlenecks in additional places given\n> > non-cone-mode's fundamental performance design problem. We should\n> > instead (in rough priority order)\n>\n> I'm not sure what the bug was - although I can (and should) read through the\n> list archive to find out - but the rest of your point is convincing enough\n> on its own. Even if we sacrificed correctness for performance in this one\n> case, there are countless other places in the code like it, and changing all\n> of them could seriously hurt user experience in other ways.\n>\n> Thanks for your perspective!\n\n:-)\n\n> >\n> > * encourage people to adopt cone mode\n> > * discourage people still using non-cone mode from having lots of patterns\n>\n> While I know these are the recommended best practice, I do want to\n> acknowledge that switching to cone mode in some repositories is a huge lift\n> or otherwise infeasible [1]. While people make that transition (if they even\n> can), I don't think it's unreasonable to look for ways to improve\n> performance in non-cone sparse checkout, especially if those performance\n> gains can also be realized in cone mode.\n>\n> [1] https://lore.kernel.org/git/nycvar.QRO.7.76.6.2205212347060.352@tvgsbejvaqbjf.bet/\n\nYep, very good point. These dovetail with why I used \"encourage\" and\n\"discourage\", and with why I had several more things that should be\ndone in my list, including performance work. I know that non-cone\nmode is important to still support.\n\nBut I would also like to point out that folks sometimes aren't\nadopting cone mode out of inertia or bad assumptions about how cone\nmode operates, rather than having sound reasons. In fact, I've even\nseen them describe conditions that sound like a perfect fit for cone\nmode and yet use their described usecase as rationale to _not_ use\ncone mode simply because they assume cone mode does something other\nthan what it really does. (See\nhttps://lore.kernel.org/git/CABPp-BEwMAPHGt5xD9jDU58grbrAqCdqNY9Nh8UJGLKuLbArXQ@mail.gmail.com/\nand the previous email in that thread for an example). If even other\nGit developers do that, that suggests we do need to probe a bit and\nsee if people can switch instead of just accepting they are one of the\ncases that can't. We still have some education work to do.\n\n> > * make sure people aren't misusing things (the lack of a `git\n> > read-tree -mu HEAD` or `git sparse-checkout reapply` seemed very\n> > suspicious)\n>\n> A warning if a particular git operation sees a lot of out-of-cone\n> non-`SKIP_WORKTREE` files might help with this (and would be especially\n> impactful for someone working with a sparse index). I'm not sure how to\n> quantify \"a lot\", though.\n\nYeah, this kind of reminds me of the present-despite-skipped check we\nadded. Adding something like that which always runs is probably a\nno-go, though, since this additional check would be much more\nexpensive than the present-despite-skipped one. And, like you, I'm\nalso a little unsure how to quantify \"a lot\".\n\nHowever, perhaps there's a way to tackle this problem from a different\nangle. I just noticed that the only place outside of the \"git\nsparse-checkout\" command that sparse checkouts are documented, in\ngit-read-tree(1), that it didn't bother to give a list of steps for\nemploying sparse-checkouts and that people have to figure it out by\ntrial and error. (Or read a random mailing list post or commit\nmessage like 94c0956b60 (sparse-checkout: create builtin with 'list'\nsubcommand, 2019-11-21)). So perhaps it's not surprising that users\nmiss one of the crucial steps. Perhaps if we fix that documentation\nto mention the necessary steps (\"git config core.sparseCheckout true\",\npopulate $GIT_DIR/info/sparse-checkout, then either run \"git read-tree\n-mu HEAD\" or \"git sparse-checkout reapply\"), then users can discover\nand make sure to do all the steps instead of just a subset?\n\n> > * educate people that non-cone mode is just fundamentally slow, among\n> > other problems, and that the slowness might appear in additional\n> > places in the future as we fix various usability issues.\n> > * provide workarounds users can adopt if they really want to persist\n> > with non-cone mode with lots of patterns (e.g. add \"--sparse\" to their\n> > \"git add\" commands), though warn them about the possible side effects\n> > they'll face (the added files can seemingly randomly disappear in the\n> > working tree with future checkout/pull/merge/rebase/reset/etc commands\n> > if the added files don't match the sparsity patterns).\n> > * investigate ways to optimize the code to lower the constant in the\n> > O(N*M) behavior on a case-by-case basis\n> >\n> > We deprecated non-cone mode in v2.37 in part because of this type of\n> > issue, and I really don't want the see the deprecated side of things\n> > dictating how commands work for the now-default mode.\n> >\n> >> 2. After every call to `ce_path_match()`, check if all pathspecs are marked\n> >> as `seen` and, if so, return early. This would slow down each individual\n> >> file check and wouldn't help you if a pathspec matches nothing, but\n> >> prevents checking more files once all pathspecs are matched.\n> >\n> > Might be interesting. Would need some careful measurements and\n> > attempts to validate how often all pathspecs are matched early in some\n> > kind of way, because this would definitely slow down some cases and\n> > speed others up, but I don't have a good feel for which side happens\n> > more frequently in practice.\n> >\n> >> 3. Do some heuristic checks on the pathspecs before checking index entries.\n> >> For example, exact file or directory matches could be searched in the\n> >> index. This would still require falling back on the per-file checks if\n> >> not all pathspecs are matched, but makes some typical use-cases much\n> >> faster.\n> >\n> > I'm confused. \"before checking index entries\", you're checking things\n> > (namely, exact file or directory matches) \"in the index\"?\n>\n> Sorry, I definitely wasn't clear. I mean \"perform heuristic checks *per\n> pathspec item* before iterating *per index entry*.\" Pathspecs used in `git\n> add` are (at least in my experience) pretty small, so there could be\n> performance gains if all the items can be marked `seen` without iterating\n> over every entry of the index. I was thinking something like\n> `pathspec_needs_expanded_index()` in `reset` (4d1cfc1351 (reset: make\n> --mixed sparse-aware, 2021-11-29)), but tailored to this particular case.\n\nAh, okay makes sense now.\n\n\n\n\n\n>\n> >\n> >> There are almost certainly other options, and I can dig around `add.c` more\n> >> to see if there's anything I'm missing (although I'd love to hear other\n> >> ideas too!).\n> >>\n> >> Hopefully this helps!\n> >> - Victoria\n> >>\n> >> [1] `path_in_sparse_checkout()` is significantly faster in cone mode, but\n> >> with 16k patterns I'm assuming you're not using cone patterns ;)\n> >>\n> >>>\n> >>> Please help us take a look at this issue and let us know if you need\n> >>> more information.\n> >>>\n> >>> Thanks,\n> >>>\n> >>> Dian Xu\n> >>> Mathworks, Inc\n> >>> 1 Lakeside Campus Drive, Natick, MA 01760\n> >>> 508-647-3583\n> >>\n>\n"},{"id":"458414","messageId":"CAKSRnEx2seC41QCe8sQOPf0=VNqHB6GkZ3M_CpGmOZRS0FS1gA@mail.gmail.com","threadId":"58086","inReplyTo":"CABPp-BFRHjF7+9T8dGG=ixsezksZUNU7pm29MG2kcLEYwE06Og@mail.gmail.com","subject":"Re: git bug report: 'git add' hangs in a large repo which has sparse-checkout file with large number of patterns in it","fromName":"Dian Xu","fromEmail":"dianxudev@gmail.com","sentAt":"2022-07-01T20:24:36Z","receivedAt":"2022-07-01T20:24:58Z","isPatch":false,"sender":{"key":"dianxudev@gmail.com","avatar":null},"body":"Hi Victoria, Elijah, Derrick,\n\nThanks a lot for the detailed insight.\n\n(Btw our company’s email mathworks.com is blocked by\nmailto:git@vger.kernel.org, hope someone can help take a look)\n\n1. We use a no-cone version of sparse-checkout to control the 'shape'\n(set of scm files) of our source code. In this case, the local sandbox\nis not necessarily 'sparse' (2m files), but it's very convenient that\nwe can use git to check out the exact amount (shape) of files. To\nVictoria's question, all these 2m files are \"H\".\n\n2. Below is the detail steps to create the local repo (sparse-checkout\nwas defined 'before' git checkout)\n % git init\n % git remote add origin \n % git config core.sparsecheckout true\n % vi .git/info/sparse-checkout\n % git fetch\n % git checkout -b \n Do I still need to 'git sparse-checkout reapply' after checkout?\n(Thanks for pointing out to run reapply once .git/info/sparse-checkout\nchanged)\n\n3. Unfortunately, after executing reapply (btw it is very slow on this\n2m files * 16k patterns scenario: 30 mins), 'git add', and 'git add\n--sparse' still hangs.\n\n4. --cone is a big topic for us now, since 2.37.0 deprecates\n--no-cone. We do have our own challenges to move away from --no-cone\n(E.g. we use lots of file specifiers and/or exclusion patterns to\ndefine our source code shape), which will be a huge amount of work, if\nfeasible. We've established a set of workflows based on --no-cone,\nbecause of its merit of being capable of defining a fine-grained scm\nshape.\n\n5. Back to this case, what we've experimented on are:\n - Remove all files/*/! patterns from our shape definition, which\nleave us with 14k directories (Obviously the scm shape no longe\nmatches, but just to proof of concept here)\n - 'git sparse-checkout set <14k directories>' finishes fast\n - 'git add' finishes fast\n As Victoria mentioned, I hope this --no-cone 'git add' performance\ncan be addressed because 'those performance gains can also be realized\nin cone mode', as we saw here.\n\nAgain thank you for your help and looking forward to your thoughts.\n\nThanks,\n\nDian Xu\nMathworks, Inc\n1 Lakeside Campus Drive, Natick, MA 01760\n508-647-3583\n\nOn Thu, Jun 30, 2022 at 11:42 PM Elijah Newren wrote:\n>\n> On Wed, Jun 29, 2022 at 10:06 PM Victoria Dye wrote:\n> >\n> > Elijah Newren wrote:\n> > > On Wed, Jun 29, 2022 at 3:04 PM Victoria Dye wrote:\n> > >>\n> > >> Dian Xu wrote:\n> > >>> Dear Git developers,\n> > >>>\n> > >>> Reporting Issue:\n> > >>> 'git add' hangs in a large repo which has\n> > >>> sparse-checkout file with large number of patterns in it\n> > >>>\n> > >>> Found in:\n> > >>> Git 2.34.3. Issue occurs after 'audit for interaction\n> > >>> with sparse-index' was introduced in add.c\n> > >>>\n> > >>> Reproduction steps:\n> > >>> 1. Clone a repo which has e.g. 2 million plus files\n> > >>> 2. Enable sparse checkout by: git config core.sparsecheckout true\n> > >>> 3. Create a .git/info/sparse-checkout file with a large\n> > >>> number of patterns, e.g. 16k plus lines\n> > >>> 4. Run 'git add', which will hang>\n> > >>> Investigations:\n> > >>> 1. Stack trace:\n> > >>> add.c: cmd_add\n> > >>> -> add.c: prune_directory\n> > >>> -> pathspec.c: add_pathspec_matches_against_index\n> > >>> -> dir.c: path_in_sparse_checkout_1\n> > >>> 2. In Git 2.33.3, the loop at pathspec.c line 42 runs\n> > >>> fast, even when istate->cache_nr is at 2 million\n> > >>> 3. Since Git 2.34.3, the newly introduced 'audit for\n> > >>> interaction with sparse-index' (dir.c line 1459:\n> > >>> path_in_sparse_checkout_1) decides to loop through 2 million files and\n> > >>> match each one of them against the sparse-checkout patterns\n> > >>> 4. This hits the O(n^2) problem thus causes 'git add' to\n> > >>> hang (or ~1.5 hours to finish)\n> > >>\n> > >> Thanks for the explanation, it helped me narrow down the source to an exact\n> > >> commit (49fdd51a23 (add: skip tracked paths outside sparse-checkout cone,\n> > >> 2021-09-24)).\n> > >>\n> > >> You're correct that the `path_in_sparse_checkout()` check is slow [1].\n> > >> However, it only runs on files that are not \"hidden\" with the\n> > >> `SKIP_WORKTREE` flag. Ideally, if you're using sparse-checkout, this will\n> > >> only be a small subset of your 2 million files.\n> > >>\n> > >> In your repro steps, you're adding patterns to a file then immediately\n> > >> running `git add`. If that reflects how you're usually working with\n> > >> sparse-checkout, `SKIP_WORKTREE` likely isn't being applied properly before\n> > >> the `add`. You can check to see whether file(s) have the flag properly\n> > >> applied with `git ls-files -t ` - each `SKIP_WORKTREE`\n> > >> file should have an \"S\" next to it. \"H\" indicates that the flag is *not*\n> > >> applied.\n> > >>\n> > >> If you see that most of the files that *should* be sparse don't have\n> > >> `SKIP_WORKTREE` applied, you can run `git sparse-checkout reapply` (make\n> > >> sure you don't have any modified files outside the patterns you're\n> > >> applying!). The downside is that it'll be as slow as what you're reporting\n> > >> for `git add`, but any subsequent `add` (or reset, status, etc.) should be\n> > >> much faster.\n> > >>\n> > >> If you do all of that but things are still slow, then the way we check\n> > >> pathspecs in `git add` would need to change (not trivial, but probably not\n> > >> impossible either). At a cursory glance, I can think of a few options for\n> > >> that:\n> > >>\n> > >> 1. Remove the `path_in_sparse_checkout()` check. It's the simplest solution,\n> > >> but it means you'd be able to stage files for commit outside the\n> > >> sparse-checkout patterns without using the '--sparse' option. I don't\n> > >> personally think that's a huge issue, but given that the implementation\n> > >> was intentionally changed *away* from this approach, I'd defer to other\n> > >> contributors to see if that's an okay change to make.\n> > >\n> > > I'm strongly against this. This just restores the original bug we\n> > > were trying to fix, attempts to paper over the fact that non-cone mode\n> > > is fundamentally O(N*M) in one small instance, and sets the precedent\n> > > that we can't fix further sparse-checkout-based usability bugs because\n> > > it might add performance bottlenecks in additional places given\n> > > non-cone-mode's fundamental performance design problem. We should\n> > > instead (in rough priority order)\n> >\n> > I'm not sure what the bug was - although I can (and should) read through the\n> > list archive to find out - but the rest of your point is convincing enough\n> > on its own. Even if we sacrificed correctness for performance in this one\n> > case, there are countless other places in the code like it, and changing all\n> > of them could seriously hurt user experience in other ways.\n> >\n> > Thanks for your perspective!\n>\n> :-)\n>\n> > >\n> > > * encourage people to adopt cone mode\n> > > * discourage people still using non-cone mode from having lots of patterns\n> >\n> > While I know these are the recommended best practice, I do want to\n> > acknowledge that switching to cone mode in some repositories is a huge lift\n> > or otherwise infeasible [1]. While people make that transition (if they even\n> > can), I don't think it's unreasonable to look for ways to improve\n> > performance in non-cone sparse checkout, especially if those performance\n> > gains can also be realized in cone mode.\n> >\n> > [1] https://lore.kernel.org/git/nycvar.QRO.7.76.6.2205212347060.352@tvgsbejvaqbjf.bet/\n>\n> Yep, very good point. These dovetail with why I used \"encourage\" and\n> \"discourage\", and with why I had several more things that should be\n> done in my list, including performance work. I know that non-cone\n> mode is important to still support.\n>\n> But I would also like to point out that folks sometimes aren't\n> adopting cone mode out of inertia or bad assumptions about how cone\n> mode operates, rather than having sound reasons. In fact, I've even\n> seen them describe conditions that sound like a perfect fit for cone\n> mode and yet use their described usecase as rationale to _not_ use\n> cone mode simply because they assume cone mode does something other\n> than what it really does. (See\n> https://lore.kernel.org/git/CABPp-BEwMAPHGt5xD9jDU58grbrAqCdqNY9Nh8UJGLKuLbArXQ@mail.gmail.com/\n> and the previous email in that thread for an example). If even other\n> Git developers do that, that suggests we do need to probe a bit and\n> see if people can switch instead of just accepting they are one of the\n> cases that can't. We still have some education work to do.\n>\n> > > * make sure people aren't misusing things (the lack of a `git\n> > > read-tree -mu HEAD` or `git sparse-checkout reapply` seemed very\n> > > suspicious)\n> >\n> > A warning if a particular git operation sees a lot of out-of-cone\n> > non-`SKIP_WORKTREE` files might help with this (and would be especially\n> > impactful for someone working with a sparse index). I'm not sure how to\n> > quantify \"a lot\", though.\n>\n> Yeah, this kind of reminds me of the present-despite-skipped check we\n> added. Adding something like that which always runs is probably a\n> no-go, though, since this additional check would be much more\n> expensive than the present-despite-skipped one. And, like you, I'm\n> also a little unsure how to quantify \"a lot\".\n>\n> However, perhaps there's a way to tackle this problem from a different\n> angle. I just noticed that the only place outside of the \"git\n> sparse-checkout\" command that sparse checkouts are documented, in\n> git-read-tree(1), that it didn't bother to give a list of steps for\n> employing sparse-checkouts and that people have to figure it out by\n> trial and error. (Or read a random mailing list post or commit\n> message like 94c0956b60 (sparse-checkout: create builtin with 'list'\n> subcommand, 2019-11-21)). So perhaps it's not surprising that users\n> miss one of the crucial steps. Perhaps if we fix that documentation\n> to mention the necessary steps (\"git config core.sparseCheckout true\",\n> populate $GIT_DIR/info/sparse-checkout, then either run \"git read-tree\n> -mu HEAD\" or \"git sparse-checkout reapply\"), then users can discover\n> and make sure to do all the steps instead of just a subset?\n>\n> > > * educate people that non-cone mode is just fundamentally slow, among\n> > > other problems, and that the slowness might appear in additional\n> > > places in the future as we fix various usability issues.\n> > > * provide workarounds users can adopt if they really want to persist\n> > > with non-cone mode with lots of patterns (e.g. add \"--sparse\" to their\n> > > \"git add\" commands), though warn them about the possible side effects\n> > > they'll face (the added files can seemingly randomly disappear in the\n> > > working tree with future checkout/pull/merge/rebase/reset/etc commands\n> > > if the added files don't match the sparsity patterns).\n> > > * investigate ways to optimize the code to lower the constant in the\n> > > O(N*M) behavior on a case-by-case basis\n> > >\n> > > We deprecated non-cone mode in v2.37 in part because of this type of\n> > > issue, and I really don't want the see the deprecated side of things\n> > > dictating how commands work for the now-default mode.\n> > >\n> > >> 2. After every call to `ce_path_match()`, check if all pathspecs are marked\n> > >> as `seen` and, if so, return early. This would slow down each individual\n> > >> file check and wouldn't help you if a pathspec matches nothing, but\n> > >> prevents checking more files once all pathspecs are matched.\n> > >\n> > > Might be interesting. Would need some careful measurements and\n> > > attempts to validate how often all pathspecs are matched early in some\n> > > kind of way, because this would definitely slow down some cases and\n> > > speed others up, but I don't have a good feel for which side happens\n> > > more frequently in practice.\n> > >\n> > >> 3. Do some heuristic checks on the pathspecs before checking index entries.\n> > >> For example, exact file or directory matches could be searched in the\n> > >> index. This would still require falling back on the per-file checks if\n> > >> not all pathspecs are matched, but makes some typical use-cases much\n> > >> faster.\n> > >\n> > > I'm confused. \"before checking index entries\", you're checking things\n> > > (namely, exact file or directory matches) \"in the index\"?\n> >\n> > Sorry, I definitely wasn't clear. I mean \"perform heuristic checks *per\n> > pathspec item* before iterating *per index entry*.\" Pathspecs used in `git\n> > add` are (at least in my experience) pretty small, so there could be\n> > performance gains if all the items can be marked `seen` without iterating\n> > over every entry of the index. I was thinking something like\n> > `pathspec_needs_expanded_index()` in `reset` (4d1cfc1351 (reset: make\n> > --mixed sparse-aware, 2021-11-29)), but tailored to this particular case.\n>\n> Ah, okay makes sense now.\n>\n>\n>\n>\n>\n> >\n> > >\n> > >> There are almost certainly other options, and I can dig around `add.c` more\n> > >> to see if there's anything I'm missing (although I'd love to hear other\n> > >> ideas too!).\n> > >>\n> > >> Hopefully this helps!\n> > >> - Victoria\n> > >>\n> > >> [1] `path_in_sparse_checkout()` is significantly faster in cone mode, but\n> > >> with 16k patterns I'm assuming you're not using cone patterns ;)\n> > >>\n> > >>>\n> > >>> Please help us take a look at this issue and let us know if you need\n> > >>> more information.\n> > >>>\n> > >>> Thanks,\n> > >>>\n> > >>> Dian Xu\n> > >>> Mathworks, Inc\n> > >>> 1 Lakeside Campus Drive, Natick, MA 01760\n> > >>> 508-647-3583\n> > >>\n> >\n"},{"id":"458425","messageId":"CABPp-BHgwaWNEJnSer0-jw8+53NDuRWLvtXp4U_JJ8T_t-bTpQ@mail.gmail.com","threadId":"58086","inReplyTo":"CAKSRnEx2seC41QCe8sQOPf0=VNqHB6GkZ3M_CpGmOZRS0FS1gA@mail.gmail.com","subject":"Re: git bug report: 'git add' hangs in a large repo which has sparse-checkout file with large number of patterns in it","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-07-01T21:52:48Z","receivedAt":"2022-07-01T21:53:04Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi Dian,\n\nAs a heads up, note that on this list we don't top-post.\n\nOn Fri, Jul 1, 2022 at 1:24 PM Dian Xu wrote:\n>\n> Hi Victoria, Elijah, Derrick,\n>\n> Thanks a lot for the detailed insight.\n>\n> (Btw our company’s email mathworks.com is blocked by\n> mailto:git@vger.kernel.org, hope someone can help take a look)\n\nKonstantin: Is this something you know how to look into? (Or do you\nknow who to ask?)\n\n> 1. We use a no-cone version of sparse-checkout to control the 'shape'\n> (set of scm files) of our source code. In this case, the local sandbox\n> is not necessarily 'sparse' (2m files), but it's very convenient that\n> we can use git to check out the exact amount (shape) of files. To\n> Victoria's question, all these 2m files are \"H\".\n\nHow many are \"H\", how many are \"S\", and how many files in total? I'd\nlike to try to construct a way to reproduce your issue, and knowing\nhow many of each will help.\n\n> 2. Below is the detail steps to create the local repo (sparse-checkout\n> was defined 'before' git checkout)\n> % git init\n> % git remote add origin \n> % git config core.sparsecheckout true\n> % vi .git/info/sparse-checkout\n> % git fetch\n> % git checkout -b \n> Do I still need to 'git sparse-checkout reapply' after checkout?\n> (Thanks for pointing out to run reapply once .git/info/sparse-checkout\n> changed)\n\nWhy didn't you list 'git sparse-checkout reapply' after editing\n.git/info/sparse-checkout? You mention it later, so I'm hoping you\nran it at that point.\n\nYou should only need to run the sparse-checkout reapply command after\nmanually editing the .git/info/sparse-checkout file. There are\nspecial cases where it might be useful after other commands, but it's\npretty rare. Most git commands, and particularly checkout, will keep\nthe sparsity of the working tree up-to-date with the sparse-checkout\nfile -- assuming it was up-to-date beforehand. Basically, feel free\nto use the rule that you only need to reapply after manual edits of\nthe $GIT_DIR/info/sparse-checkout file.\n\nAlso, with newer git, you can replace all three of\n git config core.sparsecheckout true\n vi .git/info/sparse-checkout\n git sparse-checkout reapply\nwith\n git sparse-checkout set --no-cone \n\nWith older git, you can replace those three commands with two: `git\nsparse-checkout init --no-cone && git sparse-checkout set `. But that's sometimes not wanted since the init command\nsparsifies everything away except files in the toplevel directory, and\nthen the second step restores all the files, and that two-step\napproach is really slow as it deletes and then restores a huge number\nof files from the working directory.\n\n> 3. Unfortunately, after executing reapply (btw it is very slow on this\n> 2m files * 16k patterns scenario: 30 mins), 'git add', and 'git add\n> --sparse' still hangs.\n\n'git add --sparse' is still slow? That sounds like a bug I'd like to\ninvestigate.\n\nWhat's the particular timing you get for each of 'git add' and 'git\nadd --sparse'? Are you giving it individual files (if so, how many?),\nor directories (how many files under those directories?), or globs?\n(This information will be helpful in my attempts to get a synthetic\nsetup aiming to be similar to yours.)\n\n> 4. --cone is a big topic for us now, since 2.37.0 deprecates\n> --no-cone. We do have our own challenges to move away from --no-cone\n> (E.g. we use lots of file specifiers and/or exclusion patterns to\n> define our source code shape), which will be a huge amount of work, if\n> feasible. We've established a set of workflows based on --no-cone,\n> because of its merit of being capable of defining a fine-grained scm\n> shape.\n\nTo be fair, --no-cone is deprecated as in discouraged due to various\nusability problems (including performance), but we currently have no\nplans to remove it from Git. I do heartily recommend migrating to\n--cone since it solves so many problems, but we'll still support\n--no-cone users as best we can.\n\n> 5. Back to this case, what we've experimented on are:\n> - Remove all files/*/! patterns from our shape definition, which\n> leave us with 14k directories (Obviously the scm shape no longe\n> matches, but just to proof of concept here)\n> - 'git sparse-checkout set <14k directories>' finishes fast\n\nNow I'm surprised. You said in the previous email that you were using\ngit 2.34.2. In that version, --no-cone is the default, so this would\nstill be using --no-cone mode. That either suggests you switched to\nv2.37 since your email and didn't include that detail here, or that\nthe performance issue is actually with certain specific patterns.\nWhat version of git did you use here? And did you have either an\nexplicit --cone or --no-cone when using the sparse-checkout set\ncommand?\n\n> - 'git add' finishes fast\n\n> As Victoria mentioned, I hope this --no-cone 'git add' performance\n> can be addressed because 'those performance gains can also be realized\n> in cone mode', as we saw here.\n\nAre we sure we saw that here? Could you verify by reporting: (a) what\nversion of git were you using, and (b) does `git config --list | grep\n-i sparse` show both core.sparsecheckout and core.sparsecheckoutcone\nas being true after your do your sparse-checkout set?\n\n\nElijah\n"},{"id":"458454","messageId":"CAMwyc-Q7dEwo7AzFTYXrX-0i+b80ikzv_MCzTr7ZKaCPKwcERw@mail.gmail.com","threadId":"58086","inReplyTo":"CABPp-BHgwaWNEJnSer0-jw8+53NDuRWLvtXp4U_JJ8T_t-bTpQ@mail.gmail.com","subject":"Re: git bug report: 'git add' hangs in a large repo which has sparse-checkout file with large number of patterns in it","fromName":"Konstantin Ryabitsev","fromEmail":"konstantin@linuxfoundation.org","sentAt":"2022-07-04T19:11:57Z","receivedAt":"2022-07-04T19:12:11Z","isPatch":false,"sender":{"key":"konstantin@linuxfoundation.org","avatar":"https://gravatar.com/avatar/7cb8827c6de56e1bd2dea16508c6708aa43feed3bf3813bcdacecdf96ceadd79?d=mp&s=160"},"body":"On Fri, 1 Jul 2022 at 17:53, Elijah Newren wrote:\n> > (Btw our company’s email mathworks.com is blocked by\n> > mailto:git@vger.kernel.org, hope someone can help take a look)\n>\n> Konstantin: Is this something you know how to look into? (Or do you\n> know who to ask?)\n\nUnfortunately, I'm not in charge of vger -- it's historically managed\nby volunteers outside of LF.\nYou should reach out to postmaster@vger.kernel.org.\n\nBest regards,\n-Konstantin\n"},{"id":"458477","messageId":"CAKSRnEwda+WomBQbvjZ+hry+k2vGO4ukR42f66tHqxO7LdU_sA@mail.gmail.com","threadId":"58086","inReplyTo":"CAMwyc-Q7dEwo7AzFTYXrX-0i+b80ikzv_MCzTr7ZKaCPKwcERw@mail.gmail.com","subject":"Re: git bug report: 'git add' hangs in a large repo which has sparse-checkout file with large number of patterns in it","fromName":"Dian Xu","fromEmail":"dianxudev@gmail.com","sentAt":"2022-07-05T13:08:46Z","receivedAt":"2022-07-05T13:45:30Z","isPatch":false,"sender":{"key":"dianxudev@gmail.com","avatar":null},"body":"Hi Elijah,\n\nPlease see answers below:\n\n1. H: 2.27m; S: 7.7k; Total: 2.28m\n\n2. Sure I will run 'reapply' after the sparse-checkout file has\nchanged. Just curious, do I have to run 'reapply' if 'checkout' is the\nnext immediate cmd? I thought 'checkout' does the updating index as\nwell\n\n3. I simply added one file only, 'git add' and 'git add --sparse'\nstill hang. Let me know if you need me to send you any debug info from\npathspec.c/dir.c\n\n4. Good to know and we are investigating if we have a way out from --no-cone\n\n5. I should've been clearer: The experiment done here uses 2.37.0\n\nThanks,\n\nDian Xu\nMathworks, Inc\n1 Lakeside Campus Drive, Natick, MA 01760\n508-647-3583\n\nOn Mon, Jul 4, 2022 at 3:12 PM Konstantin Ryabitsev\n wrote:\n>\n> On Fri, 1 Jul 2022 at 17:53, Elijah Newren wrote:\n> > > (Btw our company’s email mathworks.com is blocked by\n> > > mailto:git@vger.kernel.org, hope someone can help take a look)\n> >\n> > Konstantin: Is this something you know how to look into? (Or do you\n> > know who to ask?)\n>\n> Unfortunately, I'm not in charge of vger -- it's historically managed\n> by volunteers outside of LF.\n> You should reach out to postmaster@vger.kernel.org.\n>\n> Best regards,\n> -Konstantin\n"},{"id":"458621","messageId":"CABPp-BEkJQoKZsQGCYioyga_uoDQ6iBeW+FKr8JhyuuTMK1RDw@mail.gmail.com","threadId":"58086","inReplyTo":"CAKSRnEwda+WomBQbvjZ+hry+k2vGO4ukR42f66tHqxO7LdU_sA@mail.gmail.com","subject":"Re: git bug report: 'git add' hangs in a large repo which has sparse-checkout file with large number of patterns in it","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-07-08T01:53:00Z","receivedAt":"2022-07-08T01:53:17Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Jul 5, 2022 at 6:08 AM Dian Xu wrote:\n>\n> Hi Elijah,\n\nHi Dian,\n\nPlease don't top post on this list. It'd also help to respond to the\nrelevant email instead of picking a different email in the thread to\nput your answers in. Anyway, that aside...\n\n> Please see answers below:\n>\n> 1. H: 2.27m; S: 7.7k; Total: 2.28m\n>\n> 2. Sure I will run 'reapply' after the sparse-checkout file has\n> changed. Just curious, do I have to run 'reapply' if 'checkout' is the\n> next immediate cmd? I thought 'checkout' does the updating index as\n> well\n>\n> 3. I simply added one file only, 'git add' and 'git add --sparse'\n> still hang. Let me know if you need me to send you any debug info from\n> pathspec.c/dir.c\n>\n> 4. Good to know and we are investigating if we have a way out from --no-cone\n>\n> 5. I should've been clearer: The experiment done here uses 2.37.0\n\nThanks for providing these details. It was enough to at least get me\nstarted, and from my experiments, it appears the arguments to `git\nadd` are important. In particular, I could not trigger this when\npassing actual filenames that existed. I could when passing a fake\nfilename. Here's the concrete steps I used to reproduce:\n\n git clone git@github.com:newren/gvfs-like-git-bomb\n cd gvfs-like-git-bomb\n\n git init attempt\n cd attempt\n ../make-a-git-bomb.sh\n\n time git checkout bomb\n\n echo \"/*\" >.git/info/sparse-checkout\n echo '!/bomb/j/j/' >>.git/info/sparse-checkout\n for i in $(seq 1 10000); do\n printf '!some/random/file/path-%05d\\n' $i\n done >>.git/info/sparse-checkout\n git config core.sparseCheckout true\n time git sparse-checkout reapply\n\n echo hello >world\n time git add --sparse world nonexistent\n time git rm --cached --sparse world nonexistent\n time git add world nonexistent\n time git rm --cached world nonexistent\n\nThis sequence of steps will (1) clone a repo with 2 files, (2) create\nanother repository in subdirectory 'attempt' that has 1000001 files\n(but only two unique files, and only six or so unique trees) in a\nbranch called 'bomb', (3) check it out, (4) create 10002 patterns for\nthe sparse-checkout file (only the first 2 of which match anything)\nwhich will leave ~99% of files still present (990001 files checked out\nand 10000 files sparse) and turn on sparsity, (5) measure how long it\ntakes to add and remove a file from the index, both with and without\nthe --sparse flag, but always listing an extra path that won't match\nanything.\n\nThe timings I see for the setup steps are:\n 4m10.444s checkout bomb\n 1m0.380s sparse-checkout reapply\n\nAnd the timings for the add/rm steps are:\n 4m43.353s add --sparse world nonexistent\n 9m25.666s add world nonexistent\n 0m0.129s rm --cached --sparse world nonexistent\n 9m23.601s rm --cached world nonexistent\n\nwhich shows that 'rm' also has a performance problem without the\n'--sparse' flag (which seems like another bug).\n\nNow, if I remove the 'nonexistent' argument from the commands, then\nthe timings drop to:\n 0m0.236s add --sparse world\n 0m0.233s add world\n 0m0.175s rm --cached --sparse world\n 4m43.744s rm --cached world\n\nSo, I can reproduce some slowness. 'rm' without --sparse seems\nbuggily slow for either set, whereas 'add' is only slow when given a\nfake path. You never mentioned anything about the arguments you were\npassing to `git add`, so I don't know whether you are using specific\nfilenames that just don't exist (like I did above), or globs that\nperhaps match some files, or something else. That might be useful to\nknow. But there appears to be something here for both 'add' and 'rm'\nthat we could look into optimizing. I don't have time right now. I'm\nnot sure if someone else has some time to look into it; if no one else\ndoes, I'll eventually try to get back to it.\n"},{"id":"458871","messageId":"CAKSRnEz6xg6jiTqaVtYf+32kEzS0jydiajbTnvK7qy_Po=y=uA@mail.gmail.com","threadId":"58086","inReplyTo":"CABPp-BEkJQoKZsQGCYioyga_uoDQ6iBeW+FKr8JhyuuTMK1RDw@mail.gmail.com","subject":"Re: git bug report: 'git add' hangs in a large repo which has sparse-checkout file with large number of patterns in it","fromName":"Dian Xu","fromEmail":"dianxudev@gmail.com","sentAt":"2022-07-12T13:00:21Z","receivedAt":"2022-07-12T13:00:39Z","isPatch":false,"sender":{"key":"dianxudev@gmail.com","avatar":null},"body":"On Thu, Jul 7, 2022 at 9:53 PM Elijah Newren wrote:\n>\n> On Tue, Jul 5, 2022 at 6:08 AM Dian Xu wrote:\n> >\n> > Hi Elijah,\n>\n> Hi Dian,\n>\n> Please don't top post on this list. It'd also help to respond to the\n> relevant email instead of picking a different email in the thread to\n> put your answers in. Anyway, that aside...\n>\n> > Please see answers below:\n> >\n> > 1. H: 2.27m; S: 7.7k; Total: 2.28m\n> >\n> > 2. Sure I will run 'reapply' after the sparse-checkout file has\n> > changed. Just curious, do I have to run 'reapply' if 'checkout' is the\n> > next immediate cmd? I thought 'checkout' does the updating index as\n> > well\n> >\n> > 3. I simply added one file only, 'git add' and 'git add --sparse'\n> > still hang. Let me know if you need me to send you any debug info from\n> > pathspec.c/dir.c\n> >\n> > 4. Good to know and we are investigating if we have a way out from --no-cone\n> >\n> > 5. I should've been clearer: The experiment done here uses 2.37.0\n>\n> Thanks for providing these details. It was enough to at least get me\n> started, and from my experiments, it appears the arguments to `git\n> add` are important. In particular, I could not trigger this when\n> passing actual filenames that existed. I could when passing a fake\n> filename. Here's the concrete steps I used to reproduce:\n>\n> git clone git@github.com:newren/gvfs-like-git-bomb\n> cd gvfs-like-git-bomb\n>\n> git init attempt\n> cd attempt\n> ../make-a-git-bomb.sh\n>\n> time git checkout bomb\n>\n> echo \"/*\" >.git/info/sparse-checkout\n> echo '!/bomb/j/j/' >>.git/info/sparse-checkout\n> for i in $(seq 1 10000); do\n> printf '!some/random/file/path-%05d\\n' $i\n> done >>.git/info/sparse-checkout\n> git config core.sparseCheckout true\n> time git sparse-checkout reapply\n>\n> echo hello >world\n> time git add --sparse world nonexistent\n> time git rm --cached --sparse world nonexistent\n> time git add world nonexistent\n> time git rm --cached world nonexistent\n>\n> This sequence of steps will (1) clone a repo with 2 files, (2) create\n> another repository in subdirectory 'attempt' that has 1000001 files\n> (but only two unique files, and only six or so unique trees) in a\n> branch called 'bomb', (3) check it out, (4) create 10002 patterns for\n> the sparse-checkout file (only the first 2 of which match anything)\n> which will leave ~99% of files still present (990001 files checked out\n> and 10000 files sparse) and turn on sparsity, (5) measure how long it\n> takes to add and remove a file from the index, both with and without\n> the --sparse flag, but always listing an extra path that won't match\n> anything.\n>\n> The timings I see for the setup steps are:\n> 4m10.444s checkout bomb\n> 1m0.380s sparse-checkout reapply\n>\n> And the timings for the add/rm steps are:\n> 4m43.353s add --sparse world nonexistent\n> 9m25.666s add world nonexistent\n> 0m0.129s rm --cached --sparse world nonexistent\n> 9m23.601s rm --cached world nonexistent\n>\n> which shows that 'rm' also has a performance problem without the\n> '--sparse' flag (which seems like another bug).\n>\n> Now, if I remove the 'nonexistent' argument from the commands, then\n> the timings drop to:\n> 0m0.236s add --sparse world\n> 0m0.233s add world\n> 0m0.175s rm --cached --sparse world\n> 4m43.744s rm --cached world\n>\n> So, I can reproduce some slowness. 'rm' without --sparse seems\n> buggily slow for either set, whereas 'add' is only slow when given a\n> fake path. You never mentioned anything about the arguments you were\n> passing to `git add`, so I don't know whether you are using specific\n> filenames that just don't exist (like I did above), or globs that\n> perhaps match some files, or something else. That might be useful to\n> know. But there appears to be something here for both 'add' and 'rm'\n> that we could look into optimizing. I don't have time right now. I'm\n> not sure if someone else has some time to look into it; if no one else\n> does, I'll eventually try to get back to it.\n\nHi Elijah,\n\nThank you for sharing the reproduction steps. I believe they represent\nour workflow.\n\nWe use 'git add ', where path_to_file is an existing\nfile, which is also within sparse-checkout shape.\n\nNot sure this is related but we also use --reference while setting up the clone.\n\nDian Xu\nMathworks, Inc\n1 Lakeside Campus Drive, Natick, MA 01760\n508-647-3583\n"}]}