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

Previous Next

Full log

View this message in rfc822 format

From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: pipcet <at> protonmail.com, monnier <at> iro.umontreal.ca, 77924 <at> debbugs.gnu.org, stefankangas <at> gmail.com
Subject: bug#77924: 31.0.50; [Feature branch] Change marker implementation
Date: Fri, 25 Apr 2025 13:40:47 +0200

Eli Zaretskii <eliz <at> gnu.org> writes:

>> From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
>> Date: Fri, 25 Apr 2025 09:51:05 +0200
>> Cc: pipcet <at> protonmail.com, monnier <at> iro.umontreal.ca, 77924 <at> debbugs.gnu.org,
>>  stefankangas <at> gmail.com
>> 
>> 
>> Sent from my iPhone
>> 
>> > On 25. Apr 2025, at 09:45, Eli Zaretskii <eliz <at> gnu.org> wrote:
>> > 
>> > 
>> >> 
>> >> From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
>> >> Date: Fri, 25 Apr 2025 09:20:55 +0200
>> >> Cc: pipcet <at> protonmail.com, monnier <at> iro.umontreal.ca, 77924 <at> debbugs.gnu.org,
>> >> stefankangas <at> gmail.com
>> >> 
>> >> 
>> >>>> On 25. Apr 2025, at 09:01, Eli Zaretskii <eliz <at> gnu.org> wrote:
>> >>> 
>> >>> 
>> >>>> 
>> >>>> From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
>> >>>> Cc: Eli Zaretskii <eliz <at> gnu.org>,  monnier <at> iro.umontreal.ca,
>> >>>> 77924 <at> debbugs.gnu.org,  stefankangas <at> gmail.com
>> >>>> Date: Thu, 24 Apr 2025 21:53:05 +0200
>> >>>> 
>> >>>> Pip Cet <pipcet <at> protonmail.com> writes:
>> >>>> 
>> >>>>> I think what we should do is mimic FOR_EACH_TAIL, and use
>> >>>>> FOR_EACH_MARKER like this:
>> >>>>> 
>> >>>>> struct Lisp_Marker *m;
>> >>>>> FOR_EACH_MARKER (b, m)
>> >>>>> {
>> >>>>>   /* do something with m */
>> >>>>> }
>> >>>> 
>> >>>> We need an if somewhere for the MARKERP, don't we?
>> >>> 
>> >>> Why is that needed, btw?  Can't we change the representation and/or
>> >>> the functions involved to avoid the need for such a test?
>> >> 
>> >> When markers are freed their entry in the market vector no longer contains a marker reference.
>> > 
>> > I understand, but why does this need to be tested inside the loop?
>> > Can't the loop itself know how many markers are in the vector, and
>> > stop when they are exhausted?
>> 
>> You are thinking of compacting the vector when a marker is freed?
>> Then we would lose the O(1) deletion. As it is the entry is simply
>> pushed on a free list.
>
> Actually, I thought about maintaining the number of markers in the
> vector, so there would be no need to detect that by the MARKERP test.

Not sure how that would work, but maybe you are thinking of the LRU list
in igc.

Let's say we have a marker vector like [__M___M___] where _ means free,
and M stands for an entry of a live marker.

In feature/igc, the M entries are kept in a doubly-linked LRU list.
Iteration can then be done following the that list. The order in that
list is last recently used first, and the whole thing was needed to work
with the cache marker heuristic in charpos<->bytepos conversion. That
visits slots of the vector in unpredictable order.

The heuristics and cache markers are no longer used in
scratch/text-index, so the LRU list is no longer needed (= 2 words per
entry = doubling the entry size), and I removed it.

Iteration is done by stepping over all _ and M in order (= fast), and
only giving out at the M entries. And as a small optimization for the
case of over-allocation, I remember the max index of an M that was ever
used.

Previous Next

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