bug#72826: 30.0.90; icomplete-in-buffer becomes unusably slow in large Eshell

bug#72826: 30.0.90; icomplete-in-buffer becomes unusably slow in large Eshell

[Sean Whitton]

Hello,

1. emacs -q
2. (setopt icomplete-in-buffer t)
3. M-x icomplete-mode
4. M-x eshell
5. cat very_large_file.txt # I'm using an 80k line log file
6. ls <TAB>
7. Try to use C-, and C-. to cycle through the completions.
  => Emacs basically locks up.

The buffer being large should surely not affect icomplete-in-buffer in
this way.  It shouldn't need to care about all the rest of the buffer.

-- 
Sean Whitton

bug#72826: 30.0.90; icomplete-in-buffer becomes unusably slow in large Eshell

[Eli Zaretskii]

> From: Sean Whitton <spwhitton@spwhitton.name>
> Date: Tue, 27 Aug 2024 15:26:03 +0800
> 
> Hello,
> 
> 1. emacs -q
> 2. (setopt icomplete-in-buffer t)
> 3. M-x icomplete-mode
> 4. M-x eshell
> 5. cat very_large_file.txt # I'm using an 80k line log file
> 6. ls <TAB>
> 7. Try to use C-, and C-. to cycle through the completions.
>   => Emacs basically locks up.
> 
> The buffer being large should surely not affect icomplete-in-buffer in
> this way.  It shouldn't need to care about all the rest of the buffer.

Strangely enough, I can only reproduce this on GNU/Linux, but not on
MS-Windows.

Profiling seems to indicate most of the time is spent in
completion-all-sorted-completions and in GC.

bug#72826: 30.0.90; icomplete-in-buffer becomes unusably slow in large Eshell

[Sean Whitton]

[CCing Juri and João who have worked on this.]

Hello,

On Tue 27 Aug 2024 at 03:43pm +03, Eli Zaretskii wrote:

>> From: Sean Whitton <spwhitton@spwhitton.name>
>> Date: Tue, 27 Aug 2024 15:26:03 +0800
>>
>> Hello,
>>
>> 1. emacs -q
>> 2. (setopt icomplete-in-buffer t)
>> 3. M-x icomplete-mode
>> 4. M-x eshell
>> 5. cat very_large_file.txt # I'm using an 80k line log file
>> 6. ls <TAB>
>> 7. Try to use C-, and C-. to cycle through the completions.
>>   => Emacs basically locks up.
>>
>> The buffer being large should surely not affect icomplete-in-buffer in
>> this way.  It shouldn't need to care about all the rest of the buffer.
>
> Strangely enough, I can only reproduce this on GNU/Linux, but not on
> MS-Windows.
>
> Profiling seems to indicate most of the time is spent in
> completion-all-sorted-completions and in GC.

I just tried profiling it myself:

       38958  93% - icomplete-post-command-hook
       38958  93%  - icomplete-exhibit
       38819  93%   - icomplete-completions
       38749  92%      string-width
          43   0%    + icomplete--sorted-completions
          27   0%      buffer-string
         139   0%   + sit-for

I think the culprit is probably the evaulation of
(string-width (buffer-string)) in icomplete-completions.
That'll always be fast for Icomplete in the minibuffer, but for
icomplete-in-buffer it depends on the size of the buffer.

I think this code is trying to determine how much space is taken up by
the minibuffer prompt and the user's input typed so far.  So, we can
probably find a cheaper way to compute the corresponding value for
icomplete-in-buffer.

-- 
Sean Whitton

bug#72826: 30.0.90; icomplete-in-buffer becomes unusably slow in large Eshell

[Eli Zaretskii]

> From: Sean Whitton <spwhitton@spwhitton.name>
> Cc: 72826@debbugs.gnu.org, Juri Linkov <juri@linkov.net>, João Távora
>  <joaotavora@gmail.com>
> Date: Thu, 03 Oct 2024 22:28:49 +0800
> 
>        38958  93% - icomplete-post-command-hook
>        38958  93%  - icomplete-exhibit
>        38819  93%   - icomplete-completions
>        38749  92%      string-width
>           43   0%    + icomplete--sorted-completions
>           27   0%      buffer-string
>          139   0%   + sit-for
> 
> I think the culprit is probably the evaulation of
> (string-width (buffer-string)) in icomplete-completions.

Does it help to disable auto-composition-mode?

bug#72826: 30.0.90; icomplete-in-buffer becomes unusably slow in large Eshell

[Sean Whitton]

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

Hello,

On Thu 03 Oct 2024 at 06:16pm +03, Eli Zaretskii wrote:

