From: "Gerd Möllmann" <gerd.moellmann@gmail.com>
To: Stefan Monnier <monnier@iro.umontreal.ca>
Cc: Ihor Radchenko <yantar92@posteo.net>,
Eli Zaretskii <eliz@gnu.org>,
emacs-devel@gnu.org, eller.helmut@gmail.com
Subject: Re: MPS: dangling markers
Date: Sun, 30 Jun 2024 07:02:06 +0200 [thread overview]
Message-ID: <m2o77j2fch.fsf@pro2.fritz.box> (raw)
In-Reply-To: <jwvplrzs7uc.fsf-monnier+emacs@gnu.org> (Stefan Monnier's message of "Sat, 29 Jun 2024 18:59:15 -0400")
Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> Jup, it's point-marker for me. No idea who calls that so often.
>
> I think the core of the problem, then, is that currently it's completely
> normal to rely on the GC to "remove" markers we don't care about any
> more instead of explicitly removing them when we don't need them any
> more (with `move-marker`).
>
> So if the GC takes a long time to call `unchain_dead_markers`, we end up
> with a very large set of markers and it's not clear how to handle that
> efficiently.
Yes.
> I understand that relying on a prompt collection of dead objects is
> a bad idea, but we may have to try and make sure it's prompt enough
> because of the legacy of code which relies on it when it comes
> to markers.
I'm afraid the only way to force MPS to "splat", as they call it, weak
references it by requesting a full collection. Which I think we want
to avoid because that is not done concurrently, the client has to wait
for it to complete.
> If not, we'll have to work at a better data-structure able to handle
> a large set of markers. The `itree` would probably be our best best but
> if we end up with many markers at the very same place (which seems
> likely if we often call `point-marker`), we'll hit its worst case (where
> it goes back to O(N) tho this N is only the number of markers at a given
> position rather than the total number of markers).
Exactly what I was afraid of after seeing the number of point-markers:
thousands of markers with the same position. And I agree that itree
doesn't help with that, it will degenerate, and we can as well use a
vector then.
I must admit that I'm currently out of ideas.
> [ Another option might be to have a kind of two-level set of markers,
> where we keep the "recently used" markers in one data structure
> (optimized for adding/removing/moving/gettingtheposition) and then we
> demote markers that have not been recently used to a secondary
> data-structure optimized for "low-cost long term maintenance", kind of
> a like an archive of markers which are predicted to be dead. ]
>
> [ BTW, for the bytes<->chars conversion, we could also use a plain array
> indexed by CHARPOS/CHUNKSIZE where instead of updating the entries
> upon text insertion/deletion we just truncate the array to the last
> still-valid entry before the point of insertion/deletion. ]
>
>
> Stefan
next prev parent reply other threads:[~2024-06-30 5:02 UTC|newest]
Thread overview: 82+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-06-27 21:01 MPS: dangling markers Ihor Radchenko
2024-06-27 21:24 ` Stefan Monnier
2024-06-28 4:14 ` Gerd Möllmann
2024-06-28 16:37 ` Ihor Radchenko
2024-06-28 16:47 ` Gerd Möllmann
2024-06-28 16:52 ` Ihor Radchenko
2024-06-28 16:56 ` Gerd Möllmann
2024-06-28 17:18 ` Ihor Radchenko
2024-06-28 17:44 ` Gerd Möllmann
2024-06-29 3:57 ` Gerd Möllmann
2024-06-29 14:34 ` Ihor Radchenko
2024-06-29 14:56 ` Gerd Möllmann
2024-06-29 16:29 ` Eli Zaretskii
2024-06-29 17:09 ` Gerd Möllmann
2024-06-29 17:17 ` Gerd Möllmann
2024-06-29 17:23 ` Eli Zaretskii
2024-06-29 18:02 ` Gerd Möllmann
2024-06-29 18:11 ` Eli Zaretskii
2024-06-29 18:19 ` Gerd Möllmann
2024-06-29 19:51 ` Ihor Radchenko
2024-06-29 21:50 ` Gerd Möllmann
2024-06-29 22:33 ` Pip Cet
2024-06-30 4:41 ` Gerd Möllmann
2024-06-30 6:56 ` Gerd Möllmann
2024-06-30 9:51 ` Pip Cet
2024-06-30 11:02 ` Gerd Möllmann
2024-06-30 12:54 ` Pip Cet
2024-06-30 13:15 ` Gerd Möllmann
2024-06-30 19:02 ` Pip Cet
2024-06-30 19:22 ` Gerd Möllmann
2024-06-30 20:15 ` Pip Cet
2024-07-01 4:22 ` Gerd Möllmann
2024-07-01 17:14 ` Pip Cet
2024-07-01 18:20 ` Gerd Möllmann
2024-07-01 18:50 ` Eli Zaretskii
2024-07-01 19:04 ` Pip Cet
2024-07-01 19:07 ` Eli Zaretskii
2024-07-01 19:43 ` Gerd Möllmann
2024-07-01 18:56 ` Eli Zaretskii
2024-07-01 21:08 ` Pip Cet
2024-07-02 11:25 ` Eli Zaretskii
2024-07-03 18:46 ` Pip Cet
2024-07-03 19:20 ` Eli Zaretskii
2024-06-29 22:59 ` Stefan Monnier
2024-06-30 5:02 ` Gerd Möllmann [this message]
2024-06-30 5:29 ` Eli Zaretskii
2024-06-30 15:04 ` Stefan Monnier
2024-06-30 5:11 ` Eli Zaretskii
2024-06-30 4:57 ` Eli Zaretskii
2024-06-30 5:36 ` Gerd Möllmann
2024-06-30 12:25 ` Ihor Radchenko
2024-06-29 17:19 ` Ihor Radchenko
2024-06-29 18:05 ` Gerd Möllmann
2024-06-29 18:10 ` Eli Zaretskii
2024-06-29 18:17 ` Gerd Möllmann
2024-06-29 18:28 ` Ihor Radchenko
2024-06-29 17:20 ` Eli Zaretskii
2024-06-29 18:04 ` Gerd Möllmann
2024-06-29 17:16 ` Stefan Monnier
2024-06-29 18:12 ` Gerd Möllmann
2024-06-29 18:30 ` Stefan Monnier
2024-06-29 18:52 ` Gerd Möllmann
2024-06-29 21:20 ` Gerd Möllmann
2024-06-29 21:38 ` Gerd Möllmann
2024-06-30 7:11 ` Gerd Möllmann
2024-06-30 7:27 ` Gerd Möllmann
2024-06-30 7:45 ` Ihor Radchenko
2024-06-30 10:44 ` Gerd Möllmann
2024-06-30 11:23 ` Ihor Radchenko
2024-06-30 11:25 ` Gerd Möllmann
2024-06-30 11:31 ` Ihor Radchenko
2024-06-30 12:13 ` Gerd Möllmann
2024-06-30 12:18 ` Ihor Radchenko
2024-06-30 12:17 ` Ihor Radchenko
2024-06-30 12:28 ` Gerd Möllmann
2024-06-30 12:38 ` Ihor Radchenko
2024-06-30 12:48 ` Gerd Möllmann
2024-06-30 15:21 ` Ihor Radchenko
2024-06-30 15:32 ` Gerd Möllmann
2024-06-30 12:49 ` Eli Zaretskii
2024-06-29 15:17 ` Ihor Radchenko
2024-06-28 4:07 ` 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=m2o77j2fch.fsf@pro2.fritz.box \
--to=gerd.moellmann@gmail.com \
--cc=eliz@gnu.org \
--cc=eller.helmut@gmail.com \
--cc=emacs-devel@gnu.org \
--cc=monnier@iro.umontreal.ca \
--cc=yantar92@posteo.net \
/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.