[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [PATCH] `completing-read`: Add `group-function` support to completio

From: Daniel Mendler
Subject: Re: [PATCH] `completing-read`: Add `group-function` support to completion metadata (REVISED PATCH)
Date: Sun, 25 Apr 2021 23:26:11 +0200

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


reply via email to

[Prev in Thread] Current Thread [Next in Thread]