From: Stefan Monnier <monnier@iro.umontreal.ca>
To: Matt Armstrong <matt@rfc20.org>
Cc: emacs-devel@gnu.org
Subject: Re: noverlay branch
Date: Tue, 11 Oct 2022 14:59:49 -0400 [thread overview]
Message-ID: <jwvfsfumbvk.fsf-monnier+emacs@gnu.org> (raw)
In-Reply-To: <87fsfuw85t.fsf@rfc20.org> (Matt Armstrong's message of "Tue, 11 Oct 2022 11:02:22 -0700")
>>>> Regarding `otick`, I can see 2 more options:
>>>> - Get rid of it completely: its sole purpose is to try and keep
>>>> `overlay-start/end` O(1) in the usual case instead of O(log N), but
>>>> I'm not convinced it's worth the cost of propagating `otick` everywhere
>>>> all the time.
>>>> - A halfway point is to keep `otick` but update it more lazily,
>>>> i.e. only update it when we do `overlay-start/end` (e.g. in
>>>> `interval_tree_validate`).
>>> These ideas are simpler but similar in direction to my idea to use a
>>> btree instead.
>> Sorry, I fail to see the connection to btrees.
> Just a performance conjecture. A b-tree is shallower, so your first
> idea above is more attractive.
I still fail to see the connection: changes in `otick` need to be
propagated everywhere anyway, so the shape of the tree probably doesn't
make much difference.
[...time passe...]
Oh, I think you're talking specifically about the complete removal of
`otick` where a shallower tree would make that less costly.
Sorry. I understand quickly, but only after a long explanation.
>> [ FWIW, I'd like to get rid of the `tree->size` field, and thus rely on
>> auto-growing more heavily. ]
> I rather like the size field.
I agree it has its benefit, which is why I haven't removed it yet:
I'm not sure.
> I have a different idea about the stacks, though. Idea: use fixed size
> stacks, no auto-growing. 120 elements is all that is needed (the max
> possible depth of a 3-pointer red-black tree on 64 bit architectures).
> That is 1K memory overhead per traversal, which I think isn't an issue?
> At least, this is a reasonable choice in other systems I've worked in.
> Is it reasonable for Emacs?
Maybe you're right. I think this decision is muddled by the (ab)use of
stacks as collections of nodes at a few places (where we use
`interval_stack_push`), where it's not limited to O(log N).
Stefan
next prev parent reply other threads:[~2022-10-11 18:59 UTC|newest]
Thread overview: 71+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-09-25 22:38 noverlay branch Stefan Monnier
2022-09-25 22:50 ` Lars Ingebrigtsen
2022-09-25 22:56 ` Stefan Monnier
2022-09-26 2:52 ` Ihor Radchenko
2022-09-26 3:17 ` Stefan Monnier
2022-09-26 6:11 ` Eli Zaretskii
2022-09-26 13:08 ` Ihor Radchenko
2022-09-26 15:59 ` Eli Zaretskii
[not found] ` <87v8ovdosz.fsf@localhost>
2022-10-08 6:57 ` Eli Zaretskii
2022-10-09 3:25 ` Matt Armstrong
2022-10-09 4:30 ` Eli Zaretskii
2022-10-09 3:23 ` Matt Armstrong
2022-10-09 3:47 ` Stefan Monnier
2022-10-13 12:09 ` Ihor Radchenko
2022-09-29 18:12 ` Stefan Monnier
2022-09-27 5:12 ` Matt Armstrong
2022-09-27 6:53 ` Eli Zaretskii
2022-09-27 17:31 ` Matt Armstrong
2022-09-27 18:45 ` Stefan Monnier
2022-09-28 23:09 ` Stefan Monnier
2022-09-29 14:54 ` Gerd Möllmann
2022-09-29 21:36 ` Stefan Monnier
2022-09-30 5:20 ` Gerd Möllmann
2022-10-06 4:47 ` Matt Armstrong
2022-10-06 5:43 ` Gerd Möllmann
2022-10-07 4:11 ` Matt Armstrong
2022-10-07 4:34 ` Gerd Möllmann
2022-10-07 13:33 ` Stefan Monnier
2022-10-07 14:29 ` Gerd Möllmann
2022-10-07 14:51 ` Stefan Monnier
2022-10-07 15:12 ` Gerd Möllmann
2022-10-07 17:12 ` Stefan Monnier
2022-10-07 14:56 ` Stefan Monnier
2022-10-07 15:59 ` Matt Armstrong
2022-10-07 15:34 ` Matt Armstrong
2022-10-06 12:08 ` Stefan Monnier
2022-09-27 8:39 ` Gerd Möllmann
2022-09-27 9:38 ` Eli Zaretskii
2022-10-06 20:41 ` Matt Armstrong
2022-10-07 16:51 ` Matt Armstrong
2022-10-07 18:28 ` Stefan Monnier
2022-10-08 23:33 ` Matt Armstrong
2022-10-09 3:44 ` Matt Armstrong
2022-10-09 4:12 ` Stefan Monnier
2022-10-09 15:34 ` Stefan Monnier
2022-10-10 2:57 ` Matt Armstrong
2022-10-10 6:24 ` Eli Zaretskii
2022-10-10 16:26 ` Matt Armstrong
2022-10-10 14:44 ` Stefan Monnier
2022-10-11 3:46 ` Matt Armstrong
2022-10-11 4:09 ` Stefan Monnier
2022-10-11 18:02 ` Matt Armstrong
2022-10-11 18:59 ` Stefan Monnier [this message]
2022-10-12 5:18 ` Matt Armstrong
2022-10-12 18:02 ` Stefan Monnier
2022-10-12 22:26 ` Matt Armstrong
2022-10-13 4:03 ` Stefan Monnier
2022-10-09 23:47 ` Stefan Monnier
2022-10-10 0:05 ` Emanuel Berg
2022-10-10 16:27 ` Matt Armstrong
2022-10-10 16:33 ` Matt Armstrong
2022-10-10 18:32 ` Matt Armstrong
2022-10-11 16:06 ` Stefan Monnier
2022-10-12 17:33 ` Matt Armstrong
2022-10-13 3:59 ` Stefan Monnier
2022-10-16 21:53 ` Matt Armstrong
2022-10-23 4:49 ` Matt Armstrong
2022-10-24 9:14 ` Stefan Kangas
2022-10-24 16:21 ` Matt Armstrong
2022-10-24 12:51 ` Eli Zaretskii
2022-10-25 20:57 ` Dmitry Gutov
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=jwvfsfumbvk.fsf-monnier+emacs@gnu.org \
--to=monnier@iro.umontreal.ca \
--cc=emacs-devel@gnu.org \
--cc=matt@rfc20.org \
/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.