From: Stefan Monnier via "Bug reports for GNU Emacs, the Swiss army knife of text editors" <bug-gnu-emacs@gnu.org>
To: "Gerd Möllmann" <gerd.moellmann@gmail.com>
Cc: Eli Zaretskii <eliz@gnu.org>, 58158@debbugs.gnu.org
Subject: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful
Date: Thu, 29 Sep 2022 12:40:25 -0400 [thread overview]
Message-ID: <jwva66irvjo.fsf-monnier+emacs@gnu.org> (raw)
In-Reply-To: <m235cas1w2.fsf@Mini.fritz.box> ("Gerd Möllmann"'s message of "Thu, 29 Sep 2022 16:15:09 +0200")
Gerd Möllmann [2022-09-29 16:15:09] wrote:
> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> One reason is that traversing a binary tree usually requires something
>> like recursion, but that wouldn't fit very conveniently with the current
>> code (nor with C in general since you can't make a local recursive
>> closure which accesses local variables from the surrounding function).
> Ok, usually, but not necessarily. The alternative is to implement an
> iterator that starts with a node N, and an implementation of a successor
> function, which return the successor of N in a given order.
The approach currently used is somewhat similar to that. Some of the
difference is that we need an actual "iterator/generator" object to
remember the parameter of the filtering we want to apply to the set of
objects. And the problem is that this "object" is currently implemented
not only as a global value (thus restricting us to one-iteration at
a time) but also with some parts of the data stored in the tree.
I think this is the part that really needs to be changed.
> This requires a parent pointer in nodes, but that we have.
>
> (Something like this is used for ordered containers like "map" and "set"
> in C++ STL, for instance, which are based on rb-trees in GCC's
> libstdc++.)
Another difference is that itree.c's iterator uses a local "work stack"
instead of traversing the tree exclusively via left/right/parent like in
the code you show. I don't know if that difference is important, tho.
>> Another is the need to update the begin/end fields (these need updating
>> because of insertions/deletions but they're updated lazily while
>> traversing the tree to avoid an O(N) complexity during the
>> insertions/deletions). Hiding that behind 'some kind of "next node"
>> function keeps the code more readable.
>
> Is this for buffer text changes, something akin to a delayed update of
> marker positions?
Yes, exactly.
>> But yes, the current restriction to have a single iteration at a time is
>> a bit of a problem, especially because it's very "global". I added
>> a comment yesterday describing how we could make it non-global (hence
>> getting rid of the `visited` flag in the nodes).
>
> BTW, and related to iteration directly, did you notice this in
> interval_tree_insert?
>
> /* This suggests that nodes in the right subtree are strictly
> greater. But this is not true due to later rotations. */
> child = node->begin <= child->begin ? child->left : child->right;
No, I had not noticed that yet, and I don't understand this comment.
Stefan
next prev parent reply other threads:[~2022-09-29 16:40 UTC|newest]
Thread overview: 68+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-09-29 5:29 bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Gerd Möllmann
2022-09-29 6:28 ` Eli Zaretskii
2022-09-29 7:03 ` Gerd Möllmann
2022-09-29 8:08 ` Eli Zaretskii
2022-09-29 9:09 ` Gerd Möllmann
2022-09-29 9:37 ` Eli Zaretskii
2022-09-29 10:05 ` Gerd Möllmann
2022-09-29 10:43 ` Eli Zaretskii
2022-09-29 11:33 ` Gerd Möllmann
2022-09-29 13:10 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-29 13:23 ` Eli Zaretskii
2022-09-29 16:48 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-29 13:40 ` Eli Zaretskii
2022-09-29 14:15 ` Gerd Möllmann
2022-09-29 14:37 ` Gerd Möllmann
2022-09-29 22:09 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-30 5:28 ` Gerd Möllmann
2022-09-30 6:11 ` Eli Zaretskii
2022-09-30 11:31 ` Gerd Möllmann
2022-09-30 18:29 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-02 8:06 ` Gerd Möllmann
2022-10-06 22:36 ` Dmitry Gutov
2022-10-07 19:47 ` Eli Zaretskii
2022-10-08 18:50 ` Dmitry Gutov
2022-10-10 8:10 ` Eli Zaretskii
2022-10-11 2:12 ` Dmitry Gutov
2022-10-11 6:37 ` Eli Zaretskii
2022-10-11 11:36 ` xref-query-replace-in-results error message after xref-find-definitions, was: " Dmitry Gutov
2022-10-11 11:51 ` Eli Zaretskii
2022-10-11 12:10 ` Dmitry Gutov
2022-10-11 12:17 ` Eli Zaretskii
2022-10-11 12:44 ` Dmitry Gutov
2022-10-11 12:55 ` Eli Zaretskii
2022-10-11 14:55 ` Dmitry Gutov
2022-10-11 16:01 ` Eli Zaretskii
2022-10-11 16:41 ` Dmitry Gutov
2022-10-11 16:50 ` Eli Zaretskii
2022-10-11 20:31 ` Dmitry Gutov
2022-10-12 5:17 ` Eli Zaretskii
2022-10-12 10:06 ` John Yates
2022-10-12 10:17 ` Eli Zaretskii
[not found] ` <CAJnXXogKsM=gMTFi2NivDMHW4A3EBtBtsNDBV3o5vcu2xXfuvw@mail.gmail.com>
2022-10-12 13:21 ` Eli Zaretskii
2022-10-12 16:12 ` John Yates
2022-10-12 13:47 ` Dmitry Gutov
2022-10-12 14:05 ` Eli Zaretskii
2022-10-11 14:04 ` Stefan Monnier
2022-10-11 14:07 ` Stefan Monnier
2022-10-11 15:07 ` Dmitry Gutov
2022-10-11 15:37 ` Eli Zaretskii
2022-09-30 13:25 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-30 14:08 ` Gerd Möllmann
2022-09-30 15:25 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-30 16:04 ` Eli Zaretskii
2022-09-30 17:11 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-01 5:06 ` Gerd Möllmann
2022-10-01 13:54 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-02 8:22 ` Gerd Möllmann
2022-10-02 16:32 ` Andreas Politz
2022-10-03 4:35 ` Gerd Möllmann
2022-10-04 10:50 ` Andreas Politz
2022-10-01 7:25 ` Gerd Möllmann
2022-10-01 10:55 ` Gerd Möllmann
2022-10-01 14:01 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-29 16:40 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors [this message]
2022-10-01 1:57 ` Richard Stallman
2022-10-01 7:00 ` Eli Zaretskii
2022-10-06 22:26 ` Matt Armstrong
2023-10-06 13:14 ` Gerd Möllmann
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=jwva66irvjo.fsf-monnier+emacs@gnu.org \
--to=bug-gnu-emacs@gnu.org \
--cc=58158@debbugs.gnu.org \
--cc=eliz@gnu.org \
--cc=gerd.moellmann@gmail.com \
--cc=monnier@iro.umontreal.ca \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.