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

Previous Next

Full log

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

From: Eli Zaretskii <eliz <at> gnu.org>
To: Gerd Möllmann <gerd.moellmann <at> gmail.com>
Cc: monnier <at> iro.umontreal.ca, 77924 <at> debbugs.gnu.org
Subject: Re: bug#77924: 31.0.50; [Feature branch] Change marker implementation
Date: Sat, 19 Apr 2025 19:32:42 +0300

> Cc: Stefan Monnier <monnier <at> iro.umontreal.ca>
> From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
> 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?

Previous Next

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