Re: [PATCH] `completing-read` - allow history=t, sorting improvements

[Stefan Monnier <monnier@iro.umontreal.ca>]

>>> * minibuffer.el: Use completion--message consistently for the messages
>>> "Incomplete", "Sole completion" and "No completions".
>> I don't have a strong opinion on this patch, but I have the impression
>> that there might have been a good reason for the difference (i.e. the
>> above two cases could be considered "more serious" than those using
>> `completion--message`).
>> I would personally gladly get rid of `completion-show-inline-help`, so
>> I'm not the right person to judge if the above patch is doing the right
>> thing or not.
>
> For me the point was mostly to get this clarified, therefore I included it
> here. Note that the messages "Sole completion" and "No completions" are
> already shown at some other places via `completion--done` which uses
> `completion--message` itself, but on a different code path.

Oh, I see now that this var comes from:

    commit 369e974dc086452033227a5d350c357602c6274e
    Author: Chong Yidong <cyd@stupidchicken.com>
    Date:   Sun Apr 10 17:31:14 2011 -0400
    
        Fix bad interaction between icomplete and completion inline help (Bug#5849).
        
        * lisp/minibuffer.el (completion-show-inline-help): New var.
        (completion--do-completion, minibuffer-complete)
        (minibuffer-force-complete, minibuffer-complete-word): Inhibit
        minibuffer messages if completion-show-inline-help is nil.
        
        * lisp/icomplete.el (icomplete-mode): Bind completion-show-inline-help
        to avoid interference from inline help.

I mistakenly thought it was a user config inherited from way-back which
I just preserved when I moved the code from minibuf.c to minibuffer.el.
So you're right we should use it everywhere.  I pushed your patch.

> Agree generally. It makes a difference if one uses car-less-than-car, since
> then the comparison function is fast. The difference is less pronounced if
> one includes the lambdas which sort alphabetically (this is on non-native,
> on native the picture could be different).

Note that the separate alphabetical sorting can be done with (sort all
#'string-lessp) so it should also be fast ;-)

> The important change is really the quadratic one.

Yes, thank you for that fix, indeed.

> However in my Vertico package (and in other continuously updating
> UIs), the big bottleneck of the UI still is the sorting for many
> candidates, even when including optimizations.
> Therefore I am using a vertico-sort-threshold there.
> Maybe there are potential improvements on a lower level?

If O(N log N) is still too slow, then I think it's safe to say that the
problem is that N is too large: we can try and shave off a factor of `c`
or even the `log N` by optimizing the implementation, but that just
pushes the "too large" a bit further and sooner or later you'll have to
bite the bullet and introduce some "threshold" beyond which you reduce
the functionality.

In theory, if we want to optimize the speed as much as possible without
reducing the functionality, we could try to:
- first partition the set of candidates between those that appear in the
  history and those that don't.  This is linear time.
- sort the ones that appear in the history based on their position
  there: no need to check length or alphabetic order in this case.
  This is O(N log N) but the N should be significantly smaller.
- If you have enough candidates already to fill the display you can stop
  at this point and just use those candidates.
- the remaining candidates can be sorted by their length, putting
  together same-length candidates into sublists.  This could even be
  more-or-less linear time with some kind of bucket sort.
- Finally sort each of those sublists according to lexicographic order
  This is again O(N log N) but again the N should be significantly
  smaller and we can stop as soon as we've found enough candidates to
  fill the display.


        Stefan