Re: MPS: dangling markers

[Eli Zaretskii]

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