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

[Daniel Mendler <mail@daniel-mendler.de>]

Hi Stefan,

thank you for pushing. I will adjust the patches which are still 
relevant and resubmit them.

On 4/19/21 9:14 PM, Stefan Monnier wrote:
>> 1. Allow history=t to disable the `completing-read` history
> Thanks, pushed.
> I see that this was really just a bug fix: t already prevented adding
> the result to "the history", there was just one place where the code
> burped when encountering this special "history var".

Yes, also the documentation of `minibuffer-variable` specifies the 
meaning of `t`.

>> * 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.

>> * lisp/minibuffer.el (completion-all-sorted-completions): When
>> building the hash of history positions drop the prefix as determined
>> by `completion-boundaries`. For file completions drop everything
>> behind the first "/".
> I think I'm fine with this patch, but at that point, this sorting code
> *really* needs to be moved out into a separate function (already the
> previous patch, which I just pushed, was borderline in this respect).
> Also, I think this should come with a test case.

Okay, I agree with splitting up the large function. I will add a test case.

 >> * lisp/minibuffer.el (completion-all-sorted-completions): Sort by
 >> history position, length and alphabetically.
 > I'd expect this will not make a big difference in most cases, but the
 > fact that it results in a more deterministic outcome is very welcome.
 > If you rebase this patch on top of the current minibuffer.el, I'll be
 > happy to push it.

I will send an updated patch.

>>  From 23f306510c4a00b539607b9e57486c7fb72f37bf Mon Sep 17 00:00:00 2001
>> From: Daniel Mendler <mail@daniel-mendler.de>
>> Date: Mon, 19 Apr 2021 13:17:23 +0200
>> Subject: [PATCH 5/6] completion-all-sorted-completions: Sort candidates in a
>>   single pass
> Does this result in a measurable difference?
> The assumptions about maximum size and length aren't ideal, so unless
> there's a clear performance argument, I think we're better off sticking
> to the multiple passes.

>> * lisp/minibuffer.el (completion-all-sorted-completions): Sort by
>> history position, length and alphabetically.
> Here also: have you compared the performance of multiple calls to `sort`
> vs a single call to sort with a more costly comparison function?
> I'd expect the difference to be negligible (and having a separate
> alphabetical sort at the beginning would save us from having to handle
> it twice (i.e. in the two different branches)).

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).

The important change is really the quadratic one. 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?

Daniel