GNU bug report logs - #56682
Fix the long lines font locking related slowdowns

Previous Next

Full log

View this message in rfc822 format

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Gerd Möllmann <gerd.moellmann <at> gmail.com>
Cc: 56682 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>, gregory <at> heytings.org, visuweshm <at> gmail.com
Subject: bug#56682: Interval tree balance (was: Fix the long lines font locking related slowdowns)
Date: Sun, 24 Jul 2022 10:34:25 -0400

> 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

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.