From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: =?UTF-8?Q?Jo=C3=A3o_?= =?UTF-8?Q?T=C3=A1vora?= Newsgroups: gmane.emacs.bugs Subject: bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` Date: Fri, 20 Aug 2021 11:35:15 +0100 Message-ID: <87pmu8qu8s.fsf@gmail.com> References: <10d162d5-2cd6-dd87-3289-a0187dfbf51f@daniel-mendler.de> <871r6sw9iz.fsf@gmail.com> <87a6lfnld0.fsf@gmail.com> <87eearulft.fsf@gmail.com> <871r6pr8bk.fsf@gmail.com> <54e4e409-5525-b796-9e9c-582735995cc1@yandex.ru> <87r1epp6h9.fsf@gmail.com> <266d8a54-90de-e904-f548-8ec29e52923c@yandex.ru> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="4462"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux) Cc: Daniel Mendler , 48545@debbugs.gnu.org To: Dmitry Gutov Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Fri Aug 20 12:36:10 2021 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1mH1sg-0000q8-E9 for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 20 Aug 2021 12:36:10 +0200 Original-Received: from localhost ([::1]:53240 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mH1se-00088c-9I for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 20 Aug 2021 06:36:08 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:47716) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mH1sY-00088C-27 for bug-gnu-emacs@gnu.org; Fri, 20 Aug 2021 06:36:02 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:49701) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1mH1sX-0002BM-QQ for bug-gnu-emacs@gnu.org; Fri, 20 Aug 2021 06:36:01 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1mH1sX-0003Fc-Nb for bug-gnu-emacs@gnu.org; Fri, 20 Aug 2021 06:36:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: =?UTF-8?Q?Jo=C3=A3o_?= =?UTF-8?Q?T=C3=A1vora?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 20 Aug 2021 10:36:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 48545 X-GNU-PR-Package: emacs Original-Received: via spool by 48545-submit@debbugs.gnu.org id=B48545.162945572512450 (code B ref 48545); Fri, 20 Aug 2021 10:36:01 +0000 Original-Received: (at 48545) by debbugs.gnu.org; 20 Aug 2021 10:35:25 +0000 Original-Received: from localhost ([127.0.0.1]:33014 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mH1rw-0003Ek-QK for submit@debbugs.gnu.org; Fri, 20 Aug 2021 06:35:25 -0400 Original-Received: from mail-wm1-f49.google.com ([209.85.128.49]:44013) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mH1rv-0003EW-0X for 48545@debbugs.gnu.org; Fri, 20 Aug 2021 06:35:23 -0400 Original-Received: by mail-wm1-f49.google.com with SMTP id k5-20020a05600c1c85b02902e699a4d20cso5792854wms.2 for <48545@debbugs.gnu.org>; Fri, 20 Aug 2021 03:35:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:in-reply-to:references:user-agent:date :message-id:mime-version:content-transfer-encoding; bh=tdfUGpqL4skWL2wAqf3Cj/x/B2RXw0CYKLF60WtZa+w=; b=Bil/+bnlHR68R5ELKg/nLiymbmggU65j97HOutVuWKU/Twc7EwN9/a7+ujDgdSmgEW 15E336YKAV/vx3SZV4uhlqpA+tKr7HmL8NSfWIWC0Sy98uJFZsB6duq09BRHgJmkxY95 1n41HixSDhF/04SaHf7yz5/oydC32J7tZOkZSIxPjAuSLd2uRNomGiCdLideFJsflUAE 36/1nIhIj469vaRomq/QKII8tcJfZfUaZU0MrrCcvmcC63+ds9xi9ecj+qJOR11v3QgS H2mNQ5vzfbPUWxyPT+M6xn6TmWv0XwfqY/0tbJOH3wPGiVb6vBWDPhKDQw65NFOlN3RR wu3g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:in-reply-to:references :user-agent:date:message-id:mime-version:content-transfer-encoding; bh=tdfUGpqL4skWL2wAqf3Cj/x/B2RXw0CYKLF60WtZa+w=; b=djlyI8lJIwF0ys8IQY7NZ5CzIUZX7jIAvWWbMPhuwhie8kgeVvMUt+5gLajzFXsotn IDjkPnebTQ0p7LoeTvfkAC5qt84u9E3zbH9VsUrxiba1+BXnvUrNI8wRLnOmTpLtvK6t 8rTOUlQyjaPSx8mWRcfe3j0nS7QdECZTkLu6Wkf0TH2PIyZgqDfB9RtIeRVAymOBDjzy RX8y6cHf9I+tzE7N0oBziIV1EdRZIyxipMJx5KuI5ZPIbXWw2Vv1xJ4lltal0svjGWIM EXrJLanjLPXnnhCci/MZVyN143ZhBpF9Yj0Z+fN3/4bmt7Pc5xYN7GYAjOLEj2e/r4bw CFxQ== X-Gm-Message-State: AOAM5301wKaB+oNH3EjE/Pk9jT4Cw1DbWgICbOZgOJ9RYpkxMlcSFWIi G857OLBiLaC+HTpuJMns/FHxO/D9F0k= X-Google-Smtp-Source: ABdhPJzeSYSCWwl+MvS+Lx8IUzxsp44rTYswNhrNzOnXXmI+5OnIC8z4kznlIaBdeGlnFKonR/qFgw== X-Received: by 2002:a1c:27c2:: with SMTP id n185mr3106762wmn.20.1629455717092; Fri, 20 Aug 2021 03:35:17 -0700 (PDT) Original-Received: from krug (a94-133-27-132.cpe.netcabo.pt. [94.133.27.132]) by smtp.gmail.com with ESMTPSA id s1sm9794842wmh.46.2021.08.20.03.35.16 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 20 Aug 2021 03:35:16 -0700 (PDT) In-Reply-To: (Dmitry Gutov's message of "Fri, 20 Aug 2021 02:51:15 +0300") X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:212259 Archived-At: Dmitry Gutov writes: > On 20.08.2021 02:39, Jo=C3=A3o T=C3=A1vora 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=C3=A9vin 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=C3=A3o