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

[Stephen Berman via "Bug reports for GNU Emacs, the Swiss army knife of text editors" <bug-gnu-emacs@gnu.org>]

On Mon, 26 Feb 2024 21:18:25 +0200 Eli Zaretskii <eliz@gnu.org> wrote:

>> From: Stephen Berman <stephen.berman@gmx.net>
>> Cc: 69385@debbugs.gnu.org
>> Date: Mon, 26 Feb 2024 18:12:04 +0100
>> 
>> On Mon, 26 Feb 2024 18:36:42 +0200 Eli Zaretskii <eliz@gnu.org> wrote:
>> 
>> [...]
>> > Can you measure the time it takes to redraw the window after M->, with
>> > and without bidi-display-reordering?  I'd like to have numbers here,
>> > not just impressions.  For example, measure it with benchmark-run or
>> > something similar.
>> 
>> On master started with -Q in a buffer containing a single line
>> consisting of 800 repetitions of "السّلام عليكم Hello "
>
> Oh, I think I see what's going on.  The buffer you create this way is
> rendered as a paragraph with right-to-left base direction, right?
> That is, it starts at the right side of the window, and C-f generally
> moves to the left, yes?

Correct.

>                          By contrast, I thought you were doing this in
> a buffer whose bidi-paragraph-direction is set to left-to-right, or
> the text begins with Latin characters (as in "Arabic", the string the
> begins the Arabic line in HELLO).
>
> So now try your recipe, but set bidi-paragraph-direction to
> left-to-right, or prepend a single ASCII character to the long line
> (which will have the same effect on the base paragraph direction), and
> then repeat your experiment, including the timings.  I think you will
> see a big difference.

I created the test buffer now by first typing "Hello" and the inserting
" السّلام عليكم " on the right, so the base paragraph direction was LTR.
Then I ran the benchmarks, and there is indeed a big difference, but one
that I think will surprise you.  First, the timing for the LTR run with
bidi-display-reordering set to nil was:

(0.035104007 0 0.0)

This is, unsurprisingly, almost the same as the corresponding test run
with RTL base paragraph direction, which was (0.034058467 0 0.0).

In contrast, recall that with bidi-display-reordering at the default
value t, the RTL test run was (5.249231941 1 0.014300497000000023), but
now the LTR test run gave this:

(10.613699099 1 0.012965359999999981)

Again, the only difference between the buffers is the order of the
strings and, consequently, the base paragraph direction.  Both buffers
consist of 800 copies of the strings and in both point-max is 16001.

The -- in view of your below explanation -- unexpectedly large timing
for the LTR buffer reminded me of the file in which I first encountered
the slowdown, which consists of a number of Emacs Lisp sexps.  The first
group are all ASCII characters, so the base paragraph direction is LTR.
Then there is a vector of 827 lists in a single line (remember, it's a
generated file), each list containing three strings, one in Arabic
script, one in English, one a transliteration of the Arabic which in
many cases uses non-ASCII characters.  The benchmark run for M-> in the
buffer visiting this file was:

(9.308704995000001 4 0.054923504999999984)

The buffer size here is considerably larger than the buffers for my test
runs; I couldn't remember it exactly, so I typed `M-: (point)' in the
buffer, with the result 43901.  It took a number of seconds for the
result to be displayed, during which Emacs was unresponsive, so I then
ran (benchmark-run nil (point)) in that buffer, with this result:

(9.030000000000001e-07 0 0.0)

I don't know what this result means, but the reported execution time
bears no relation to actual elapsed time until the value of point was
displayed.  So I reran the benchmark and also manually timed it with a
stopwatch.  This is the result of the second benchmark:

(3.1120000000000004e-06 0 0.0)

However, the stopwatch showed fully 15 seconds.  Maybe benchmark-run
doesn't work for point for some reason.  Given my doubts, I reran the
benchmark on the test LTR buffer, but the reported execution time was
only slightly different from before:

(10.317616279000001 0 0.0)

What do you make of these results?

> 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.

This sounds plausible, but my results seem to indicate there something
else (or more) going on.

> I will see if we can do better in this matter.

I appreciate whatever you can do.

Steve Berman