From: "Gerd Möllmann" <gerd.moellmann@gmail.com>
To: Stefan Monnier <monnier@iro.umontreal.ca>
Cc: Ihor Radchenko <yantar92@posteo.net>,
emacs-devel@gnu.org, Eli Zaretskii <eliz@gnu.org>,
eller.helmut@gmail.com
Subject: Re: MPS: dangling markers
Date: Sat, 29 Jun 2024 20:12:39 +0200 [thread overview]
Message-ID: <m2frsv7h48.fsf@pro2.fritz.box> (raw)
In-Reply-To: <jwvikxru1fp.fsf-monnier+emacs@gnu.org> (Stefan Monnier's message of "Sat, 29 Jun 2024 13:16:27 -0400")
Stefan Monnier <monnier@iro.umontreal.ca> writes:
>>> 36.34% emacs emacs [.] igc_remove_marker
>>> 35.77% emacs emacs [.] igc_add_marker
>
> I don't understand this:
>
> - Why is `igc_remove_marker` slower than `unchain_marker`?
> `unchain_marker` is also O(N), but should have a worse constant
> because of the linked-list structure suffering much more from
> memory latency.
>
> - Why does `igc_add_marker` take as much time as `igc_remove_marker`?
> `igc_add_marker` only needs to find an empty spot (whereas
> `igc_remove_marker` needs to find the one and only spot that holds
> the marker), so while it's also O(N) in the worst case, it should be
> faster on average.
Yes, that doesn't make much sense to me either. add_marker even includes
allacaton/re-allocation costs.
Can it be that remove_marker is called much more often than add_marker?
@Ihor, do can see call counts?
void
igc_add_marker (struct buffer *b, struct Lisp_Marker *m)
{
Lisp_Object v = BUF_MARKERS (b);
if (NILP (v))
v = BUF_MARKERS (b) = alloc_vector_weak (1, Qnil);
ptrdiff_t i = find_nil_index (v);
if (i == ASIZE (v))
v = BUF_MARKERS (b) = larger_vector_weak (v);
Lisp_Object marker = make_lisp_ptr (m, Lisp_Vectorlike);
ASET (v, i, marker);
}
void
igc_remove_marker (struct buffer *b, struct Lisp_Marker *m)
{
m->buffer = NULL;
Lisp_Object v = BUF_MARKERS (b);
igc_assert (VECTORP (v));
Lisp_Object marker = make_lisp_ptr (m, Lisp_Vectorlike);
for (ptrdiff_t i = 0; i < ASIZE (v); ++i)
if (EQ (AREF (v, i), marker))
{
ASET (v, i, Qnil);
break;
}
}
> [ FWIW, I'm incidentally playing with an implementation of the "set of
> markers" as an ordered array-with-gap, so bytes<->chars conversions
> take O(log N) time for N markers, because we can use binary search.
> Removal and addition of a marker can also use the binary search to
> find the spot, tho it's still O(N) overall because of the need to move
> the gap, but hopefully the gap is usually nearby already (and the
> constant is much smaller because it's just a `memmove`).
> Mostly fighting with the pdumper now. ]
Hey, that's really really good! :-)
next prev parent reply other threads:[~2024-06-29 18:12 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
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 [this message]
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=m2frsv7h48.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.