[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful
From: |
Eli Zaretskii |
Subject: |
bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful |
Date: |
Fri, 30 Sep 2022 19:04:05 +0300 |
> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: Eli Zaretskii <eliz@gnu.org>, 58158@debbugs.gnu.org, Andreas Politz
> <mail@andreas-politz.de>
> Date: Fri, 30 Sep 2022 11:25:30 -0400
>
> > And, perhaps, if it doesn't order duplicates, would it be an idea to
> > order them, maybe at some later point? I'm asking this because
> > a successor(N) function would return nodes in the order in the tree,
> > always, and I don't know what the order is now.
>
> Ordering based on interval end could arguably make sense. I'm not
> completely sure how/where it would benefit us, tho. Most times we look
> at the itree, we just look at *all* the nodes within a specific
> interval, so the order in which they're returned doesn't matter very
> much (the ordering within the tree does matter in terms of how we manage
> to prune the tree, but that has more to do with which elements are near
> the root, which is a different kind of "ordering" than the "binary tree
> ordering" itself). Maybe the `next/previous-overlay-change` code
> benefit from sub-ordering based on `end`, but I suspect the effect would
> be lost in the noise: if we want to speed up that part of the code,
> I expect that a better avenue is to rewrite the
> `next/previous-single-overlay-change` so as not to work by (while ..
> (next/previous-overlay-change ..) .. (get-char-property ..) ..) where
> both functions do the O(log N) itree-iteration dance, but instead doing
> the itree iteration itself.
The display engine sorts the overlays, so order could be important.
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, (continued)
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Gerd Möllmann, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Gerd Möllmann, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Stefan Monnier, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Gerd Möllmann, 2022/09/30
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Eli Zaretskii, 2022/09/30
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Gerd Möllmann, 2022/09/30
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Stefan Monnier, 2022/09/30
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Stefan Monnier, 2022/09/30
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Gerd Möllmann, 2022/09/30
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Stefan Monnier, 2022/09/30
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful,
Eli Zaretskii <=
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Stefan Monnier, 2022/09/30
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Stefan Monnier, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Richard Stallman, 2022/09/30