bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Ihor Radchenko]

Try the following:

1. emacs -Q
2. M-x org-mode <RET>
3. M-x org-table-create <RET> 30x30 <RET>
4. M-: (setq show-trailing-whitespace t) <RET>
4. M-x org-table-insert-column <RET> (20x times)
5. M-> type something
6. Observe significant lag when typing. CPU profiler does not expose much.

In GNU Emacs 30.0.50 (build 1, x86_64-pc-linux-gnu, cairo version
 1.17.8) of 2023-04-05 built on localhost
Repository revision: fa669c4b17c04eff852eb23a6179ccb8fab864db
Repository branch: master
Windowing system distributor 'The X.Org Foundation', version 11.0.12101008
System Description: Gentoo Linux

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Date: Tue, 11 Apr 2023 18:52:43 +0000
> 
> 1. emacs -Q
> 2. M-x org-mode <RET>
> 3. M-x org-table-create <RET> 30x30 <RET>
> 4. M-: (setq show-trailing-whitespace t) <RET>
> 4. M-x org-table-insert-column <RET> (20x times)
> 5. M-> type something
> 6. Observe significant lag when typing. CPU profiler does not expose much.

show-trailing-whitespace disables quite a few redisplay optimizations,
including even the cursor-motion optimization (when nothing has
changed on display except the position of point).  And full thorough
redisplay becomes slow when you have relatively long lines, because
Emacs is forced to consider all of them.

In addition, org-table seems to put a large number of 'display'
properties (like, 2 per cell?), which also slows down redisplay.

Are you saying there's been a regression in Emacs 30 in this situation
wrt Emacs 29 and Emacs 28?  I don't think I see a regression in my
testing here.

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

> show-trailing-whitespace disables quite a few redisplay optimizations,
> including even the cursor-motion optimization (when nothing has
> changed on display except the position of point).  And full thorough
> redisplay becomes slow when you have relatively long lines, because
> Emacs is forced to consider all of them.

Well. But it is not even that big of a file. And the lines are shorter
than window width.

I could understand Emacs lagging on some really large file or long
lines, but this does not look large at all!

> In addition, org-table seems to put a large number of 'display'
> properties (like, 2 per cell?), which also slows down redisplay.

These properties are for the purpose of bidirectional ordering:

(defconst org-table--separator-space-pre
  (propertize " " 'display '(space :relative-width 1))
  "Space used in front of fields when aligning the table.
This space serves as a segment separator for the purposes of the
bidirectional reordering.
Note that `org-table--separator-space-pre' is not `eq' to
`org-table--separator-space-post'.  This is done to prevent Emacs from
visually merging spaces in an empty table cell.  See bug#45915.")

Maybe there is a better way?

> Are you saying there's been a regression in Emacs 30 in this situation
> wrt Emacs 29 and Emacs 28?  I don't think I see a regression in my
> testing here.

No, I do not mean a regression. But the slowdown appears to be
unreasonable for such a small test case. What is the point having
`show-trailing-whitespace' if it is this much inefficient? Maybe a
simple font-lock rule can be better?

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: 62780@debbugs.gnu.org
> Date: Tue, 11 Apr 2023 19:41:01 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > show-trailing-whitespace disables quite a few redisplay optimizations,
> > including even the cursor-motion optimization (when nothing has
> > changed on display except the position of point).  And full thorough
> > redisplay becomes slow when you have relatively long lines, because
> > Emacs is forced to consider all of them.
> 
> Well. But it is not even that big of a file.

The size of the file doesn't matter, only what's shown in the window
matters.

> And the lines are shorter than window width.

Not here, they aren't: a 50x30 table takes more than twice the default
window width of "emacs -Q".  However, I don't think this aspect is
important, either.

> > In addition, org-table seems to put a large number of 'display'
> > properties (like, 2 per cell?), which also slows down redisplay.
> 
> These properties are for the purpose of bidirectional ordering:
> 
> (defconst org-table--separator-space-pre
>   (propertize " " 'display '(space :relative-width 1))
>   "Space used in front of fields when aligning the table.
> This space serves as a segment separator for the purposes of the
> bidirectional reordering.
> Note that `org-table--separator-space-pre' is not `eq' to
> `org-table--separator-space-post'.  This is done to prevent Emacs from
> visually merging spaces in an empty table cell.  See bug#45915.")

I understand.  But it's definitely what causes most of the slowdown;
show-trailing-whitespace just adds the last straw.  With the patch
below I can see no slowdown at all with your recipe.

> Maybe there is a better way?

Maybe.  Can you point me to the discussion which caused you to use
these display properties there?  I think this was done in two steps:
first you added the same display property as pre and post, then made
them subtly different; I need to re-read the discussions that led to
both of these.

Alternatively, if you can describe the use cases where these
properties are needed, that could be enough for me to try to look for
alternative solutions.

> > Are you saying there's been a regression in Emacs 30 in this situation
> > wrt Emacs 29 and Emacs 28?  I don't think I see a regression in my
> > testing here.
> 
> No, I do not mean a regression. But the slowdown appears to be
> unreasonable for such a small test case. What is the point having
> `show-trailing-whitespace' if it is this much inefficient? Maybe a
> simple font-lock rule can be better?

See above: show-trailing-whitespace is not the main culprit here;
these particular display properties are.  If you could produce a perf
profile with this recipe, it might give ideas for speeding up the C
code without any changes on the Lisp level.

Btw, these properties were introduced into org-table.el some time ago,
so how come this issue comes up only now?  Aren't Org tables used
quite a lot?

diff --git a/lisp/org/org-table.el b/lisp/org/org-table.el
index 5116b11..658b5aa 100644
--- a/lisp/org/org-table.el
+++ b/lisp/org/org-table.el
@@ -4354,11 +4354,12 @@ org-table--align-field
 		   ("r" (make-string spaces ?\s))
 		   ("c" (make-string (/ spaces 2) ?\s))))
 	 (suffix (make-string (- spaces (length prefix)) ?\s)))
