Re: MPS: dangling markers

[Gerd Möllmann]

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?