Subject: Re: bug#77924: 31.0.50; [Feature branch] Change marker implementation

From: Eli Zaretskii <[email-masked]>
Date: Sat, 19 Apr 2025 19:32:42 +0300

> Cc: Stefan Monnier <[email-masked]>
> From: Gerd Möllmann <[email-masked]>
> Date: Sat, 19 Apr 2025 18:05:38 +0200
> 
> This is about the branch scratch/text-index on savannah, which is a port
> of what I have in my Emacs.
> 
> The branch changes the implementation of Lisp markers.
> 
> - Markers no longer form a doubly-linked list, they are stored in a
>   marker vector instead which allows O(1) insertion and deletion of
>   markers. (The idea of a marker vector is from what I did in igc. In my
>   Emacs, both igc and old GC use the same marker vector implementation.
>   The new one is different from the one in feature/igc.)
> 
> - Lisp_Marker doesn't contain the character position directly. It is
>   stored in the marker vector instead. This leads to faster,
>   cache-friendly, marker position adjustments.
> 
> - Markers don't contain byte positions. Byte positions are computed when
>   needed. Bytepos <-> charpos conversion are done using a text-index
>   data structure. This removes the heuristics currently used in master,
>   and allows removing byte positions from markers.
> 
> In summary, I'd say performance is good, to say the least, in many cases
> better, and it fixes corner cases leading the abysmal performance in
> current master.
> 
> Please see the comments at the start of marker-vector.c and text-index.c
> for more details. Also see the thread(s) on emacs-devel with Stef an me.

Thanks.

Are there any backward-incompatible changes with this?

Do all the tests still pass as well as they did before these changes?