bug#72830: Big rectangular selections are slow

bug#72830: Big rectangular selections are slow

[Mattias Engdegård]

Selecting rectangles that stretch across many lines is very slow. Recipe:

  C-x b example RET
  C-u 60 x C-u 200000 M-x duplicate-dwim RET C-a
  C-x SPC
  M-> C-f C-f C-f C-f

Each keystroke at the end lags noticeably, to the point that this isn't practical.

Why this matters: rectangular selections are very useful for editing large amount of data in a homogeneous way, and such a file (12 MB) isn't huge.

Possible causes:

- Slow `region-beginning` and `region-end`.
  Fixed on master (3a8222e7).

- `select-active-regions` makes each selection change very expensive.
  Can be set to nil by the user, but I really suggest that we change the default to nil, at least for non-X11 since the default assumes old-school X11 PRIMARY selection which is alien on most other platforms.

- Slow `rectangle--highlight-for-redisplay`. This is the remaining cause.
Profiling shows that most of the time is spent in the function passed to `apply-on-rectangle`.
Here is an excerpt of that profile:

|        Weight         Self
|  31.93 Gc   57.4%   103.06 Mc   Fmove_to_column
|  31.52 Gc   56.7%   884.80 Mc     scan_for_column
|  14.45 Gc   26.0%    27.82 Mc       check_display_width
|  14.30 Gc   25.7%   648.23 Mc         get_char_property_and_overlay
|   9.79 Gc   17.6%     1.07 Gc           itree_iterator_next
|   2.00 Gc    3.6%    42.68 Mc           Fget_text_property
| 743.88 Mc    1.3%   154.63 Mc           itree_iterator_start
| 678.00 Mc    1.2%   183.02 Mc           lookup_char_property
|   7.28 Gc   13.0%   155.15 Mc       skip_invisible
|   4.22 Gc    7.6%   701.27 Mc       composition_compute_stop_pos
|   3.00 Gc    5.3%   153.86 Mc       window_loop
|   1.28 Gc    2.3%   216.97 Mc       find_newline
|   2.28 Gc    4.1%    80.59 Mc   Fmove_overlay
|   1.46 Gc    2.6%    40.18 Mc   lookup_char_property

This excludes GC costs (about 18 % I think), which in turn is dominated by scanning overlays.

It's a bit surprising (to me) how expensive move-to-column is. The text is all-ASCII without any complications (no long lines, properties, etc).

bug#72830: Big rectangular selections are slow

[Eli Zaretskii]

> Cc: Stefan Monnier <monnier@iro.umontreal.ca>, Juri Linkov <juri@linkov.net>
> From: Mattias Engdegård <mattias.engdegard@gmail.com>
> Date: Tue, 27 Aug 2024 14:39:37 +0200
> 
> It's a bit surprising (to me) how expensive move-to-column is. The text is all-ASCII without any complications (no long lines, properties, etc).

Does turning off auto-composition-mode help in any way?

Also, since highlighting is AFAIR implemented as overlays, it slows
down check_display_width, which I think would otherwise have moved
very fast if you say there are no properties and no overlays.

bug#72830: Big rectangular selections are slow

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

> Selecting rectangles that stretch across many lines is very slow.

Yup.

> - Slow `region-beginning` and `region-end`.
>   Fixed on master (3a8222e7).

Seems unlikely.

> - `select-active-regions` makes each selection change very expensive.
>   Can be set to nil by the user, but I really suggest that we change the
> default to nil, at least for non-X11 since the default assumes old-school
> X11 PRIMARY selection which is alien on most other platforms.

Didn't think of that.  Do we re-set the PRIMARY every time the (active)
rectangular region is changed (i.e. after each key press)?  That would
make it non-scalable to large rectangular regions, indeed.

I thought the extraction of the region's content to put it into PRIMARY
and friends happened more lazily (e.g. when another application
requests the PRIMARY/CLIPBOARD, or when we deactivate the region).

> - Slow `rectangle--highlight-for-redisplay`.  This is the remaining cause.

This is the one I'm aware of.

> Profiling shows that most of the time is spent in the function passed
> to `apply-on-rectangle`.  Here is an excerpt of that profile:
>
> |        Weight         Self
> |  31.93 Gc   57.4%   103.06 Mc   Fmove_to_column
> |  31.52 Gc   56.7%   884.80 Mc     scan_for_column
> |  14.45 Gc   26.0%    27.82 Mc       check_display_width
> |  14.30 Gc   25.7%   648.23 Mc         get_char_property_and_overlay
> |   9.79 Gc   17.6%     1.07 Gc           itree_iterator_next
> |   2.00 Gc    3.6%    42.68 Mc           Fget_text_property
> | 743.88 Mc    1.3%   154.63 Mc           itree_iterator_start
> | 678.00 Mc    1.2%   183.02 Mc           lookup_char_property
> |   7.28 Gc   13.0%   155.15 Mc       skip_invisible
> |   4.22 Gc    7.6%   701.27 Mc       composition_compute_stop_pos
> |   3.00 Gc    5.3%   153.86 Mc       window_loop
> |   1.28 Gc    2.3%   216.97 Mc       find_newline
> |   2.28 Gc    4.1%    80.59 Mc   Fmove_overlay
> |   1.46 Gc    2.6%    40.18 Mc   lookup_char_property

