bug#56682: Interval tree balance (was: Fix the long lines font locking related slowdowns)

[Stefan Monnier]

> 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).


        Stefan