Re: [PATCH] `completing-read`: Add `group-function` support to completion metadata (REVISED PATCH)

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

On 4/25/21 10:45 PM, Juri Linkov wrote:> I tried and it looks really 
nice.  One question about performance:
 > there are 3 calls of the same function on every completion candidate:
 > twice it's called with the nil arg, and one call with the 'transform' 
arg:

Thanks, I am glad you like the UI.

 >> +(defun minibuffer--group-by (fun elems)
 >> +      (let* ((key (funcall fun cand nil))
 >
 >> @@ -1780,6 +1829,12 @@ completion--insert-strings
 >> +          (let ((title (funcall group-fun (if (consp str) (car str) 
str) nil)))
 >
 >> @@ -1825,8 +1880,15 @@ completion--insert-strings
 >> +                        (funcall group-fun str 'transform)
 >
 >> @@ -2098,15 +2171,22 @@ minibuffer-completion-help
 >> +                              (minibuffer--group-by group-fun 
completions)))
 >
 > My concern is how fast it will work on a large list of candidate strings?

The current implementation already focuses quite a bit on efficiency 
since I am using it in my continuously updating vertical UI (Vertico). 
The function `minibuffer--group-by` is linear time and significantly 
faster than the sorting which comes before it. It is crucial that the 
group function does not allocate when called with transform=nil, 
otherwise `minibuffer--group-by` would lead to a slowdown.

Then the calls to the group function with transform/=nil are allowed to 
be more costly, since they only occur for the candidates which are 
displayed by the UI. These calls will then not matter in comparison to 
the other costs of displaying the candidates.

 > Would it be possible to optimize it to call the group function only once
 > on every candidate?  This might require changing the data structure,
 > for example, to an alist like is returned by `seq-group-by`.

One could return a cons of the transformed candidate and the title, but 
this has the downside that you always compute/allocate the transformed 
candidate. It is better to perform the candidate transformation lazily 
only for the candidates which are actually displayed. This is similar to 
the computation of annotations/affixations, which are only computed 
lazily if the completion UI displays only a subset of the actual candidates.

Dmitry, Stefan and I discussed multiple possible incarnations of such a 
group-function functionality 
(https://github.com/minad/consult/issues/283). The current solution 
turned out to be an efficient and simple solution. We also discussed 
solutions which avoided multiple function calls for every candidate, but 
these were more complex. Note that I am using group functions heavily in 
my Consult package with the design proposed here.

 > Another variant is to put additional text properties on candidate 
strings,
 > e.g. a text property on redundant prefix with the group title that
 > completion--insert-strings then could fetch from the input string.
Yes, this would be possible, but it would be a less flexible design. I 
followed the design of the annotation/affixation-functions for this. I 
also like about the design that it is somehow "pluggable", you add the 
group-function and you can augment your completion table with grouping 
without having to do other adjustments to how the candidates are 
generated. (Note that you may still want to attach a title property to 
the candidates to ensure that the transform=nil call is fast and 
non-allocating, as I did in the xref modifications in this patch.)

Daniel