Re: Long lines and bidi

[Eli Zaretskii <eliz@gnu.org>]

> Date: Sat, 09 Feb 2013 01:05:01 -0800
> From: Paul Eggert <eggert@cs.ucla.edu>
> CC: dmantipov@yandex.ru, emacs-devel@gnu.org
> 
> On 02/09/2013 12:46 AM, Eli Zaretskii wrote:
> 
> > 25% faster is still terribly slow for redisplay.
> 
> Yes, as I said, it doesn't solve the performance problem.
> Still, it doesn't complicate the code, and it significantly
> improves speed in code likely to be executed often, so it
> seems worth doing in its own right.

I suspect that the use case that makes scan_buffer so high on the
profile is very much skewed.  My crystal ball says that the file in
question was one very long paragraph, or at least had many-many
_thousands_ of lines between empty lines that delimit paragraphs.
scan_buffer is high on the profile because the bidi.c code tries to
find the beginning of a paragraph, which determines the base direction
of the paragraph, which in turn determines how the text should be
reordered for display.

By contrast, most real-life files have much less text between empty
lines, so scan_buffer will not be at any prominent place in the
profile.  But redisplay of a buffer with very long lines will still be
awfully slow, even if there's an empty line between every 2 long
lines, although scan_buffer will no longer be a factor.

OTOH, if you create a file with a single long paragraph, but whose
lines have "normal" width, like 100 characters, redisplay will perform
adequately, even though scan_buffer will be heavily used.  (It would
be interesting to see a profile for that, btw.)

IOW, the solution in bidi.c for extremely long paragraphs is optimized
for the 99% of use cases, where lines are not too long, i.e. for those
cases where the old unidirectional display engine gave reasonable
performance.  Dmitry's use case, OTOH, is skewed on several counts:

 . it uses extremely long lines
 . it uses too many neutral/weak characters
 . it uses extremely long paragraphs

This simultaneously hits on several unrelated weaknesses of the
current display engine, with the result that the profile is a
combination of at least 3 different reasons for slow-down, which makes
it very hard to analyze the results and look for solutions.

That is why I think we should attack this problem one reason at a
time.  The most important reason is the first one: long lines cause
the display code traverse too much of buffer text.  This is why you
see x_produce_glyphs so high on the profile in the unidirectional
case: it examines too many characters, much more than what will be
actually displayed on the screen.  Solve this problem, and the 2nd one
will simply disappear without a trace, because it is at least linear
in the number of scanned characters.  If the 3rd problem is still a
factor, after the 1st one is gone, we can tune the current
optimization at that time.