From: "João Távora" <joaotavora@gmail.com>
To: Dmitry Gutov <dgutov@yandex.ru>
Cc: Daniel Mendler <mail@daniel-mendler.de>, 48545@debbugs.gnu.org
Subject: bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function`
Date: Fri, 20 Aug 2021 11:35:15 +0100 [thread overview]
Message-ID: <87pmu8qu8s.fsf@gmail.com> (raw)
In-Reply-To: <c3f743eb-cf8b-10bf-a9ac-04bd3c0014be@yandex.ru> (Dmitry Gutov's message of "Fri, 20 Aug 2021 02:51:15 +0300")
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
next prev parent reply other threads:[~2021-08-20 10:35 UTC|newest]
Thread overview: 21+ messages / expand[flat|nested] mbox.gz Atom feed top
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 [this message]
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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87pmu8qu8s.fsf@gmail.com \
--to=joaotavora@gmail.com \
--cc=48545@debbugs.gnu.org \
--cc=dgutov@yandex.ru \
--cc=mail@daniel-mendler.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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.