>> From: Sean Whitton <spwhitton@spwhitton.name>
>> Cc: 72826@debbugs.gnu.org, Juri Linkov <juri@linkov.net>, João Távora
>>  <joaotavora@gmail.com>
>> Date: Thu, 03 Oct 2024 22:28:49 +0800
>>
>>        38958  93% - icomplete-post-command-hook
>>        38958  93%  - icomplete-exhibit
>>        38819  93%   - icomplete-completions
>>        38749  92%      string-width
>>           43   0%    + icomplete--sorted-completions
>>           27   0%      buffer-string
>>          139   0%   + sit-for
>>
>> I think the culprit is probably the evaulation of
>> (string-width (buffer-string)) in icomplete-completions.
>
> Does it help to disable auto-composition-mode?

It looks like that slightly improves the situation, but does not fix it.
It's still extremely slow.

I think I have a fix, which I've attached.  I'll test it locally for a
couple of days before installing it.

-- 
Sean Whitton

[-- Attachment #2: 0001-icomplete-completions-Compute-prospects-len-more-eff.patch --]
[-- Type: text/x-diff, Size: 1496 bytes --]

From 98cfa9bf6d9ec23573365031b3734fb9c2965dd5 Mon Sep 17 00:00:00 2001
From: Sean Whitton <spwhitton@spwhitton.name>
Date: Fri, 4 Oct 2024 08:19:40 +0800
Subject: [PATCH] icomplete-completions: Compute prospects-len more efficiently

* lisp/icomplete.el (icomplete-completions): Avoid calling
string-width on the entire buffer-string when computing
prospects-len (bug#72826).
---
 lisp/icomplete.el | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/lisp/icomplete.el b/lisp/icomplete.el
index 2ea5e36fa88..9497b46c6cf 100644
--- a/lisp/icomplete.el
+++ b/lisp/icomplete.el
@@ -1007,7 +1007,12 @@ icomplete-completions
                                   (or determ (concat open-bracket close-bracket)))
                                  (string-width icomplete-separator)
                                  (+ 2 (string-width ellipsis)) ;; take {…} into account
-                                 (string-width (buffer-string))))
+                                 (string-width
+                                  (buffer-substring
+                                   (save-excursion
+                                     (goto-char (icomplete--field-beg))
+                                     (pos-bol))
+                                   (icomplete--field-end)))))
                (prospects-max
                 ;; Max total length to use, including the minibuffer content.
                 (* (+ icomplete-prospects-height
-- 
2.45.2

bug#72826: 30.0.90; icomplete-in-buffer becomes unusably slow in large Eshell

[Eli Zaretskii]

> From: Sean Whitton <spwhitton@spwhitton.name>
> Cc: 72826@debbugs.gnu.org,  juri@linkov.net,  joaotavora@gmail.com
> Date: Fri, 04 Oct 2024 08:20:01 +0800
> 
> > Does it help to disable auto-composition-mode?
> 
> It looks like that slightly improves the situation, but does not fix it.
> It's still extremely slow.
> 
> I think I have a fix, which I've attached.  I'll test it locally for a
> couple of days before installing it.

Can you explain why taking a substring of the buffer text is TRT in
this case and how it makes such a big difference without omitting text
whose width should be measured?  IOW, are you saying the current code
produces too large width? if so, how can the layout of completion
candidates be correct?

bug#72826: 30.0.90; icomplete-in-buffer becomes unusably slow in large Eshell

[Sean Whitton]

Hello,

On Fri 04 Oct 2024 at 09:11am +03, Eli Zaretskii wrote:

> Can you explain why taking a substring of the buffer text is TRT in
> this case and how it makes such a big difference without omitting text
> whose width should be measured?  IOW, are you saying the current code
> produces too large width? if so, how can the layout of completion
> candidates be correct?

Here is my thinking:

I think that the current code was not written with icomplete-in-region
in mind, which makes sense, because icomplete-in-region was added later.

The current code simply calculates the width taken up by the minibuffer
prompt and (minibuffer-contents), and starts the candidates to the right
of those.  Ignoring icomplete-in-region, (buffer-string) is exactly what
we want, because there is nothing else in the minibuffer.

So, how can we perform an equivalent calculation that will work in the
case that we might not be in a minibuffer?  Well, the characters between
(icomplete--field-beg) and (icomplete--field-end) are the equivalent of
(minibuffer-contents).  Then going back to (pos-bol) before
(icomplete--field-beg) is the equivalent of including the width of the
minibuffer prompt.

Cases where the old code and new code are different are when the
minibuffer prompt contains line breaks.  The new code effectively
ignores all parts of the minibuffer prompt except its last line.  I
think that's correct, and the old code could have calculated an overly
large width if previous lines of the minibuffer prompt were longer than
the final line.

One case I am not sure about is when the existing input takes up more
than one line.  I believe the old and new code will always do the same
thing, but I'm not sure it's correct.

-- 
Sean Whitton

bug#72826: 30.0.90; icomplete-in-buffer becomes unusably slow in large Eshell

[Eli Zaretskii]

> From: Sean Whitton <spwhitton@spwhitton.name>
> Cc: joaotavora@gmail.com,  72826@debbugs.gnu.org,  juri@linkov.net
> Date: Fri, 04 Oct 2024 17:02:25 +0800
> 
> Cases where the old code and new code are different are when the
> minibuffer prompt contains line breaks.  The new code effectively
> ignores all parts of the minibuffer prompt except its last line.  I
> think that's correct, and the old code could have calculated an overly
> large width if previous lines of the minibuffer prompt were longer than
> the final line.

So you are saying that the old code never worked correctly for
minibuffer prompts that include embedded newlines?  Then how come no
one complained about that before?  This bug is not about incorrect
result, it's about slow responses, and that's something entirely
different.

bug#72826: 30.0.90; icomplete-in-buffer becomes unusably slow in large Eshell

[Sean Whitton]

Hello,

On Fri 04 Oct 2024 at 01:53pm +03, Eli Zaretskii wrote:

>> From: Sean Whitton <spwhitton@spwhitton.name>
>> Cc: joaotavora@gmail.com,  72826@debbugs.gnu.org,  juri@linkov.net
>> Date: Fri, 04 Oct 2024 17:02:25 +0800
>>
>> Cases where the old code and new code are different are when the
>> minibuffer prompt contains line breaks.  The new code effectively
>> ignores all parts of the minibuffer prompt except its last line.  I
>> think that's correct, and the old code could have calculated an overly
>> large width if previous lines of the minibuffer prompt were longer than
>> the final line.
>
> So you are saying that the old code never worked correctly for
> minibuffer prompts that include embedded newlines?  Then how come no
> one complained about that before?  This bug is not about incorrect
> result, it's about slow responses, and that's something entirely
> different.

Well, not many people use Icomplete mode, and not many minibuffer
prompts have embedded newlines.

If you prefer I could conditionalise the code so it does exactly the
same as it always did in the minibuffer, and only does something
different when completing in a region in a non-minibuffer?

-- 
Sean Whitton

bug#72826: 30.0.90; icomplete-in-buffer becomes unusably slow in large Eshell

[Eli Zaretskii]

> From: Sean Whitton <spwhitton@spwhitton.name>
> Cc: joaotavora@gmail.com,  72826@debbugs.gnu.org,  juri@linkov.net
> Date: Fri, 04 Oct 2024 19:02:27 +0800
> 
> On Fri 04 Oct 2024 at 01:53pm +03, Eli Zaretskii wrote:
> 
> >> From: Sean Whitton <spwhitton@spwhitton.name>
> >> Cc: joaotavora@gmail.com,  72826@debbugs.gnu.org,  juri@linkov.net
> >> Date: Fri, 04 Oct 2024 17:02:25 +0800
> >>
> >> Cases where the old code and new code are different are when the
> >> minibuffer prompt contains line breaks.  The new code effectively
> >> ignores all parts of the minibuffer prompt except its last line.  I
> >> think that's correct, and the old code could have calculated an overly
> >> large width if previous lines of the minibuffer prompt were longer than
> >> the final line.
> >
> > So you are saying that the old code never worked correctly for
> > minibuffer prompts that include embedded newlines?  Then how come no
> > one complained about that before?  This bug is not about incorrect
> > result, it's about slow responses, and that's something entirely
> > different.
> 
> Well, not many people use Icomplete mode, and not many minibuffer
> prompts have embedded newlines.
> 
> If you prefer I could conditionalise the code so it does exactly the
> same as it always did in the minibuffer, and only does something
> different when completing in a region in a non-minibuffer?

That's not exactly my problem.  I actually wonder whether the current
code does TRT when there are embedded newlines, regardless of whether
it's slow or not.  Can you look at that?  If the current code works
correctly, then I think your analysis of what is wrong with it might
not be correct/complete, and there's some other factor at work here.

IOW, I think we should understand the issue and its root causes
completely before we discuss the solution.

bug#72826: 30.0.90; icomplete-in-buffer becomes unusably slow in large Eshell

[Sean Whitton]

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

Hello,

On Fri 04 Oct 2024 at 02:52pm +03, Eli Zaretskii wrote:

> I actually wonder whether the current code does TRT when there are
> embedded newlines, regardless of whether it's slow or not.  Can you
> look at that?  If the current code works correctly, then I think your
> analysis of what is wrong with it might not be correct/complete, and
> there's some other factor at work here.
>
> IOW, I think we should understand the issue and its root causes
> completely before we discuss the solution.

I played around with this a bit.

Firstly, I previously mentioned newlines in the input or candidates.
But Icomplete isn't really meant to work at all with candidates
containing newlines, so this part of the display algorithm certainly
doesn't.  So let's ignore that.  It's an extreme edge case.
(I'm not sure any of the completion infrastructure in Emacs is meant to
be able to handle candidates containing newlines.)

So, what we are interested in is the case of embedded newlines in the
minibuffer prompt, where the last line of the prompt is shorter than
previous lines, such that (string-width (buffer-string)) would give an
answer that's too large.

1. emacs -q
2. M-x icomplete-mode
3. (setopt icomplete-show-matches-on-no-input t)
4. (completing-read "Here we go: " obarray)


[-- Attachment #2: melete_2024-10-04_22.04.57.png --]
[-- Type: image/png, Size: 19406 bytes --]

[-- Attachment #3: Type: text/plain, Size: 91 bytes --]


5. C-g
6. (completing-read "Here we go here we go
here we go: " obarray)

This displays:


[-- Attachment #4: melete_2024-10-04_22.06.00.png --]
[-- Type: image/png, Size: 17791 bytes --]

[-- Attachment #5: Type: text/plain, Size: 192 bytes --]


This is wrong -- fewer candidates are displayed than there is space for,
and there is a big empty gap.

I believe this supports my analysis and the patch I posted.

Thanks.

-- 
Sean Whitton

bug#72826: 30.0.90; icomplete-in-buffer becomes unusably slow in large Eshell

[Eli Zaretskii]

> From: Sean Whitton <spwhitton@spwhitton.name>
> Cc: joaotavora@gmail.com,  72826@debbugs.gnu.org,  juri@linkov.net
> Date: Fri, 04 Oct 2024 22:09:54 +0800
> 
> This is wrong -- fewer candidates are displayed than there is space for,
> and there is a big empty gap.
> 
> I believe this supports my analysis and the patch I posted.

Thanks.  But the difference between the two cases is larger than the
difference between the first and the second line of the prompt.  How
do you explain that?  Also, why doesn't the first image show more
candidates, so as to use all of the second screen line in the
mini-window? is that expected?

But if your analysis is correct, does the value returned by
string-pixel-width divided by default-font-width produce the correct
result?

bug#72826: 30.0.90; icomplete-in-buffer becomes unusably slow in large Eshell

[Sean Whitton]

Hello,

On Fri 04 Oct 2024 at 05:33pm +03, Eli Zaretskii wrote:

> Thanks.  But the difference between the two cases is larger than the
> difference between the first and the second line of the prompt.  How
> do you explain that?  Also, why doesn't the first image show more
> candidates, so as to use all of the second screen line in the
> mini-window? is that expected?

It's expected, indeed.  The explanation for all the cases you ask about
here is that the parts of the algorithm subsequent to the computation of
prospects-max do not try especially hard to fill up prospects-max.

My patch to address this bug only attempts to correct the computation of
prospects-max, not to make any change to how that value is subsequently
used.  If you think the latter should be changed, I think that should be
a separate bug report.  (Speaking as a longterm Icomplete user, I don't
especially think it needs to change.)

I've prepared two diffs that display the problem and how my patch
fixes it.  Apply the first diff and then try the (completing-read ...)
examples from my previous message.  In the case of the multiline prompt,
you can see that the XXXXXXX do not extend as far as they should.

Then apply the second diff, and try the (completing-read ...) again.
Even though the algorithm doesn't aggressively use up prospects-max, the
XXXXXX extend to the correct position, demonstrating the correctness of
my reworked computation of prospects-max.

--8<---------------cut here---------------start------------->8---
diff --git a/lisp/icomplete.el b/lisp/icomplete.el
index 2ea5e36fa88..e2607812d5e 100644
--- a/lisp/icomplete.el
+++ b/lisp/icomplete.el
@@ -1074,11 +1079,19 @@ icomplete-completions
                     (put-text-property 0 (length first)
                                        'face 'icomplete-first-match first)
                     (push first prospects)))
-                (concat determ
-                        "{"
-                        (mapconcat #'identity prospects icomplete-separator)
-                        (concat (and limit (concat icomplete-separator ellipsis))
-                                "}")))
+                (let ((res
+                       (concat determ
+                               "{"
+                               (mapconcat #'identity prospects icomplete-separator)
+                               (concat (and limit (concat icomplete-separator ellipsis))
+                                       "}"))))
+                  ;; Show the space out of prospects-max we didn't use.
+                  (if (window-minibuffer-p)
+                      (concat res (make-string (- prospects-max
+                                                  (length res)
+                                                  (string-width (buffer-string)))
+                                               ?X))
+                    res)))
             ;; Restore the base-size info, since completion-all-sorted-completions
             ;; is cached.
             (if last (setcdr last base-size))))))))
