Subject: Re: bug#20365: 24.5; all-completions returns duplicates for Info-read-node-name-1

From: Oleh Krehel <[email-masked]>
Date: Sun, 19 Apr 2015 19:00:48 +0200

On Sun, Apr 19, 2015 at 6:44 PM, Dmitry Gutov <[email-masked]> wrote:

> That could have been a decent argument if we're discussing a new API, and
> not an already widely-used one.

No problem: no completion package will complain if you don't pass it duplicates.
Then it's just a matter of fixing the offening callers of completion one by one.

>> Here's my line of thought: a
>> completion function is expected to have an O(N) complexity, where N is
>> the amount of candidates. Removing duplicates is O(N^2) at worst, and
>> O(NlogN) at best.
>
>
> O(NlogN) is closer to the truth:
>
> First, you copy - O(N), then sort - O(NlogN), then call
> `delete-consecutive-dups' (linear time).
>
>> So the completion function should not attempt to
>> remove the duplicates. It's doesn't affect the performance when I do
>> it for 1000 candidates, but when it's 20k (`describe-function') it can
>> have an impact.
>
>
> Even on a decently-sized collection (38K), this takes only 80ms:
>
> (delete-consecutive-dups (sort (all-completions "" obarray) #'string<))
>
> That's not terrible.

Actually, 0.08 is a lot when you consider that I would call this after
each key press (in case when the collection is a function, not for the
static list).  The sluggishness would be perceptible even for a
relatively slow typist. And this is only the overhead, there's also
actual computing to be done. There's no reason not to avoid this
overhead cost.

Oleh