bug#30457: 26.0.91; bidi-display-reordering makes navigation around melpa/archive-contents slow

[Eli Zaretskii <eliz@gnu.org>]

> From: Aaron Jensen <aaronjensen@gmail.com>
> Date: Thu, 15 Feb 2018 10:49:23 -0800
> Cc: 30457@debbugs.gnu.org
> 
> > It isn't WONTFIX, I just don't know how to make the BPA implementation
> > faster with such long lines and deeply nested parentheses.  It already
> > includes all the optimizations I could think of.  But maybe someone
> > else will find a way to optimize it more.
> 
> I'm only just now learning about BPA, so I apologize if this is a
> silly question, but would it be any faster to scan a buffer and
> determine that there are no rtl characters so parentheses matching is
> unnecessary?

Scanning the entire buffer could be faster only for small buffers.
But with a very large buffer we'd be scanning a lot more than needed,
because redisplay tries very hard not to examine much more of the
buffer than is needed to show one window-full.  And due to the way the
display engine is designed, it doesn't lend itself easily to caching
stuff, so you'd need to scan the entire buffer every redisplay cycle,
e.g., after each C-n.

The current code in bidi_find_bracket_pairs scans only as much as
needed (which unfortunately could be quite a lot for deeply nested
parens in a long line).  And it already includes an optimization for
strictly left-to-right text inside the parens, something that it
detects as part of the scan.

> > It does, sort of.  At least near the end of the buffer you clearly see
> > that bidi-display-reordering has a much smaller effect, in relative
> > terms.
> 
> Yeah, I wasn't aware that the end of the buffer had more slowness, but
> that's good to know.

The farther you are from the beginning of line, the more buffer
positions Emacs needs to scan to determine where to put point after
C-n or C-p.  That's because the layout calculations needed for
determining coordinates of each buffer position must start from some
known anchor, and currently the only anchor is the line beginning,
where we sure the X coordinate is zero.  So Emacs needs to go back to
the line beginning (something it can do very fast), and then come back
(much slower) one character at a time, until it hits the buffer
position with the right coordinate.  That coming back is the main
reason why doing this near the end of the line is so much slower than
near the beginning.