Subject: Re: bug#76538: 31.0.50; 31.0.50; 31.0.50; feature/igc: using magit-section-cycle-global (S-TAB) and magit-section-toggle (TAB) in some random ways blocks GNU Emacs.

From: Gerd Möllmann <[email-masked]>
Date: Fri, 28 Feb 2025 06:09:03 +0100

Stefan Monnier <[email-masked]> writes:

>> FYI, I tried various tweaks to that loop while debugging and concluded
>> that DO_MARKERS loop is not the main bottleneck in this particular bug
>> report.
>
> The DO_MARKERS is probably not the main bottleneck nowadays, because the
> code explicitly reduces the "estimated benefit" of remaining in the loop
> at each iteration and exits once that gets too small.
>
> But that just pushes the problem to the subsequent bytes-scan.
>
> The main problem is simply that we need to make sure some nearby
> (cache-)marker is found near the "beginning" of the set of markers we
> consider.  Once this set becomes large the ordering between the markers
> becomes super-important.  The code on `master` behaves a bit like an
> "move to front" policy which works fairly well for the usual locality
> properties of buffer navigation, whereas the code on the `igc` branch
> has a tendency of putting new entries near the end where they risk not
> being found at all, making the cache ineffective.

Right, the order is important because the DO_MARKERS loop relies on the
assumption that cache-markers are found "early" in the loop. Or that's
how I understand it.

>From just reading the code again, and taking into account what Pip
said about the number of markers being created, I think what happens
in igc is something like this, in buf_charpos_to_bytepos.

Let's say we have initially our array of markers [m1, m2, m3, ...]. We
are looping over the array with DO_MARKERS. With each round, we decrease
our expectations what a good enough marker looks like. M1 would have to
be relatively close to the position we are looking for, m2 not so close,
m3 may be even farther away, and so on.

Okay. Let's say we don't find our position, and add a cache-marker.
The array now looks like [m1, m2, m3, ..., c1, ...].

Next time in the function, we loop again. We compare with m1, then m2,
m3 as before. But there is nothing saying that we'll reach c1. We add
c2 and now have [m1, m2, m3, ..., c2, c1, ...].

And so on, and so on. And we can't really say where c1 and c2 are added
in the array. That depends on the free-list, which depends on how
markers are added/removed or weakly fixed (fix_marker_vector).

Do we know how often fix_marker_vector runs?

In any case, I think I would try to change DO_MARKERS to start at the
end of the marker vector. If fix_marker_vector runs often enough one
could also "straighten" the free-list there, maybe.

(Sorry, I can't bring me to dive deep into this, ATM.)