[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#56682: Interval tree balance (was: Fix the long lines font locking r
From: |
Stefan Monnier |
Subject: |
bug#56682: Interval tree balance (was: Fix the long lines font locking related slowdowns) |
Date: |
Sun, 24 Jul 2022 10:34:25 -0400 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) |
> 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
- bug#56682: Fix the long lines font locking related slowdowns, (continued)
- bug#56682: Fix the long lines font locking related slowdowns, Eli Zaretskii, 2022/07/23
- bug#56682: Fix the long lines font locking related slowdowns, Eli Zaretskii, 2022/07/23
- bug#56682: Fix the long lines font locking related slowdowns, Gerd Möllmann, 2022/07/24
- bug#56682: Fix the long lines font locking related slowdowns, Eli Zaretskii, 2022/07/24
- bug#56682: Fix the long lines font locking related slowdowns, Stefan Monnier, 2022/07/24
- bug#56682: Fix the long lines font locking related slowdowns, Eli Zaretskii, 2022/07/24
- bug#56682: Fix the long lines font locking related slowdowns, Stefan Monnier, 2022/07/24
- bug#56682: Fix the long lines font locking related slowdowns, Eli Zaretskii, 2022/07/24
- bug#56682: Fix the long lines font locking related slowdowns, Lars Ingebrigtsen, 2022/07/24
- bug#56682: Fix the long lines font locking related slowdowns, Eli Zaretskii, 2022/07/24
- bug#56682: Interval tree balance (was: Fix the long lines font locking related slowdowns),
Stefan Monnier <=
- bug#56682: Interval tree balance, Stefan Monnier, 2022/07/24
- bug#56682: Fix the long lines font locking related slowdowns, Gerd Möllmann, 2022/07/25
- bug#56682: Fix the long lines font locking related slowdowns, Gregory Heytings, 2022/07/25
- bug#56682: Fix the long lines font locking related slowdowns, Gerd Möllmann, 2022/07/26
- bug#56682: Fix the long lines font locking related slowdowns, Gregory Heytings, 2022/07/26
- bug#56682: Fix the long lines font locking related slowdowns, Eli Zaretskii, 2022/07/23
- bug#56682: Fix the long lines font locking related slowdowns, Gerd Möllmann, 2022/07/23
- bug#56682: Fix the long lines font locking related slowdowns, Eli Zaretskii, 2022/07/23
- bug#56682: Fix the long lines font locking related slowdowns, Gregory Heytings, 2022/07/25
- bug#56682: Fix the long lines font locking related slowdowns, Gerd Möllmann, 2022/07/26