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

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

[Spencer Baugh via Bug reports for GNU Emacs, the Swiss army knife of text editors]

[-- Attachment #1: Type: text/plain, Size: 1754 bytes --]

Tags: patch


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.

By adding completions-list-max with a very large default, performance
is greatly improved in these situations without impacting the normal
case of completion on reasonably sized sets.

Limiting the work done by display-completion-list is also important
for packages which auto-update *Completions* inside while-no-input:
since display-completion-list doesn't do anything which reads input,
while-no-input won't interrupt it.  Such packages can instead just
bind completions-list-max to a smaller value.

* lisp/minibuffer.el (display-completion-list): Add FULL-COUNT
argument.
(completions-list-max): Add.
(minibuffer-completion-help): Truncate completions based on
completions-list-max.

In GNU Emacs 29.2.50 (build 9, x86_64-pc-linux-gnu, X toolkit, cairo
 version 1.15.12, Xaw scroll bars) of 2024-11-20 built on
 igm-qws-u22796a
Repository revision: 28dc0b6f9987e0def7dff4deaa23aa60f021d2a7
Repository branch: emacs-29
Windowing system distributor 'The X.Org Foundation', version 11.0.12011000
System Description: Rocky Linux 8.10 (Green Obsidian)

Configured using:
 'configure --with-x-toolkit=lucid --without-gpm --without-gconf
 --without-selinux --without-imagemagick --with-modules --with-gif=no
 --with-tree-sitter --with-native-compilation=aot
 PKG_CONFIG_PATH=/usr/local/home/garnish/libtree-sitter/0.22.6-1/lib/pkgconfig/'


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Allow-limiting-the-size-of-Completions.patch --]
[-- Type: text/patch, Size: 6047 bytes --]

From 808b1a6d01fcd2d2cc03324aa9826b3160047653 Mon Sep 17 00:00:00 2001
From: Spencer Baugh <sbaugh@janestreet.com>
Date: Thu, 14 Nov 2024 17:14:10 -0500
Subject: [PATCH] Allow limiting the size of *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.

By adding completions-list-max with a very large default, performance
is greatly improved in these situations without impacting the normal
case of completion on reasonably sized sets.

Limiting the work done by display-completion-list is also important
for packages which auto-update *Completions* inside while-no-input:
since display-completion-list doesn't do anything which reads input,
while-no-input won't interrupt it.  Such packages can instead just
bind completions-list-max to a smaller value.

* lisp/minibuffer.el (display-completion-list): Add FULL-COUNT
argument.
(completions-list-max): Add.
(minibuffer-completion-help): Truncate completions based on
completions-list-max.
---
 lisp/minibuffer.el | 38 +++++++++++++++++++++++++++++++-------
 1 file changed, 31 insertions(+), 7 deletions(-)

diff --git a/lisp/minibuffer.el b/lisp/minibuffer.el
index 5d11064d900..8078e1603ae 100644
--- a/lisp/minibuffer.el
+++ b/lisp/minibuffer.el
@@ -2354,7 +2354,7 @@ completion-hilit-commonality
         completions)
        base-size))))
 
