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

[João Távora]

Dmitry Gutov <dgutov@yandex.ru> writes:

> Aside from the mutability/ownership issue,
>
> On 13.08.2021 15:05, João Távora wrote:
>> If one removes these lines, the process becomes much faster, but there is a
>> problem with highlighting.  My idea is indeed to defer highlighting by not
>> setting the 'face property directly on that shared string, but some
>> other property
>> that is read later from the shared string by compliant frontents.
>
> I haven't done any direct benchmarking, but I'm pretty sure that this
> approach cannot, by definition, be as fast as the non-mutating one.
>
> Because you go through the whole list and mutate all of its elements,
> you have to perform a certain bit of work W x N times, where N is the
> size of the whole list.

Let's call W the work that you perform N times in this istuation.  In
the non-mutation, let's call it Z.  So

W <= Z, because Z not only propertizes the string with a calculation of
faces but _also copies its character contents_.

Also I think it's better to start about copying rather than mutating.
As Eli points out, putting a text property in a string (my idea) is not
equivalent with "mutating" it.

> Whereas the deferred-mutation approach will only have to do its bit
> (which is likely more work, like, WWW) only 20 times, or 100 times, or
> however many completions are displayed. And this is usually
> negligible.

I think you're going in the same fallacy you went briefly in the other
bug report.  The flex and pcm styles (meaning
completion-pcm--hilit-commonality) has to go through all the completions
when deciding the score to atribute to each completion that we already
know matches the pattern.  That's because this scoring is essential to
sorting.  That's a given in both scenarios, copying and non-copying.

Then, it's true that only a very small set of those eventually have to
be displayed to the user, depending on where wants she wants her
scrolling page to be.  So that's when you have to apply 'face' to, say
20 strings, and that can indeed be pretty fast.  But where does the
information come from?

- Currently, it comes from the string's 'face' itself, which was copied
  entirely.

- In the non-copying approach, it must come from somewhere else.  One
  idea is that it comes from a new "private" property 'lazy-face', also
  in the string itselv, but which was _not_ copied.  Another idea is
  just to remember the pattern and re-match it to those 20 strings.

I think the second alternative is always faster.

> However big the difference is going to be, I can't say in advance, of
> course, or whether it's going to be shadowed by some other performance
> costs. But the non-mutating approach should have the best optimization
> potential when the list is long.

Don't think so.  I'm doing benchmarks, will post soon.

João