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

From: Gerd Möllmann <[email-masked]>
Date: Fri, 25 Apr 2025 14:22:30 +0200

Eli Zaretskii <[email-masked]> writes:

>> From: Gerd Möllmann <[email-masked]>
>> Cc: [email-masked],  [email-masked],
>>   [email-masked],  [email-masked]
>> Date: Fri, 25 Apr 2025 13:40:47 +0200
>> 
>> Eli Zaretskii <[email-masked]> writes:
>> 
>> > 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.
>
> We were talking about different aspects, sorry.
>
> Regarding the issue with a marker vector where some slots are free, we
> could simply compare with NULL.  Or we could keep a pointer to the
> next non-free slot.  Not sure what should be cheaper, since iteration
> over all the markers is quite frequent, whereas adding and removing
> markers is probably less so.
>
>> 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.
>
> Compacting the vector would also be possible, and I'm not sure it will
> be too expensive, since memcpy is quite fast on modern machines.
>
> All of this is not very important, except that we are talking about
> simplifications of FOR_EACH_MARKER macro, so if any of this
> facilitates a simpler macro without hampering performance, I'd suggest
> to consider it seriously.

(Just to mention an important aspect to keep in mind:

Some iteration over markers in master are for adjusting marker
positions, and these positions are held in the marker objects
themselves. These loops touch memory memory "all over the place".

In scratch/text-index, the marker positions are kept in the marker
vector, and adjusting positions can be done by accessing only the vector
from left to right. I think that is very CPU-cache-friendly. I would
expect that to be *much* faster than in master.)