* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` @ 2021-05-20 18:56 Daniel Mendler 2021-08-17 12:17 ` João Távora 0 siblings, 1 reply; 21+ messages in thread From: Daniel Mendler @ 2021-05-20 18:56 UTC (permalink / raw) To: 48545; +Cc: Gregory Heytings 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). ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-05-20 18:56 bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` Daniel Mendler @ 2021-08-17 12:17 ` João Távora 2021-08-18 9:38 ` Kévin Le Gouguec 0 siblings, 1 reply; 21+ messages in thread From: João Távora @ 2021-08-17 12:17 UTC (permalink / raw) To: Daniel Mendler; +Cc: Gregory Heytings, 48545 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-17 12:17 ` João Távora @ 2021-08-18 9:38 ` Kévin Le Gouguec 2021-08-18 9:55 ` João Távora 0 siblings, 1 reply; 21+ messages in thread From: Kévin Le Gouguec @ 2021-08-18 9:38 UTC (permalink / raw) To: João Távora; +Cc: Daniel Mendler, Gregory Heytings, 48545 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). ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-18 9:38 ` Kévin Le Gouguec @ 2021-08-18 9:55 ` João Távora 2021-08-19 11:18 ` João Távora 0 siblings, 1 reply; 21+ messages in thread From: João Távora @ 2021-08-18 9:55 UTC (permalink / raw) To: Kévin Le Gouguec; +Cc: Daniel Mendler, Gregory Heytings, 48545 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-18 9:55 ` João Távora @ 2021-08-19 11:18 ` João Távora 2021-08-19 12:38 ` Kévin Le Gouguec 2021-08-19 15:02 ` Dmitry Gutov 0 siblings, 2 replies; 21+ messages in thread From: João Távora @ 2021-08-19 11:18 UTC (permalink / raw) To: Kévin Le Gouguec Cc: Daniel Mendler, Gregory Heytings, 48545-done, dgutov [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))))) ^ permalink raw reply related [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-19 11:18 ` João Távora @ 2021-08-19 12:38 ` Kévin Le Gouguec 2021-08-19 13:29 ` João Távora 2021-08-19 15:02 ` Dmitry Gutov 1 sibling, 1 reply; 21+ messages in thread From: Kévin Le Gouguec @ 2021-08-19 12:38 UTC (permalink / raw) To: 48545; +Cc: mail, Gregory Heytings, joaotavora, dgutov 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! ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-19 12:38 ` Kévin Le Gouguec @ 2021-08-19 13:29 ` João Távora 2021-08-19 19:36 ` Kévin Le Gouguec 0 siblings, 1 reply; 21+ messages in thread From: João Távora @ 2021-08-19 13:29 UTC (permalink / raw) To: Kévin Le Gouguec Cc: Daniel Mendler, Gregory Heytings, 48545, Dmitry Gutov [-- 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 --] ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-19 13:29 ` João Távora @ 2021-08-19 19:36 ` Kévin Le Gouguec 0 siblings, 0 replies; 21+ messages in thread From: Kévin Le Gouguec @ 2021-08-19 19:36 UTC (permalink / raw) To: João Távora Cc: Daniel Mendler, Gregory Heytings, 48545, Dmitry Gutov 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 👍 ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-19 11:18 ` João Távora 2021-08-19 12:38 ` Kévin Le Gouguec @ 2021-08-19 15:02 ` Dmitry Gutov 2021-08-19 19:41 ` João Távora 1 sibling, 1 reply; 21+ messages in thread From: Dmitry Gutov @ 2021-08-19 15:02 UTC (permalink / raw) To: 48545, joaotavora, mail 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. ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-19 15:02 ` Dmitry Gutov @ 2021-08-19 19:41 ` João Távora 2021-08-19 22:37 ` Dmitry Gutov 0 siblings, 1 reply; 21+ messages in thread From: João Távora @ 2021-08-19 19:41 UTC (permalink / raw) To: Dmitry Gutov; +Cc: mail, 48545 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-19 19:41 ` João Távora @ 2021-08-19 22:37 ` Dmitry Gutov 2021-08-19 23:39 ` João Távora 0 siblings, 1 reply; 21+ messages in thread From: Dmitry Gutov @ 2021-08-19 22:37 UTC (permalink / raw) To: João Távora; +Cc: mail, 48545 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. ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-19 22:37 ` Dmitry Gutov @ 2021-08-19 23:39 ` João Távora 2021-08-19 23:51 ` Dmitry Gutov 0 siblings, 1 reply; 21+ messages in thread From: João Távora @ 2021-08-19 23:39 UTC (permalink / raw) To: Dmitry Gutov; +Cc: Daniel Mendler, 48545 [-- 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 --] ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-19 23:39 ` João Távora @ 2021-08-19 23:51 ` Dmitry Gutov 2021-08-20 10:35 ` João Távora 2021-08-21 0:24 ` João Távora 0 siblings, 2 replies; 21+ messages in thread From: Dmitry Gutov @ 2021-08-19 23:51 UTC (permalink / raw) To: João Távora; +Cc: Daniel Mendler, 48545 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. ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-19 23:51 ` Dmitry Gutov @ 2021-08-20 10:35 ` João Távora 2021-08-21 2:09 ` Dmitry Gutov 2021-08-21 0:24 ` João Távora 1 sibling, 1 reply; 21+ messages in thread From: João Távora @ 2021-08-20 10:35 UTC (permalink / raw) To: Dmitry Gutov; +Cc: Daniel Mendler, 48545 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-20 10:35 ` João Távora @ 2021-08-21 2:09 ` Dmitry Gutov 2021-08-21 9:40 ` João Távora 0 siblings, 1 reply; 21+ messages in thread From: Dmitry Gutov @ 2021-08-21 2:09 UTC (permalink / raw) To: João Távora; +Cc: Daniel Mendler, 48545 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. ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-21 2:09 ` Dmitry Gutov @ 2021-08-21 9:40 ` João Távora 2021-08-21 12:01 ` Dmitry Gutov 0 siblings, 1 reply; 21+ messages in thread From: João Távora @ 2021-08-21 9:40 UTC (permalink / raw) To: Dmitry Gutov; +Cc: Daniel Mendler, 48545 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-21 9:40 ` João Távora @ 2021-08-21 12:01 ` Dmitry Gutov 2021-08-21 12:42 ` João Távora 0 siblings, 1 reply; 21+ messages in thread From: Dmitry Gutov @ 2021-08-21 12:01 UTC (permalink / raw) To: João Távora; +Cc: Daniel Mendler, 48545 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. ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-21 12:01 ` Dmitry Gutov @ 2021-08-21 12:42 ` João Távora 2021-08-22 13:52 ` Dmitry Gutov 0 siblings, 1 reply; 21+ messages in thread From: João Távora @ 2021-08-21 12:42 UTC (permalink / raw) To: Dmitry Gutov; +Cc: Daniel Mendler, 48545 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-21 12:42 ` João Távora @ 2021-08-22 13:52 ` Dmitry Gutov 2021-08-22 15:44 ` João Távora 0 siblings, 1 reply; 21+ messages in thread From: Dmitry Gutov @ 2021-08-22 13:52 UTC (permalink / raw) To: João Távora; +Cc: Daniel Mendler, 48545 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. ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-22 13:52 ` Dmitry Gutov @ 2021-08-22 15:44 ` João Távora 0 siblings, 0 replies; 21+ messages in thread From: João Távora @ 2021-08-22 15:44 UTC (permalink / raw) To: Dmitry Gutov; +Cc: Daniel Mendler, 48545 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
* bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` 2021-08-19 23:51 ` Dmitry Gutov 2021-08-20 10:35 ` João Távora @ 2021-08-21 0:24 ` João Távora 1 sibling, 0 replies; 21+ messages in thread From: João Távora @ 2021-08-21 0:24 UTC (permalink / raw) To: Dmitry Gutov; +Cc: Daniel Mendler, 48545 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 ^ permalink raw reply [flat|nested] 21+ messages in thread
end of thread, other threads:[~2021-08-22 15:44 UTC | newest] Thread overview: 21+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2021-05-20 18:56 bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` Daniel Mendler 2021-08-17 12:17 ` João Távora 2021-08-18 9:38 ` Kévin Le Gouguec 2021-08-18 9:55 ` João Távora 2021-08-19 11:18 ` João Távora 2021-08-19 12:38 ` Kévin Le Gouguec 2021-08-19 13:29 ` João Távora 2021-08-19 19:36 ` Kévin Le Gouguec 2021-08-19 15:02 ` Dmitry Gutov 2021-08-19 19:41 ` João Távora 2021-08-19 22:37 ` Dmitry Gutov 2021-08-19 23:39 ` João Távora 2021-08-19 23:51 ` Dmitry Gutov 2021-08-20 10:35 ` João Távora 2021-08-21 2:09 ` Dmitry Gutov 2021-08-21 9:40 ` João Távora 2021-08-21 12:01 ` Dmitry Gutov 2021-08-21 12:42 ` João Távora 2021-08-22 13:52 ` Dmitry Gutov 2021-08-22 15:44 ` João Távora 2021-08-21 0:24 ` João Távora
Code repositories for project(s) associated with this external index https://git.savannah.gnu.org/cgit/emacs.git https://git.savannah.gnu.org/cgit/emacs/org-mode.git This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.