From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: [PATCH] `completing-read` - allow history=t, sorting improvements Date: Mon, 19 Apr 2021 16:15:01 -0400 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="22109"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux) Cc: "emacs-devel@gnu.org" To: Daniel Mendler Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Mon Apr 19 22:17:32 2021 Return-path: Envelope-to: ged-emacs-devel@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 1lYaKp-0005eM-PW for ged-emacs-devel@m.gmane-mx.org; Mon, 19 Apr 2021 22:17:31 +0200 Original-Received: from localhost ([::1]:37642 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lYaKo-0001DC-Sr for ged-emacs-devel@m.gmane-mx.org; Mon, 19 Apr 2021 16:17:30 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:60314) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lYaIi-00089o-HC for emacs-devel@gnu.org; Mon, 19 Apr 2021 16:15:20 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:51425) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lYaId-0007ZH-MB for emacs-devel@gnu.org; Mon, 19 Apr 2021 16:15:18 -0400 Original-Received: from pmg1.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 8A55510021B; Mon, 19 Apr 2021 16:15:13 -0400 (EDT) Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg1.iro.umontreal.ca (Proxmox) with ESMTP id 035F810005D; Mon, 19 Apr 2021 16:15:03 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1618863303; bh=x390MX01HYzhRDUf5uPuGkzmwt2xqgb9JWBw3l9+Dew=; h=From:To:Cc:Subject:References:Date:In-Reply-To:From; b=Fi3aTMcmj8FQpzh0iy/29qWEslz/Q82CNtNtf+GM3sl+9jU494l09PEVzLZMNI1KP iS5OmkrO/UpxsEjPWjojn2aC87UdoXTRCmpVjVR13gMOLCIdUg1mBVoQzR6FkuGjhL cdAH54wW61070cDwSUPMQK+f8imlK4451oQw6CDc62tnO87tS1pLoEyAEDtB1cizuM Bk6IYSK0zcRnqEz1Z8mDS0HGeypVKqQHQtxb/wpBfzzmefZaZj+WiS1hw3GW7dihop 2jDYeY6d+00CrKGcqIvLEkVo932hj4uKpU0P254GEhouOqN/Pj8OKY5mc1F6Uhg0U0 VcSu7zJtMfZJg== Original-Received: from alfajor (104-222-126-84.cpe.teksavvy.com [104.222.126.84]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id CF06312005B; Mon, 19 Apr 2021 16:15:02 -0400 (EDT) In-Reply-To: (Daniel Mendler's message of "Mon, 19 Apr 2021 21:36:50 +0200") Received-SPF: pass client-ip=132.204.25.50; envelope-from=monnier@iro.umontreal.ca; helo=mailscanner.iro.umontreal.ca X-Spam_score_int: -42 X-Spam_score: -4.3 X-Spam_bar: ---- X-Spam_report: (-4.3 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:268190 Archived-At: >>> * minibuffer.el: Use completion--message consistently for the messages >>> "Incomplete", "Sole completion" and "No completions". >> I don't have a strong opinion on this patch, but I have the impression >> that there might have been a good reason for the difference (i.e. the >> above two cases could be considered "more serious" than those using >> `completion--message`). >> I would personally gladly get rid of `completion-show-inline-help`, so >> I'm not the right person to judge if the above patch is doing the right >> thing or not. > > For me the point was mostly to get this clarified, therefore I included it > here. Note that the messages "Sole completion" and "No completions" are > already shown at some other places via `completion--done` which uses > `completion--message` itself, but on a different code path. Oh, I see now that this var comes from: commit 369e974dc086452033227a5d350c357602c6274e Author: Chong Yidong Date: Sun Apr 10 17:31:14 2011 -0400 Fix bad interaction between icomplete and completion inline help (Bug#5849). * lisp/minibuffer.el (completion-show-inline-help): New var. (completion--do-completion, minibuffer-complete) (minibuffer-force-complete, minibuffer-complete-word): Inhibit minibuffer messages if completion-show-inline-help is nil. * lisp/icomplete.el (icomplete-mode): Bind completion-show-inline-help to avoid interference from inline help. I mistakenly thought it was a user config inherited from way-back which I just preserved when I moved the code from minibuf.c to minibuffer.el. So you're right we should use it everywhere. I pushed your patch. > Agree generally. It makes a difference if one uses car-less-than-car, since > then the comparison function is fast. The difference is less pronounced if > one includes the lambdas which sort alphabetically (this is on non-native, > on native the picture could be different). Note that the separate alphabetical sorting can be done with (sort all #'string-lessp) so it should also be fast ;-) > The important change is really the quadratic one. Yes, thank you for that fix, indeed. > However in my Vertico package (and in other continuously updating > UIs), the big bottleneck of the UI still is the sorting for many > candidates, even when including optimizations. > Therefore I am using a vertico-sort-threshold there. > Maybe there are potential improvements on a lower level? If O(N log N) is still too slow, then I think it's safe to say that the problem is that N is too large: we can try and shave off a factor of `c` or even the `log N` by optimizing the implementation, but that just pushes the "too large" a bit further and sooner or later you'll have to bite the bullet and introduce some "threshold" beyond which you reduce the functionality. In theory, if we want to optimize the speed as much as possible without reducing the functionality, we could try to: - first partition the set of candidates between those that appear in the history and those that don't. This is linear time. - sort the ones that appear in the history based on their position there: no need to check length or alphabetic order in this case. This is O(N log N) but the N should be significantly smaller. - If you have enough candidates already to fill the display you can stop at this point and just use those candidates. - the remaining candidates can be sorted by their length, putting together same-length candidates into sublists. This could even be more-or-less linear time with some kind of bucket sort. - Finally sort each of those sublists according to lexicographic order This is again O(N log N) but again the N should be significantly smaller and we can stop as soon as we've found enough candidates to fill the display. Stefan