--8<---------------cut here---------------end--------------->8---

--8<---------------cut here---------------start------------->8---
diff --git a/lisp/icomplete.el b/lisp/icomplete.el
index 2ea5e36fa88..c37788d85e3 100644
--- a/lisp/icomplete.el
+++ b/lisp/icomplete.el
@@ -1002,12 +1002,18 @@ icomplete-completions
                                   ((< compare (+ 2 (string-width ellipsis))) most)
                                   (t (concat ellipsis (substring most compare))))
                                  close-bracket)))
+               (temp (string-width
+                      (buffer-substring
+                       (save-excursion
+                         (goto-char (icomplete--field-beg))
+                         (pos-bol))
+                       (icomplete--field-end))))
                ;;"-prospects" - more than one candidate
                (prospects-len (+ (string-width
                                   (or determ (concat open-bracket close-bracket)))
                                  (string-width icomplete-separator)
                                  (+ 2 (string-width ellipsis)) ;; take {…} into account
-                                 (string-width (buffer-string))))
+                                 temp))
                (prospects-max
                 ;; Max total length to use, including the minibuffer content.
                 (* (+ icomplete-prospects-height
@@ -1074,11 +1080,19 @@ icomplete-completions
                     (put-text-property 0 (length first)
                                        'face 'icomplete-first-match first)
                     (push first prospects)))
-                (concat determ
-                        "{"
-                        (mapconcat #'identity prospects icomplete-separator)
-                        (concat (and limit (concat icomplete-separator ellipsis))
-                                "}")))
+                (let ((res
+                       (concat determ
+                               "{"
+                               (mapconcat #'identity prospects icomplete-separator)
+                               (concat (and limit (concat icomplete-separator ellipsis))
+                                       "}"))))
+                  ;; Show the space out of prospects-max we didn't use.
+                  (if (window-minibuffer-p)
+                      (concat res (make-string (- prospects-max
+                                                  (length res)
+                                                  temp)
+                                               ?X))
+                    res)))
             ;; Restore the base-size info, since completion-all-sorted-completions
             ;; is cached.
             (if last (setcdr last base-size))))))))
