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

[Stephen Berman]

On Sun, 03 Mar 2024 17:18:31 +0200 Eli Zaretskii <eliz@gnu.org> wrote:

>> 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 applied the patch, rebuilt, started with -Q, made two test buffers
using 800 concatenated copies of a bidirectional Arabic + English
string, one with base paragraph direction RTL, one with LTR, and ran the
end-of-buffer benchmark; here are the results:

RTL with patch: (0.099171108 0 0.0)
LTR with patch: (0.143149541 1 0.01330051900000001)

Here for comparison my previous results without your patch:

RTL without patch: (5.249231941 1 0.014300497000000023)
LTR without patch: (10.613699099 1 0.012965359999999981)

That's more than 50 times faster for the RTL test and more than 70 times
faster for the LTR test -- impressive!

>                         I hope you are editing those files with
> embedded Arabic frequently enough for these changes to be exercised.

As I mentioned previously, my real files are programmatically generated
elisp files (so base paragraph direction LTR) not meant to be manually
edited or even just viewed by users of the program, and I haven't edited
them manually, and normally wouldn't.  But I just now ran the
end-of-buffer benchmark on one of them (the one I described previous,
containing a vector of 827 lists of bidirectional strings in a single
line), with this result:

(0.849369497 4 0.05337466599999996)

This was the timing without your patch:

(9.308704995000001 4 0.054923504999999984)

So for this file your patch yields "only" an almost 11 times faster
benchmark.  For navigation besides M-> and M-<, I find C-v, M-v, C-n,
C-p in the buffer visiting this file still very slow (noticeably more
than in the test buffers) and holding them down still freezes Emacs
(with C-n and C-p for many seconds) and uses 100% of a CPU core; though,
while I haven't tried timing these yet, my impression is that the
freezes are not as long as the ones I observed without your patch.
Also, there is still a marked delay when entering the minibuffer with
M-x or M-: or when switching to another buffer with C-x b, though
impressionistically no worse than the delays without your patch.  I'll
try to do more testing.

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

Thanks.

Steve Berman