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

[Stefan Kangas]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

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

This sounds great.  I pushed a couple of typo fixes while reading the
patches, please use them as you see fit (squash, etc.).

- Any chance you could add a comment explaining how you arrived at
  text_index_interval=4*1024?  If it's arbitrarily chosen, adding a
  comment to that effect might be useful.

- Maybe rename `text-index-interval` to `text-index--interval` (to
  indicate that it's internal)?

- I guess `use-text-index` can be removed?

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

For posterity, I guess that would be:

Re: Question about region caches
https://lists.gnu.org/r/emacs-devel/2025-03/msg01382.html

PS. BTW, a small procedural thing.  Instead of merging master into a
    scratch/ branch, I recommend deleting the branch, rebasing it on
    master, and then pushing it again.  This way, when we later merge it
    into master, we avoid the merge commits, and the history is kept
    clean and more easily reviewable.  Not the end of the world either
    way, but something to consider.