Re: Huge delay for completions when not sorting

[Martin Vaeth <martin@xxxxxxxx>]

Bart Schaefer <schaefer@xxxxxxxxxxxxxxxx> wrote:
> On Sun, Jul 1, 2018 at 1:38 PM, dana <dana@xxxxxxx> wrote:
>
>> For each completion possibility, it performs a series of
>> checks against every subsequent possibility (compcore.c @ 3239)

Quadratic running time; so the result is not surprising.

BTW, the timing came from a real-world application:
Completion of package names for eix (a package database lookup in gentoo):
~20000 packages of the form "category/package" and then
~20000 with only "category/" (i.e. most of the latter are duplicates,
but these duplicates happen to be at the very end).

Unsorted output makes sense in this example since each of the 2 forms
are already added in a sorted manner.

> hash table

When building a temporary hash table it would be enough to store pointers
to the strings there to avoid data duplication.