From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Dmitry Gutov Newsgroups: gmane.emacs.bugs Subject: bug#48545: 28.0.50; `icomplete-vertical-mode` does not support the `group-function` Date: Sat, 21 Aug 2021 05:09:40 +0300 Message-ID: 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> <87pmu8qu8s.fsf@gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="3496"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.11.0 Cc: Daniel Mendler , 48545@debbugs.gnu.org To: =?UTF-8?Q?Jo=C3=A3o_?= =?UTF-8?Q?T=C3=A1vora?= Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sat Aug 21 04:10:12 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 1mHGSa-0000ko-1t for geb-bug-gnu-emacs@m.gmane-mx.org; Sat, 21 Aug 2021 04:10:12 +0200 Original-Received: from localhost ([::1]:51680 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mHGSY-0002CE-Hn for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 20 Aug 2021 22:10:10 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:33108) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mHGSQ-0002C6-Fj for bug-gnu-emacs@gnu.org; Fri, 20 Aug 2021 22:10:02 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:52395) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1mHGSP-0007hj-T1 for bug-gnu-emacs@gnu.org; Fri, 20 Aug 2021 22:10:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1mHGSP-0007v9-Hs for bug-gnu-emacs@gnu.org; Fri, 20 Aug 2021 22:10:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Dmitry Gutov Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 21 Aug 2021 02:10: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.162951179130428 (code B ref 48545); Sat, 21 Aug 2021 02:10:01 +0000 Original-Received: (at 48545) by debbugs.gnu.org; 21 Aug 2021 02:09:51 +0000 Original-Received: from localhost ([127.0.0.1]:35708 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mHGSF-0007ui-Di for submit@debbugs.gnu.org; Fri, 20 Aug 2021 22:09:51 -0400 Original-Received: from mail-wr1-f42.google.com ([209.85.221.42]:34664) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mHGSD-0007uT-6g for 48545@debbugs.gnu.org; Fri, 20 Aug 2021 22:09:50 -0400 Original-Received: by mail-wr1-f42.google.com with SMTP id h13so16753740wrp.1 for <48545@debbugs.gnu.org>; Fri, 20 Aug 2021 19:09:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=sender:subject:to:cc:references:from:message-id:date:user-agent :mime-version:in-reply-to:content-language:content-transfer-encoding; bh=2tcFN5KlTeQl4F2SDGA/WwMCT9SvK7qiW3xQLSFYJcw=; b=tDYaAWTlw2tJuob+smuFoBd1GzOrehmGVblNIkSgzQICvg5T/OJKS700FzUOxAnTQB cjx3J+5jK22zosIfqIlz9YjvV6pjwHYHQq3XF/e3+McS9FEr6OzrBLvIUz5/iY+En25c S24/0AYVd2oYo1dnwYE5EVzlZRHeemYdPmF/TPn3HMYsVhIBNMnVkTntZgB/dfdLmnkS RdJAGahgkz+kwcQPekN/NYVVkjVI0mRzwi2qwqKIiSaGsGofp2BMXC8Jy3QGryqytaZ5 QE708fXBsAT31KkhjVL3IvnyFoGvQcgeAA4ZZPjN9RDaswaWffouO3UfVyldEKJUEA7s TthA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:subject:to:cc:references:from:message-id :date:user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=2tcFN5KlTeQl4F2SDGA/WwMCT9SvK7qiW3xQLSFYJcw=; b=mpsyRI3r2nskqnxLV+uhEy3MXi7BDzYp7F5kLlfQrvd8cNJ8k6h74N8FCM2GGwc9H4 drducnFqbLV5R3Sssm6Lyr2hLDuMKnYqzb7pAeUC00wqhSeEbV1pF6ItsA+FgujBkd5s DS5+XZcs2oO2EPQ5Ukos2VrxHDJxQsJlk8jCIRRKGF3qnMJRRlcYOSravUkPA1v+X3gd /mnhvbCN5GCgM3IUuDeSBFojLkUokzGT2f9MM03CSAtQtDvjtbUOfhQDN70eAMDF1tuE DFmsiE8MDiEm1lhnDy680XCI5/7xnJX5OoRKPEYvqCltLnonHFPe/OEsb884ga+NiyPK GPVA== X-Gm-Message-State: AOAM531hZql7NeE5Rv777weLszRNcVOIRvJFT1oCasFNvn3DoT/CtiJB rDl64itB84e+GLxnnBGe2PZ0Ol+N2ik= X-Google-Smtp-Source: ABdhPJxTQhp8lSLrlBpVGT+NLEaQ12iaDCHfDMfi5iuuQajv4oH2QbcHV7W1mLZUuOmPtGY3/5itQQ== X-Received: by 2002:a5d:6483:: with SMTP id o3mr1551259wri.197.1629511783422; Fri, 20 Aug 2021 19:09:43 -0700 (PDT) Original-Received: from [192.168.0.6] ([46.251.119.176]) by smtp.googlemail.com with ESMTPSA id y1sm6792868wmq.43.2021.08.20.19.09.41 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 20 Aug 2021 19:09:42 -0700 (PDT) In-Reply-To: <87pmu8qu8s.fsf@gmail.com> Content-Language: en-US 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:212310 Archived-At: 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.