-    (concat org-table--separator-space-pre
+    (concat " " ;org-table--separator-space-pre
 	    prefix
 	    field
 	    suffix
-	    org-table--separator-space-post)))
+	    " " ;org-table--separator-space-post
+            )))
 
 (defun org-table-align ()
   "Align the table at point by aligning all vertical bars."

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> Maybe there is a better way?
>
> Maybe.  Can you point me to the discussion which caused you to use
> these display properties there?  I think this was done in two steps:
> first you added the same display property as pre and post, then made
> them subtly different; I need to re-read the discussions that led to
> both of these.

The first step was in
https://lists.gnu.org/archive/html/emacs-orgmode/2017-12/msg00526.html

Then, we had an issue with empty cells |<spc><spc>| with Emacs joining
two spaces with eq text properties.
https://debbugs.gnu.org/cgi/bugreport.cgi?bug=45915

>> No, I do not mean a regression. But the slowdown appears to be
>> unreasonable for such a small test case. What is the point having
>> `show-trailing-whitespace' if it is this much inefficient? Maybe a
>> simple font-lock rule can be better?
>
> See above: show-trailing-whitespace is not the main culprit here;
> these particular display properties are.  If you could produce a perf
> profile with this recipe, it might give ideas for speeding up the C
> code without any changes on the Lisp level.

Ok. I will look into it. If we can speed this up, it will hopefully
benefit more than just this particular scenario.

> Btw, these properties were introduced into org-table.el some time ago,
> so how come this issue comes up only now?  Aren't Org tables used
> quite a lot?

I guess things are not that much obvious without show-trailing-whitespace.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: 62780@debbugs.gnu.org
> Date: Wed, 12 Apr 2023 07:39:37 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> Maybe there is a better way?
> >
> > Maybe.  Can you point me to the discussion which caused you to use
> > these display properties there?  I think this was done in two steps:
> > first you added the same display property as pre and post, then made
> > them subtly different; I need to re-read the discussions that led to
> > both of these.
> 
> The first step was in
> https://lists.gnu.org/archive/html/emacs-orgmode/2017-12/msg00526.html
> 
> Then, we had an issue with empty cells |<spc><spc>| with Emacs joining
> two spaces with eq text properties.
> https://debbugs.gnu.org/cgi/bugreport.cgi?bug=45915

Thanks, will look into those.

> > Btw, these properties were introduced into org-table.el some time ago,
> > so how come this issue comes up only now?  Aren't Org tables used
> > quite a lot?
> 
> I guess things are not that much obvious without show-trailing-whitespace.

I see a substantial slowdown even with show-trailing-whitespace turned
off.

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

> See above: show-trailing-whitespace is not the main culprit here;
> these particular display properties are.  If you could produce a perf
> profile with this recipe, it might give ideas for speeding up the C
> code without any changes on the Lisp level.

Here are perf results when typing, using the same recipe.

Full summary:

    29.89%  emacs         emacs                       [.] lookup_char_property
    16.58%  emacs         emacs                       [.] next_interval
    13.99%  emacs         emacs                       [.] Fassq
     5.44%  emacs         emacs                       [.] find_interval
     5.17%  emacs         emacs                       [.] Fcdr
     3.97%  emacs         emacs                       [.] Fnext_single_property_change
     2.32%  emacs         emacs                       [.] composition_compute_stop_pos
     1.51%  emacs         emacs                       [.] validate_interval_range
     1.03%  emacs         emacs                       [.] get_char_property_and_overlay
     0.99%  emacs         emacs                       [.] textget
     0.79%  emacs         emacs                       [.] plist_get
     0.77%  emacs         emacs                       [.] produce_stretch_glyph
     0.76%  emacs         emacs                       [.] balance_an_interval
     0.54%  emacs         emacs                       [.] lface_hash

Call graph:

(next_interval is spread thin across the call graph, used all over the place)

99.10%--command_loop_1
 97.65%--read_key_sequence
  97.55%--read_char
   97.51%--redisplay redisplay_internal
    97.49%--redisplay_windows internal_condition_case_1 redisplay_window_0
     97.49%--redisplay_window
      |65.03%--try_window
      ||32.55%--display_line
      || 28.90%--get_next_display_element
      ||  28.83%--next_element_from_buffer
      ||   28.75%--handle_stop
      ||    23.87%--compute_stop_pos
      ||     23.52%--composition_compute_stop_pos
      ||      21.61%--find_composition
      ||       21.31%--Fnext_single_property_change
      ||        17.84%--textget
      ||         16.84%--lookup_char_property
      ||	  6.15%--builtin_lisp_symbol
      ||	   5.28%--make_lisp_symbol
      ||	  5.94%--Fassq
      || 32.47%--partial_line_height move_it_to
      |   31.11%--move_it_in_display_line_to
      |    28.95%--get_next_display_element
      |    28.86%--next_element_from_buffer
      |     28.80%--handle_stop
      |      ... 16.75%--lookup_char_property
      |32.42%--set_vertical_scroll_bar
        32.41%--move_it_to
	 31.05%--move_it_in_display_line_to
	  28.86%--get_next_display_element
	   ... 16.54%--lookup_char_property


-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: 62780@debbugs.gnu.org
> Date: Thu, 13 Apr 2023 09:46:31 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > See above: show-trailing-whitespace is not the main culprit here;
> > these particular display properties are.  If you could produce a perf
> > profile with this recipe, it might give ideas for speeding up the C
> > code without any changes on the Lisp level.
> 
> Here are perf results when typing, using the same recipe.
> 
> Full summary:
> 
>     29.89%  emacs         emacs                       [.] lookup_char_property
>     16.58%  emacs         emacs                       [.] next_interval
>     13.99%  emacs         emacs                       [.] Fassq
>      5.44%  emacs         emacs                       [.] find_interval
>      5.17%  emacs         emacs                       [.] Fcdr
>      3.97%  emacs         emacs                       [.] Fnext_single_property_change
>      2.32%  emacs         emacs                       [.] composition_compute_stop_pos
>      1.51%  emacs         emacs                       [.] validate_interval_range
>      1.03%  emacs         emacs                       [.] get_char_property_and_overlay
>      0.99%  emacs         emacs                       [.] textget
>      0.79%  emacs         emacs                       [.] plist_get
>      0.77%  emacs         emacs                       [.] produce_stretch_glyph
>      0.76%  emacs         emacs                       [.] balance_an_interval
>      0.54%  emacs         emacs                       [.] lface_hash
> 
> Call graph:
> 
> (next_interval is spread thin across the call graph, used all over the place)
> 
> 99.10%--command_loop_1
>  97.65%--read_key_sequence
>   97.55%--read_char
>    97.51%--redisplay redisplay_internal
>     97.49%--redisplay_windows internal_condition_case_1 redisplay_window_0
>      97.49%--redisplay_window
>       |65.03%--try_window
>       ||32.55%--display_line
>       || 28.90%--get_next_display_element
>       ||  28.83%--next_element_from_buffer
>       ||   28.75%--handle_stop
>       ||    23.87%--compute_stop_pos
>       ||     23.52%--composition_compute_stop_pos
>       ||      21.61%--find_composition
>       ||       21.31%--Fnext_single_property_change
>       ||        17.84%--textget
>       ||         16.84%--lookup_char_property
>       ||	  6.15%--builtin_lisp_symbol
>       ||	   5.28%--make_lisp_symbol
>       ||	  5.94%--Fassq
>       || 32.47%--partial_line_height move_it_to
>       |   31.11%--move_it_in_display_line_to
>       |    28.95%--get_next_display_element
>       |    28.86%--next_element_from_buffer
>       |     28.80%--handle_stop
>       |      ... 16.75%--lookup_char_property
>       |32.42%--set_vertical_scroll_bar
>         32.41%--move_it_to
> 	 31.05%--move_it_in_display_line_to
> 	  28.86%--get_next_display_element
> 	   ... 16.54%--lookup_char_property

This unfortunately says that looking up text properties is what takes
a large fraction of the time, which is consistent with the fact that
there are a lot of text properties in the buffer, and they happen
almost every character.

So maybe the immediate band-aid would be to offer a user option, by
default off, which will control whether these 'display' properties are
used: only users who actually need to type bidirectional text inside
the table will need to turn on the option.

Another possibility is to use "Method 1" I described in

  https://lists.gnu.org/archive/html/emacs-orgmode/2017-12/msg00526.html

I know I said afterwards that Method 2 was better (and it is), but I
obviously didn't consider the effect on performance, and neither had a
test case for that back then.  So maybe Method 1, while theoretically
less desirable, will in practice do the job and avoid the performance
issues, assuming that the invisibility aspect can be ignored
(i.e. users won't mind having 1-pixel thin spaces in the cells).

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> 	  28.86%--get_next_display_element
>> 	   ... 16.54%--lookup_char_property
>
> This unfortunately says that looking up text properties is what takes
> a large fraction of the time, which is consistent with the fact that
> there are a lot of text properties in the buffer, and they happen
> almost every character.

This looks up a very specific text property - 'composition. The property
that does not even exist in the buffer. The lookup takes so long because
buffer interval tree is very fragmented - each table cell adds at least 4
intervals.

May Emacs hold a property cache and make textget search EQ property
lists just once? 

Or, may it make sense to maintain additional interval trees for some
important text properties like 'invisible/'composition/'display? These
trees will only track text regions containing these important text
properties? Then, `next-single-property-change' can be much, much faster
compared to the current scan across all the buffer intervals.

> So maybe the immediate band-aid would be to offer a user option, by
> default off, which will control whether these 'display' properties are
> used: only users who actually need to type bidirectional text inside
> the table will need to turn on the option.

While it might fix the immediate issue for some set of users, it will
also limit our options to make use of 'display text property in tables.
In particular, it will be nice to auto-adjust the table column width
with pixel precision - one of the top-requested features for Org.

> Another possibility is to use "Method 1" I described in
>
>   https://lists.gnu.org/archive/html/emacs-orgmode/2017-12/msg00526.html
>
> I know I said afterwards that Method 2 was better (and it is), but I
> obviously didn't consider the effect on performance, and neither had a
> test case for that back then.  So maybe Method 1, while theoretically
> less desirable, will in practice do the job and avoid the performance
> issues, assuming that the invisibility aspect can be ignored
> (i.e. users won't mind having 1-pixel thin spaces in the cells).

I'd very much prefer to avoid Method 1. It will "litter" the Org files,
unless we also remove these symbols during save. And people will
definitely complain about kill containing "weird" staff. So, then also
substring filters. I am afraid that Method 1 will cause more trouble in
practice.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: 62780@debbugs.gnu.org
> Date: Thu, 13 Apr 2023 11:15:21 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> 	  28.86%--get_next_display_element
> >> 	   ... 16.54%--lookup_char_property
> >
> > This unfortunately says that looking up text properties is what takes
> > a large fraction of the time, which is consistent with the fact that
> > there are a lot of text properties in the buffer, and they happen
> > almost every character.
> 
> This looks up a very specific text property - 'composition.

Are you sure?  look up_char_property is also called for processing
'display' properties.  Here's the chain:

 handle_display_prop
  -> get_char_property_and_overlay
      -> Fget_text_property
          -> textget
	      -> lookup_char_property

> The property that does not even exist in the buffer. The lookup
> takes so long because buffer interval tree is very fragmented - each
> table cell adds at least 4 intervals.

> May Emacs hold a property cache and make textget search EQ property
> lists just once? 
> 
> Or, may it make sense to maintain additional interval trees for some
> important text properties like 'invisible/'composition/'display? These
> trees will only track text regions containing these important text
> properties? Then, `next-single-property-change' can be much, much faster
> compared to the current scan across all the buffer intervals.

These ideas came up before, but implementing them is not easy and
would add quite a bit of complexity.  We could, perhaps, keep a
buffer-local flag to record whether 'composition' property was ever
set on any buffer text, but once the flag is set, we won't easily know
if it could be reset.

Moreover, I just disabled static compositions completely, by making
find_composition return zero immediately, which basically avoids the
calls to next/previous-single-property-change which search for
'composition' property, and I still see quite a significant slowdown
with the recipe of this bug (50x30 org-table).  Can you reproduce
this?  If you can, what does the profile say now?

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> This looks up a very specific text property - 'composition.
>
> Are you sure?  look up_char_property is also called for processing
> 'display' properties.  Here's the chain:
>
>  handle_display_prop
>   -> get_char_property_and_overlay
>       -> Fget_text_property
>           -> textget
> 	      -> lookup_char_property

AFAIU, it does not show up in the call graph.
So, even if it is called, somehow, it should be fewer times. May
composition be queried excessively compared to 'display?

>> Or, may it make sense to maintain additional interval trees for some
>> important text properties like 'invisible/'composition/'display? These
>> trees will only track text regions containing these important text
>> properties? Then, `next-single-property-change' can be much, much faster
>> compared to the current scan across all the buffer intervals.
>
> These ideas came up before, but implementing them is not easy and
> would add quite a bit of complexity.

Is it a problem to keep multiple interval trees: one for all properties,
and several for individual properties? Then, all the code dealing with
intervals can be extended, repeating interval tree edits for the extra
trees. When the special properties are requested, we can then work with
special trees instead.

> We could, perhaps, keep a
> buffer-local flag to record whether 'composition' property was ever
> set on any buffer text, but once the flag is set, we won't easily know
> if it could be reset.

I do not feel like it will improve things in practice - complex buffers
with 'display/'composition properties are the ones that tend to be slow.
Simpler buffers with less text properties are already not problematic.

> Moreover, I just disabled static compositions completely, by making
> find_composition return zero immediately, which basically avoids the
> calls to next/previous-single-property-change which search for
> 'composition' property, and I still see quite a significant slowdown
> with the recipe of this bug (50x30 org-table).  Can you reproduce
> this?  If you can, what does the profile say now?

I cannot reproduce.
The typing has no noticeable delays.

I used ./configure && make with

@@ -421,6 +421,7 @@ find_composition (ptrdiff_t pos, ptrdiff_t limit,
 		  ptrdiff_t *start, ptrdiff_t *end,
 		  Lisp_Object *prop, Lisp_Object object)
 {
+  return 0;

Best,
Ihor

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: 62780@debbugs.gnu.org
> Date: Fri, 14 Apr 2023 09:20:01 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > Moreover, I just disabled static compositions completely, by making
> > find_composition return zero immediately, which basically avoids the
> > calls to next/previous-single-property-change which search for
> > 'composition' property, and I still see quite a significant slowdown
> > with the recipe of this bug (50x30 org-table).  Can you reproduce
> > this?  If you can, what does the profile say now?
> 
> I cannot reproduce.
> The typing has no noticeable delays.

Your build is optimized, yes?  Try building without optimizations, you
will see quite significant delays just by creating the table.

In any case, if you think disabling static composition can be a
reasonable option for Org Table users (do they use
prettify-symbols-mode, for example, in the same buffer where they have
Org tables?), that should be easy.

> Is it a problem to keep multiple interval trees: one for all properties,
> and several for individual properties?

Yes, I think so, because search for any non-nil properties will be
greatly complicated.  But if someone wants to work on such a split,
and can present working code, I won't reject it without testing.

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> I cannot reproduce.
>> The typing has no noticeable delays.
>
> Your build is optimized, yes?  Try building without optimizations, you
> will see quite significant delays just by creating the table.

Sure, but there is no obvious culprit then:

     4.01%  emacs         emacs                       [.] lookup_char_property
     3.04%  emacs         emacs                       [.] make_lisp_symbol
     3.01%  emacs         emacs                       [.] find_interval
     2.85%  emacs         emacs                       [.] next_interval
     2.37%  emacs         emacs                       [.] XSYMBOL
     2.27%  emacs         emacs                       [.] SYMBOLP
     2.16%  emacs         emacs                       [.] make_lisp_symbol
     2.06%  emacs         emacs                       [.] make_lisp_symbol

Various functions contribute almost equally with relatively larger (yet,
just 4%) contribution from lookup_char_property called from face_at_pos
(according to the call graph).

I looked into the number of calls to face_at_pos, find_composition, and
handle_display_prop. The number of calls is almost the same. Thus, my
guess is that find_composition is somehow slower than the other two
functions.

Looking int the code, I can see that handle_display_prop does not call
Fnext_single_property_change at all and face_at_pos limits the forward
lookup by TEXT_PROP_DISTANCE_LIMIT. In contrast, compute_stop_pos calls
composition_compute_stop_pos without making use of
TEXT_PROP_DISTANCE_LIMIT (AFAIU) and looks all the way to point-max. (Do
I understand correctly that it implies O(N_intervals^2)??)

> In any case, if you think disabling static composition can be a
> reasonable option for Org Table users (do they use
> prettify-symbols-mode, for example, in the same buffer where they have
> Org tables?), that should be easy.

I'd still prefer to find a better way and leave this workaround as the
last resort.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: 62780@debbugs.gnu.org
> Date: Fri, 14 Apr 2023 11:36:09 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> I cannot reproduce.
> >> The typing has no noticeable delays.
> >
> > Your build is optimized, yes?  Try building without optimizations, you
> > will see quite significant delays just by creating the table.
> 
> Sure, but there is no obvious culprit then:

The culprit is the humongous number of calls to handle_stop, I think.

> Looking int the code, I can see that handle_display_prop does not call
> Fnext_single_property_change at all and face_at_pos limits the forward
> lookup by TEXT_PROP_DISTANCE_LIMIT. In contrast, compute_stop_pos calls
> composition_compute_stop_pos without making use of
> TEXT_PROP_DISTANCE_LIMIT (AFAIU) and looks all the way to point-max. (Do
> I understand correctly that it implies O(N_intervals^2)??)
> 
> > In any case, if you think disabling static composition can be a
> > reasonable option for Org Table users (do they use
> > prettify-symbols-mode, for example, in the same buffer where they have
> > Org tables?), that should be easy.
> 
> I'd still prefer to find a better way and leave this workaround as the
> last resort.

OK, I have an idea: I think the fact that compute_stop_pos calls
find_composition (via composition_compute_stop_pos) is a mistake,
because the 'composition' text property is found by the previous code
in compute_stop_pos, exactly like we find 'display' and 'fontified'.
So compute_stop_pos has no reason to call find_composition.

But to test this idea, I need enough test cases that use the
'composition' property to make sure the property still works after I
disable that call.  Can you collect a few test cases which use the
'composition' property, with or without Org tables?  I guess
prettify-symbols-mode is one of them, but are there others?  I will
then try to find time to test this idea.

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Eli Zaretskii]

> Cc: 62780@debbugs.gnu.org
> Date: Fri, 14 Apr 2023 15:06:17 +0300
> From: Eli Zaretskii <eliz@gnu.org>
> 
> > From: Ihor Radchenko <yantar92@posteo.net>
> > Cc: 62780@debbugs.gnu.org
> > Date: Fri, 14 Apr 2023 11:36:09 +0000
> > 
> > Looking int the code, I can see that handle_display_prop does not call
> > Fnext_single_property_change at all and face_at_pos limits the forward
> > lookup by TEXT_PROP_DISTANCE_LIMIT. In contrast, compute_stop_pos calls
> > composition_compute_stop_pos without making use of
> > TEXT_PROP_DISTANCE_LIMIT (AFAIU) and looks all the way to point-max. (Do
> > I understand correctly that it implies O(N_intervals^2)??)

Btw, it is not true that we are looking all the way to point-max in
this case: you will see in composition_compute_stop_pos that it limits
the search to the next 500 buffer positions:

  void
  composition_compute_stop_pos (struct composition_it *cmp_it, ptrdiff_t charpos,
				ptrdiff_t bytepos, ptrdiff_t endpos,
				Lisp_Object string)
  {
    ptrdiff_t start, end;
    int c;
    Lisp_Object prop, val;
    /* This is from forward_to_next_line_start in xdisp.c.  */
    const int MAX_NEWLINE_DISTANCE = 500;

    if (charpos < endpos)
      {
	if (endpos > charpos + MAX_NEWLINE_DISTANCE)
	  endpos = charpos + MAX_NEWLINE_DISTANCE;
      }
  [...]
    if (charpos < endpos
	&& find_composition (charpos, endpos, &start, &end, &prop, string)
	&& start >= charpos
	&& composition_valid_p (start, end, prop))

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

> But to test this idea, I need enough test cases that use the
> 'composition' property to make sure the property still works after I
> disable that call.  Can you collect a few test cases which use the
> 'composition' property, with or without Org tables?  I guess
> prettify-symbols-mode is one of them, but are there others?  I will
> then try to find time to test this idea.

1. The most obvious is prettify-symbols-mode in Emacs sources
   Say, (setq-local prettify-symbols-alist '(("!" . ?¬)) M-x
   prettify-symbols-mode

2. https://github.com/integral-dw/org-superstar-mode
   You can use tests/*.org example files
   Also, https://github.com/jdtsmith/shakespeare.org has a giant example
   Org file. And https://github.com/casouri/valign/blob/master/test.org
   has a number of example tables (though the package itself does not
   use composition).

3. Typing using TeX input method will produce composed glyphs. The same
   if you set org-pretty-entities to t and then type \alpha, \beta, etc
   in Org buffers.

4. Composing long spans of text might be a reasonable edge case to test.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

> Btw, it is not true that we are looking all the way to point-max in
> this case: you will see in composition_compute_stop_pos that it limits
> the search to the next 500 buffer positions:

Sure. Though 500 is clearly not small enough threshold.

Also, I am a bit confused about the purpose of

      /* Make sure the above arbitrary limit position is not in the
	 middle of composable text, so we don't break compositions by
	 submitting the composable text to the shaper in separate
	 chunks.  We play safe here by assuming that only SPC, TAB,
	 FF, and NL cannot be in some composition; in particular, most
	 ASCII punctuation characters could be composed into ligatures.  */

in compute_stop_pos

AFAIU, it tries hard to not stop in the middle of composed region. Then,
why need to fall back to 500 in the composition_compute_stop_pos call?

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: 62780@debbugs.gnu.org
> Date: Fri, 14 Apr 2023 12:52:32 +0000
> 
> Also, I am a bit confused about the purpose of
> 
>       /* Make sure the above arbitrary limit position is not in the
> 	 middle of composable text, so we don't break compositions by
> 	 submitting the composable text to the shaper in separate
> 	 chunks.  We play safe here by assuming that only SPC, TAB,
> 	 FF, and NL cannot be in some composition; in particular, most
> 	 ASCII punctuation characters could be composed into ligatures.  */
> 
> in compute_stop_pos
> 
> AFAIU, it tries hard to not stop in the middle of composed region. 

That one is mainly about automatic compositions, not static
compositions.

> Then, why need to fall back to 500 in the
> composition_compute_stop_pos call?

Because composition_compute_stop_pos is called from many other places,
for other reasons.

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> AFAIU, it tries hard to not stop in the middle of composed region. 
>
> That one is mainly about automatic compositions, not static
> compositions.

>> Then, why need to fall back to 500 in the
>> composition_compute_stop_pos call?
>
> Because composition_compute_stop_pos is called from many other places,
> for other reasons.

I see. But can the same limit be re-used for static compositions? At
least within the specific call to composition_compute_stop_pos from
compute_stop_pos?

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: 62780@debbugs.gnu.org
> Date: Fri, 14 Apr 2023 13:56:55 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> AFAIU, it tries hard to not stop in the middle of composed region. 
> >
> > That one is mainly about automatic compositions, not static
> > compositions.
> 
> >> Then, why need to fall back to 500 in the
> >> composition_compute_stop_pos call?
> >
> > Because composition_compute_stop_pos is called from many other places,
> > for other reasons.
> 
> I see. But can the same limit be re-used for static compositions?

Which limit is that?

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> I see. But can the same limit be re-used for static compositions?
>
> Which limit is that?

I am referring to limit in compute_stop_pos. It is unused
when calling composition_compute_stop_pos.

Of course, if your idea with completely bypassing
composition_compute_stop_pos call works, it will be even better.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: 62780@debbugs.gnu.org
> Date: Fri, 14 Apr 2023 14:56:13 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> I see. But can the same limit be re-used for static compositions?
> >
> > Which limit is that?
> 
> I am referring to limit in compute_stop_pos. It is unused
> when calling composition_compute_stop_pos.

You want to reduce the limit inside composition_compute_stop_pos from
500 to 100?  If you try that, does it speed up this scenario enough to
consider such a change?

> Of course, if your idea with completely bypassing
> composition_compute_stop_pos call works, it will be even better.

We cannot bypass composition_compute_stop_pos in compute_stop_pos,
because it also looks for auto-composable characters, those controlled
by composition-function-table.  But I think we _can_ avoid calling
find_composition from composition_compute_stop_pos in this particular
case.

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> I am referring to limit in compute_stop_pos. It is unused
>> when calling composition_compute_stop_pos.
>
> You want to reduce the limit inside composition_compute_stop_pos from
> 500 to 100?  If you try that, does it speed up this scenario enough to
> consider such a change?

There is a noticeable speed up on the optimized build. The delay is not
completely gone though.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: 62780@debbugs.gnu.org
> Date: Fri, 14 Apr 2023 12:28:25 +0000
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > But to test this idea, I need enough test cases that use the
> > 'composition' property to make sure the property still works after I
> > disable that call.  Can you collect a few test cases which use the
> > 'composition' property, with or without Org tables?  I guess
> > prettify-symbols-mode is one of them, but are there others?  I will
> > then try to find time to test this idea.
> 
> 1. The most obvious is prettify-symbols-mode in Emacs sources
>    Say, (setq-local prettify-symbols-alist '(("!" . ?¬)) M-x
>    prettify-symbols-mode
> 
> 2. https://github.com/integral-dw/org-superstar-mode
>    You can use tests/*.org example files
>    Also, https://github.com/jdtsmith/shakespeare.org has a giant example
>    Org file. And https://github.com/casouri/valign/blob/master/test.org
>    has a number of example tables (though the package itself does not
>    use composition).
> 
> 3. Typing using TeX input method will produce composed glyphs. The same
>    if you set org-pretty-entities to t and then type \alpha, \beta, etc
>    in Org buffers.
> 
> 4. Composing long spans of text might be a reasonable edge case to test.

Thanks, and apologies for the long delay.

I've now installed on master several optimizations related to search
of composable characters by the display engine.  I tested some of the
above scenarios (not all of them), and they seem to work as well as
before.

Do these changes make significant improvements in redisplay speed in
org-table buffers?  If not, can you tell me where are the hot spots
after these changes?

Also, if you see any regressions due to these changes, please report
them.  I will keep this bug open for now.

bug#62780: 30.0.50; Redisplay gets slow when using Org tables + show-trailing-whitespace

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

> I've now installed on master several optimizations related to search
> of composable characters by the display engine.  I tested some of the
> above scenarios (not all of them), and they seem to work as well as
> before.

Thanks!

> Do these changes make significant improvements in redisplay speed in
> org-table buffers?  If not, can you tell me where are the hot spots
> after these changes?

With my normal (optimized) build, I can no longer observe typing latency
using the original reproducer.

> Also, if you see any regressions due to these changes, please report
> them.  I will keep this bug open for now.

So far so good. At least for the compositions I use personally in my
pretty-symbols config.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>