GNU bug report logs - #77924
31.0.50; [Feature branch] Change marker implementation

Previous Next

Full log

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Cc: Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: 31.0.50; [Feature branch] Change marker implementation
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.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.