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>]

Hi Joao,

On 30/10/2023 01:12, João Távora wrote:

>> 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.
> 
> Yes, it could, but I've reproduced this in different hardware.
> 
> Check that you're taking enough samples, I take about 15-20 samples.
> Maybe the lazy-hilit patch pays a an extra cost upfront for the very
> first C-h v or completing-read, to create the properties keys on the
> strings, which are then reused.

I actually do see that. At first I didn't pay much attention to such 
outliers. They usually look like the second measurement here:

Elapsed time: 0.541624s (0.164396s in 5 GCs)
Elapsed time: 0.861175s (0.415142s in 10 GCs)
Elapsed time: 0.486012s (0.057915s in 1 GCs)
Elapsed time: 0.505339s (0.055759s in 1 GCs)
Elapsed time: 0.481024s (0.057757s in 1 GCs)
Elapsed time: 0.471350s (0.056383s in 1 GCs)
Elapsed time: 0.495125s (0.056129s in 1 GCs)
Elapsed time: 0.513310s (0.058437s in 1 GCs)
Elapsed time: 0.491978s (0.057144s in 1 GCs)

Which keys are those? I only know about one key - 'completion-score'.

> This cost is ammortized very quickly,
> of course, but if you're taking the measurement immediately after Emacs
> -Q and with few samples, it skews the numbers.

I always took around 16 samples, and now made sure to take exactly that 
number, starting with "y" and then "yo", "y", etc. Although the timing 
for the empty input is usually included (but it doesn't look too 
different from the rest).

Anyway, I retook the numbers a couple of times. One of the patches (the 
same one) still looks a little faster, but the fluctuations between runs 
are large enough to avoid making any big conclusions:

d+d
300000
completing-read 0.504
C-h v 0.630

lazy-hilit-2023-v4
300000
completing-read 0.517
C-h v 0.661

d+d again
300000
completing-read 0.486
C-h v 0.587

lazy-hilit-2023-v4 again
300000
completing-read 0.519
C-h v 0.651

And to double-check, these are comparison between 
0001-Add-new-completion-filter-completions-API-and-deferr-v3.diff and 
lazy-hilit-2023-v4.diff.

16 samples every time. And I think I dropped the run with the "spike" in 
all or most of the above. The first of the patches doesn't seem to cause 
it, though.

>> All averages made using 'M-x calc-grab-region' followed by 'u M'.
> 
> Wow, thanks for this tip.  I wondered if there was an easier way than
> M-x cua-rectangle-mark-mode + hand rolled avg function.

No problem! I lost your snippet for avg, so had to google. :-/

rectangle-mark-mode (C-x SPC) is still part of the recipe, though.

>>>> 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,
> 
> I think further optimization would be localized to the scoring function
> itself, not to the place where it is performed.

Most likely, yes. It seems to be the most expensive part. But it still 
seems easier to measure/tweak when it happens during a separate step, 
rather than mixed in with the rest of completion-all-completions' business.

>> But if course it would be nice to avoid the wart, so if you have any
>> better ideas, they are welcome.
> 
> I'm not saying it would necessarily spread even further, but if you want
> to do scoring "just in time" like I suggested -- presumably to
> completely avoid propertizing strings -- that particular wart spreads a
> little more and thus becomes something that is slightly harder to remove
> later on.

Could you describe the other places you think it might spread to? Other 
completion styles like Orderless?

As long as there's only one place producing this property (as opposed to 
consuming it), it seems straightforward enough to remove anyway.

>> So far you advocated toward avoiding breaking changes while
>> implementing the present performance improvement.
> 
> Both patches do that, so what I've been arguing for is simplicity and
> coherence.  I don't think completion-sorted-completions and the
> complexity it brings to minibuffer.el is a step in the rigth direction,
> and the performance benefits it does undeniably bring can be achieved
> with less drastic means.

What I meant is, solving the quote-unquote conundrum might require a 
larger breaking change than the one that you wanted for this discussion.

Anyway, have you looked into what it would take to solve it? Such text 
propertization might actually work as a cheap replacement to returning 
"a function to ... requote them". If both highlighting and scoring 
functions work fine on the "unquoted" strings, then we would only need 
to make sure the "quoted" is used when the completion is inserted. Could 
we make a rule that every table-with-quoting would have to call a 
particular exit-function? Perhaps before the existing exit-function.

That might solve a bunch of things, though I don't see a robust way to 
enforce this practice, given that completion-table-with-quoting works on 
the level of completion tables, whereas :exit-function is only specified 
in the capf tuple.