From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Daniel Mendler Newsgroups: gmane.emacs.devel Subject: Re: [PATCH] `completing-read` - allow history=t, sorting improvements Date: Mon, 19 Apr 2021 22:44:18 +0200 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="11045"; mail-complaints-to="usenet@ciao.gmane.io" Cc: "emacs-devel@gnu.org" To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Mon Apr 19 22:49:43 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 1lYapy-0002i8-U8 for ged-emacs-devel@m.gmane-mx.org; Mon, 19 Apr 2021 22:49:42 +0200 Original-Received: from localhost ([::1]:38566 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lYapx-0003N9-VP for ged-emacs-devel@m.gmane-mx.org; Mon, 19 Apr 2021 16:49:42 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:38844) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lYaku-0005UC-6v for emacs-devel@gnu.org; Mon, 19 Apr 2021 16:44:28 -0400 Original-Received: from server.qxqx.de ([2a01:4f8:121:346::180]:35263 helo=mail.qxqx.de) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lYakp-0002y3-KL for emacs-devel@gnu.org; Mon, 19 Apr 2021 16:44:27 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=qxqx.de; s=mail1392553390; h=Content-Transfer-Encoding:Content-Type:In-Reply-To: MIME-Version:Date:Message-ID:From:References:Cc:To:Subject:Sender:Reply-To: Content-ID:Content-Description:Resent-Date:Resent-From:Resent-Sender: Resent-To:Resent-Cc:Resent-Message-ID:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=NoZCwRiWCShFW2tniKZqMPPDYW4kIgGcEIRjx5u9fPM=; b=jEBjduvusdeDxS1Pm+rS2u6cnk 1ubcpErNE+bYYZeehjGIAi5uUPqg+PnBmkhmY+ZnDpMTWW9U3fhv0GoR0cAqB20LPmECzAP2gBZKE 6Xv/7GHg8whed+HWFUKOrZu7zUzBdtgQrYVT4Ro2SdHz/wbYGQfviVCZy44gnDVflSJM=; In-Reply-To: Content-Language: en-US Received-SPF: pass client-ip=2a01:4f8:121:346::180; envelope-from=mail@daniel-mendler.de; helo=mail.qxqx.de X-Spam_score_int: -41 X-Spam_score: -4.2 X-Spam_bar: ---- X-Spam_report: (-4.2 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_PASS=-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:268192 Archived-At: On 4/19/21 10:15 PM, Stefan Monnier wrote: >> 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. N is not that large. I want the sorting to be reasonably fast for the the candidate sets which occur now in Emacs. But if this get improved, people may throw more candidates at it and then we will end up again with a threshold. > 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. Yes, we can do bucketing/radix sort by length. However I was looking for a solution which cuts down the constants enough such that the solution is good enough for the candidate sets we have now. By moving more of the algorithm to elisp I will also get some larger constants which may neglect the benefits until one reaches a large N. Daniel