Bash completion very slow in large repo

[Matthew Hughes <matthewhughes934@gmail.com>]

Hi,

While working in a repo with _a lot_ of directories I've noticed a painful
slowdown in some of the bash completion for git. Specifically, for any
completion that calls `git ls-files` and needs to iterate through the
file-system (and not just check the index), e.g. `git add`. Has anyone run into
this? Are there existing solutions or workarounds?

I first ran into it when running something like

    $ git add ./<tab> # hangs for a good second or two

For reference the number of files/directories in the actual repo I work with:

    # this many files
    $ git ls-files | wc --lines
    367628
    # this many directories
    $ git ls-files -z | xargs -0 dirname | sort --unique | wc --lines
    58404

See below for a reproduction and my logic, but I conclude this is because e.g.
in the case of `git add` (with no other args) git will need to look through
every directory in the repo to discover if there any untracked files at any
level.

I'm not sure about potential fixes. Hacking around on it the best I could come
up with was a workaround: add an env var to skip index completion during bash
completion, so the completion falls back to the default Bash file completion
(i.e. complete any time), here that is (just for demonstration):

diff --git i/contrib/completion/git-completion.bash w/contrib/completion/git-completion.bash
index e875787710..7b412e5b74 100644
--- i/contrib/completion/git-completion.bash
+++ w/contrib/completion/git-completion.bash
@@ -727,6 +727,10 @@ __git_index_files ()
 # The exception is --committable, which finds the files appropriate commit.
 __git_complete_index_file ()
 {
+       if test -n "${GIT_COMPLETION_NO_COMPLETE_INDEX-}"
+       then
+               return
+       fi
        local dequoted_word pfx="" cur_
 
        __git_dequote "$cur"

For reproduction: here's a roughly similar setup of a repo, with many
directories at the root:

    $ git init .
    $ for i in {1..25000}; do echo dir_$i/sub_dir/; done | xargs mkdir -p
    $ for i in {1..25000}; do for j in {1..12}; do echo dir_$i/sub_dir/file_$j.txt; done; done | xargs touch
    $ git add .

With that setup I see slow completion e.g. on `git add ./di<TAB>`. Debugging
the completion script I see it hangs for a while on:

    git -C ./ -c core.quotePath=false ls-files --exclude-standard --others --modified --directory --no-empty-directory -- 'di*'

(via `_git_add->__git_complete_index_file->__git_index_files`)

And running that through `strace` (on my Linux/AMD64 machine) tells me for each
directory there is (among other syscalls):

* ~100_000 calls to `getdents64`
* ~75_000 calls to `openat`
* ~50_000 calls to `fstat`

So that explains the slowdown. 

Thanks,
Matt