Re: MPS: dangling markers

["Gerd Möllmann" <gerd.moellmann@gmail.com>]

Ihor Radchenko <yantar92@posteo.net> writes:

> Related: bug#71644, bug#63040
>
> When running the scratch/igc branch, I noticed a severe slowdown (10x or
> more) of redisplay on my large Org buffers.
>
> - The redisplay manifests itself as I build agenda multiple times
>   (agenda creates many new markers).
>
> - perf points to (1) itree lookup; (2) bytepos<->charpos, which implies
>   that things may be related to the number of allocated markers and
>   overlays.
>
> - I observe things slowing down as the number of "PVEC_MARKER" in the
>   output of `igc-info' grows.
>
> - Forcing (igc--collect) returns speed to normal

Ok, interesting.

> I believe that my observation reveals one important point that may need
> to be considered when using MPS:
>
> We may need to more careful about cases in Emacs C code that traverse
> object lists that may contain unreferenced objects.  Because MPS does
> not perform GC as regularly as the traditional mark-and-sweep, some
> unreferenced objects may remain live and present in internal data
> structures for a long time.

Maybe it's helpful when I describe what I do for the buffer markers, as
opposed to what is done currently.

In master, buffer_text::markers is a singly-linked list of Lisp_Markers,
using Lisp_Marker::next. In the sweep phase of GC, in sweeo_buffers, we
iterate over all buffers and remove markers from the list that were not
marked during the mark phase of GC. The list itself is left alone in the
mark phase, so that references from these lists don't keep markers
alive. The buffer markers thus acts as a weak list. Since
garbage_collect is called often enough, markers are swiftly remnoved
from the marker lists.

What I've done in igc so far: buffer_text::markers is a Lisp vector and
Lisp_Marker::next is gone. Elements of the vector are either nil or a
marker. The vector is weak, entries for markers that are not referenced
from somewhere else are set to nil eventually. Adding and removing
markers is done naively in O(N) where N is the size of the vector. The
vectors are resized if needed by doubling their size. They are never
shrunk. Iteration goes over the whole vector, ignoring nil entries.

Possibly, there is some potential for improvement :-).

What we can't do is hope to make this weakness more "eager" so to say.
Entries in weak vectors are reset to nil, but when MPS thinks it's a
good time doing that. (It's BTW the wrong mental model to think of MPS
doing GC at a specific time. It's more like doing GC work all the time,
concurrently.) But it's true that MPS doesn't "eagerly" reset entries in
these vectors. And there's no way, to my knowledge, to force it to do
that other than to trigger a full GC.

Ideas welcome, or better yet implemenations :-). I'm currently not
working on this.

> AFAIK, at least overlays, buffers, and markers are used in C code within
> object lists/trees are often traversed in full. If objects in these
> lists are not regularly garbage-collected, we may end up in situation
> when dead objects significantly impact performance. I believe that what
> I observe locally is exactly the described scenario.

Probably.