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#48841: [PATCH] Make fido-mode about as fast as ido-mode even with many completions Date: Sun, 15 Aug 2021 19:32:51 +0100 Message-ID: <87sfzaimng.fsf_-_@gmail.com> References: <3d3f894f-a6fa-53ae-5d50-c3aa9bffc73e@daniel-mendler.de> <56ab18b1-4348-9b2c-85bb-af9b76cd429a@daniel-mendler.de> <38a06f3c-4a7a-755c-c99b-708f91afabfa@daniel-mendler.de> <9f59f87c-2489-aaa0-5b3f-0e911b7ffa6c@daniel-mendler.de> <8a36e61a-1c5b-bf3b-a454-077348589c4f@yandex.ru> <87y29471ov.fsf@gmail.com> 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="10790"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux) Cc: Daniel Mendler , Stefan Monnier , 48841@debbugs.gnu.org To: Dmitry Gutov Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sun Aug 15 20:34:11 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 1mFKxX-0002ZT-6v for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 15 Aug 2021 20:34:11 +0200 Original-Received: from localhost ([::1]:53590 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mFKxV-0007NG-Bv for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 15 Aug 2021 14:34:09 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:35440) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mFKxO-0007Mr-Qt for bug-gnu-emacs@gnu.org; Sun, 15 Aug 2021 14:34:02 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:36220) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1mFKxO-0003zP-L0 for bug-gnu-emacs@gnu.org; Sun, 15 Aug 2021 14:34:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1mFKxO-0003Ag-IF for bug-gnu-emacs@gnu.org; Sun, 15 Aug 2021 14:34:02 -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: Sun, 15 Aug 2021 18:34: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.162905238912117 (code B ref 48841); Sun, 15 Aug 2021 18:34:02 +0000 Original-Received: (at 48841) by debbugs.gnu.org; 15 Aug 2021 18:33:09 +0000 Original-Received: from localhost ([127.0.0.1]:47766 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mFKwX-00039K-54 for submit@debbugs.gnu.org; Sun, 15 Aug 2021 14:33:09 -0400 Original-Received: from mail-wm1-f52.google.com ([209.85.128.52]:43768) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mFKwO-00038g-UZ for 48841@debbugs.gnu.org; Sun, 15 Aug 2021 14:33:07 -0400 Original-Received: by mail-wm1-f52.google.com with SMTP id k5-20020a05600c1c85b02902e699a4d20cso10234977wms.2 for <48841@debbugs.gnu.org>; Sun, 15 Aug 2021 11:33:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version:content-transfer-encoding; bh=YXF2qUVvdzM5o/nGSed59SKJ2JnjtUpemwnqCaYD6XI=; b=HRKCSIpdjOWm2BjHlj2WKN1k58iy6jzHg+nQYSi10QP920YBc/fwEHhuSklU8zM8nj BjJwdqVOjFV+x5fIy3M9btjCdzNHCh6oKn/mmTV8j079l5huHf0fTdIXJfp9A6q00KWh 3m3E5KwAj0uLPKUW8Hq+h7Q+nSQ0tLXK1b+D1c1MfbhqQw1D7sR8Yy1irJdTgpFqx+5f jJGKnJN8zEsd+Ju5e/elawySgh5FOgu/+YDmwMCTtcfZ1vLs3NuKAJsvtdEaEJJaMet7 nvUSdiO/hL2ExHeNcbAtBvl0kJ6520bPY6fq7Fht1pIfrpD88Ea8SwuF3Ks7QwZ5hZMg aJEg== 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:references:date:in-reply-to :message-id:user-agent:mime-version:content-transfer-encoding; bh=YXF2qUVvdzM5o/nGSed59SKJ2JnjtUpemwnqCaYD6XI=; b=lrUvs+ASWtTRRDXsMggVH11qc/2hEGJo7gamD7L3ooz5iHzqKzoDQi5dQzxYM2N6pl ozUq6lNhZCJQB2pSaic90Mm0mMyBiQH0iKL9zg2e+P9ENQZU1il4nJx99FtPgXMQ4Klp YZyHdU+YR1Bk8A3ss2Xd8Fu8MVWVVFoOSTyOCP6YhFR/ao/NLrPYYQrM+EfQ7VwOHXy0 TDi+gvHa6P81cNfKzBqcy08qvniTTZh/6+82n4q9SC7WG7D3ltlIXxHG3VJsYQRv5lsD ykz4Ar6cGYt+5sLzjJM+r/WxErqfjukZJWg+8jcLcNxjOcNK0n70aQxt9o4xJNnGW08K x7+w== X-Gm-Message-State: AOAM530Lq6abUxJNIyxoZM3BzgaVd9r/SkypFzCUYkZTszSrCOgmK8tz T5+AnTALtyrVl2kp6wZpk2g= X-Google-Smtp-Source: ABdhPJwgiX4E67CgM53aewsBqIzI2P790G+knOG9mdQFast9rhJ9EhzJ4w6H0J4ZryqucrRwX5HS9Q== X-Received: by 2002:a1c:804a:: with SMTP id b71mr11758170wmd.141.1629052374991; Sun, 15 Aug 2021 11:32:54 -0700 (PDT) Original-Received: from krug (a94-133-27-132.cpe.netcabo.pt. [94.133.27.132]) by smtp.gmail.com with ESMTPSA id h11sm9784614wmc.23.2021.08.15.11.32.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 15 Aug 2021 11:32:54 -0700 (PDT) In-Reply-To: <87y29471ov.fsf@gmail.com> ("=?UTF-8?Q?Jo=C3=A3o_?= =?UTF-8?Q?T=C3=A1vora?="'s message of "Sat, 14 Aug 2021 11:36:32 +0100") 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:211943 Archived-At: [I've removed bug#47711 from the list, since I haven't read the bug. This is only directly concerned with this report bug#48841 about speed differences between fido-mode and ido-mode.] Jo=C3=A3o T=C3=A1vora writes: > scratch/icomplete-lazy-highlight-attempt-2, although still incomplete, > is one such approach, though it still sets `completion-score` on the > "shared" string, used later for sorting. But also that could be > prevented (again, only if it turns out to be actually problematic > IMO). I have tested the patch more thoroughly now, and have not found any problems. It's now opt-in for both frontends and completion styles. Used four combinations: - For adhering styles (substring, pcm and flex) and adhering frontends (icomplete-mode and fido-mode). - For adherint styles with non-adhering but style-respecting frontends (company and "vanilla" completion). - Non-adhering styles with adhering frontends, also no problems. - Non-adhering styles and non-adhering frontends, also no problems. As for performance, I'm using the usual simple benchmark from Emacs -Q (require 'cl-lib) (fido-mode 1) (fido-vertical-mode 1) (defmacro lotsoffunctions () `(progn ,@(cl-loop repeat 300000 collect `(defun ,(intern (symbol-name (gensym "heyhey")))= () 42)))) (lotsoffunctions) I then press C-u C-x C-e C-m (benchmark-run (completing-read "" obarray)) To get a quantitative benchmark or just C-h f to get a qualitative one. Without the optimization this takes about 5s to evaluate, with the optimization is usually around 2.6s. I also tested ido-mode on this, with (ido-mode) (ido-ubiquitous-mode) (setq ido-enable-flex-matching t) But it seems with ido-ubiquitous-mode, C-h f gives up around 20000 functions. So I tested around that mark and found: * ido-mode to be minutely faster still in displaying the first set though it isn't as well sorted by recency, size and alphanumericity. However, I don't now if I'm seeing correctly ifo-mode=20 * ido-mode to be slower in responding to quick input (C-h f a), for example. There's some flickering. It's also problematic when quitting with C-g (almost hanging sometimes). All in all I'm satisfied with the speed increase imparted to fido-mode and fido-vertical mode. In particular, the sluggishness reported for short inputs (which makes the flex style consider a great deal of matches) seems to be completely gone. I'll let people try this out and review the patch, which is after my sig. If there's one thing I'm not crazy about, it's the opt-in interface for frontends which requires them to somehow explain to the completion machinery what constitutes a completion "session". That, of course, is essential to allow any caches to be invalidated. I don't know if the current completion framework has any better mechanism than the one explained in the docstring of `completion-lazy-hilit'. Maybe Stefan can speak to that, maybe the table "metadata" is a good place, but that object seems complicated to access and manipuate. Other than that detail, the fact that the opt-in is just a variable and a function call seems simple enough, in my opinion. Another note: the actual cache implementation is done with "private", non-display-related string properties on non-copied strings. That's somewhat of a bad practice to some us, but not to others. I haven't seen any evidence of mischief, real or academic, but if it ever comes forward, the implementation can use some off-string caching mechanism (likely just a hash-table). Jo=C3=A3o diff --git a/lisp/icomplete.el b/lisp/icomplete.el index cd1979d04a..d69cb7568d 100644 --- a/lisp/icomplete.el +++ b/lisp/icomplete.el @@ -494,6 +494,7 @@ icomplete-minibuffer-setup (setq-local icomplete--initial-input (icomplete--field-string)) (setq-local completion-show-inline-help nil) (setq icomplete--scrolled-completions nil) + (setq completion-lazy-hilit (cl-gensym)) (use-local-map (make-composed-keymap icomplete-minibuffer-map (current-local-map))) (add-hook 'post-command-hook #'icomplete-post-command-hook nil t) @@ -800,7 +801,9 @@ icomplete--render-vertical (cl-return-from icomplete--render-vertical (concat " \n" - (mapconcat #'identity torender icomplete-separator)))) + (mapconcat #'identity + (mapcar #'completion-lazy-hilit torender) + icomplete-separator)))) for (comp prefix) in triplets maximizing (length prefix) into max-prefix-len maximizing (length comp) into max-comp-len @@ -812,7 +815,7 @@ icomplete--render-vertical (cl-loop for (comp prefix suffix) in triplets concat prefix concat (make-string (- max-prefix-len (length prefix)) ? ) - concat comp + concat (completion-lazy-hilit comp) concat (make-string (- max-comp-len (length comp)) ? ) concat suffix concat icomplete-separator)))) @@ -962,7 +965,8 @@ icomplete-completions (if (< prospects-len prospects-max) (push comp prospects) (setq limit t))) - (setq prospects (nreverse prospects)) + (setq prospects + (nreverse (mapcar #'completion-lazy-hilit prospects)= )) ;; Decorate first of the prospects. (when prospects (let ((first (copy-sequence (pop prospects)))) diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el index f335a9e13b..c21f234053 100644 --- a/lisp/minibuffer.el +++ b/lisp/minibuffer.el @@ -3512,6 +3512,54 @@ flex-score-match-tightness than the latter (which has two \"holes\" and three one-letter-long matches).") =20 +(defvar-local completion-lazy-hilit nil + "If non-nil, request lazy highlighting of completion matches. + +Completion-presenting frontends may opt to bind this variable to +a unique non-nil value in the context of completion-producing +calls (such as `completion-all-sorted-completions'). This hints +the intervening completion styles that they do not need to +propertize completion strings with the `face' property. + +When doing so, it is the frontend -- not the style -- who becomes +responsible for `face'-propertizing the completion matches meant +to be displayed to the user, frequently a small subset of all +completion matches. This can be done by calling the function +`completion-lazy-hilit' which returns a `face'-propertized +string. + +The value stored in this variable by the completion frontend must +be unique to each completion attempt/session. For instance, +frontends which utilize the minibuffer as the locus of completion +may set it to a buffer-local value returned by `gensym'. For +frontends operating within a recursive command loop, let-binding +it to `gensym' is appropriate. + +Note that the optimization enabled by variable is only actually +performed some completions styles. To others, it is a harmless +and useless hint. To author a completion style that takes +advantage of this, look in the source of +`completion-pcm--hilit-commonality' for ideas.") + +(defun completion-lazy-hilit (str) + "Return a copy of completion STR that is `face'-propertized. +See documentation for variable `completion-lazy-hilit' for more +details." + (let* ((str (copy-sequence str)) + (data (get-text-property 0 'completion-lazy-hilit-data str)) + (re (and + completion-lazy-hilit + (eq completion-lazy-hilit (car data)) (cdr data))) + (md (and re (string-match re str) (cddr (match-data t)))) + (me (and md (match-end 0))) + (from 0)) + (while md + (add-face-text-property from (pop md) 'completions-common-part nil s= tr) + (setq from (pop md))) + (unless (or (not me) (=3D from me)) + (add-face-text-property from me 'completions-common-part nil str)) + str)) + (defun completion-pcm--hilit-commonality (pattern completions) "Show where and how well PATTERN matches COMPLETIONS. PATTERN, a list of symbols and strings as seen @@ -3527,8 +3575,10 @@ completion-pcm--hilit-commonality last-md) (mapcar (lambda (str) - ;; Don't modify the string itself. - (setq str (copy-sequence str)) + (unless completion-lazy-hilit + ;; Make a copy of `str' since in this case we're about to + ;; `face'-propertize it. + (setq str (copy-sequence str))) (unless (string-match re str) (error "Internal error: %s does not match %s" re str)) (let* ((pos (if point-idx (match-beginning point-idx) (match-end = 0))) @@ -3576,9 +3626,10 @@ completion-pcm--hilit-commonality (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) + (unless completion-lazy-hilit + (add-face-text-property a b + 'completions-common-part + nil str)) (setq score-numerator (+ score-numerator (- b a))) (unless (or (=3D a last-b) @@ -3601,7 +3652,10 @@ completion-pcm--hilit-commonality ;; for that extra bit of match (bug#42149). (unless (=3D from match-end) (funcall update-score-and-face from match-end)) - (if (> (length str) pos) + (put-text-property 0 1 'completion-lazy-hilit-data + (cons completion-lazy-hilit re) str) + (if (and (> (length str) pos) + (not completion-lazy-hilit)) (add-face-text-property pos (1+ pos) 'completions-first-difference