Subject: 31.0.50; [Feature branch] Change marker implementation

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.