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: Pip Cet <[email-masked]>
Date: Sat, 01 Mar 2025 13:33:54 +0000

Gerd Möllmann <[email-masked]> writes:

> Gerd Möllmann <[email-masked]> writes:
>
>> Gerd Möllmann <[email-masked]> writes:
>>
>>> Gerd Möllmann <[email-masked]> writes:
>>>
>>>> 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.
>>>
>>> Or one could build a doubly-linked list of markers in most-recently
>>> created order. But that would mean 3 array slots per marker in the
>>> marker vector. Don't know.
>>
>> Which would be something like the attached. Can someone try this with
>> the original recipe? (It's a quick sketch, and blah blah.)

Performance seems slightly better, but not as good as disabling the
bytepos<->charpos cache entirely and skipping the DO_MARKERS loop.

OTOH, it's not worse!  And keeping the markers in an effectively
doubly-linked list allows us to sort them whatever way we want.

> And I think I'll keep that. It makes an overall nicer implementation of
> DO_MARKERS, keeps add and remove O(1), and provides iteration in
> most-recently added order, which should be the same as without igc.

I think we might want to sort markers at some point:  if we start out
with the median marker, then the 25-percentile one, then the
75-percentile one, etc., we should arrive at an acceptable one fairly
early without changing the scanning code at all!

(In more detail, I think we should start with any marker, then choose
the one with the greatest distance to all previously-chosen ones next,
recursively.  I don't remember whether there's a particularly efficient
algorithm to do that in the general case, but in the linear case, it's
pretty simple, just build a btree and emit it in depth-first order.  Fun
fact: do the same with a visual color metric and you get a usable color
scheme!).

> I like it :-). Until something better comes along, of course.

I still think I have "something better" in my head, but it's not so much
in code form yet, and work on that is quite slow right now, for various
reasons, so having a no-worse-than-master solution is important!

So I'd be happy to see this merged!  If it improves performance to be
acceptable, that's most likely sufficient, as far as this problem goes,
for merging feature/igc (which I still believe in), even though the
xdisp.c change (invisible.patch) I proposed (and analogous ones) should
improve things a lot for magit even on master.

Pip