I don't think we want to try and optimize the operations here because
that will only push the limit of what is "too large" a bit further.

More promising to me would be to try and skip any part of the buffer
that's not displayed.


        Stefan

bug#72830: Big rectangular selections are slow

[Mattias Engdegård]

27 aug. 2024 kl. 15.48 skrev Eli Zaretskii <eliz@gnu.org>:

> Does turning off auto-composition-mode help in any way?

I don't think so. Were you able to reproduce the problem?

> Also, since highlighting is AFAIR implemented as overlays, it slows
> down check_display_width, which I think would otherwise have moved
> very fast if you say there are no properties and no overlays.

Yes, overlays indeed seem to be at the heart of the problem.


27 aug. 2024 kl. 16.04 skrev Stefan Monnier <monnier@iro.umontreal.ca>:

>> - Slow `region-beginning` and `region-end`.
>>  Fixed on master (3a8222e7).
> 
> Seems unlikely.

It did show up on the profile, something had to be done. Before that change, (region-beginning) with the active region as in the example took 0.96 s on this machine. Now, maybe 30 µs.

>> - `select-active-regions` makes each selection change very expensive.
>>  Can be set to nil by the user, but I really suggest that we change the
>> default to nil, at least for non-X11 since the default assumes old-school
>> X11 PRIMARY selection which is alien on most other platforms.
> 
> Didn't think of that.  Do we re-set the PRIMARY every time the (active)
> rectangular region is changed (i.e. after each key press)?  That would
> make it non-scalable to large rectangular regions, indeed.

It's pretty bonkers, yes. There is even a noticeable slow-down with a single contiguous selection.
Fortunately the cure is easy.

> I thought the extraction of the region's content to put it into PRIMARY
> and friends happened more lazily (e.g. when another application
> requests the PRIMARY/CLIPBOARD, or when we deactivate the region).

That would indeed have made some kind of sense. If confined to X11, that is. And opt-in, even then.

> I don't think we want to try and optimize the operations here because
> that will only push the limit of what is "too large" a bit further.

Yes, but it is educational to see what the costs are

> More promising to me would be to try and skip any part of the buffer
> that's not displayed.

Yes, I see no reason for having the highlight overlay on something that can't be seen. 

But how do we know what the viewport will be in `rectangle--highlight-for-redisplay`? Since it is redisplay that determines window-start and window-end, and it hasn't run yet, this puts us in some kind of chicken-egg situation. Maybe it has to be done inside redisplay.

bug#72830: Big rectangular selections are slow

[Eli Zaretskii]

> From: Mattias Engdegård <mattias.engdegard@gmail.com>
> Date: Tue, 27 Aug 2024 18:42:19 +0200
> Cc: Emacs Bug Report <bug-gnu-emacs@gnu.org>,
>  Juri Linkov <juri@linkov.net>
> 
> 27 aug. 2024 kl. 15.48 skrev Eli Zaretskii <eliz@gnu.org>:
> 
> > Does turning off auto-composition-mode help in any way?
> 
> I don't think so. Were you able to reproduce the problem?

I didn't have time to try, sorry.  Too much stuff on my plate, and
still only 24 hours a day, even with Emacs 30...

> Yes, I see no reason for having the highlight overlay on something that can't be seen. 
> 
> But how do we know what the viewport will be in `rectangle--highlight-for-redisplay`? Since it is redisplay that determines window-start and window-end, and it hasn't run yet, this puts us in some kind of chicken-egg situation. Maybe it has to be done inside redisplay.

It has to be done with the display code, but does not have to be as
part of redisplay.  We can use functions like vertical-motion,
window-text-pixel-size, posn-at-point, and other similar APIs, which
all employ display code that performs layout-related calculations
without actually displaying anything.

bug#72830: Big rectangular selections are slow

[Eli Zaretskii]

> Cc: 72830@debbugs.gnu.org, monnier@iro.umontreal.ca, juri@linkov.net
> Date: Tue, 27 Aug 2024 20:47:18 +0300
> From: Eli Zaretskii <eliz@gnu.org>
> 
> > But how do we know what the viewport will be in `rectangle--highlight-for-redisplay`? Since it is redisplay that determines window-start and window-end, and it hasn't run yet, this puts us in some kind of chicken-egg situation. Maybe it has to be done inside redisplay.
> 
> It has to be done with the display code, but does not have to be as
> part of redisplay.  We can use functions like vertical-motion,
> window-text-pixel-size, posn-at-point, and other similar APIs, which
> all employ display code that performs layout-related calculations
> without actually displaying anything.

Btw, the horizontal dimensions of the window are known in advance even
without calling the display code, and we could use posn-at-x-y to find
the buffer position that corresponds to the right edge of the window.
Isn't that what's needed to avoid highlighting the portions of text
that are outside of the viewport?

bug#72830: Big rectangular selections are slow

[Juri Linkov]

>> 27 aug. 2024 kl. 15.48 skrev Eli Zaretskii <eliz@gnu.org>:
>>
>> > Does turning off auto-composition-mode help in any way?
>>
>> I don't think so. Were you able to reproduce the problem?
>
> I didn't have time to try, sorry.  Too much stuff on my plate, and
> still only 24 hours a day, even with Emacs 30...

For Emacs 30 it's time to increase the default value of hours-per-day to 30.

