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#48841: fido-mode is slower than ido-mode with similar settings Date: Fri, 11 Jun 2021 05:19:03 +0300 Message-ID: <858682b2-b8fd-898b-bef3-97dbe5e4debc@yandex.ru> References: <87eedgy7pt.fsf@gmail.com> <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@yandex.ru> <87a6o3x5j7.fsf@gmail.com> <87y2bnv5xc.fsf@gmail.com> <35be6652-9c8d-ee21-e9eb-9598ad6777eb@yandex.ru> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------F6E563123C8DCDF34497F7F5" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="38056"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.8.1 Cc: Stefan Monnier , 48841@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 Fri Jun 11 04:20: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 1lrWmK-0009mB-6k for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 11 Jun 2021 04:20:12 +0200 Original-Received: from localhost ([::1]:48392 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lrWmI-0005HR-Jv for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 10 Jun 2021 22:20:10 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:44962) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lrWmB-0005H4-4I for bug-gnu-emacs@gnu.org; Thu, 10 Jun 2021 22:20:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:54610) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1lrWmA-0001Pv-TF for bug-gnu-emacs@gnu.org; Thu, 10 Jun 2021 22:20:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1lrWmA-0002ER-HJ for bug-gnu-emacs@gnu.org; Thu, 10 Jun 2021 22:20:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Dmitry Gutov Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 11 Jun 2021 02:20:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 48841 X-GNU-PR-Package: emacs Original-Received: via spool by 48841-submit@debbugs.gnu.org id=B48841.16233779558520 (code B ref 48841); Fri, 11 Jun 2021 02:20:02 +0000 Original-Received: (at 48841) by debbugs.gnu.org; 11 Jun 2021 02:19:15 +0000 Original-Received: from localhost ([127.0.0.1]:37923 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1lrWlP-0002DL-Bj for submit@debbugs.gnu.org; Thu, 10 Jun 2021 22:19:15 -0400 Original-Received: from mail-wr1-f46.google.com ([209.85.221.46]:41546) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1lrWlM-0002D8-0X for 48841@debbugs.gnu.org; Thu, 10 Jun 2021 22:19:14 -0400 Original-Received: by mail-wr1-f46.google.com with SMTP id o3so4294788wri.8 for <48841@debbugs.gnu.org>; Thu, 10 Jun 2021 19:19:11 -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; bh=wj5EuA8ANQmlPd2nPzxl3lhKoHqXxF0/XggB9vFIOoY=; b=Ga6QZ3Yyi3s7iQojdKhvk9qo57ReFABYTy7xG1nxrhI2MXtHPnIcnyJJyQ1sC6IF52 AvyWa7bjGi3xhqmNcXZrmJTjuv7MwG+sc7UU0ScpUHpmSbqJJB52aO45FzNS0n8OGEUQ hKRUTLi28pcTwKyzMYwjYzIX1vY4LIfPp8Nt1gnT9GfR1ykVxxvOXkhkAj5Jl09vrsQy y8zTFWiaurC2IM7RxtTOgaBS4d0N+gDfW6kH6BngGpRNI0qXzKsDXkLEIHl8SvQSx+b/ uS37aY/WkYB44qWmAta4aEHPVBdNUF21OhLsEhldWagsSWk2fyjhDXSWiG2tQ2k74WyB cZ+g== 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; bh=wj5EuA8ANQmlPd2nPzxl3lhKoHqXxF0/XggB9vFIOoY=; b=nHgPIjozb0UwMc30gMbhMt/FCWE54yfVnMo/nDwubadmtVGSevgimqZxmMkuWEtPVS o3Rdz7+5X0yBfxmQyABKlnbZFzWMVLhzoACqGeEKiX+GDFDRW16UvsB57JgkYJqTKghr V6H9Sgo0abeNZyuzYi+2DMM9CBUMsda3z+O/U9h5VKgBxgNbgcT5y4QpJ9aJjQ8wpL/J bPfsKHzqsIlvCkFU/dsPETHJsEUgPDUqChAgUBcJSBZ0jH88eOysnYctcSBWBxKsjpW9 XoRpr3C3OyH/TQ2SHNyXmGZ1m5alY10TKLnrvJRwrsUbc+L0wHqRK9m7kax/q9qqSvsY dJKA== X-Gm-Message-State: AOAM530VF5BzJwL9sCGF0W6Tk5rsC4WuVo3hQFCBHTQ047fcM/6KPYDX MW1R9ByP3trK2UeZxcHSFxxd4Qrn6k4= X-Google-Smtp-Source: ABdhPJyAKBusvaaIqK80+XSE7+FozrzXuD4eABDRQj7bsk8td6+cmaILw8Cdxl/Gx8vDQNfu3j7YvA== X-Received: by 2002:adf:d1c9:: with SMTP id b9mr1242584wrd.101.1623377945937; Thu, 10 Jun 2021 19:19:05 -0700 (PDT) Original-Received: from [192.168.0.6] ([46.251.119.176]) by smtp.googlemail.com with ESMTPSA id k8sm5327836wrp.3.2021.06.10.19.19.04 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 10 Jun 2021 19:19:04 -0700 (PDT) In-Reply-To: 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:208339 Archived-At: This is a multi-part message in MIME format. --------------F6E563123C8DCDF34497F7F5 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit On 07.06.2021 11:52, João Távora wrote: > Maybe moving all of them to parameters and return values (making it a > static function and having the caller manage state) would help, I > haven't tried that exactly. > > > Normally, in those adventures you end up with the same allocations > somewhere else, and uglier code. But you can try. I have it a try, with little success (patch attached, for posterity). Since there's no multiple value returns in Lisp, I had to define a container for the three values. The performance is basically the same, which seems to indicate that either Elisp has to allocate very little for a compiled lambda code, or it's optimized out (which would also make sense: the only thing necessary for it is a new container for the current scope). > > Might be noise, or you might be thrashing of CPU caches, who > knows? If > > the string length is on the same cache line as the contents of the > > string you're reading, then evicting that to go read the value of a > > boxed integer somewhere radically different is slow. > > But the string value is boxed as well, right? > > > The key is locality. If the string length and data happen to live nearby > in memory (in the same box, so to speak), there's a decent chance that > reading one brings the other into the cache, and you get a nice hit > depending on your subsequent operation. > > Here I'm just speculating, as I said. In managed languages such as > Lisps, it's somewhat unpredictable. It's also always hardware dependent. > Though given C/C++, a known processor and the right application, this > will make a world of a difference, and will yield truly "weird" results > (which arent weird at all after you understand the logic). Like, for > example a vector being much better at sorted insertion than a linked > list. (!) Look it up. Bjarne Stroustrup has one of those talks. When you have to do some work, better memory locality can indeed change a lot. But in this case we have an already computed value vs. something the code still needs to compute, however fast that is. Accessing function arguments must be currently much faster than looking up the current scope defined with 'let'. Anyway, looking at what else could be removed, now that the extra allocation in 'match-data' is gone, what really speeds it up 2x-11x (depending on whether GC kicks in, but it more often doesn't), is commenting out the line: (setq str (copy-sequence str)) So if it were possible to rearrange completion-pcm--hilit-commonality not to have to modify the strings (probably removing the function altogether?), that would improve the potential performance of c-a-p-f quite a bit, for fido-mode and other frontends (depending on how much overhead the other layers add). Ultimately, the scoring information doesn't have to live in the text properties. For sorting, the frontend could allocate a hash table, then ask the [backends? styles?] for completion scores on each item and sort based on that. Since faces are needed only for the completions that are currently displayed, even having to repeat the regexp matching stuff for each of them later would be no big deal performance-wise, compared to the current approach. Anyway, these are musing for the much-discussed future iteration of the API. With the current version, and tied by backward compatibility, it might be possible to wring 10ms of improvement by consolidating text property changes somehow, but likely no more than that. Looking forward for your analysis of fido-vertical-mode's performance improvement over the "normal" one. --------------F6E563123C8DCDF34497F7F5 Content-Type: text/x-patch; charset=UTF-8; name="completion-pcm-score-struct.diff" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="completion-pcm-score-struct.diff" diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el index d5a0118b7c..0cb247fc19 100644 --- a/lisp/minibuffer.el +++ b/lisp/minibuffer.el @@ -3485,6 +3485,7 @@ completion-pcm--hilit-commonality (let* ((re (completion-pcm--pattern->regex pattern 'group)) (point-idx (completion-pcm--pattern-point-idx pattern)) (case-fold-search completion-ignore-case) + (score (make-vector 3 0)) last-md) (mapcar (lambda (str) @@ -3531,37 +3532,17 @@ completion-pcm--hilit-commonality ;; (SUM_across_i(hole_i_contrib) + 1) * len ;; ;; , where "len" is the string's length. - (score-numerator 0) - (score-denominator 0) - (last-b 0) - (update-score-and-face - (lambda (a b) - "Update score and face given match range (A B)." - (add-face-text-property a b - 'completions-common-part - nil str) - (setq - score-numerator (+ score-numerator (- b a))) - (unless (or (= a last-b) - (zerop last-b) - (= a (length str))) - (setq - score-denominator (+ score-denominator - 1 - (expt (- a last-b 1) - (/ 1.0 - flex-score-match-tightness))))) - (setq - last-b b)))) + ) + (fillarray score 0) (while md - (funcall update-score-and-face from (pop md)) + (completion-pcm--update-score-and-face str from (pop md) score) (setq from (pop md))) ;; If `pattern' doesn't have an explicit trailing any, the ;; regex `re' won't produce match data representing the ;; region after the match. We need to account to account ;; for that extra bit of match (bug#42149). (unless (= from match-end) - (funcall update-score-and-face from match-end)) + (completion-pcm--update-score-and-face str from match-end score)) (if (> (length str) pos) (add-face-text-property pos (1+ pos) @@ -3570,10 +3551,35 @@ completion-pcm--hilit-commonality (unless (zerop (length str)) (put-text-property 0 1 'completion-score - (/ score-numerator (* end (1+ score-denominator)) 1.0) str))) + (/ (completion-pcm--score-numerator score) + (* end (1+ (completion-pcm--score-denominator score))) + 1.0) + str))) str) completions)))) +(cl-defstruct (completion-pcm--score (:type vector)) + (numerator 0) (denominator 0) (last-b 0)) + +(defun completion-pcm--update-score-and-face (str a b score) + "Update score and face in STR given match range (A B)." + (add-face-text-property a b + 'completions-common-part + nil str) + (let ((last-b (completion-pcm--score-last-b score))) + (setf (completion-pcm--score-numerator score) + (+ (completion-pcm--score-numerator score) (- b a))) + (unless (or (= a last-b) + (zerop last-b) + (= a (length str))) + (setf (completion-pcm--score-denominator score) + (+ (completion-pcm--score-denominator score) + 1 + (expt (- a last-b 1) + (/ 1.0 + flex-score-match-tightness))))) + (setf (completion-pcm--score-last-b score) b))) + (defun completion-pcm--find-all-completions (string table pred point &optional filter) "Find all completions for STRING at POINT in TABLE, satisfying PRED. @@ -3980,7 +3986,7 @@ completion-flex-all-completions string table pred point #'completion-flex--make-flex-pattern))) (when all - (nconc (completion-pcm--hilit-commonality pattern all) + (nconc (benchmark-progn (completion-pcm--hilit-commonality pattern all)) (length prefix)))))) ;; Initials completion --------------F6E563123C8DCDF34497F7F5--