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: Ihor Radchenko <[email-masked]>
Date: Wed, 26 Feb 2025 17:39:39 +0000

Eli Zaretskii <[email-masked]> writes:

>> The reproducer involves 20+Mb magit buffer with a lot of text hidden.
>> I toyed around with gdb a bit, and it appears to me that the problem is
>> not with the number of markers. Rather an opposite. Marker cache does
>> not help here initially and we need to scan all the way through 20Mb of
>> bytes.
>
> ??? AFAIR, we perform binary search there, no?

No. AFAIU, the search goes like the following:

1. Go through all the buffer markers and find the nearest marker to
   charpos/bytepos
   [ This is O(num_of_markers) on master and O(length_of_marker_array)
   on feature/igc ]
2. Starting from the nearest marker, scan bytes symbol by symbol until
   we find the requested charpos/bytepos
   [ O(distance to nearest marker) ]
3. While scanning, every 5000 bytes, create a new marker to cache the
   charpos and bytepos.

> Can you show the details of what you saw in GDB?

Here is what I did:
1. I modified the marker scan in buf_charpos_to_bytepos to record the
   number of markers in buffer (just stored it in a C variable)
2. I followed the reproducer (C-p from point-max) and paused Emacs from
   gdb while Emacs was hanging, looking at the backtrace and checking
   the number of markers
3. I observed ~8-11k markers in the buffer. Notably, the number of
   markers often decreased while runnign buf_charpos_to_bytepos,
   indicating that the marker list is cleaned up along the way.

>> In my testing, I looked into the total number of markers in the buffer,
>> and it appears that the number is always fairly small.
>
> How small?

8-11k. Probably, not that small after all in terms of absolute numbers.
The reason why it is small in my mind is that limiting the loop over
markers to 50 iterations max did not speed things up.

>> May someone more familiar with the code check if markers created in
>> buf_charpos_to_bytepos might be created and immediately GCed? That's my
>> impression (maybe totally wrong).
>
> Why is the immediate GC a problem?  And why do you think there is an
> immediate GC?  And finally, are we still talking about the igc branch
> or about master (or both)?

I compared with Emacs 30. Emacs 30 takes a few seconds for C-p to work
and then does not hang (presumably, marker cache is populated). On
feature/igc, I did not manage to wait enough for C-p to compelte
(minutes).

Why do I think that there is an immediate GC? It is a guess (possibly
incorrect). My guess is originating from the fact that
bug_charpos_to_bytepos is calling build_marker directly to cache buffer
positions. However, the returned Lisp object is not used and thus
probably not referenced by any of the roots (it does get stored in the
buffer's marker list - but that's a weak array). So, there is a chance
that it can be collected the next time IGC decides to run the
collection.  Given that we produce a large number of markers in
buf_charpos_to_bytepos, that "next time" might be very soon.
But I may be misunderstanding something important about how IGC code
works.

-- 
Ihor Radchenko // yantar92,
Org mode maintainer,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>