>> 27 aug. 2024 kl. 16.04 skrev Stefan Monnier <monnier@iro.umontreal.ca>:
>>
>> More promising to me would be to try and skip any part of the buffer
>> that's not displayed.
>
> Yes, I see no reason for having the highlight overlay on something that can't be seen.
>
> But how do we know what the viewport will be in
> `rectangle--highlight-for-redisplay`? Since it is redisplay that determines
> window-start and window-end, and it hasn't run yet, this puts us in some
> kind of chicken-egg situation. Maybe it has to be done inside redisplay.

I'm sure it should be possible to use `pre-redisplay-functions'
that by default updates region highlighting, and I was able to use it
to make region highlighting window-local even when the same buffer
is displayed in separate windows.

bug#72830: Big rectangular selections are slow

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

> For Emacs 30 it's time to increase the default value of hours-per-day to 30.

+1.

bug#72830: Big rectangular selections are slow

[Eli Zaretskii]

> From: Juri Linkov <juri@linkov.net>
> Cc: Stefan Monnier <monnier@iro.umontreal.ca>,  Eli Zaretskii
>  <eliz@gnu.org>,  72830@debbugs.gnu.org
> Date: Tue, 27 Aug 2024 21:23:05 +0300
> 
> >> 27 aug. 2024 kl. 15.48 skrev Eli Zaretskii <eliz@gnu.org>:
> >>
> > I didn't have time to try, sorry.  Too much stuff on my plate, and
> > still only 24 hours a day, even with Emacs 30...
> 
> For Emacs 30 it's time to increase the default value of hours-per-day to 30.

That'd be backward-incompatible, so we'd need a user option to get
back the old behavior.  And it's too late for new features in Emacs 30
anyway.

bug#72830: Big rectangular selections are slow

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

>>> - `select-active-regions` makes each selection change very expensive.
>>>  Can be set to nil by the user, but I really suggest that we change the
>>> default to nil, at least for non-X11 since the default assumes old-school
>>> X11 PRIMARY selection which is alien on most other platforms.
>> 
>> Didn't think of that.  Do we re-set the PRIMARY every time the (active)
>> rectangular region is changed (i.e. after each key press)?  That would
>> make it non-scalable to large rectangular regions, indeed.
>
> It's pretty bonkers, yes. There is even a noticeable slow-down with
> a single contiguous selection.  Fortunately the cure is easy.

I rely on it on a regular basis, and I'm probably not the only one, so
even if we disable it by default, we should make it work well enough for
large rectangular regions.

> But how do we know what the viewport will be in
> `rectangle--highlight-for-redisplay`? Since it is redisplay that determines
> window-start and window-end, and it hasn't run yet, this puts us in some
> kind of chicken-egg situation. Maybe it has to be done inside redisplay.

The code should use `window-start` and `window-end` for that.

There might be some remaining issues with (re)running the
`pre-redisplay-function(s)` when redisplay forces a change in
`window-start` (or in the unlikely case where the highlighting moves the
`window-end` further), but these are things we need to fix anyway.

There are further issues when several windows display the buffer.  🙂

We could also move some of the work to jit-lock, which would have the
advantage that it would additionally be able to skip over (large) chunks
that are marked as `invisible`.


        Stefan

bug#72830: Big rectangular selections are slow

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

Stefan Monnier via "Bug reports for GNU Emacs, the Swiss army knife of
text editors" <bug-gnu-emacs@gnu.org> writes:

> There are further issues when several windows display the buffer.  🙂

Is it that bad?  Currently the overlays used for rectangle visualizing
specify a window overlay property.  Only one window gets updated now.


My idea would be: highlight from or up to "rectangle point" maximally
(window-height) lines.  Then the visual appearance is the same as now
(right?), and when the user moves point or selects a different window,
AFAIU the rectangle needs to be redrawn anyway.


Michael.

bug#72830: Big rectangular selections are slow

[Mattias Engdegård]

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

29 aug. 2024 kl. 05.56 skrev Michael Heerdegen <michael_heerdegen@web.de>:

> My idea would be: highlight from or up to "rectangle point" maximally
> (window-height) lines.

Here I was digging into the redisplay code in the hope of finding an obscure hook to subvert, and you turn up and give us the obvious, simple and correct solution right away. Thank you, Michael!

The patch below is crude but seems to work. Please give it a try.
If the original recipe is still stuttering, try setting `select-active-regions` to nil.


