bug#9470: 24.0.50; Possible bidi-related slowness

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: Lars Magne Ingebrigtsen <larsi@gnus.org>,  9470@debbugs.gnu.org
> Date: Sat, 10 Sep 2011 23:06:06 -0400
> 
> > The long search is for the paragraph beginning.  Looking for R2L
> > characters during that search will slow it even more.
> > Anyway, I reopened the bug and will try to think of something.
> 
> I think Lars's point is a good one: maybe the paragraph direction can be
> based on the predominance of L2R or R2L chars in the previous N chars,
> in case the paragraph beginning is further than that (N should be large
> enough to include all chars displayed).

It might be a good idea in general, but I don't see how it would help
in this case, as I pointed out above.

Let me explain a bit more.

The current code works by searching backwards for a line that begins
with certain regexp.  Unless someone can show a _really_ fast way of
counting types of characters we move across while searching for that
regexp, such counting will just make redisplay slower yet.

What bothers me even more is that such heuristics will give chaotic
results: adding a single character in some strategic place, or moving
up or down by a single line, can change the paragraph direction, with
dramatic effect on display.  It will also effectively disable the
try_cursor_movement optimization (because the glyph matrix will be
entirely different), which is a big loss for users that just move
cursor.

So I generally favor a less smart algorithm, but one that gives
predictably constant results in a given buffer, and does not force us
to disable redisplay optimizations, even if it will sometimes produce
incorrect results.  I have a simple idea for such an algorithm, but I
need to test it first.

> Otherwise, I think the only way to make it faster is by caching the
> result of the computation (I suspect you already do some caching, but
> maybe we just need to be more aggressive).

The caching is done in the iterator structure for the paragraph
through which the display engine iterates while preparing it for
display.  The problem is that every redisplay cycle following a
command must begin by computing the paragraph direction of the first
paragraph whose text is about to be displayed.  (Any following
paragraphs have their direction computed on the fly when we iterate
through their beginning.)  And that first paragraph is what takes time
in these pathological buffers, especially when user types commands
that don't require complete redisplay of a window, and thus are
expected to be fast.

I don't see any easy way of gaining from more aggressive caching of
this info, because the cache would need to be updated on every edit
and on any redisplay, which would just move the slowdown from one
group of commands to another.  Clever ideas are welcome.