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

From: Eli Zaretskii <[email-masked]>
Date: Sun, 24 Jul 2022 09:52:51 +0300

> From: Gerd Möllmann <[email-masked]>
> Cc: [email-masked],  [email-masked],  [email-masked],
>   [email-masked]
> Date: Sun, 24 Jul 2022 08:16:33 +0200
> 
> And another BTW: I was never 100% certain if the interval tree is
> really always balanced because it didn't use an algorithm that I
> knew and could recognize.

AFAIU, we balance on-the-fly (see find_interval, which calls
balance_possible_root_interval).

> "frequent" changes of faces certainly have an effect on iterator
> performance.  It stops, looks up properties again to determine the
> next stop pos, does what has to be done for current properties...

To be more accurate: changes in text properties that are not relevant
to display basically affect the iterator performance in only one way:
they make the search for the next change in _relevant_ properties more
expensive.  See the last part of compute_stop_pos for the gory
details.  In a nutshell, we check one by one the intervals following
the interval of the current iterator position, until we find an
interval whose values for one or more of the properties of interest to
redisplay are different.  When we find one such interval, it is
guaranteed to have changes only in the text properties that are of
interest to redisplay, but the search could take more time if there
are many text properties that are not interesting, because there are
more intervals to check.

Btw, it might be interesting to measure the effect of enlarging
TEXT_PROP_DISTANCE_LIMIT, currently 100 character positions, on the
performance.  Looking at the code, it is not clear to me whether it
could affect the performance in any significant ways, but maybe I'm
wrong.