Subject: Re: bug#74561: [PATCH] Allow limiting the size of *Completions*

From: [email-masked]
Date: Mon, 13 Jan 2025 19:39:50 +0000 (UTC)

Spencer Baugh <[email-masked]> writes:
> Stefan Monnier <[email-masked]> writes:
>> I think we should try and fill the buffer lazily.  We don't have much
>> experience with "jit" populating a buffer (the closest I can think of is
>> the `vlf` package, which doesn't do "jit", IIRC), so it may take some
>> trial-and-error until we have something that works, but it
>> seems worthwhile.
>
> Yes, I think filling the *Completions* buffer lazily would be way better
> than limiting the size of the buffer, thanks everyone for your comments.
>
> I think it would be sufficient to do something simple, and just split
> filling the *Completions* buffer into two parts:
>
> - In minibuffer-completion-help, insert only enough completion
> candidates that the part of the *Completions* buffer that's displayed in
> a window initially looks normal.  Save the rest of the completions in a
> buffer-local in *Completions*.
>
> - Upon any kind of interaction with the *Completions* buffer, insert all
> the rest of the completion candidates in completions--finish-populate.
>
> We could be lazier than this, but this is probably sufficient to give a
> big speedup, since I think *Completions* is rendered much more often
> than it's interacted with.
>
> So to do this, all we need is a way to do completions--finish-populate
> at the right time.
>
> I'm not sure when to do that.  Maybe we could just call it in
> window-selection-change-functions and with-minibuffer-completions-window
> and maybe a few other places?

I've done this in the attached patch and it seems to work well.  As a
fallback, there's also a button at the end of the *Completions* buffer
to finish filling it, in case something goes wrong with the automatic
laziness.

Incidentally, filling the buffer lazily allows the default completion
frontend to start using completion-lazy-hilit, which will be another
nice performance benefit (which can happen in a later follow-up patch).

>From d0ff52fbe81b4eea0bc319c14df269d90cfba4d2 Mon Sep 17 00:00:00 2001
From: Spencer Baugh <[email-masked]>
Date: Mon, 13 Jan 2025 14:32:18 -0500
Subject: [PATCH] Lazily 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
inserting the remaining only when necessary, performance is much
improved.

* lisp/minibuffer.el (completions-insert-lazily): Add defcustom
for inserting completions lazily. (bug#74561)
(completion--lazy-insert-completions)
(completion--lazy-insert-group-fun)
(completion--lazy-insert-start, completion--lazy-insert-end):
Add.
(completion--insert-strings): Check completions-insert-lazily.
(completion--lazy-display-completion-list): Add.
(with-minibuffer-completions-window): Call
completion--lazy-display-completion-list.
* lisp/simple.el (completion-setup-function): Preserve
buffer-locals required for lazy completion insertion.
(switch-to-completions): Call
completion--lazy-display-completion-list.
---
 lisp/minibuffer.el | 42 ++++++++++++++++++++++++++++++++++++++++--
 lisp/simple.el     | 11 ++++++++++-
 2 files changed, 50 insertions(+), 3 deletions(-)

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 1f33bda5f65..dc6999c7532 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -2230,6 +2230,19 @@ completions-header-format
                  (string :tag "Format string for heading line"))
   :version "29.1")
 
+(defcustom completions-insert-lazily 200
+  "If non-nil, completions are inserted lazily.
+
+When a number, only that many completions are inserted, and the
+rest are inserted lazily."
+  :type '(choice (const :tag "Render all completions immediately" nil)
+                 (integer :tag "Only render this many completions")))
+
+(defvar-local completion--lazy-insert-completions nil)
+(defvar-local completion--lazy-insert-group-fun nil)
+(defvar-local completion--lazy-insert-start nil)
+(defvar-local completion--lazy-insert-end nil)
+
 (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,14 +2264,26 @@ 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))
+           is-truncated)
       (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))))
+      (when (and completions-insert-lazily (< completions-insert-lazily (length strings)))
+        (setq is-truncated t)
+        (setq-local completion--lazy-insert-completions strings)
+        (setq-local completion--lazy-insert-group-fun group-fun)
+        (setq-local completion--lazy-insert-start (point-marker))
+        (setq strings (take completions-insert-lazily strings)))
       (funcall (intern (format "completion--insert-%s" completions-format))
-               strings group-fun length wwidth colwidth columns))))
+               strings group-fun length wwidth colwidth columns)
+      (when is-truncated
+        (newline)
+        (insert-button "[Completions truncated, click here to insert the rest.]"
+                       'action #'completion--lazy-display-completion-list)
+        (setq-local completion--lazy-insert-end (point-marker))))))
 
 (defun completion--insert-horizontal (strings group-fun
                                               length wwidth
@@ -2507,6 +2532,18 @@ display-completion-list
   (run-hooks 'completion-setup-hook)
   nil)
 
+(defun completion--lazy-display-completion-list (&optional _button)
+  (when completion--lazy-insert-completions
+    (let ((completions-insert-lazily nil)
+          (standard-output (current-buffer))
+          (inhibit-read-only t))
+      (delete-region completion--lazy-insert-start completion--lazy-insert-end)
+      (save-excursion
+        (goto-char completion--lazy-insert-start)
+        (completion--insert-strings
+         completion--lazy-insert-completions completion--lazy-insert-group-fun)
+        (setq-local completion--lazy-insert-completions nil)))))
+
 (defvar completion-extra-properties nil
   "Property list of extra properties of the current completion job.
 These include:
@@ -4962,6 +4999,7 @@ with-minibuffer-completions-window
                             (get-buffer-window "*Completions*" 0)))))
      (when window
        (with-selected-window window
+         (completion--lazy-display-completion-list)
          ,@body))))
 
 (defcustom minibuffer-completion-auto-choose t
diff --git a/lisp/simple.el b/lisp/simple.el
index c47ea8660f9..44221ba1bed 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -10455,10 +10455,18 @@ 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-completions completion--lazy-insert-completions)
+            (lazy-group-fun completion--lazy-insert-group-fun)
+            (lazy-start completion--lazy-insert-start)
+            (lazy-end completion--lazy-insert-end))
         (completion-list-mode)
         (when completions-highlight-face
           (setq-local cursor-face-highlight-nonselected-window t))
+        (setq-local completion--lazy-insert-completions lazy-completions)
+        (setq-local completion--lazy-insert-group-fun lazy-group-fun)
+        (setq-local completion--lazy-insert-start lazy-start)
+        (setq-local completion--lazy-insert-end lazy-end)
         (setq-local completion-base-position base-position)
         (setq-local completion-list-insert-choice-function insert-fun))
       (setq-local completion-reference-buffer mainbuf)
@@ -10504,6 +10512,7 @@ switch-to-completions
                           (progn (minibuffer-completion-help)
                                  (get-buffer-window "*Completions*" 0)))))
     (select-window window)
+    (completion--lazy-display-completion-list)
     (when (bobp)
       (cond
        ((and (memq this-command '(completion-at-point minibuffer-complete))
-- 
2.44.0