bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful

[Eli Zaretskii]

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