bug#48841: bug#47711: [PATCH VERSION 2] Add new `completion-filter-completions` API and deferred highlighting

[Daniel Mendler <mail@daniel-mendler.de>]

On 8/13/21 12:56 PM, João Távora wrote:
> I've read the discussion and am indeed aware of some non-neglibile
> performance problems in the flex and pcm completion styles since
> they need to copy strings around.  Other -- completely different --
> performance problems affect fido-mode specifically (but not
> fido-vertical-mode, curiously).
> 
> In some conversation with Dmitry
> 
>   bug#48841: fido-mode is slower than ido-mode with similar settings
> 
> We discussed this.

I've read the discussion.  You are probably aware of my efforts to in
Vertico to implement deferred highlighting.  The patch I implemented
here implements the deferred highlighting in a clean way.

> There was also talk of removing the string copying with minimal (but not null)
> backward compatibility breakage.  I recall Dmitry saying it was easy
> to fix on the
> completion frontend side.  Many such frontends live in Emacs or GNU Elpa.
> On the other hand, the patch that we (or at least I) envisioned in
> that discussion
> was almost certainly much, much simpler than the one being presented here,
> and thus much easier to reason about and discuss.

No, this is not the case. There is no simple fix of the allocation issue
on the frontend side.  The existing API `completion-all-completions`
necessarily has to allocate all the strings in order to attach
highlighting and scoring.  The new API solves this in a clean way by
both deferring highlighting and scoring.

I claim that my patch is easy to reason about and refactors the existing
code to address the exact problem we are having. Please take some time
in reviewing it.

> But to avoid comparing apples to oranges, I would you to summarize exactly,
> perhaps in the forms of code snippets, and/or benchmarks exactly what problems
> your large patch solves. State the problem(s) first, then the solution
> (to each).

The main problem is that `completion-all-completions` allocates all the
strings every time the completions are filtered.  This is the same
performance issue you encountered in fido-mode/icomplete-mode.

The second problem addressed by the new API
`completion-filter-completions` is that `completion-all-completions` is
limited in what it can return.  For example it cannot return the end
position of the completion.  This is also solved by the new API.  The
new API is a clean extensible way forward.

Daniel