Package: emacs;
Reported by: Spencer Baugh <sbaugh <at> janestreet.com>
Date: Wed, 27 Nov 2024 20:26:02 UTC
Severity: wishlist
Tags: patch
Done: Stefan Monnier <monnier <at> iro.umontreal.ca>
Bug is archived. No further changes may be made.
Message #49 received at 74561 <at> debbugs.gnu.org (full text, mbox):
From: Spencer Baugh <sbaugh <at> janestreet.com> To: Stefan Kangas <stefankangas <at> gmail.com> Cc: sbaugh <at> catern.com, juri <at> linkov.net, dmitry <at> gutov.dev, joaotavora <at> gmail.com, Eli Zaretskii <eliz <at> gnu.org>, 74561 <at> debbugs.gnu.org, monnier <at> iro.umontreal.ca Subject: Re: bug#74561: [PATCH] Allow limiting the size of *Completions* Date: Fri, 14 Feb 2025 15:54:44 -0500
[Message part 1 (text/plain, inline)]
Stefan Kangas <stefankangas <at> gmail.com> writes: > Spencer Baugh via "Bug reports for GNU Emacs, the Swiss army knife of > text editors" <bug-gnu-emacs <at> gnu.org> writes: > >> Nope, no user-facing behavior changes. In fact, this probably shouldn't >> be user-customizable at all, since it's an internal optimization with >> essentially no cost. So I've changed this into a defvar >> completions--insert-lazily. > > SGTM, but I have a question: > > What happens on very large displays? Is 200 always going to be enough > completions? I imagine some users will be doing unusual things like > having the completion buffer take up their whole 42" 5K monitor. > > So should this perhaps be calculated dynamically based on the geometry > of the window, somehow? Yes, good point, it definitely should be calculated dynamically. The easiest way to do this correctly is to insert completion candidates until we have at least frame-height lines in the *Completions* buffer. Then no matter how the window gets resized afterwards (and it will indeed be resized, by fit-window-to-buffer) there will be enough completion candidates that the displayed part of the window is full. I've done this in the attached patch. In the process, I realized that this optimization doesn't help completions-format=vertical without a lot of effort, since that fills the entire first column before continuing to the second column. That's fine, the optimization works for other values of completions-format, and I can straightforwardly extend the optimization to completions-format=vertical in later changes. I've also updated NEWS to be more clear about the lack of user-facing behavior changes. BTW, the current implementation uses throw and catch to interrupt the process of inserting completions when enough have been inserted. This opens up the possibility of further optimization later: instead of throwing the symbol "truncated" as I do now, I could throw a function, a continuation which could be called to continue inserting the completions from where I left off. That would avoid duplicating some work, and therefore make things even faster.
[0001-Lazily-highlight-and-insert-candidates-in-Completion.patch (text/x-patch, inline)]
From 3641bb9cb64b671ca0abd846b1b32d760884bb43 Mon Sep 17 00:00:00 2001
From: Spencer Baugh <sbaugh <at> catern.com>
Date: Mon, 13 Jan 2025 14:32:18 -0500
Subject: [PATCH] Lazily highlight and insert candidates in *Completions*
From profiling, the main bottleneck in completion over large
completion sets is display-completion-list, when there are many
available candidates. For example, in my large monorepo, when
completing over the 589196 files or the 73897 branches, even
with the candidates narrowed down by typing some prefix to
complete, TAB (when it shows *Completions*) or ? is slow, mostly
in display-completion-list.
However, rendering all the completion candidates is unnecessary if
the *Completions* window is never scrolled to see those candiates. By
eagerly inserting only some candidates and lazily highlighting and
inserting the remaining candidates only when necessary, performance is
much improved.
* lisp/minibuffer.el (completion--insert-strings): Insert
completions lazily. (bug#74561)
(completion--lazy-insert-strings, completions--insert-lazily)
(completion--newline, completions--lazy-insert-button): Add.
(completion--insert-horizontal, completion--insert-vertical)
(completion--insert-one-column): Add LINES argument.
(completion--insert): Call completion-lazy-hilit.
(minibuffer-completion-help): Set completion-lazy-hilit.
(with-minibuffer-completions-window): Call
completion--lazy-insert-strings.
* lisp/simple.el (completion-setup-function): Preserve
buffer-locals required for lazy completion insertion.
(switch-to-completions): Call completion--lazy-insert-strings.
---
etc/NEWS | 10 ++++++++
lisp/minibuffer.el | 64 +++++++++++++++++++++++++++++++++++++++-------
lisp/simple.el | 5 +++-
3 files changed, 69 insertions(+), 10 deletions(-)
diff --git a/etc/NEWS b/etc/NEWS
index 9fe46d818bd..f9cb7b4a247 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -176,6 +176,16 @@ will still be on that candidate after "*Completions*" is updated with a
new list of completions. The candidate is automatically deselected when
the "*Completions*" buffer is hidden.
+---
+*** "*Completions*" is displayed faster with many completion candidates.
+As always, if there are more completion candidates than can be displayed
+in the current frame, only a subset of the candidates is displayed.
+This process is now faster: only that subset of the candidates is
+actually inserted into "*Completions*" until you run a command which
+interacts with the text of the "*Completions*" buffer. This
+optimization only applies when 'completions-format' is 'horizontal' or
+'one-column'.
+
** Windows
+++
diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index b401e4a920c..af13cb8d79a 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -2230,6 +2230,15 @@ completions-header-format
(string :tag "Format string for heading line"))
:version "29.1")
+(defvar-local completions--lazy-insert-button nil)
+
+(defvar completion--insert-strings-lazily t
+ "If non-nil, `completion--insert-strings' inserts strings lazily.
+
+Candidate strings are inserted until the buffer contents has enough
+lines to fill the current frame. The remainder will be inserted by
+`completion--lazy-insert-strings'.")
+
(defun completion--insert-strings (strings &optional group-fun)
"Insert a list of STRINGS into the current buffer.
The candidate strings are inserted into the buffer depending on the
@@ -2251,18 +2260,53 @@ completion--insert-strings
;; Don't allocate more columns than we can fill.
;; Windows can't show less than 3 lines anyway.
(max 1 (/ (length strings) 2))))
- (colwidth (/ wwidth columns)))
+ (colwidth (/ wwidth columns))
+ (lines (when completion--insert-strings-lazily (frame-height))))
(unless (or tab-stop-list (null completion-tab-width)
(zerop (mod colwidth completion-tab-width)))
;; Align to tab positions for the case
;; when the caller uses tabs inside prefix.
(setq colwidth (- colwidth (mod colwidth completion-tab-width))))
- (funcall (intern (format "completion--insert-%s" completions-format))
- strings group-fun length wwidth colwidth columns))))
+ (let ((start (point))
+ (truncated
+ (catch 'completions-truncated
+ (funcall (intern (format "completion--insert-%s" completions-format))
+ strings group-fun length wwidth colwidth columns lines))))
+ (when (eq truncated 'truncated)
+ (newline)
+ ;; If there's a bug which causes us to not insert the remaining
+ ;; completions automatically, the user can at least press this button.
+ (setq-local completions--lazy-insert-button
+ (insert-button "[Completions truncated, click here to insert the rest.]"
+ 'action #'completion--lazy-insert-strings))
+ (button-put completions--lazy-insert-button 'group-fun group-fun)
+ (button-put completions--lazy-insert-button 'completions-start (copy-marker start))
+ (button-put completions--lazy-insert-button 'completion-strings strings))))))
+
+(defun completion--lazy-insert-strings (&optional button)
+ (setq button (or button completions--lazy-insert-button))
+ (when button
+ (let ((completion--insert-strings-lazily nil)
+ (completion-lazy-hilit t)
+ (standard-output (current-buffer))
+ (inhibit-read-only t)
+ (group-fun (button-get button 'group-fun))
+ (strings (button-get button 'completion-strings)))
+ (save-excursion
+ (goto-char (button-get button 'completions-start))
+ (delete-region (point) (button-end button))
+ (setq-local completions--lazy-insert-button nil)
+ (completion--insert-strings strings group-fun)))))
+
+(defun completion--newline (wanted-lines)
+ "Insert a newline and throw if there are more than WANTED-LINES."
+ (newline)
+ (when (and wanted-lines (> (line-number-at-pos) wanted-lines))
+ (throw 'completions-truncated 'truncated)))
(defun completion--insert-horizontal (strings group-fun
length wwidth
- colwidth _columns)
+ colwidth _columns lines)
(let ((column 0)
(first t)
(last-title nil)
@@ -2286,7 +2330,7 @@ completion--insert-horizontal
(apply #'+ (mapcar #'string-width str))
(string-width str)))))
;; No space for `str' at point, move to next line.
- (progn (insert "\n") (setq column 0))
+ (progn (completion--newline lines) (setq column 0))
(insert " \t")
;; Leave the space unpropertized so that in the case we're
;; already past the goal column, there is still
@@ -2307,7 +2351,7 @@ completion--insert-horizontal
(defun completion--insert-vertical (strings group-fun
_length _wwidth
- colwidth columns)
+ colwidth columns _lines)
(while strings
(let ((group nil)
(column 0)
@@ -2357,7 +2401,7 @@ completion--insert-vertical
(insert "\n"))
(setq row (1+ row)))))))
-(defun completion--insert-one-column (strings group-fun &rest _)
+(defun completion--insert-one-column (strings group-fun _length _wwidth _colwidth _columns lines)
(let ((last-title nil) (last-string nil))
(dolist (str strings)
(unless (equal last-string str) ; Remove (consecutive) duplicates.
@@ -2369,14 +2413,14 @@ completion--insert-one-column
(when title
(insert (format completions-group-format title) "\n")))))
(completion--insert str group-fun)
- (insert "\n")))
+ (completion--newline lines)))
(delete-char -1)))
(defun completion--insert (str group-fun)
(if (not (consp str))
(add-text-properties
(point)
- (progn
+ (let ((str (completion-lazy-hilit str)))
(insert
(if group-fun
(funcall group-fun str 'transform)
@@ -2644,6 +2688,7 @@ minibuffer-completion-help
(end (or end (point-max)))
(string (buffer-substring start end))
(md (completion--field-metadata start))
+ (completion-lazy-hilit t)
(completions (completion-all-completions
string
minibuffer-completion-table
@@ -4986,6 +5031,7 @@ with-minibuffer-completions-window
(get-buffer-window "*Completions*" 0)))))
(when window
(with-selected-window window
+ (completion--lazy-insert-strings)
,@body))))
(defcustom minibuffer-completion-auto-choose t
diff --git a/lisp/simple.el b/lisp/simple.el
index e1c0dd4a092..c7742689897 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -10455,10 +10455,12 @@ completion-setup-function
(buffer-substring (minibuffer-prompt-end) (point)))))))
(with-current-buffer standard-output
(let ((base-position completion-base-position)
- (insert-fun completion-list-insert-choice-function))
+ (insert-fun completion-list-insert-choice-function)
+ (lazy-button completions--lazy-insert-button))
(completion-list-mode)
(when completions-highlight-face
(setq-local cursor-face-highlight-nonselected-window t))
+ (setq-local completions--lazy-insert-button lazy-button)
(setq-local completion-base-position base-position)
(setq-local completion-list-insert-choice-function insert-fun))
(setq-local completion-reference-buffer mainbuf)
@@ -10504,6 +10506,7 @@ switch-to-completions
(progn (minibuffer-completion-help)
(get-buffer-window "*Completions*" 0)))))
(select-window window)
+ (completion--lazy-insert-strings)
(when (bobp)
(cond
((and (memq this-command '(completion-at-point minibuffer-complete))
--
2.39.3
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997,2003 nCipher Corporation Ltd,
1994-97 Ian Jackson.