Huge delay for completions when not sorting

Huge delay for completions when not sorting

[Martin Vaeth]

I would have expected that the line

zstyle ':completion:*' sort false

speeds things up if there is a huge number of completions.
However, quite the opposite is true.
If the above zstyle is in effect, the completion for the
artificial command "2" defined by the completion file

#compdef 2
local expl
_description a expl a
compadd "$expl[@]" - {1..40000}

takes ages. Inserting e.g. "touch" commands, it can be verified
that the delay happens _after_ the return of the completion function,
i.e. it is _not_ the compadd itself which is slow.

Moreover, without the _description line there is no delay.

If the 40000 is replaced by 10000, the delay "almost" vanishes
on my machine. Maybe the "critical" number is different on
other systems.

Re: Huge delay for completions when not sorting

[Bart Schaefer]

On Sun, Jul 1, 2018 at 10:56 AM, Martin Vaeth <martin@mvath.de> wrote:
> I would have expected that the line
>
> zstyle ':completion:*' sort false
>
> speeds things up if there is a huge number of completions.
> However, quite the opposite is true.

This is probably a consequence of duplicate removal.  It's a lot
harder to search a single unsorted group for possible duplicates, even
if there aren't any to find.

Re: Huge delay for completions when not sorting

[dana]

On 1 Jul 2018, at 12:56, Martin Vaeth <martin@mvath.de> wrote:
>I would have expected that the line
>
>zstyle ':completion:*' sort false
>
>speeds things up if there is a huge number of completions.
>However, quite the opposite is true.

It's to do with the way it checks for duplicates in the unsorted results (-V
without -1 or -2). For each completion possibility, it performs a series of
checks against every subsequent possibility (compcore.c @ 3239)

I'm pretty bad at maths, but i think that for 40'000 unique possibilities it'll
have to make, like, 800 million calls to strcmp()

dana

Re: Huge delay for completions when not sorting

[Bart Schaefer]

On Sun, Jul 1, 2018 at 1:38 PM, dana <dana@dana.is> wrote:
>
> It's to do with the way it checks for duplicates in the unsorted results (-V
> without -1 or -2). For each completion possibility, it performs a series of
> checks against every subsequent possibility (compcore.c @ 3239)

Holy crap RE matcheq(Cmatch a, Cmatch b) ... there must be some way to
condense that into a single datum for each Cmatch and use a hash table
lookup from makearray().

Re: Huge delay for completions when not sorting

[Martin Vaeth]

Bart Schaefer <schaefer@brasslantern.com> wrote:
> On Sun, Jul 1, 2018 at 1:38 PM, dana <dana@dana.is> 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.

Re: Huge delay for completions when not sorting

[Bart Schaefer]

[-- Attachment #1: Type: text/plain, Size: 425 bytes --]

On Sun, Jul 1, 2018, 10:54 PM Martin Vaeth <martin@mvath.de> wrote:

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

The immediate problem is that there are no simple strings to store.  What's
being compared are data structures that break the words down into the
substrings used later to reconstruct parts of the word on the command line.

>