From: "Gerd Möllmann" <gerd.moellmann@gmail.com>
To: Eli Zaretskii <eliz@gnu.org>
Cc: yantar92@posteo.net, monnier@iro.umontreal.ca,
emacs-devel@gnu.org, eller.helmut@gmail.com
Subject: Re: MPS: dangling markers
Date: Sat, 29 Jun 2024 19:17:21 +0200 [thread overview]
Message-ID: <m2wmm77joe.fsf@pro2.fritz.box> (raw)
In-Reply-To: <m24j9b8ymo.fsf@pro2.fritz.box> ("Gerd Möllmann"'s message of "Sat, 29 Jun 2024 19:09:03 +0200")
Gerd Möllmann <gerd.moellmann@gmail.com> writes:
> Eli Zaretskii <eliz@gnu.org> writes:
>
>>> From: Gerd Möllmann <gerd.moellmann@gmail.com>
>>> Cc: Stefan Monnier <monnier@iro.umontreal.ca>, emacs-devel@gnu.org, Eli
>>> Zaretskii <eliz@gnu.org>, eller.helmut@gmail.com
>>> Date: Sat, 29 Jun 2024 16:56:10 +0200
>>>
>>> Ihor Radchenko <yantar92@posteo.net> writes:
>>>
>>> > I did a small perf benchmark generating large agendas multiple times,
>>> > and got the following output:
>>> >
>>> > 36.34% emacs emacs [.] igc_remove_marker
>>> > 35.77% emacs emacs [.] igc_add_marker
>>> > 3.41% emacs emacs [.] buf_charpos_to_bytepos
>>> > 2.12% emacs emacs [.] re_search_2
>>> > 1.60% emacs emacs [.] re_match_2_internal
>>> > 1.13% emacs emacs [.] exec_byte_code
>>> > 0.95% emacs emacs [.] buf_bytepos_to_charpos
>>> >
>>> > I guess O(N) is not all the fast, after all :)
>>>
>>> Thanks for testing it, and yeah O(n) isn't that great. Bad is that I
>>> have no idea how to improve that ATM :-/.
>>
>> I think we can use a completely different data structure for
>> character-to-byte conversions. There's no need to use markers for
>> that, and there's no need to create extra markers. We could instead
>> maintain an itree of positions with their character and byte values,
>> as a field of 'struct buffer' that is not exposed to Lisp.
>>
>> WDYT?
>
> I must admit that my overview of that whole area is pretty limited.
> I only remember that markers were always kind of a problem :-).
>
> Would such a data structure be similar to recording deletions/insertions
> of buffer text? Or, maybe in other words, what would entries contain,
> and when would entries be inserted/removed/changed? (Somehow, this
> reminds me a bit of a piece table, if you remember, but without holding
> the text...)
>
> Anyway, it's a lot of work, of course. So far, with the kind of buffers
> I use I don't notice anything. I don't know if the figure of 500K
> markers is real, but that sounds erm strange...
And let me add a question: do we know for sure that these markers stem
from char<->byte position code?
next prev parent reply other threads:[~2024-06-29 17:17 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 [this message]
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
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=m2wmm77joe.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.