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

[Gerd Möllmann]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> Don't know if this is relevant for anything in this case.  I thought I
>> just mention that the interval tree might also have a potential for
>> improvement, if you will.  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.
>
> I can answer this one: no it's not always balanced (tho in practice
> it is most of the time).  We could make it use a more standard
> algorithm, but I have not been able to measure any impact on performance
> (I also played with a splay-tree alternative, under the assumption that
> we mostly consult the tree "locally" (within the visible part of the
> buffer, basically), so a splay-tree could turn the O(log N) into an O(n)
> where `N` is the buffer-size and `n` is the distance between
> window-start and window-end).

Thanks.  And too bad.

But I'd really prefer a standard algorithm with formally proven
properties anyway.  Call me German.