all messages for Emacs-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
From: Eli Zaretskii <eliz@gnu.org>
To: Stefan Monnier <monnier@iro.umontreal.ca>
Cc: gerd.moellmann@gmail.com, 58158@debbugs.gnu.org
Subject: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful
Date: Thu, 29 Sep 2022 16:23:47 +0300	[thread overview]
Message-ID: <83o7uyfh5o.fsf@gnu.org> (raw)
In-Reply-To: <jwvh70q9whx.fsf-monnier+emacs@gnu.org> (message from Stefan Monnier on Thu, 29 Sep 2022 09:10:19 -0400)

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: Gerd Möllmann <gerd.moellmann@gmail.com>,
>   58158@debbugs.gnu.org
> Date: Thu, 29 Sep 2022 09:10:19 -0400
> 
> > I may be missing something, but it looks like the sole purpose of the
> > iter_start/iter_finish dance is to ensure only one iteration per tree
> > is running at any given time, and that's because the iteration uses
> > some state variable(s) of which there's only one instance per tree.
> >
> > Stefan, am I missing something?
> 
> 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).

I'm not sure I understand how recursion is related.  Are you saying
that recursion is replaced with iteration?  But then, if _start and
_finish are called by the same caller, we don't really need the
protection, since no one can start another iteration while the first
one runs.  Right?

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

Where in the code do you see iteration that adds or deletes nodes?

> For now, I pushed a simple fix to traverse the tree "by hand" in the GC
> rather than via the iterator.

So this removes the restriction of not having GC during iteration?

Also, I take it that you don't consider the current code is as
"harmful" as Gerd thinks it is?  IOW, you don't share his opinion that
this implementation is a "no-go"?





  reply	other threads:[~2022-09-29 13:23 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 [this message]
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
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=83o7uyfh5o.fsf@gnu.org \
    --to=eliz@gnu.org \
    --cc=58158@debbugs.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.