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?