git bug report: 'git add' hangs in a large repo which has sparse-checkout file with large number of patterns in it

Dear Git developers,

Reporting Issue:
              'git add' hangs in a large repo which has
sparse-checkout file with large number of patterns in it

Found in:
              Git 2.34.3. Issue occurs after 'audit for interaction
with sparse-index' was introduced in add.c

Reproduction steps:
              1. Clone a repo which has e.g. 2 million plus files
              2. Enable sparse checkout by: git config core.sparsecheckout true
              3. Create a .git/info/sparse-checkout file with a large
number of patterns, e.g. 16k plus lines
              4. Run 'git add', which will hang

Investigations:
              1. Stack trace:
                       add.c: cmd_add
                  -> add.c: prune_directory
                  -> pathspec.c: add_pathspec_matches_against_index
                  -> dir.c: path_in_sparse_checkout_1
              2. In Git 2.33.3, the loop at pathspec.c line 42 runs
fast, even when istate->cache_nr is at 2 million
              3. Since Git 2.34.3, the newly introduced 'audit for
interaction with sparse-index' (dir.c line 1459:
path_in_sparse_checkout_1) decides to loop through 2 million files and
match each one of them against the sparse-checkout patterns
              4. This hits the O(n^2) problem thus causes 'git add' to
hang (or ~1.5 hours to finish)

Please help us take a look at this issue and let us know if you need more information.

Thanks,

Dian Xu Mathworks, Inc 1 Lakeside Campus Drive, Natick, MA 01760 508-647-3583