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.