--8<---------------cut here---------------end--------------->8---

> But if your analysis is correct, does the value returned by
> string-pixel-width divided by default-font-width produce the correct
> result?

Do you mean to propose (/ (string-pixel-width (buffer-string))
                          (default-font-width))
as an alternative to my fix?

I've just tried that, and while it appears to be slightly faster than
the existing code, Icomplete in a large buffer remains unusably slow.

-- 
Sean Whitton

bug#72826: 30.0.90; icomplete-in-buffer becomes unusably slow in large Eshell

[Eli Zaretskii]

> From: Sean Whitton <spwhitton@spwhitton.name>
> Cc: joaotavora@gmail.com,  72826@debbugs.gnu.org,  juri@linkov.net
> Date: Sat, 05 Oct 2024 08:21:56 +0800
> 
> On Fri 04 Oct 2024 at 05:33pm +03, Eli Zaretskii wrote:
> 
> > Thanks.  But the difference between the two cases is larger than the
> > difference between the first and the second line of the prompt.  How
> > do you explain that?  Also, why doesn't the first image show more
> > candidates, so as to use all of the second screen line in the
> > mini-window? is that expected?
> 
> It's expected, indeed.  The explanation for all the cases you ask about
> here is that the parts of the algorithm subsequent to the computation of
> prospects-max do not try especially hard to fill up prospects-max.
> 
> My patch to address this bug only attempts to correct the computation of
> prospects-max, not to make any change to how that value is subsequently
> used.  If you think the latter should be changed, I think that should be
> a separate bug report.  (Speaking as a longterm Icomplete user, I don't
> especially think it needs to change.)

Thanks, I'm convinced.  Please install your changes.

bug#72826: 30.0.90; icomplete-in-buffer becomes unusably slow in large Eshell

[Sean Whitton]

Done, and thanks!
-- 
Sean Whitton