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

[Dmitry Gutov]

On 04/19/2015 02:53 PM, Oleh Krehel wrote:

> About the duplicate entries, I think it should be the responsibility
> of the caller to remove the duplicates.

That could have been a decent argument if we're discussing a new API, 
and not an already widely-used 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.