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

[João Távora]

Eli Zaretskii <eliz@gnu.org> writes:

>> > On Fri, Aug 13, 2021 at 1:22 PM Daniel Mendler <mail@daniel-mendler.de> 
>> > wrote:
>> > 
>> >> It is important to keep this property since this will preclude many bugs
>> >> due to string mutation.
>> > I am aware of this, of course.  Can you give examples of these "many bugs"?
>> > Perhaps other than the one I already described and addressed?
>> No, João, this is not how it goes.  I don't have to prove to you that
>> your idea introduces bugs.  You have to show that mutation of the
>> completion table strings (which are not supposed to be mutated) will not
>> lead to bugs, which are hard to find.
> Please calm down, both of you.  No one has to prove anything to anyone
> here, that's not how Emacs development works.  We need to see which
> idea is better, and if none is significantly better, we will probably
> have both of them living side by side.
>
> And while asking for an example of potential bugs is reasonable,
> asking for a proof that a change will NOT lead to bugs isn't.

As far as I remember, I have done the first. I found bugs and addressed
them. I cannot _prove_ that my change will not leads to bugs indeed:
no-one can with any change.  I've just stated repeteadly that I'm not
aware of any such bugs.  I can understand intuition" for bugs to a
certain extent (everyone has intuition), but this intuition must always
resolve into actual reality to be useful in the end.

> So how
> about a couple of examples where having original strings unchanged is
> important, which could then be discussed?

Good idea, so in the absence of any controlled benchmarks I did some of
my own, using the most controlled environment I could devise.  I start
Emacs like so:

   ~/Source/Emacs/emacs/src/emacs -Q -f fido-mode -f fido-vertical-mode -l 
~/tmp/benchmark.el ~/tmp/benchmark.el

I prime the obarry with lots of symblos to make completion purposedly
slow:

   (require 'cl-lib)
   (cl-loop repeat 300000 do (intern (symbol-name (gensym))))

I attach the file. Then I try a run of 10 invocations of

  ;; Press C-u C-x C-e C-m quickly to produce a sample.  
  (benchmark-run (completing-read "" obarray))

This, I think, is a good representation of the responsiveness of the
completion system.  It always prints well after I finish typing, so I
don't think I'm inducing any artificial slowdows while it waits for my
input.  When not measuring quantitatively, I also feel the difference in
responsiveness between different approaches.

Summarized results with an assortment of Emacs builds.

   - the current master (254dc6ab4ca8e6a549a795f9eaf45378ce51b61f).

     20.25 seconds total
   
   - Applying Daniel's patch over 254dc6.

     23.41 seconds total
   
   - The theoretical best situation where we don't highlight in
     completion-pcm--hilit-commonality (like 254dc6, but just removed
     the copy-sequence)

     10.70 seconds total

   - Experimental patch published in
     scratch/icomplete-lazy-highlight-attempt-2 (not finished, still
     needs a way for frontends to opt into the optimization).

     10.80 seconds total

I invite you all to reproduce these results.

In conclusion, I don't think Daniel's patch is going in the right
direction, *performance-wise*, for the kind of responsiveness scenarios
that I am concerned with, and which were discussed with Dmitry in
bug#48841.  It seems to slow down the process by about 10%.

Note 1: there may be *other* performance scenarios that I am not aware
of, where Daniel's patch excels.  I've requested these benchmarks,
regrettably without any success.

Note 2: doesn't mean that there aren't *other* merits to Daniel's patch,
but I have not understood these yet.  That is due to the stated fact
that the patch is very long, and seems to comprise performance
improvements, refactorings, and API redesign.  It has no documentation
in manual and/or examples on how to use the new API.

>> >> Note that your idea also does not address the other issues which are
>> >> addressed by my patch.
>> > 
>> > That's for sure.  My patch idea addresses only that single problem.
>> > I think this is a good property of patches: to solve one thing, not many.
>> 
>> No, this is not necessarily true.  This is only good if the problem is
>> solved in a way which is future proof.  The idea of mutating the strings
>> is a hack and not a solution.
>
> Just to make sure we are on the same page: adding a text property to a
> string doesn't mutate a string.  Lisp programs that process these
> strings will not necessarily see any difference, and displaying those
> strings will also not show any difference if the property is not
> related to display.  So the assumption that seems to be made here,
> that adding a property is the same as mutating a string, is IMO
> inaccurate if not incorrect.

Yes, in Lisp it is very common to attach a "private" property to an
object.  If no-one else knows about the existence of that property, then
attaching it is not harmful. Generally, of course: there are situations
where adding a private property brings side-effects to other parts of
the code.  But IMO that other code is in the wrong, not the one that
adds properties.

Also, to be clear, attaching a different property (as in, not 'face') to
the completion string is only _one_ of the ways of the ways to bypass
copying.  According to my measurements, performance doesn't seem to be
decided by property attachments, but by copying or not copying of the
character data of said strings in completion-pcm--hilit-commonality.

João

benchmark.el
Description: benchmark.el