bug#56682: Fix the long lines font locking related slowdowns

[Eli Zaretskii <eliz@gnu.org>]

> Date: Thu, 04 Aug 2022 18:16:02 +0000
> From: Gregory Heytings <gregory@heytings.org>
> cc: gerd.moellmann@gmail.com, 56682@debbugs.gnu.org, monnier@iro.umontreal.ca, 
>     dgutov@yandex.ru
> 
> >> Hmmm...  I still think it would be possible to do better.  With the 
> >> above recipe (M-g g 70000 RET C-n), composition_compute_stop_pos is 
> >> called 627663 times and uses about 2 seconds of CPU time.  What 
> >> surprises me (and makes me believe it's perhaps possible to do better) 
> >> is that it is called repeatedly with the same arguments.  For example, 
> >> when doing C-n it is called 26 times with charpos = 69980.
> >
> > I'll see where these come from and whether some of them could be 
> > avoided.
> >
> > Are you capable of running under perf and producing the profile of these 
> > commands?  Because I wonder whether we correctly identify the main 
> > bottlenecks in these scenarios.
> >
> 
> I can't speak in general, but in this particular scenario, the bottleneck 
> is clearly composition_compute_stop_pos.

I looked into this, and I don't see how this could be avoided,
unfortunately, not without disabling auto-composition-mode (which I'm
told produces display of Arabic that makes readers of that script turn
away in disgust).  Disabling auto-composition-mode makes navigation
there about twice faster, as fast as in the other parts of the file.

The problem here is that bidi iteration through buffer text is
non-linear (it follows the visual order, not the order of buffer
positions), so the iterator frequently finds itself out of sync with
the next known "stop position", and needs to resync, to be able to
find which faces, overlays, and invisible and display properties are
in effect.  That's what handle_stop_backwards does, and that involves
going back and rescanning text.  With Arabic, this is exacerbated by
the fact that every Arabic character is "composable" (in the sense of
the CHAR_COMPOSED_P macro), and triggers a call to
composition_compute_stop_pos to find the next (or previous) one.

And on top of that, C-n calls pos-visible-in-window-p two or 3 times,
posn-at-point 2 times, and then vertical-motion.  Each one of these
needs to scan text around point starting from the beginning of the
previous visible line.  The narrowing limits that to some reasonable
distance, but it is still several thousand characters back.

So if composition_compute_stop_pos is the bottleneck, perhaps some
simple caching could help?  But note that when this function is called
twice with the same character position, it is called to search in
different directions -- once forward and another time back.  So even
such low-hanging fruit is not simple to reap, as these two calls will
return two different results.

For now, I don't see how to speed this up, without producing woefully
incorrect display.  I will keep thinking, but I'm not too worried
about this case, since the current performance is tolerable enough,
even if somewhat sluggish.

> You didn't tell me whether it's okay to merge the branch with the latest 
> changes?

I think you can merge.