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

[Dmitry Gutov <dmitry@gutov.dev>]

On 27/10/2023 20:16, João Távora wrote:

> My attempts to fix the optimization to work correctly in all cases
> complicated the code and then slowed down the bare completion-read case.
> Not worth it IMO, therefore I have reverted it in the branch and in the
> latest patch I attach (lazy-hilit-2023-v4.diff).  Here are the latest
> measurements for the "yoyo" test, now considering the C-h v scenario:
> 
> ;; Daniel+Dmitry completin-read: 0.834s avg
> ;; Daniel+Dmitry C-h v:          0.988s avg
>                                             
> ;; lazy-hilit completing-read:   0.825s avg
> ;; lazy-hilit C-h v:             0.946s avg
> 
> Again, this shows my patch to be about 2-4% faster, though not really
> relevant.
> 
> Again, the optimization I removed, if it were done correctly (which it
> wasn't) could maybe shave off another 8-9% off that.

Thanks. My measurements are similar, except the difference switch the 
other way a little bit. It might depend on the particulars of the 
individual machine anyway. I also tried to compare the perf for 150K 
symbols, in case either the filtering or the sorting (which should have 
different complexities) would come to the front, but no such luck:

lazy-hilit

300000
completing-read 0.6063497
C-h v 0.72435995

150000
completing-read 0.316961
C-h v 0.39933575

d+d

300000
completing-read 0.571481
C-h v 0.69817995

150000
completing-read 0.308940
C-h v 0.350437

All averages made using 'M-x calc-grab-region' followed by 'u M'.

>> But there are differences. The first is that the highlighter function
>> takes one string as an argument instead of a collection. I mentioned
>> this before, this will be much handier to use in company-capf.
> 
> Don't fully follow this.  Can you perhaps show two versions (or two
> snippets) of the company-capf code, the handy and the non-handy version?

I just meant that your version will be easier to use in 
company--match-from-capf-face (because it works on individual completions).

>> Third, it made a principled stance to avoid altering the original
>> strings, even the non-visual text properties. This approach could be
>> adopted piecewise from Daniel's patch, especially if the performance
>> ends up the same or insignificantly different in practical usage.
> 
> If we really wanted to, we could also adopt the non-propertizing
> approach in my lazy-hilit patch, by calculating the score "just in
> time", much like Daniel's patch does it.  But it should be clear that
> what we save in allocation in completion-pcm--hilit-commonality, we'll
> pay for in the same amount in consing later.  So no performance benefit.

Not for performance, no. Although the way it separates the sorting into 
its own phase makes it easier to reason about that particular cost. And 
for 300000 symbols, scoring and sorting really take the most time, e.g. 
about 2/3rds. Which might help with optimizing it further down in the 
future, somehow,

> And if we do that, don't forget there will be the ugly "unquoted"
> complication to deal with.  Then again, in my understanding that
> complication is due to similar problem of mixing business and display
> logic.  That's assuming I understand this comment in minibuffer.el
> correctly:
> 
>     ;; Here we choose to quote all elements returned, but a better option
>     ;; would be to return unquoted elements together with a function to
>     ;; requote them, so that *Completions* can show nicer unquoted values
>     ;; which only get quoted when needed by choose-completion.
> 
> So I would look into solving that first, instead of allowing the
> "unquoted" hacks to spread even further in minibuffer.el

I don't really understand this quoting-requoting business, never dug 
into the feature or the code. But perhaps keeping the original string 
might even help avoid the "requoting" step? Though that would depend on 
which version of the string the scoring and highligher functions expect 
to work on.

Speaking of the comment, it sounds like the said "requote function" 
would need to be passed up the call stack and used according to some 
protocol. The idea itself reminds me of the proposal described in 
https://github.com/company-mode/company-mode/discussions/1422 (it was 
also previously brought up on the lsp-mode tracker). It seems like 
either the completion tables would need a new method, or the capf tuples 
- a new function property, which all UIs using would need to start 
supporting in lock-step. At least that's the case if we use that to 
solve the requoting issue (the LSP clients' migration to use 
complete-function can be done more easily).

So far you advocated toward avoiding breaking changes while implementing 
the present performance improvement. Daniel's argument that the quoting 
completion tables are already slow enough sounds very reasonable to me, 
that an extra text property round-trip won't be noticeable. And the 
current version of the patch is functional and passes all tests, so it's 
not clear which other places would the "hack" need to spead into. Unless 
it helps with reducing code, etc, as per my vague guess above.

But if course it would be nice to avoid the wart, so if you have any 
better ideas, they are welcome.