bug#69385: 30.0.50; Long lines with bidi text slow down Emacs

[Eli Zaretskii]

> Cc: 69385@debbugs.gnu.org
> Date: Mon, 26 Feb 2024 21:18:25 +0200
> From: Eli Zaretskii <eliz@gnu.org>
> 
> The reason is that, when a paragraph's direction is right-to-left,
> inserting a new glyph into glyph matrices pushes all the previous
> glyphs, thus reversing them on the fly.  Whereas in LTR paragraphs a
> glyph is inserted by adding it to the end of the previous glyphs.  And
> pushing is more expensive.  So now I understand why resetting
> bidi-display-reordering had such a dramatic effect in your case: it
> makes the paragraph render LTR as its side effect, which avoids the
> costly pushing of glyphs.  In a very long line, this cost is very
> high.
> 
> I will see if we can do better in this matter.

Actually, the fact that glyphs are pushed is not the culprit here,
since we only push as many glyphs as fit in a screen line, and that
cannot be too many.

The real culprit is the way we look for the next (actually, previous)
composition that includes the given buffer position, when we scan
characters backward (due to reordering).  The current code causes us
to scan all the way to BOB, which is especially painful with long
lines without newlines.

I've coded an optimization for that, see the patch below.  Could you
please try running with this patch for a week or two, and see if you
can spot any problems?  I hope you are editing those files with
embedded Arabic frequently enough for these changes to be exercised.

If you see no problems after a week or two, I will install this.

Thanks.

diff --git a/src/bidi.c b/src/bidi.c
index 36d1a04..306b44a 100644
--- a/src/bidi.c
+++ b/src/bidi.c
@@ -754,6 +754,16 @@ bidi_cache_find_level_change (int level, int dir, bool 
before)
   return -1;
 }
 
+ptrdiff_t
+bidi_level_start (int level)
+{
+  ptrdiff_t slot = bidi_cache_find_level_change (level, -1, true);
+
+  if (slot >= 0)
+    return bidi_cache[slot].charpos;
+  return -1;
+}
+
 static void
 bidi_cache_ensure_space (ptrdiff_t idx)
 {
diff --git a/src/dispextern.h b/src/dispextern.h
index 5387cb4..1c3232f 100644
--- a/src/dispextern.h
+++ b/src/dispextern.h
@@ -3438,6 +3438,7 @@ #define TTY_CAP_STRIKE_THROUGH    0x20
 extern void *bidi_shelve_cache (void);
 extern void bidi_unshelve_cache (void *, bool);
 extern ptrdiff_t bidi_find_first_overridden (struct bidi_it *);
+extern ptrdiff_t bidi_level_start (int);
 
 /* Defined in xdisp.c */
 
diff --git a/src/xdisp.c b/src/xdisp.c
index d03769e..140d711 100644
--- a/src/xdisp.c
+++ b/src/xdisp.c
@@ -4353,7 +4353,7 @@ compute_stop_pos (struct it *it)
          an automatic composition, limit the search of composable
          characters to that position.  */
       if (it->bidi_p && it->bidi_it.scan_dir < 0)
-       stoppos = -1;
+       stoppos = bidi_level_start (it->bidi_it.resolved_level) - 1;
       else if (!STRINGP (it->string)
               && it->cmp_it.stop_pos <= IT_CHARPOS (*it)
               && cmp_limit_pos > 0)
@@ -8712,9 +8712,8 @@ set_iterator_to_next (struct it *it, bool reseat_p)
              ptrdiff_t stop = it->end_charpos;
 
              if (it->bidi_it.scan_dir < 0)
-               /* Now we are scanning backward and don't know
-                  where to stop.  */
-               stop = -1;
+               /* Now we are scanning backward; figure out where to stop.  */
+               stop = bidi_level_start (it->bidi_it.resolved_level) - 1;
              composition_compute_stop_pos (&it->cmp_it, IT_CHARPOS (*it),
                                            IT_BYTEPOS (*it), stop, Qnil, true);
            }
@@ -8745,7 +8744,7 @@ set_iterator_to_next (struct it *it, bool reseat_p)
                     re-compute the stop position for composition.  */
                  ptrdiff_t stop = it->end_charpos;
                  if (it->bidi_it.scan_dir < 0)
-                   stop = -1;
+                   stop = bidi_level_start (it->bidi_it.resolved_level) - 1;
                  composition_compute_stop_pos (&it->cmp_it, IT_CHARPOS (*it),
                                                IT_BYTEPOS (*it), stop, Qnil,
                                                true);
@@ -9190,7 +9189,9 @@ get_visually_first_element (struct it *it)
          bytepos = IT_BYTEPOS (*it);
        }
       if (it->bidi_it.scan_dir < 0)
-       stop = -1;
+       stop = STRINGP (it->string)
+              ? -1
+              : bidi_level_start (it->bidi_it.resolved_level) - 1;
       composition_compute_stop_pos (&it->cmp_it, charpos, bytepos, stop,
                                    it->string, true);
     }
@@ -9694,9 +9695,10 @@ next_element_from_buffer (struct it *it)
                    && PT < it->end_charpos) ? PT : it->end_charpos;
        }
       else
-       stop = it->bidi_it.scan_dir < 0 ? -1 : it->end_charpos;
-      if (CHAR_COMPOSED_P (it, IT_CHARPOS (*it), IT_BYTEPOS (*it),
-                          stop)
+       stop = it->bidi_it.scan_dir < 0
+              ? bidi_level_start (it->bidi_it.resolved_level) - 1
+              : it->end_charpos;
+      if (CHAR_COMPOSED_P (it, IT_CHARPOS (*it), IT_BYTEPOS (*it), stop)
          && next_element_from_composition (it))
        {
          return true;