-(defun display-completion-list (completions &optional common-substring group-fun)
+(defun display-completion-list (completions &optional common-substring group-fun full-count)
   "Display the list of completions, COMPLETIONS, using `standard-output'.
 Each element may be just a symbol or string
 or may be a list of two strings to be printed as if concatenated.
@@ -2366,7 +2366,9 @@ display-completion-list
 At the end, this runs the normal hook `completion-setup-hook'.
 It can find the completion buffer in `standard-output'.
 GROUP-FUN is a `group-function' used for grouping the completion
-candidates."
+candidates.
+If FULL-COUNT is non-nil, it's used as the total number of
+completions."
   (declare (advertised-calling-convention (completions) "24.4"))
   (if common-substring
       (setq completions (completion-hilit-commonality
@@ -2379,17 +2381,24 @@ display-completion-list
 	(let ((standard-output (current-buffer))
 	      (completion-setup-hook nil))
           (with-suppressed-warnings ((callargs display-completion-list))
-	    (display-completion-list completions common-substring group-fun)))
+	    (display-completion-list completions common-substring group-fun full-count)))
 	(princ (buffer-string)))
 
     (with-current-buffer standard-output
       (goto-char (point-max))
       (if completions-header-format
-          (insert (format completions-header-format (length completions)))
+          (insert (format completions-header-format (or full-count (length completions))))
         (unless completion-show-help
           ;; Ensure beginning-of-buffer isn't a completion.
           (insert (propertize "\n" 'face '(:height 0)))))
-      (completion--insert-strings completions group-fun)))
+      (completion--insert-strings completions group-fun)
+      (when (and full-count (/= full-count (length completions)))
+        (newline)
+        (insert (propertize
+                 (format "Displaying %s of %s possible completions.\n"
+                         (length completions) full-count)
+                 'face
+                 'shadow)))))
 
   (run-hooks 'completion-setup-hook)
   nil)
@@ -2455,6 +2464,15 @@ completions--fit-window-to-buffer
         (resize-temp-buffer-window win))
     (fit-window-to-buffer win completions-max-height)))
 
+(defcustom completions-list-max 10000
+  "Maximum number of completions for `minibuffer-completion-help' to list.
+
+After the completions are sorted, any beyond this amount are
+discarded and a message about truncation is inserted.  This can
+improve performance when displaying large numbers of completions."
+  :type 'number
+  :version "31.1")
+
 (defcustom completion-auto-deselect t
   "If non-nil, deselect current completion candidate when you type in minibuffer.
 
@@ -2554,7 +2572,8 @@ minibuffer-completion-help
              ;; window, mark it as softly-dedicated, so bury-buffer in
              ;; minibuffer-hide-completions will know whether to
              ;; delete the window or not.
-             (display-buffer-mark-dedicated 'soft))
+             (display-buffer-mark-dedicated 'soft)
+             full-count)
         (with-current-buffer-window
           "*Completions*"
           ;; This is a copy of `display-buffer-fallback-action'
@@ -2610,6 +2629,11 @@ minibuffer-completion-help
                                  (_ completions-group-sort))
                                completions)))
 
+                      (when completions-list-max
+                        (setq full-count (length completions))
+                        (when (< completions-list-max full-count)
+                          (setq completions (take completions-list-max completions))))
+
                       (cond
                        (aff-fun
                         (setq completions
@@ -2661,7 +2685,7 @@ minibuffer-completion-help
                                                      (if (eq (car bounds) (length result))
                                                          'exact 'finished))))))
 
-                      (display-completion-list completions nil group-fun)
+                      (display-completion-list completions nil group-fun full-count)
                       (when current-candidate-and-offset
                         (with-current-buffer standard-output
                           (when-let* ((match (text-property-search-forward
-- 
2.39.3

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

[Drew Adams via Bug reports for GNU Emacs, the Swiss army knife of text editors]

FWIW, Icicles has had this since 2010.
`C-h v icicle-max-candidates':

  icicle-max-candidates is a variable defined in `icicles-opt.el'.

  Its value is nil

  Documentation:
  Non-nil means truncate completion candidates to at most this many.
  If you use library `doremi.el' then you can use `C-x #' during
  completion to increment or decrement the option value using the
  vertical arrow keys or the mouse wheel.  A numeric prefix argument for
  `C-x #' sets the increment size.  A plain prefix argument (`C-u')
  resets `icicle-max-candidates' to nil, meaning no truncation.

  If the value is an integer and you use Do Re Mi (library `doremi.el')
  then you can use multi-command `icicle-increment-option' anytime to
  change the option value incrementally.

  You can customize this variable.

If the list of candidates shown in `*Completions*' is truncated
because of `icicle-max-candidates' then:

1. Mode-line minor-mode lighter `Icy' is suffixed by `...'.  If you
   see `...' you know that if you increase `icicle-max-candidates'
   (e.g. by using `C-x #') then more candidates will be available.

2. The mode-line of buffer *Completions*' shows the number of
   candidates - e.g., `567 candidates'.  If the display is truncated
   then it shows the number displayed and the total number - e.g.,
   `149/567 candidates shown'.

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

[Eli Zaretskii]

(Adding Stefan to the discussion.)

> Cc: dmitry@gutov.dev, juri@linkov.net
> Date: Wed, 27 Nov 2024 15:25:19 -0500
> From:  Spencer Baugh via "Bug reports for GNU Emacs,
>  the Swiss army knife of text editors" <bug-gnu-emacs@gnu.org>
> 
> >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.
> 
> By adding completions-list-max with a very large default, performance
> is greatly improved in these situations without impacting the normal
> case of completion on reasonably sized sets.
> 
> Limiting the work done by display-completion-list is also important
> for packages which auto-update *Completions* inside while-no-input:
> since display-completion-list doesn't do anything which reads input,
> while-no-input won't interrupt it.  Such packages can instead just
> bind completions-list-max to a smaller value.

IMO, that's the wrong way of solving this issue.  A Lisp program can
hardly know what limitation to impose in each case.  It could very
well set a limitation that leaves the important candidates out.

(And, btw, the fact that completion is slow when there are many
candidates is the wrong rationale for this kind of feature.  If I
magically speed up completion by 2 orders of magnitude, would you drop
the proposal and agree to showing 589196 candidates to the user?)

IMO, this is something for the user to specify, not for Lisp programs
or global options.  So the better solution for this is to ask the user
whether to show all the candidates and how many of them to show, and
the user's response will probably be different depending on the
context and the circumstances.

This is what Bash does:

  User: TAB
  Bash: Display all 4741 possibilities? (y or n)

Why shouldn't Emacs learn from Bash, let alone improve it (Bash
doesn't let you ask for the first 1000 possibilities, for example, or
for the last 110)?

The proposal here does not allow such UI, AFAIU.  So I think we should
instead add a mechanism for supporting such a UI, and include in it
the capability for the user to tell Emacs how many candidates to show.
Then we could improve the completion interaction by using that
mechanism.

> >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.

If display-completion-list takes most of the time (something that is
expected, I think), then the problem is in display, and any
improvements should be there first.  For example, could it be that it
is slow due to long lines? if not, what makes display-completion-list
so slow?  More detailed analysis needed, IMO.

This is independent of the larger issue above: whatever we do to limit
the number of candidates, it's ridiculous to spend most of the time in
showing the candidates on display, so we should make that as fast as
possible, regardless of the rest.

> Limiting the work done by display-completion-list is also important
> for packages which auto-update *Completions* inside while-no-input:
> since display-completion-list doesn't do anything which reads input,
> while-no-input won't interrupt it.

Here's another immediate hint for improving the UX: make it so
display-completion-list could be interrupted.  Again, limiting the
number of completions is blunt instrument, which misses opportunities
for important improvements.

> +If FULL-COUNT is non-nil, it's used as the total number of
> +completions."

This is hard to parse.  Does FULL-COUNT have to be a number? if so,
the doc string should say so.  And how is "total number of
completions" used by the function? without knowing that, this addition
to the doc string is not useful.

> +      (completion--insert-strings completions group-fun)
> +      (when (and full-count (/= full-count (length completions)))
> +        (newline)
> +        (insert (propertize
> +                 (format "Displaying %s of %s possible completions.\n"
> +                         (length completions) full-count)
> +                 'face
> +                 'shadow)))))

That leaves no possibility to display the next portion of the
candidates.  Why not? couldn't some UI want to present such a feature?

> +(defcustom completions-list-max 10000
> +  "Maximum number of completions for `minibuffer-completion-help' to list.

"to show" or "to display", not "to list".  The latter is ambiguous,
whereas minibuffer-completion-help's job is to display the candidates.

> +After the completions are sorted, any beyond this amount are
> +discarded and a message about truncation is inserted.

Passive tense alert!

>                                                         This can
> +improve performance when displaying large numbers of completions."

Performance is not the only reason to avoid showing a very long list
of completions.  If we want to include in the doc string the reasons
to use this variable, let's mention the other reasons.

More generally, since this is a user option, we should perhaps have a
variable that takes the default value from the option, and let Lisp
programs bind that variable, not the option.  Suppose we have a
situation with nested completion -- would we want the outer one affect
the inner one if it binds the option to some value?

> +                      (when completions-list-max
> +                        (setq full-count (length completions))
> +                        (when (< completions-list-max full-count)
> +                          (setq completions (take completions-list-max completions))))
> +

This assumes that the process of producing the completion can never be
the bottleneck, but that is not a given.  How about extending this to
allow stopping the process of collecting the candidates once the limit
is reached?

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

[Juri Linkov]

> +(defcustom completions-list-max 10000
> +  "Maximum number of completions for `minibuffer-completion-help' to list.

10000 is too small default value.  I often use 'C-x 8 RET TAB'
to browse the full list of 50866 Unicode characters
and use Isearch to find a character by name.  And it's quite fast -
usually takes only 1-2 seconds to show the completion list.

An alternative would be to populate the list lazily by small chunks
added with an idle timer.  But not sure it's worth the complexity.

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

[Drew Adams via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> > +(defcustom completions-list-max 10000
> > +  "Maximum number of completions for `minibuffer-completion-help' to
> list.
> 
> 10000 is too small default value.  I often use 'C-x 8 RET TAB'
> to browse the full list of 50866 Unicode characters
> and use Isearch to find a character by name.  And it's quite fast -
> usually takes only 1-2 seconds to show the completion list.

Why have a count as default?  The option I
have (`icicle-max-candidates') has default
value `nil', meaning there's no limit by
default.

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

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> From profiling, the main bottleneck in completion over large
> completion sets is display-completion-list, when there are many
> available candidates.

Hmm... interesting.  I expected it would be the computation of faces
from things like `completion-pcm--hilit-commonality`.

Do you happen to know which part of `display-completion-list` is the
most costly?  is it the actual insertion into the buffer?

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.


        Stefan

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

[Spencer Baugh via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> From profiling, the main bottleneck in completion over large
>> completion sets is display-completion-list, when there are many
>> available candidates.
>
> Hmm... interesting.  I expected it would be the computation of faces
> from things like `completion-pcm--hilit-commonality`.
>
> Do you happen to know which part of `display-completion-list` is the
> most costly?  is it the actual insertion into the buffer?

A simple way to profile this is:
(progn
  (require 'profiler)
  (profiler-reset)
  (profiler-cpu-start 10000)
  (completing-read ":" (mapcar #'number-to-string (number-sequence 0 100000)))
  (profiler-cpu-stop)
  (setq profiler-cpu-log (profiler-cpu-log))
  (profiler-report-cpu))

The biggest individual contributors of runtime are
set/add-text-properties and insert.

> 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?

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

[Dmitry Gutov]

On 29/11/2024 16:45, Spencer Baugh wrote:
>> Hmm... interesting.  I expected it would be the computation of faces
>> from things like `completion-pcm--hilit-commonality`.
>>
>> Do you happen to know which part of `display-completion-list` is the
>> most costly?  is it the actual insertion into the buffer?
> A simple way to profile this is:
> (progn
>    (require 'profiler)
>    (profiler-reset)
>    (profiler-cpu-start 10000)
>    (completing-read ":" (mapcar #'number-to-string (number-sequence 0 100000)))
>    (profiler-cpu-stop)
>    (setq profiler-cpu-log (profiler-cpu-log))
>    (profiler-report-cpu))
> 
> The biggest individual contributors of runtime are
> set/add-text-properties and insert.

Buffer text properties are implemented in terms of plists, so it makes 
sense that they're consing and contribute to GC churn.

Actually limiting the completions buffer to N completions makes a lot of 
sense from my POV - not in the least because it corresponds to rendering 
a completion popup (which only shows N lines), with similar big-O 
complexity.

I suppose supporting full C-s searches is something of a complication, 
though. In Xref buffer, we do such adjustments in post-command-hook (for 
line truncation).