[-- Attachment #2: rect-highlight.diff --]
[-- Type: application/octet-stream, Size: 10422 bytes --]

diff --git a/lisp/rect.el b/lisp/rect.el
index 93007824679..1fadb4c768a 100644
--- a/lisp/rect.el
+++ b/lisp/rect.el
@@ -869,81 +869,107 @@ rectangle--highlight-for-redisplay
         (cl-assert (eq (window-buffer window) (current-buffer)))
         ;; `rectangle--pos-cols' looks up the `selected-window's parameter!
         (with-selected-window window
-          (apply-on-rectangle
-           (lambda (leftcol rightcol)
-             (let* ((mleft (move-to-column leftcol))
-                    (left (point))
-                    ;; BEWARE: In the presence of other overlays with
-                    ;; before/after/display-strings, this happens to move to
-                    ;; the column "as if the overlays were not applied", which
-                    ;; is sometimes what we want, tho it can be
-                    ;; considered a bug in move-to-column (it should arguably
-                    ;; pay attention to the before/after-string/display
-                    ;; properties when computing the column).
-                    (mright (move-to-column rightcol))
-                    (right (point))
-                    (ol
-                     (if (not old)
-                         (let ((ol (make-overlay left right)))
-                           (overlay-put ol 'window window)
-                           (overlay-put ol 'face 'region)
-                           ol)
-                       (let ((ol (pop old)))
-                         (move-overlay ol left right (current-buffer))
-                         ol))))
-               ;; `move-to-column' may stop before the column (if bumping into
-               ;; EOL) or overshoot it a little, when column is in the middle
-               ;; of a char.
-               (cond
-                ((< mleft leftcol)      ;`leftcol' is past EOL.
-                 (overlay-put ol 'before-string (rectangle--space-to leftcol))
-                 (setq mright (max mright leftcol)))
-                ((and (> mleft leftcol) ;`leftcol' is in the middle of a char.
-                      (eq (char-before left) ?\t))
-                 (setq left (1- left))
-                 (move-overlay ol left right)
-                 (goto-char left)
-                 (overlay-put ol 'before-string (rectangle--space-to leftcol)))
-                ((overlay-get ol 'before-string)
-                 (overlay-put ol 'before-string nil)))
-               (cond
-                ;; While doing rectangle--string-preview, the two sets of
-                ;; overlays steps on the other's toes.  I fixed some of the
-                ;; problems, but others remain.  The main one is the two
-                ;; (rectangle--space-to rightcol) below which try to virtually
-                ;; insert missing text, but during "preview", the text is not
-                ;; missing (it's provided by preview's own overlay).
-                (rectangle--string-preview-state
-                 (if (overlay-get ol 'after-string)
-                     (overlay-put ol 'after-string nil)))
-                ((< mright rightcol)    ;`rightcol' is past EOL.
-                 (let ((str (rectangle--space-to rightcol)))
-                   (put-text-property 0 (length str) 'face 'region str)
-                   ;; If cursor happens to be here, draw it at the right place.
-                   (rectangle--place-cursor leftcol left str)
-                   (overlay-put ol 'after-string str)))
-                ((and (> mright rightcol) ;`rightcol's in the middle of a char.
-                      (eq (char-before right) ?\t))
-                 (setq right (1- right))
-                 (move-overlay ol left right)
-                 (if (= rightcol leftcol)
-                     (overlay-put ol 'after-string nil)
-                   (goto-char right)
-                   (let ((str (rectangle--space-to rightcol)))
-                     (put-text-property 0 (length str) 'face 'region str)
-                     (when (= left right)
-                       (rectangle--place-cursor leftcol left str))
-                     (overlay-put ol 'after-string str))))
-                ((overlay-get ol 'after-string)
-                 (overlay-put ol 'after-string nil)))
-               (when (and (= leftcol rightcol) (display-graphic-p))
-                 ;; Make zero-width rectangles visible!
-                 (overlay-put ol 'after-string
-                              (concat (propertize " "
-                                                  'face '(region (:height 0.2)))
-                                      (overlay-get ol 'after-string))))
-               (push ol nrol)))
-           start end))
+          (let* ((pt (point))
+                 (cols (rectangle--pos-cols start end))
+                 (startcol (car cols))
+                 (endcol (cdr cols))
+                 (leftcol (min startcol endcol))
+                 (rightcol (max startcol endcol))
+                 ;; We don't know what lines will actually be displayed,
+                 ;; so add highlight overlays on lines within the window
+                 ;; height from point.
+                 (height (window-height))
+                 (start-pt (max (point-min) start
+                                (progn (forward-line (- height)) (point))))
+                 (end-pt (min (point-max) end
+                              (progn (goto-char pt)
+                                     (forward-line height)
+                                     (point)))))
+            (goto-char start-pt)
+            (beginning-of-line)
+            (while
+                (let* ((mleft (move-to-column leftcol))
+                       (left (point))
+                       ;; BEWARE: In the presence of other overlays with
+                       ;; before/after/display-strings, this happens to move to
+                       ;; the column "as if the overlays were not applied",
+                       ;; which is sometimes what we want, tho it can be
+                       ;; considered a bug in move-to-column (it should
+                       ;; arguably pay attention to the
+                       ;; before/after-string/display properties when computing
+                       ;; the column).
+                       (mright (move-to-column rightcol))
+                       (right (point))
+                       (ol
+                        (if (not old)
+                            (let ((ol (make-overlay left right)))
+                              (overlay-put ol 'window window)
+                              (overlay-put ol 'face 'region)
+                              ol)
+                          (let ((ol (pop old)))
+                            (move-overlay ol left right (current-buffer))
+                            ol))))
+                  ;; `move-to-column' may stop before the column (if bumping
+                  ;; into EOL) or overshoot it a little, when column is in the
+                  ;; middle of a char.
+                  (cond
+                   ((< mleft leftcol)      ;`leftcol' is past EOL.
+                    (overlay-put ol 'before-string
+                                 (rectangle--space-to leftcol))
+                    (setq mright (max mright leftcol)))
+                   ((and (> mleft leftcol) ;`leftcol' is in the middle of a char
+                         (eq (char-before left) ?\t))
+                    (setq left (1- left))
+                    (move-overlay ol left right)
+                    (goto-char left)
+                    (overlay-put ol 'before-string
+                                 (rectangle--space-to leftcol)))
+                   ((overlay-get ol 'before-string)
+                    (overlay-put ol 'before-string nil)))
+                  (cond
+                   ;; While doing rectangle--string-preview, the two sets of
+                   ;; overlays steps on the other's toes.  I fixed some of the
+                   ;; problems, but others remain.  The main one is the two
+                   ;; (rectangle--space-to rightcol) below which try to
+                   ;; virtually insert missing text, but during "preview", the
+                   ;; text is not missing (it's provided by preview's own
+                   ;; overlay).
+                   (rectangle--string-preview-state
+                    (if (overlay-get ol 'after-string)
+                        (overlay-put ol 'after-string nil)))
+                   ((< mright rightcol)    ;`rightcol' is past EOL.
+                    (let ((str (rectangle--space-to rightcol)))
+                      (put-text-property 0 (length str) 'face 'region str)
+                      ;; If cursor happens to be here, draw it at the right
+                      ;; place.
+                      (rectangle--place-cursor leftcol left str)
+                      (overlay-put ol 'after-string str)))
+                   ((and (> mright rightcol) ;`rightcol' in the middle of a char
+                         (eq (char-before right) ?\t))
+                    (setq right (1- right))
+                    (move-overlay ol left right)
+                    (if (= rightcol leftcol)
+                        (overlay-put ol 'after-string nil)
+                      (goto-char right)
+                      (let ((str (rectangle--space-to rightcol)))
+                        (put-text-property 0 (length str) 'face 'region str)
+                        (when (= left right)
+                          (rectangle--place-cursor leftcol left str))
+                        (overlay-put ol 'after-string str))))
+                   ((overlay-get ol 'after-string)
+                    (overlay-put ol 'after-string nil)))
+                  (when (and (= leftcol rightcol) (display-graphic-p))
+                    ;; Make zero-width rectangles visible!
+                    (overlay-put ol 'after-string
+                                 (concat (propertize
+                                          " " 'face '(region (:height 0.2)))
+                                         (overlay-get ol 'after-string))))
+                  (push ol nrol)
+                  (and (zerop (forward-line 1))
+                       (bolp)
+                       (<= (point) end-pt))))
+            )
+          )
         (mapc #'delete-overlay old)
         `(rectangle ,(buffer-chars-modified-tick)
                     ,start ,end ,(rectangle--crutches)

bug#72830: Big rectangular selections are slow

[Mattias Engdegård]

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

29 aug. 2024 kl. 12.22 skrev Mattias Engdegård <mattias.engdegard@gmail.com>:

> The patch below is crude but seems to work.

That phrase is highly effective for forcing bugs into daylight. Here is an improved version.

Previously, `exchange-point-and-mark` didn't regenerate the overlays because it wasn't necessary, but now it is, so we save point in our rectangle overlay tuple. (Should use a struct at this point.)


[-- Attachment #2: rect-highlight.diff --]
[-- Type: application/octet-stream, Size: 11525 bytes --]

diff --git a/lisp/rect.el b/lisp/rect.el
index 93007824679..5d68a6bafab 100644
--- a/lisp/rect.el
+++ b/lisp/rect.el
@@ -857,102 +857,131 @@ rectangle--highlight-for-redisplay
          (eq (nth 1 rol) (buffer-chars-modified-tick))
          (eq start (nth 2 rol))
          (eq end (nth 3 rol))
-         (equal (rectangle--crutches) (nth 4 rol)))
+         (equal (rectangle--crutches) (nth 4 rol))
+         (eq (nth 5 rol) (point)))
     rol)
    (t
     (save-excursion
-      (let* ((nrol nil)
+      (let* ((pt (point))
+             (nrol nil)
              (old (if (eq 'rectangle (car-safe rol))
-                      (nthcdr 5 rol)
+                      (nthcdr 6 rol)
                     (funcall redisplay-unhighlight-region-function rol)
                     nil)))
         (cl-assert (eq (window-buffer window) (current-buffer)))
         ;; `rectangle--pos-cols' looks up the `selected-window's parameter!
         (with-selected-window window
-          (apply-on-rectangle
-           (lambda (leftcol rightcol)
-             (let* ((mleft (move-to-column leftcol))
-                    (left (point))
-                    ;; BEWARE: In the presence of other overlays with
-                    ;; before/after/display-strings, this happens to move to
-                    ;; the column "as if the overlays were not applied", which
-                    ;; is sometimes what we want, tho it can be
-                    ;; considered a bug in move-to-column (it should arguably
-                    ;; pay attention to the before/after-string/display
-                    ;; properties when computing the column).
-                    (mright (move-to-column rightcol))
-                    (right (point))
-                    (ol
-                     (if (not old)
-                         (let ((ol (make-overlay left right)))
-                           (overlay-put ol 'window window)
-                           (overlay-put ol 'face 'region)
-                           ol)
-                       (let ((ol (pop old)))
-                         (move-overlay ol left right (current-buffer))
-                         ol))))
-               ;; `move-to-column' may stop before the column (if bumping into
-               ;; EOL) or overshoot it a little, when column is in the middle
-               ;; of a char.
-               (cond
-                ((< mleft leftcol)      ;`leftcol' is past EOL.
-                 (overlay-put ol 'before-string (rectangle--space-to leftcol))
-                 (setq mright (max mright leftcol)))
-                ((and (> mleft leftcol) ;`leftcol' is in the middle of a char.
-                      (eq (char-before left) ?\t))
-                 (setq left (1- left))
-                 (move-overlay ol left right)
-                 (goto-char left)
-                 (overlay-put ol 'before-string (rectangle--space-to leftcol)))
-                ((overlay-get ol 'before-string)
-                 (overlay-put ol 'before-string nil)))
-               (cond
-                ;; While doing rectangle--string-preview, the two sets of
-                ;; overlays steps on the other's toes.  I fixed some of the
-                ;; problems, but others remain.  The main one is the two
-                ;; (rectangle--space-to rightcol) below which try to virtually
-                ;; insert missing text, but during "preview", the text is not
-                ;; missing (it's provided by preview's own overlay).
-                (rectangle--string-preview-state
-                 (if (overlay-get ol 'after-string)
-                     (overlay-put ol 'after-string nil)))
-                ((< mright rightcol)    ;`rightcol' is past EOL.
-                 (let ((str (rectangle--space-to rightcol)))
-                   (put-text-property 0 (length str) 'face 'region str)
-                   ;; If cursor happens to be here, draw it at the right place.
-                   (rectangle--place-cursor leftcol left str)
-                   (overlay-put ol 'after-string str)))
-                ((and (> mright rightcol) ;`rightcol's in the middle of a char.
-                      (eq (char-before right) ?\t))
-                 (setq right (1- right))
-                 (move-overlay ol left right)
-                 (if (= rightcol leftcol)
-                     (overlay-put ol 'after-string nil)
-                   (goto-char right)
-                   (let ((str (rectangle--space-to rightcol)))
-                     (put-text-property 0 (length str) 'face 'region str)
-                     (when (= left right)
-                       (rectangle--place-cursor leftcol left str))
-                     (overlay-put ol 'after-string str))))
-                ((overlay-get ol 'after-string)
-                 (overlay-put ol 'after-string nil)))
-               (when (and (= leftcol rightcol) (display-graphic-p))
-                 ;; Make zero-width rectangles visible!
-                 (overlay-put ol 'after-string
-                              (concat (propertize " "
-                                                  'face '(region (:height 0.2)))
-                                      (overlay-get ol 'after-string))))
-               (push ol nrol)))
-           start end))
+          (let* ((cols (rectangle--pos-cols start end))
+                 (startcol (car cols))
+                 (endcol (cdr cols))
+                 (leftcol (min startcol endcol))
+                 (rightcol (max startcol endcol))
+                 ;; We don't know what lines will actually be displayed,
+                 ;; so add highlight overlays on lines within the window
+                 ;; height from point.
+                 (height (window-height))
+                 (start-pt (max start (progn (forward-line (- height))
+                                             (point))))
+                 (end-pt (min end (progn (goto-char pt)
+                                         (forward-line height)
+                                         (point)))))
+            ;; (printf
+            ;;  "pt %S (%S) height %S start %S end %S start-pt %S end-pt %S\n"
+            ;;  pt (point) height start end start-pt end-pt)
+            (goto-char start-pt)
+            (beginning-of-line)
+            (while
+                (let* ((mleft (move-to-column leftcol))
+                       (left (point))
+                       ;; BEWARE: In the presence of other overlays with
+                       ;; before/after/display-strings, this happens to move to
+                       ;; the column "as if the overlays were not applied",
+                       ;; which is sometimes what we want, tho it can be
+                       ;; considered a bug in move-to-column (it should
+                       ;; arguably pay attention to the
+                       ;; before/after-string/display properties when computing
+                       ;; the column).
+                       (mright (move-to-column rightcol))
+                       (right (point))
+                       (ol
+                        (if (not old)
+                            (let ((ol (make-overlay left right)))
+                              (overlay-put ol 'window window)
+                              (overlay-put ol 'face 'region)
+                              ol)
+                          (let ((ol (pop old)))
+                            (move-overlay ol left right (current-buffer))
+                            ol))))
+                  ;; `move-to-column' may stop before the column (if bumping
+                  ;; into EOL) or overshoot it a little, when column is in the
+                  ;; middle of a char.
+                  (cond
+                   ((< mleft leftcol)      ;`leftcol' is past EOL.
+                    (overlay-put ol 'before-string
+                                 (rectangle--space-to leftcol))
+                    (setq mright (max mright leftcol)))
+                   ((and (> mleft leftcol) ;`leftcol' is in the middle of a char
+                         (eq (char-before left) ?\t))
+                    (setq left (1- left))
+                    (move-overlay ol left right)
+                    (goto-char left)
+                    (overlay-put ol 'before-string
+                                 (rectangle--space-to leftcol)))
+                   ((overlay-get ol 'before-string)
+                    (overlay-put ol 'before-string nil)))
+                  (cond
+                   ;; While doing rectangle--string-preview, the two sets of
+                   ;; overlays steps on the other's toes.  I fixed some of the
+                   ;; problems, but others remain.  The main one is the two
+                   ;; (rectangle--space-to rightcol) below which try to
+                   ;; virtually insert missing text, but during "preview", the
+                   ;; text is not missing (it's provided by preview's own
+                   ;; overlay).
+                   (rectangle--string-preview-state
+                    (if (overlay-get ol 'after-string)
+                        (overlay-put ol 'after-string nil)))
+                   ((< mright rightcol)    ;`rightcol' is past EOL.
+                    (let ((str (rectangle--space-to rightcol)))
+                      (put-text-property 0 (length str) 'face 'region str)
+                      ;; If cursor happens to be here, draw it at the right
+                      ;; place.
+                      (rectangle--place-cursor leftcol left str)
+                      (overlay-put ol 'after-string str)))
+                   ((and (> mright rightcol) ;`rightcol' in the middle of a char
+                         (eq (char-before right) ?\t))
+                    (setq right (1- right))
+                    (move-overlay ol left right)
+                    (if (= rightcol leftcol)
+                        (overlay-put ol 'after-string nil)
+                      (goto-char right)
+                      (let ((str (rectangle--space-to rightcol)))
+                        (put-text-property 0 (length str) 'face 'region str)
+                        (when (= left right)
+                          (rectangle--place-cursor leftcol left str))
+                        (overlay-put ol 'after-string str))))
+                   ((overlay-get ol 'after-string)
+                    (overlay-put ol 'after-string nil)))
+                  (when (and (= leftcol rightcol) (display-graphic-p))
+                    ;; Make zero-width rectangles visible!
+                    (overlay-put ol 'after-string
+                                 (concat (propertize
+                                          " " 'face '(region (:height 0.2)))
+                                         (overlay-get ol 'after-string))))
+                  (push ol nrol)
+                  (and (zerop (forward-line 1))
+                       (bolp)
+                       (<= (point) end-pt))))
+            )
+          )
         (mapc #'delete-overlay old)
         `(rectangle ,(buffer-chars-modified-tick)
-                    ,start ,end ,(rectangle--crutches)
+                    ,start ,end ,(rectangle--crutches) ,pt
                     ,@nrol))))))
 
 (defun rectangle--unhighlight-for-redisplay (orig rol)
   (if (not (eq 'rectangle (car-safe rol)))
       (funcall orig rol)
-    (mapc #'delete-overlay (nthcdr 5 rol))
+    (mapc #'delete-overlay (nthcdr 6 rol))
     (setcar (cdr rol) nil)))
 
 (defun rectangle--duplicate-right (n displacement)

bug#72830: Big rectangular selections are slow

[Mattias Engdegård]

27 aug. 2024 kl. 21.16 skrev Eli Zaretskii <eliz@gnu.org>:

>> It has to be done with the display code, but does not have to be as
>> part of redisplay.  We can use functions like vertical-motion,
>> window-text-pixel-size, posn-at-point, and other similar APIs, which
>> all employ display code that performs layout-related calculations
>> without actually displaying anything.
> 
> Btw, the horizontal dimensions of the window are known in advance even
> without calling the display code, and we could use posn-at-x-y to find
> the buffer position that corresponds to the right edge of the window.
> Isn't that what's needed to avoid highlighting the portions of text
> that are outside of the viewport?

Unfortunately I don't think that helps. The way it works now is that a pre-redisplay function puts a highlight overlay on every line in the rectangular selection. All this work and memory completely tanks performance.

Only putting overlays on lines where they can be seen would solve the problem, but we have to know the first and last line that will be displayed. I tried using `posn-at-x-y` but it doesn't seem to recompute `window-start` so it has the same problem.

27 aug. 2024 kl. 21.44 skrev Stefan Monnier <monnier@iro.umontreal.ca>:

> I rely on it on a regular basis, and I'm probably not the only one, so
> even if we disable it by default, we should make it work well enough for
> large rectangular regions.

Yes, that's probably true. Let's deal with that concern later; it's orthogonal to the redisplay problem.

> There might be some remaining issues with (re)running the
> `pre-redisplay-function(s)` when redisplay forces a change in
> `window-start` (or in the unlikely case where the highlighting moves the
> `window-end` further), but these are things we need to fix anyway.

That's what I wondered how to deal with. I agree we can probably assume that highlighting won't affect the viewport in any substantial way.

To be clear, just using the (inaccurate) window-start and window-end to clip the setting of highlight overlays works very well and with excellent speed until the viewport moves, in which case it no longer does.

> There are further issues when several windows display the buffer.

Are there? The highlight overlay is set with a `window` parameter that keeps it visible in one window only.

> We could also move some of the work to jit-lock, which would have the
> advantage that it would additionally be able to skip over (large) chunks
> that are marked as `invisible`.

Not sure how this would work. Isn't it guided by (comparatively persistent) `fontified` properties?

bug#72830: Big rectangular selections are slow

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

>> There might be some remaining issues with (re)running the
>> `pre-redisplay-function(s)` when redisplay forces a change in
>> `window-start` (or in the unlikely case where the highlighting moves the
>> `window-end` further), but these are things we need to fix anyway.
> That's what I wondered how to deal with. I agree we can probably assume that
> highlighting won't affect the viewport in any substantial way.
> To be clear, just using the (inaccurate) window-start and window-end to clip
> the setting of highlight overlays works very well and with excellent speed
> until the viewport moves, in which case it no longer does.

"The viewport moves" is what I referred to as "when redisplay forces
a change in `window-start`" (there are actually many cases where the
viewport moves before redisplay is invoked, in which case "just using
the (inaccurate) window-start and window-end to clip the setting of
highlight overlays works very well").

We should investigate the case(s) where it doesn't work well and fix
them (not by changing your `pre-redisplay-function` but by re-running
that hook), because these cases likely affect other users of this hook
(such as the normal region highlighting).

>> There are further issues when several windows display the buffer.
> Are there? The highlight overlay is set with a `window` parameter that keeps
> it visible in one window only.

Ah, great, then.  I didn't remember this.

>> We could also move some of the work to jit-lock, which would have the
>> advantage that it would additionally be able to skip over (large) chunks
>> that are marked as `invisible`.
> Not sure how this would work. Isn't it guided by (comparatively
> persistent) `fontified` properties?

We'd set that property to nil.
[ See the recentish discussion about how to change jit-lock so that it
  can be told to flush only some of its backends.  ]


        Stefan

bug#72830: Big rectangular selections are slow

[Mattias Engdegård]

29 aug. 2024 kl. 22.04 skrev Stefan Monnier <monnier@iro.umontreal.ca>

> We should investigate the case(s) where it doesn't work well and fix
> them (not by changing your `pre-redisplay-function` but by re-running
> that hook), because these cases likely affect other users of this hook
> (such as the normal region highlighting).

What would the problem be for normal (contiguous) region highlighting? There is a single overlay, so there should be no particular cost for large selections. Is there?

The latest patch posted seems to work well enough and all but eliminates the problem (when `select-active-regions` is nil, anyway), so that it outweighs some rare cosmetic issues.

(Those cosmetic issues may occur when a rectangular selection straddles invisible text, because this invalidates the assumption that the other end of the selection is at most (window-height) away. But the selection still operate on the invisible test, so I don't think it's a problem in practice.)

I think the patch is good enough for master. If you have an even better solution, perhaps it could be made as a subsequent improvement?

bug#72830: Big rectangular selections are slow

[Mattias Engdegård]

30 aug. 2024 kl. 17.20 skrev Mattias Engdegård <mattias.engdegard@gmail.com>:

> I think the patch is good enough for master.

And it has now been pushed. To recap, remaining concerns:

- `select-active-regions`: as mentioned, it slows down rectangle selection massively and is alien to non-X11 platforms so I'd suggest it be set to nil by default on macOS and Windows at least. Not sure what to do on TTY frames.
For that matter, on X11 it seems strange to copy the entire selection each time it is made or modified even slightly; PRIMARY selection data isn't sent to the server until actually requested.

- Rectangle operations other than selection are still very slow. This isn't quite as big a problem but still annoying. Both `move-to-column` and `line-end-position` are unexpectedly expensive here. (And shouldn't rect.el use `pos-eol` instead? It's not much faster, though.)

- There are some mostly theoretical cases when the current rectangular selection code produces ugly results. I don't think they are likely to occur in practice but would be happy to work with someone who thinks he or she can do better.

bug#72830: Big rectangular selections are slow

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

Mattias Engdegård <mattias.engdegard@gmail.com> writes:

> It's pretty bonkers, yes. There is even a noticeable slow-down with a
> single contiguous selection.  Fortunately the cure is easy.
>
>> I thought the extraction of the region's content to put it into PRIMARY
>> and friends happened more lazily (e.g. when another application
>> requests the PRIMARY/CLIPBOARD, or when we deactivate the region).
>
> That would indeed have made some kind of sense. If confined to X11,
> that is. And opt-in, even then.

No well-written X program of the past 30 years does not export its
selected text as the primary selection, and users of free desktops are
long accustomed to its existence, with the result that Wayland desktops
implement primary selections by a number of protocols.  This is simply
not an option.

bug#72830: Big rectangular selections are slow

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

Po Lu via "Bug reports for GNU Emacs, the Swiss army knife of text
editors" <bug-gnu-emacs@gnu.org> writes:

> No well-written X program of the past 30 years does not export its
> selected text as the primary selection, and users of free desktops are
> long accustomed to its existence, with the result that Wayland desktops
> implement primary selections by a number of protocols.  This is simply
> not an option.

One data point from me: When I foll the recipe and then insert the
current primary selection into a different Emacs instance, I get a
column of 2500 "x"s inserted.  The recipe had 200,000 lines of "x"s.
That means, at least using my settings, what Emacs does in this extreme
case seems to be a waste of time because 99% of the selection is thrown
away by X or whatever.


Michael.

bug#72830: Big rectangular selections are slow

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

Michael Heerdegen <michael_heerdegen@web.de> writes:

> One data point from me: When I foll the recipe and then insert the
> current primary selection into a different Emacs instance, I get a
> column of 2500 "x"s inserted.  The recipe had 200,000 lines of "x"s.
> That means, at least using my settings, what Emacs does in this extreme
> case seems to be a waste of time because 99% of the selection is thrown
> away by X or whatever.

This must be isolated to rectangular selections.

bug#72830: Big rectangular selections are slow

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

Mattias Engdegård <mattias.engdegard@gmail.com> writes:

> - `select-active-regions` makes each selection change very expensive.
>   Can be set to nil by the user, but I really suggest that we change
>   the default to nil, at least for non-X11 since the default assumes
>   old-school X11 PRIMARY selection which is alien on most other
>   platforms.

No!!!  Primary selections are an integral part of X, and users (many
trained on X) have come to expect it of Emacs on other systems.

Emacs supports saving a region in a buffer as a selection rather than an
entire string, which could be exercised in the case of rectangular
selections.