GNU bug report logs - #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.

Previous Next

Full log

Message #38 received at 76538 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Ihor Radchenko <yantar92 <at> posteo.net>
Cc: joaomoreira <at> gmx.se, Eli Zaretskii <eliz <at> gnu.org>, 76538 <at> debbugs.gnu.org,
 eller.helmut <at> gmail.com, pipcet <at> protonmail.com
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.
Date: Wed, 26 Feb 2025 14:57:42 -0500

>> ??? 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.

FWIW, I have a branch `scratch/markers-as-gap-array` where I replace the
linked list of markers with an "array with a gap" where markers are
sorted, so we use a binary search.  It might help in your case.

It was pretty close to be "ready to merge" at some point, except that
I had trouble convincing myself that it was a clear win: in my tests, it
made `save-excursion` slower (the current naïve data-structure is ideal
for most "trivial" uses of `save-excursion`: we create a marker,
push it onto the head of the list, do a bit of unrelated work in the
body and then come back and just pop the marker that's still at the head
of the list) and the cases where it makes the code faster are hard to
come by, other than artificial micro-benchmarks.

>> How small?
> 8-11k.

I'd expect around 20MB / 5kB = 4k markers, so that seems about right.

> Probably, not that small after all in terms of absolute numbers.

Definitely not small if you scan it linearly/naïvely.

> 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.

We already limit the max number of iterations by increasing
progressively the distance considered "close enough", so maybe the
problem is simply that we have to choose between spending too much time
in the linear scan of the list of markers or we have to spend too much
time in the linear scan of the chars.

If that's the case, my branch should help significantly.

> 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).

Indeed those cache-markers are referenced only weakly so they currently
disappear at every GC.  I can't remember if I kept this behavior in my
branch, but I remember considering some alternative where we keep every
other weak marker.


        Stefan

Previous Next

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