Re: MPS: dangling markers

[Gerd Möllmann]

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