Package: emacs;
Reported by: Dmitry Gutov <dgutov <at> yandex.ru>
Date: Sat, 5 Jun 2021 01:40:01 UTC
Severity: normal
Done: João Távora <joaotavora <at> gmail.com>
Bug is archived. No further changes may be made.
View this message in rfc822 format
From: João Távora <joaotavora <at> gmail.com> To: Dmitry Gutov <dgutov <at> yandex.ru> Cc: Daniel Mendler <mail <at> daniel-mendler.de>, eliz <at> gnu.org, Stefan Monnier <monnier <at> iro.umontreal.ca>, 48841 <at> debbugs.gnu.org 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
[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ão Távora <joaotavora <at> gmail.com> 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
* 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ão
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).")
+(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 str)
+ (setq from (pop md)))
+ (unless (or (not me) (= 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 (= a last-b)
@@ -3601,7 +3652,10 @@ completion-pcm--hilit-commonality
;; for that extra bit of match (bug#42149).
(unless (= 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
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997,2003 nCipher Corporation Ltd,
1994-97 Ian Jackson.