completion very slow with gigantic list

[Eric Wong]

Hi, I noticed bash struggles with gigantic completion lists
(100k items of ~70 chars each)

It's reproducible with both LANG+LC_ALL set to en_US.UTF-8 and C,
so it's not just locales slowing things down.

This happens on the up-to-date `devel' branch
(commit 584a2b4c9e11bd713030916d9d832602891733d7),
but I first noticed this on Debian oldstable (5.1.4)

strcoll and strlen seem to be at the top of profiles, and
mregister_free when building devel with default options...
ltrace reveals it's doing strlen repeatedly on the entire
(100k items * 70 chars each = ~7MB)

Sidenote: I'm not really sure what one would do with ~100K
completion candidates, but I managed to hit that case when
attempting completion for an NNTP group + IMAP mailbox listing.

Standalone reproducer here:
-------8<------
# bash struggles with giant completion list (100K items of ~70 chars each)
# Usage:
#       . giant_complete.bash
#       giant_complete a<TAB> # watch CPU usage spike
#
# derived from lei-completion.bash in https://80x24.org/public-inbox.git
# There could be something wrong in my code, too, since I'm not
# familiar with writing completions...

_giant_complete() {
        # generate a giant list:
        local wordlist="$(awk </dev/null '
BEGIN{for(i=0; i<64; i++) v=v"v"; for(i=0; i<100000; i++) print "a"v""i }
' ${COMP_WORDS[@]})"
        wordlist="${wordlist//;/\\\\;}" # escape ';' for ';UIDVALIDITY' and such

        local word="${COMP_WORDS[COMP_CWORD]}"
        if test "$word" = ':' && test $COMP_CWORD -ge 1
        then
                COMPREPLY=($(compgen -W "$wordlist" --))
        else
                COMPREPLY=($(compgen -W "$wordlist" -- "$word"))
        fi
        return 0
}

giant_complete() {
        echo hi
}
complete -o default -o bashdefault -F _giant_complete giant_complete
# Thanks.  EOM