compgen is slow for large numbers of options

[Richard Neill]

Dear All,

I don't know for certain if this is a bug per se, but I think
"compgen -W" is much slower than it "should" be in the case of a large 
(10000+) number of options.

For example (on a fast i7 2700 CPU), I measure:

compgen -W "`seq 1 50000`" 1794        #3.83 s
compgen -W "`seq 1 50000 | grep 1794`"   #0.019 s

In these examples, I'm using `seq` as a trivial way to generate some 
data, and picking 1794 as a totally arbitrary match.

In the first example, compgen is doing the filtering, whereas in the 
2nd, I obtain the same result very much faster with grep.

If I increase the upper number by a factor of 10, to 500000, these times 
become,  436 s (yes, really, 7 minutes!) and 0.20 s respectively.  This 
suggests that the algorithm used by compgen is O(n^2) whereas the 
algorithm used by grep is 0(1).


For a real world example, see:
  https://bugs.mageia.org/show_bug.cgi?id=373#c8
in which we are using completion on package-management.
In this case, the number is 43031.


I hope this is helpful.

Richard