bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[Daniel Mendler]

The recently introduced `icomplete-vertical-mode` should support the
`group-function`, which can be specified by the completion metadata. The
group function allows grouping the completion candidates by group titles.

Additional to the default completion UI, support for group functions is
already present in the following vertical minibuffer UIs, which are
similar to `icomplete-vertical-mode`: Vertico (GNU ELPA), Selectrum
(MELPA) and Icomplete-vertical (MELPA).

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[João Távora]

Daniel Mendler <mail@daniel-mendler.de> writes:

> The recently introduced `icomplete-vertical-mode` should support the
> `group-function`, which can be specified by the completion metadata. The
> group function allows grouping the completion candidates by group titles.
>
> Additional to the default completion UI, support for group functions is
> already present in the following vertical minibuffer UIs, which are
> similar to `icomplete-vertical-mode`: Vertico (GNU ELPA), Selectrum
> (MELPA) and Icomplete-vertical (MELPA).

I just tried

   (setq xref-show-definitions-function 'xref-show-definitions-completing-read)

To enable what seems to be the only table in Emacs core that has this
feature with fido-vertical-mode.

It seemed to do the right thing, prepending each entry with the name of
its associated "group".  Is this what it means to support this?  If so,
I'll close.  Else, please explain what support you're looking for.

Thanks,
João

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[Kévin Le Gouguec]

João Távora <joaotavora@gmail.com> writes:

> It seemed to do the right thing, prepending each entry with the name of
> its associated "group".  Is this what it means to support this?  If so,
> I'll close.  Else, please explain what support you're looking for.

I think Daniel is referring to what happens if you set completions-group
to t and type e.g. C-x 8 RET ROMAN TAB TAB (without icomplete): you will
see two "sections" titled 'symbol' and 'ancient-symbol'.

Right now icomplete-vertical-mode does not make use of this information,
AFAICT (unlike e.g. Vertico).

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[João Távora]

Kévin Le Gouguec <kevin.legouguec@gmail.com> writes:

> João Távora <joaotavora@gmail.com> writes:
>
>> It seemed to do the right thing, prepending each entry with the name of
>> its associated "group".  Is this what it means to support this?  If so,
>> I'll close.  Else, please explain what support you're looking for.
>
> I think Daniel is referring to what happens if you set completions-group
> to t and type e.g. C-x 8 RET ROMAN TAB TAB (without icomplete): you will
> see two "sections" titled 'symbol' and 'ancient-symbol'.

Thanks you, easy to reproduce and see clearly what you mean now that
you've filled the missing information in this bug report.

> Right now icomplete-vertical-mode does not make use of this information,
> AFAICT (unlike e.g. Vertico).

That's right.  I guess I'll copy Vertico's UI here, it seems reasonable.

João

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[João Távora]

[Dmitry, I've tagged you since you're generally interested in this
stuff.]

João Távora <joaotavora@gmail.com> writes:
> Kévin Le Gouguec <kevin.legouguec@gmail.com> writes:
>> I think Daniel is referring to what happens if you set completions-group
>> to t and type e.g. C-x 8 RET ROMAN TAB TAB (without icomplete): you will
>> see two "sections" titled 'symbol' and 'ancient-symbol'.
> Thanks you, easy to reproduce and see clearly what you mean now 

I've pushed this feature.  This is how I tested:

  src/emacs -Q --eval '(setq completions-group t)' \
               --eval '(setq xref-show-definitions-function (quote xref-show-definitions-completing-read))'
               -f fido-vertical-mode

  C-U M-. xref-location-marker RET

This should produce 5 locations.  It shows, with section headers, how 4
of these belong to xref.el and 1 belongs to elisp-mode.el.  When typing
a pattern which leads to filtering (e.g. with flex) sections are
preserved.  Sane scrolling should also be maintained, though this was
complicated to get right and may still have some bugs (I haven't
noticed any yet.)

I noticed a quirk, though.  If I add '-l etags' to the 'emacs -Q' line,
one gets 6 matches instead of 5 (due to etags having another
xref-location-marker).  That's fine, but due to the default
alphanumeric/length sorting, it gets shoved into the group of xref.el
matches and thus we get two xref.el groups.  I.e. it looks like

    xref.el
    (cl-defgeneric xref-location-marker)                          
    (cl-defmethod xref-location-marker ((l xref-file-location)))  
    (cl-defmethod xref-location-marker ((l xref-bogus-location))) 
    etags.el
    (cl-defmethod xref-location-marker ((l xref-etags-location))) 
    xref.el
    (cl-defmethod xref-location-marker ((l xref-buffer-location)))
    elisp-mode.el
    (cl-defmethod xref-location-marker ((l xref-elisp-location)))

I don't use completions-group so I don't care strongly for this, but I
believe that this is generally undesired, for non-filtering scenarios.
All the entries from the xref.el group should probably be clumped
together.  If a user were flex-matching and thus expecting certain sort
score-based order, it _would_ make sense to me, but here no flexy things
were happening at all.

To fix this, perhaps the default sorting methods should be turned off in
completion-all-sorted-completions in minibuffer.el if a table supplies
`group-function`.  A patch for this is after my sig.

Alternatively, tables that do support `group-function` could also start
specifying:

    (display-sort-function . identity)

I've tested both alternatives and they seem to do the right thing.  But
this may be the subject for some other bug, if someone cares.

Anyway, I'm marking this closed this bug since its main work is done.
Feedback welcome, of course.

João

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index ffcd5d88ab..20fbc326a2 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -1506,17 +1506,18 @@ completion-all-sorted-completions
           (setq all (delete-dups all))
           (setq last (last all))
 
-          (if sort-fun
-              (setq all (funcall sort-fun all))
-            ;; Sort first by length and alphabetically.
-            (setq all (minibuffer--sort-by-length-alpha all))
-            ;; Sort by history position, put the default, if it
-            ;; exists, on top.
-            (when (minibufferp)
-              (setq all (minibuffer--sort-by-position
-                         (minibuffer--sort-preprocess-history
-                          (substring string 0 base-size))
-                         all))))
+          (cond (sort-fun
+                 (setq all (funcall sort-fun all)))
+                ((not (completion-metadata-get all-md 'group-function))
+                 ;; Sort first by length and alphabetically.
+                 (setq all (minibuffer--sort-by-length-alpha all))
+                 ;; Sort by history position, put the default, if it
+                 ;; exists, on top.
+                 (when (minibufferp)
+                   (setq all (minibuffer--sort-by-position
+                              (minibuffer--sort-preprocess-history
+                               (substring string 0 base-size))
+                              all)))))

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[Kévin Le Gouguec]

João Távora <joaotavora@gmail.com> writes:

> To fix this, perhaps the default sorting methods should be turned off in
> completion-all-sorted-completions in minibuffer.el if a table supplies
> `group-function`.  A patch for this is after my sig.

FWIW (I didn't take the time to understand the ins and outs of the
completion system nor the changes that are being made; sorry about
that), with this tentative patch, Icomplete seems to honour
read-char-by-name-sort.  With icomplete enabled and
read-char-by-name-sort set to 'code, try

    C-x 8 RET CLOCK FACE

- with the current master branch, the completions are sorted
  alphabetically,
- with the tentative patch applied, the completions are sorted by code
  point.

This seems to compose well with completions-group AFAICT (see e.g. C-x 8
RET ROMAN).

At any rate, thanks for teaching icomplete-vertical about
group-function!

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[João Távora]

[-- Attachment #1: Type: text/plain, Size: 936 bytes --]

On Thu, Aug 19, 2021, 13:38 Kévin Le Gouguec <kevin.legouguec@gmail.com>
wrote:

> João Távora <joaotavora@gmail.com> writes:
>
> FWIW (I didn't take the time to understand the ins and outs of the
> completion system nor the changes that are being made; sorry about
> that),


Don't beat yourself over it, it's not an easy or pleasent thing to
understand.

with this tentative patch, Icomplete seems to honour
> read-char-by-name-sort.  With icomplete enabled and
> read-char-by-name-sort set to 'code, try
>
>     C-x 8 RET CLOCK FACE
>
> - with the current master branch, the completions are sorted
>   alphabetically,
> - with the tentative patch applied, the completions are sorted by code
>   point.
>

Yes I think that's the idea. But do you think that's good or bad?

This seems to compose well with completions-group AFAICT (see e.g. C-x 8
> RET ROMAN).
>

 This is good, right?

João

>

[-- Attachment #2: Type: text/html, Size: 2492 bytes --]

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[Dmitry Gutov]

On 19.08.2021 14:18, João Távora wrote:
> I noticed a quirk, though.  If I add '-l etags' to the 'emacs -Q' line,
> one gets 6 matches instead of 5 (due to etags having another
> xref-location-marker).  That's fine, but due to the default
> alphanumeric/length sorting, it gets shoved into the group of xref.el
> matches and thus we get two xref.el groups.  I.e. it looks like
> 
>      xref.el
>      (cl-defgeneric xref-location-marker)
>      (cl-defmethod xref-location-marker ((l xref-file-location)))
>      (cl-defmethod xref-location-marker ((l xref-bogus-location)))
>      etags.el
>      (cl-defmethod xref-location-marker ((l xref-etags-location)))
>      xref.el
>      (cl-defmethod xref-location-marker ((l xref-buffer-location)))
>      elisp-mode.el
>      (cl-defmethod xref-location-marker ((l xref-elisp-location)))
> 
> I don't use completions-group so I don't care strongly for this, but I
> believe that this is generally undesired, for non-filtering scenarios.
> All the entries from the xref.el group should probably be clumped
> together.  If a user were flex-matching and thus expecting certain sort
> score-based order, it_would_  make sense to me, but here no flexy things
> were happening at all.
> 
> To fix this, perhaps the default sorting methods should be turned off in
> completion-all-sorted-completions in minibuffer.el if a table supplies
> `group-function`.  A patch for this is after my sig.

We discussed this problem when group-function was introduced. Another 
approach is to just change the method of grouping: first the completions 
are sorted, and then they are sorted into groups.

The group that goes first is the group to which the first completion in 
the sorted list belongs to. It doesn't matter whether some of the 
subsequent items in it are sorted at the end of the list: as long as 
they return the same value for "group", they get put into that first group.

I wonder which strategy Daniel ultimately chose to use in Consult. 
Perhaps we should document it in the API, so that the implementations 
stay consistent.

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[Kévin Le Gouguec]

João Távora <joaotavora@gmail.com> writes:

>  FWIW (I didn't take the time to understand the ins and outs of the
>  completion system nor the changes that are being made; sorry about
>  that), 
>
> Don't beat yourself over it, it's not an easy or pleasent thing to understand.

(It's not for lack of trying either *cough*bug#40152*cough*)

>  with this tentative patch, Icomplete seems to honour
>  read-char-by-name-sort.  With icomplete enabled and
>  read-char-by-name-sort set to 'code, try
>
>      C-x 8 RET CLOCK FACE
>
>  - with the current master branch, the completions are sorted
>    alphabetically,
>  - with the tentative patch applied, the completions are sorted by code
>    point.
>
> Yes I think that's the idea. But do you think that's good or bad?

Apologies, my message was fairly clinical and lacked emphasis.
Icomplete heeding read-char-by-name-sort?  Yes please!  👍 for this
tentative patch.

>  This seems to compose well with completions-group AFAICT (see e.g. C-x 8
>  RET ROMAN).
>
>  This is good, right?

Yes, also good 👍

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[João Távora]

Dmitry Gutov <dgutov@yandex.ru> writes:
> On 19.08.2021 14:18, João Távora wrote:

>> completion-all-sorted-completions in minibuffer.el if a table supplies
>> `group-function`.  A patch for this is after my sig.
>
> We discussed this problem when group-function was introduced. Another
> approach is to just change the method of grouping: first the
> completions are sorted, and then they are sorted into groups.

That's a possiblity. But it might be performing too much work, at least
at first sight.  For the C-x 8 RET case and the xref table (the only
tables I know which use this) things seem to be naturally put into
groups already.  So sorting them alphabetically, by length, by history,
and _then_ destroying most (but not all) with the grouping could be not
so interesting if the there's a big a price to pay.

I recommend whatever is done that some quantitative benchmarking is
performed to the before/after.  Enabling fido-vertical-mode and pressing
C-u C-x C-e C-m after

   (benchmark-run (call-interactively 'insert-char))

Seems to be a decent way to measure.

Currently, with the alpha/length/history sorting, it takes about 1
second in my machine.  Without any sorting (and the natural grouping),
takes about 0.6 seconds.  You should measure what the re-grouping
sorting does.

João

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[Dmitry Gutov]

On 19.08.2021 22:41, João Távora wrote:

>> We discussed this problem when group-function was introduced. Another
>> approach is to just change the method of grouping: first the
>> completions are sorted, and then they are sorted into groups.
> 
> That's a possiblity. But it might be performing too much work, at least
> at first sight.

Not sure I understand. Grouping is a linear operation, isn't it? O(N).

Which is generally cheaper than the sorting step that came before.

> For the C-x 8 RET case and the xref table (the only
> tables I know which use this) things seem to be naturally put into
> groups already.  So sorting them alphabetically, by length, by history,
> and _then_ destroying most (but not all) with the grouping could be not
> so interesting if the there's a big a price to pay.

Could be it misses information.

OTOH, if you split completions belonging to the same group apart, you 
can end up with a list where there as as many group headers, as there 
completions (in the extreme case).

What behavior does (setq completions-group t) have? It affects the 
default UI, IIUC.

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[João Távora]

[-- Attachment #1: Type: text/plain, Size: 2626 bytes --]

On Thu, Aug 19, 2021, 23:37 Dmitry Gutov <dgutov@yandex.ru> wrote:

> On 19.08.2021 22:41, João Távora wrote:
>
> > That's a possiblity. But it might be performing too much work, at least
> > at first sight.
>
> Not sure I understand. Grouping is a linear operation, isn't it? O(N).


> Which is generally cheaper than the sorting step that came before.
>

Yes, but you'd be adding to it and that is always worse than _not_ adding
to it. And there's a constant factor in front of that O(N). So that's why I
think measurements should be taken, always.

Not to mention that if the table is already "naturally" grouped upfront,
your're incurring in both the sorting cost and the grouping cost, when you
could just be skipping both with little to no downsides, I would presume.

Of course, maybe I presume wrong, but Kévins report, who does use
completions-group, seems to confirm it.

> For the C-x 8 RET case and the xref table (the only
> > tables I know which use this) things seem to be naturally put into
> > groups already.  So sorting them alphabetically, by length, by history,
> > and _then_ destroying most (but not all) with the grouping could be not
> > so interesting if the there's a big a price to pay.
>
> Could be it misses information.
>

? Don't understand this...

OTOH, if you split completions belonging to the same group apart, you
> can end up with a list where there as as many group headers, as there
> completions (in the extreme case).
>

That's true. That's why my idea is to skip sorting altogether when tables
have a group-function, under the assumption that good speed matters much
more than applying the default sorting within each group.

For example, what does it matter to have a recently chosen UTF-8 completion
bubble up to the top of a group that's buried deep down in the long list of
groups? Not much, I think. And largely the same for the length and
lexicographical sorting.

I'd even venture to say it's like this for any table with a group-function,
though I only know two such tables. And that's why I proposed that generic
minibuffer.el patch. But, the alternative, to do it per table, could also
be fine and is reasonably short, too.

What behavior does (setq completions-group t) have?


Seems to be a flag that controls the presence of 'group-function' in some
tables. Can't speak of the other UIs, but icomplete just honors
'group-function' and does not double check the flag. It could, if it were
relevant, I guess.

It affects the default UI, IIUC.


Yes, I believe so. But what is the relevance?


João

[-- Attachment #2: Type: text/html, Size: 4856 bytes --]

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[Dmitry Gutov]

On 20.08.2021 02:39, João Távora wrote:

>     Not sure I understand. Grouping is a linear operation, isn't it? O(N).
> 
> 
>     Which is generally cheaper than the sorting step that came before.
> 
> 
> Yes, but you'd be adding to it and that is always worse than _not_ 
> adding to it.

True, but since sorting has higher complexity, for large N it should 
take much longer, and for small N anything is fast anyway.

> And there's a constant factor in front of that O(N). So 
> that's why I think measurements should be taken, always.

Please go ahead, if you like. I just wanted to make a couple of 
suggestions here.

> Not to mention that if the table is already "naturally" grouped upfront, 
> your're incurring in both the sorting cost and the grouping cost, when 
> you could just be skipping both with little to no downsides, I would 
> presume.

Right. I just don't think either is costly, most of the time.

> Of course, maybe I presume wrong, but Kévins report, who does use 
> completions-group, seems to confirm it.

Performance degradation? Guess I missed it.

>     Could be it misses information.
> 
> 
> ? Don't understand this...

Maybe I should say: destroys information. One conveyed by the original 
sorting order.

>     OTOH, if you split completions belonging to the same group apart, you
>     can end up with a list where there as as many group headers, as there
>     completions (in the extreme case).
> 
> 
> That's true. That's why my idea is to skip sorting altogether when 
> tables have a group-function, under the assumption that good speed 
> matters much more than applying the default sorting within each group.
> 
> For example, what does it matter to have a recently chosen UTF-8 
> completion bubble up to the top of a group that's buried deep down in 
> the long list of groups? Not much, I think. And largely the same for the 
> length and lexicographical sorting.

Suppose the sorting was performed by the 'flex' style (as one example).

Then, at the very least, you will see at the top of the first group the 
best available match for your input. That's useful, I think. Even if the 
remaining items in that group are much worse matches.

>     What behavior does (setq completions-group t) have? 
> 
> 
> Seems to be a flag that controls the presence of 'group-function' in 
> some tables. Can't speak of the other UIs, but icomplete just honors 
> 'group-function' and does not double check the flag. It could, if it 
> were relevant, I guess.
> 
>     It affects the default UI, IIUC.
> 
> 
> Yes, I believe so. But what is the relevance?

icomplete's grouping behavior should probably match the default UI's 
behavior in that regard. Or, if people actually don't like it, see it 
changed in both places.

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[João Távora]

Dmitry Gutov <dgutov@yandex.ru> writes:

> On 20.08.2021 02:39, João Távora wrote:
>
>>     Not sure I understand. Grouping is a linear operation, isn't it? O(N).
>>     Which is generally cheaper than the sorting step that came
>> before.
>> Yes, but you'd be adding to it and that is always worse than _not_
>> adding to it.
>
> True, but since sorting has higher complexity, for large N it should
> take much longer, and for small N anything is fast anyway.

This is IME a common misunderstanding, that is usually cleared up by the
phrase "constant factors matter".  In

   k1 * O(NlogN) + k2 * O(N)

which is our example, Big-O notation can drop the constants to describe
the growth rate of functions, but in the real world and for a real N, k1
and k2 matter.

In the particular case we're discussing k2 isn't even under "our"
(meaning minibuffer.el or "the framework") control.  It is determined by
whatever the completion table author put into `group-function`.  So
eliding the second term from that equation may be premature.

>> And there's a constant factor in front of that O(N). So that's why I
>> think measurements should be taken, always.
>
> Please go ahead, if you like. I just wanted to make a couple of
> suggestions here.

I don't think we understand each other.  If I understand correctly, your
suggestions is to add a re-grouping, meaning grouping on top the current
sorting, under the presumption that it will not significantly slow
things down.  That's fine.  My suggestion, however, is different.  It is
to skip the current sorting for these cases altogether.  My suggestion
has an actual implementation in the form of a patch, has been tested by
Kévin and has been benchmarked to show that it speeds up the process.

You suggestion, as far as I can see, has none of these three elements.
So if you or someone else wants to experiment with the re-grouping (with
whichever implemention), then it is you or that someone who should
perform these measurements.  I can't imagine or guess what re-grouping
implementation you or anyone else has in mind, and if even I could I
wouldn't be able to take measurements from my imagination.

>> Not to mention that if the table is already "naturally" grouped
>> upfront, your're incurring in both the sorting cost and the grouping
>> cost, when you could just be skipping both with little to no
>> downsides, I would presume.
>
> Right. I just don't think either is costly, most of the time.

Did you read my previous message where I reported that C-x 8 RET takes
currently takes about a second to compute completions and only 0.6
seconds when sorting is removed?

> Maybe I should say: destroys information. One conveyed by the original
> sorting order.

Yes, both the current sorting and your proposed sorting-and-regrouping
implementation will do that.

> Then, at the very least, you will see at the top of the first group
> the best available match for your input. That's useful, I think. Even
> if the remaining items in that group are much worse matches.

I thought we weren't discussing pattern-matching scenarios here, but OK,
this is what currently happens (meaning, you can try it yourself!).  As
always with flex the best available match globally is sorted to the top,
along with its group.  Icomplete will chose about, say, 10 best matches
to display.  If two first ones happen happens to have same group,
Icomplete will shown under the same section.  If the third has another
group, another section header.  If the fourth global best has again the
same group as the first two, another section header.  This is flex doing
its thing.

> icomplete's grouping behavior should probably match the default UI's
> behavior in that regard. Or, if people actually don't like it, see it
> changed in both places.

Anything and everything could be interesting, I guess. If you want to
propose changes to icomplete, propose changes to icomplete, as in with
actual code.  Then things can be evaluated against reality

João

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[João Távora]

Dmitry Gutov <dgutov@yandex.ru> writes:

> On 20.08.2021 02:39, João Távora wrote:

> icomplete's grouping behavior should probably match the default UI's
> behavior in that regard. Or, if people actually don't like it, see it
> changed in both places.

Because it was fairly easy to, i tested the default UI with grouping and
C-x 8 RET.  It seems that it doesn't use
completion-all-sorted-completions, and hence doesn't do the normal
alphabetical+length+recency sorting (let's call it a+l+r from now on) at
all by default.  It does do the re-grouping though.  And it takes a long
time, about 3-4 seconds (when one presses TAB at the prompt) to see the
first page of the completions list.

This is versus Icomplete which about a second  (or even less if
you skip the a+l+r).

So whatever the default completion UI does, I don't think Icomplete
should imitate it if it means the same slow behaviour.

The default UI can do some sorting on top of regrouping if you set yet
another variable completions-group-sort, but then it will be only
alphabetical, not a+l+r.  No idea why.

However, I've also discovered that my previous assumption that C-x 8 RET
returns naturally grouped chars is also wrong.  They are _not_ naturally
grouped.

João

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[Dmitry Gutov]

On 20.08.2021 13:35, João Távora wrote:

>> True, but since sorting has higher complexity, for large N it should
>> take much longer, and for small N anything is fast anyway.
> 
> This is IME a common misunderstanding, that is usually cleared up by the
> phrase "constant factors matter".  <...>
> 
> In the particular case we're discussing k2 isn't even under "our"
> (meaning minibuffer.el or "the framework") control.  It is determined by
> whatever the completion table author put into `group-function`.  So
> eliding the second term from that equation may be premature.

Even if the constant factor is somehow significant (which would be a 
surprise, but OK, some pathological cases might turn up), if you do any 
kind of grouping at all, you will incur the same cost, won't you?

Unless you only apply the grouping to the first V matches (where it's 
the number of lines visible in the minibuffer). But even then my 
suggestion can be adapted to this approach. Using the example from the 
message I replied to, you would put all the matches in 'xref.el' into 
the same group, not two groups.

The cost of the grouping function doesn't matter when making this choice.

>>> And there's a constant factor in front of that O(N). So that's why I
>>> think measurements should be taken, always.
>>
>> Please go ahead, if you like. I just wanted to make a couple of
>> suggestions here.
> 
> I don't think we understand each other.  If I understand correctly, your
> suggestions is to add a re-grouping, meaning grouping on top the current
> sorting, under the presumption that it will not significantly slow
> things down.

I took an existing example of a grouping UI and suggested a slightly 
different one. With no expected difference in performance.

> That's fine.  My suggestion, however, is different.  It is
> to skip the current sorting for these cases altogether.  My suggestion
> has an actual implementation in the form of a patch, has been tested by
> Kévin and has been benchmarked to show that it speeds up the process.

And I offered a reason for why people might still want that sorting.

That reason is not related to performance.

> You suggestion, as far as I can see, has none of these three elements.
> So if you or someone else wants to experiment with the re-grouping (with
> whichever implemention),

Why do you call it re-grouping? Grouping happens after sorting, there is 
no prior grouping step.

>>> Not to mention that if the table is already "naturally" grouped
>>> upfront, your're incurring in both the sorting cost and the grouping
>>> cost, when you could just be skipping both with little to no
>>> downsides, I would presume.
>>
>> Right. I just don't think either is costly, most of the time.
> 
> Did you read my previous message where I reported that C-x 8 RET takes
> currently takes about a second to compute completions and only 0.6
> seconds when sorting is removed?

I was talking about the grouping step, obviously. Not being costly.

Try disabling grouping. Is completion still slow? Then it's a problem 
with sorting speed that needs to be solved separately anyway.

>> Then, at the very least, you will see at the top of the first group
>> the best available match for your input. That's useful, I think. Even
>> if the remaining items in that group are much worse matches.
> 
> I thought we weren't discussing pattern-matching scenarios here, but OK,
> this is what currently happens (meaning, you can try it yourself!).  As
> always with flex the best available match globally is sorted to the top,
> along with its group.  Icomplete will chose about, say, 10 best matches
> to display.  If two first ones happen happens to have same group,
> Icomplete will shown under the same section.  If the third has another
> group, another section header.  If the fourth global best has again the
> same group as the first two, another section header.  This is flex doing
> its thing.

Yup. This is what I suggested to change.

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[João Távora]

Dmitry Gutov <dgutov@yandex.ru> writes:

> On 20.08.2021 13:35, João Távora wrote:

> Even if the constant factor is somehow significant (which would be a
> surprise, but OK, some pathological cases might turn up), if you do
> any kind of grouping at all, you will incur the same cost, won't you?

Some tables and grouping strategies, like the xref table, seem to be
"naturally" grouped by the way you harvest candidates.  For others, we
could make just make it so that they are.  That "make it so" wouldn't
necessarily mean calling `group-function` for every candidate.

> Unless you only apply the grouping to the first V matches (where it's
> the number of lines visible in the minibuffer). But even then my
> suggestion can be adapted to this approach. Using the example from the
> message I replied to, you would put all the matches in 'xref.el' into
> the same group, not two groups.
>
> The cost of the grouping function doesn't matter when making this
> choice.

Yes, I think you see what you mean.  But I also imagine it would be
terrifyingly confusing for a user of a scrolling dropdown to see
candidates jump back and forth into their groups as the user scrolls
down to see a new candidate and hide another.  If what I imagine isn't
what you mean, maybe you could code something up and show what you mean.

> I took an existing example of a grouping UI and suggested a slightly
> different one. With no expected difference in performance.

As I wrote, that's a fine presumption/intutition, though it is, IMHO,
vunerable to the graces of whatever 'group-function' has been coded by
the completion table author.  You should now confirm your intuition with
an actual patch and benchmarks.

My original point about "doing too much work" is that it is almost
impossible that it will somehow make the process _quicker_ than what it
actually is right now.  My suggestion to eliminate sorting _does_ makes
it quicker, demonstrably.

But maybe the two suggestions can even coexist: eliminate a+l+r sorting
and add re-grouping.  That is likely quicker than the current state.

>> You suggestion, as far as I can see, has none of these three elements.
>> So if you or someone else wants to experiment with the re-grouping (with
>> whichever implemention),
>
> Why do you call it re-grouping? Grouping happens after sorting, there
> is no prior grouping step.

For example, in xref.el the matches provided by the completion table
are, IIUC, already "naturally" grouped, because they are collected file
by file, and the file is the group.  That grouping is then completely
destroyed by a+l+r sorting.  Your proposal would, I presume, destroy
that sorting to restore grouping.  Hence "re-group".

Note that I previously assumed, mistakenly, that the entries in C-x 8
RET were also naturally grouped.  They're not.  They could very easily
be, and with no performance penalty.

>>>> upfront, your're incurring in both the sorting cost and the grouping
>>>> cost, when you could just be skipping both with little to no
>>>> downsides, I would presume.
>>> Right. I just don't think either is costly, most of the time.
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>> Did you read my previous message where I reported that C-x 8 RET
>> currently takes about a second to compute completions and only 0.6
>> seconds when sorting is removed?
> I was talking about the grouping step, obviously. Not being costly.

You wrote "I just don't think either is costly".  

> Try disabling grouping. Is completion still slow? Then it's a problem
> with sorting speed that needs to be solved separately anyway.

icomplete.el doesn't do any grouping, it merely prints the grouping
information as headers for the few matches that it will print.
completion-all-sorted-completions also doesn't care about grouping.  So
there's nothing to disable in that regard.

>> This is flex doing its thing.
> Yup. This is what I suggested to change.

As I explained two or three times now: you can.  In a new dmitry-flex
style.  That style is only a few lines of code away, I suppose.  Or a
defcustom, if you prefer those.  The current behaviour for 'flex' is the
correct one.  It was conceived like this.  flex scoring trumps grouping,
table orders, etc...  If you don't like this you can change this, like
everything in Emacs.

João

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[Dmitry Gutov]

On 21.08.2021 12:40, João Távora wrote:

> Some tables and grouping strategies, like the xref table, seem to be
> "naturally" grouped by the way you harvest candidates.  For others, we
> could make just make it so that they are.  That "make it so" wouldn't
> necessarily mean calling `group-function` for every candidate.

Whether it's called for every candidate, is a UI/design choice.

>> The cost of the grouping function doesn't matter when making this
>> choice.
> 
> Yes, I think you see what you mean.  But I also imagine it would be
> terrifyingly confusing for a user of a scrolling dropdown to see
> candidates jump back and forth into their groups as the user scrolls
> down to see a new candidate and hide another.  If what I imagine isn't
> what you mean, maybe you could code something up and show what you mean.

I suppose yes, if you only group candidates that are visible on the 
screen, it could lead to jumping. Good point. Then I would suggest to go 
back to "global" grouping.

>>> You suggestion, as far as I can see, has none of these three elements.
>>> So if you or someone else wants to experiment with the re-grouping (with
>>> whichever implemention),
>>
>> Why do you call it re-grouping? Grouping happens after sorting, there
>> is no prior grouping step.
> 
> For example, in xref.el the matches provided by the completion table
> are, IIUC, already "naturally" grouped, because they are collected file
> by file, and the file is the group.  That grouping is then completely
> destroyed by a+l+r sorting.  Your proposal would, I presume, destroy
> that sorting to restore grouping.  Hence "re-group".

I see.

The order of completions coming from xref is essentially random. Yes, 
they are grouped by files (usually), but the files are not coming in any 
particular order. So I would prefer not to skip the sorting step.

Of course, there might be different scenarios and preferences in that 
regard.

> Note that I previously assumed, mistakenly, that the entries in C-x 8
> RET were also naturally grouped.  They're not.  They could very easily
> be, and with no performance penalty.
> 
>>>>> upfront, your're incurring in both the sorting cost and the grouping
>>>>> cost, when you could just be skipping both with little to no
>>>>> downsides, I would presume.
>>>> Right. I just don't think either is costly, most of the time.
>             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>>> Did you read my previous message where I reported that C-x 8 RET
>>> currently takes about a second to compute completions and only 0.6
>>> seconds when sorting is removed?
>> I was talking about the grouping step, obviously. Not being costly.
> 
> You wrote "I just don't think either is costly".

Okay. Sorting seems to indeed be costly in this case (if I trust your 
measurements).

Sorting is part of the default completion behavior (with grouping or 
not). You want to remove it instead of fixing?

>> Try disabling grouping. Is completion still slow? Then it's a problem
>> with sorting speed that needs to be solved separately anyway.
> 
> icomplete.el doesn't do any grouping, it merely prints the grouping
> information as headers for the few matches that it will print.
> completion-all-sorted-completions also doesn't care about grouping.  So
> there's nothing to disable in that regard.

That addressed 3 words out of 20.

>>> This is flex doing its thing.
>> Yup. This is what I suggested to change.
> 
> As I explained two or three times now: you can.  In a new dmitry-flex
> style.  That style is only a few lines of code away, I suppose.  Or a
> defcustom, if you prefer those.  The current behaviour for 'flex' is the
> correct one.  It was conceived like this.  flex scoring trumps grouping,
> table orders, etc...  If you don't like this you can change this, like
> everything in Emacs.

Nothing I suggested should call for a change in completion style.

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[João Távora]

Dmitry Gutov <dgutov@yandex.ru> writes:

> On 21.08.2021 12:40, João Távora wrote:

>> Yes, I think you see what you mean.  But I also imagine it would be
>> terrifyingly confusing for a user of a scrolling dropdown to see
>> candidates jump back and forth into their groups as the user scrolls
>> down to see a new candidate and hide another.  If what I imagine isn't
>> what you mean, maybe you could code something up and show what you mean.
>
> I suppose yes, if you only group candidates that are visible on the
> screen, it could lead to jumping. Good point. Then I would suggest to
> go back to "global" grouping.

Then do.  Go back to that experiment and its drawbacks and actually
prototype it the way you envision it.  Then share results here.

> The order of completions coming from xref is essentially random. Yes,
> they are grouped by files (usually), but the files are not coming in
> any particular order. So I would prefer not to skip the sorting step.
> Of course, there might be different scenarios and preferences in that
> regard.

If you sort the groups but not _inside_ the groups, you can skip the
expensive sorting and still keep some order.  Though in xref nothing is
particularly expensive anyway.

> Okay. Sorting seems to indeed be costly in this case (if I trust your
> measurements).

You can do them yourself.  I posted what I measured from.  If it's not
clear, you should let me know.

> Sorting is part of the default completion behavior (with grouping or
> not). You want to remove it instead of fixing?

It's very simple: As I've explained some times already, I contend, and
Kévin at least seems to agree, is that when there grouping the current
slow 'a+l+r' sorting is not particularly useful.  At least the "r ===
recently" part seems completely useful there.  But the 'a+l' also seem
to be kinda lame, at least for xref and C-x 8 RET.

Now, if one agrees that sorting not particularly useful when there is
grouping and that is significantly slows things down, then there is a
good case for removing it when there is grouping.  It's super simple.

>>> Try disabling grouping. Is completion still slow? Then it's a problem
>>> with sorting speed that needs to be solved separately anyway.
>> icomplete.el doesn't do any grouping, it merely prints the grouping
>> information as headers for the few matches that it will print.
>> completion-all-sorted-completions also doesn't care about grouping.  So
>> there's nothing to disable in that regard.
>
> That addressed 3 words out of 20.

How in heck could I adress the remaining ones which refer to the first
three if those three were nonsense?  

Look, you're asking me to do vaguely worded experiments that you can
perfectly run yourself.  If you understand what you mean, go run them
yourself, document your findings and share them here for others to work
from.  It'll save us all time.

>>>> This is flex doing its thing.
>>> Yup. This is what I suggested to change.
>> As I explained two or three times now: you can.  In a new
>> dmitry-flex
>> style.  That style is only a few lines of code away, I suppose.  Or a
>> defcustom, if you prefer those.  The current behaviour for 'flex' is the
>> correct one.  It was conceived like this.  flex scoring trumps grouping,
>> table orders, etc...  If you don't like this you can change this, like
>> everything in Emacs.
>
> Nothing I suggested should call for a change in completion style.

Then I misunderstood, again.  You did suggest changes to the 'flex'
completion style in another bug thread, I naturally though you meant
that.  Here, you wrote "this is what I suggested to change" after I
described how the flex completion style worked.  You provide no accurate
description or code of what you want changed.  If you weren't a
programmer or especially versed in Elisp, I would comprehend.  Given
that you are, it is baffling, time-wasting and quite tiring.  I'll just
stop answering your hypothetical questions.

João

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[Dmitry Gutov]

On 21.08.2021 15:42, João Távora wrote:
> Dmitry Gutov<dgutov@yandex.ru>  writes:
> 
>> On 21.08.2021 12:40, João Távora wrote:
>>> Yes, I think you see what you mean.  But I also imagine it would be
>>> terrifyingly confusing for a user of a scrolling dropdown to see
>>> candidates jump back and forth into their groups as the user scrolls
>>> down to see a new candidate and hide another.  If what I imagine isn't
>>> what you mean, maybe you could code something up and show what you mean.
>> I suppose yes, if you only group candidates that are visible on the
>> screen, it could lead to jumping. Good point. Then I would suggest to
>> go back to "global" grouping.
> Then do.  Go back to that experiment and its drawbacks and actually
> prototype it the way you envision it.  Then share results here.

I don't think I'm obligated to support every trivial suggestion with a 
patch and a benchmark.

Or explain, from various POVs, why removing the sorting step "because 
it's expensive" is faulty reasoning.

Or why the grouping approach in icomplete mode should match what the 
default UI does and what other completion UIs (from which the grouping 
feature was extracted) do as well.

Whatever, do what you like. I'm out of this thread.

bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`

[João Távora]

Dmitry Gutov <dgutov@yandex.ru> writes:

> I don't think I'm obligated to support every trivial suggestion with a
> patch and a benchmark.

Of course you're not obliged to, but the fact that you won't code up
your own "trivial suggestion" is eloquent.

> Or explain, from various POVs, why removing the sorting step "because
> it's expensive" is faulty reasoning.

Could be, if it _were_ the reasoning.  But it's not, as is quite easy to
read here.

> Or why the grouping approach in icomplete mode should match what the
> default UI does and what other completion UIs (from which the grouping
> feature was extracted) do as well.

The sorting in the default completion UI is already discrepant to
completions-all-sorted-completions, regardless of grouping.  It's also
quite slow, as reported.  I doubt we want Icomplete to "match" that (not
to mention the fact that Icomplete is a different type of UI).

> Whatever, do what you like. I'm out of this thread.

I've pushed ba852512f23fdab674086e35d4207e3970dd0912 to fix the
described bugs and wrap this up.  Left a TODO in minibuffer.el for
anyone to experiment with "trivial suggestions" (or complex ones at
that).

João