Re: Some experience with the igc branch

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

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Gerd Möllmann <gerd.moellmann@gmail.com>
>> Cc: pipcet@protonmail.com,  ofv@wanadoo.es,  emacs-devel@gnu.org,
>>   eller.helmut@gmail.com,  acorallo@gnu.org
>> Date: Thu, 26 Dec 2024 06:25:33 +0100
>> 
>> Eli Zaretskii <eliz@gnu.org> writes:
>> 
>> >> >>   https://memory-pool-system.readthedocs.io/en/latest/guide/index.html#
>> >> >> 
>> >> >> help?
>> >> >
>> >> > Not really.  Their documentation is (a) too vague/abstract/circular
>> >> > (i.e., stuff is not explained for itself, but instead they
>> >> > cross-reference to some other stuff -- e.g., try to understand what is
>> >> > a "root"), and (b) not specific to Emacs, so the relation between MPS
>> >> > terminology and Emacs objects is missing.
>> >> 
>> >> Too bad. In that case, I guess I should consider to begin to think about
>> >> planning to start to try write something up. That's a bit like pulling
>> >> teeth, TBH. Don't know how long that will take.
>> >
>> > Thanks.  No matter how long it will take, it will be shorter than
>> > eternity.
>> 
>> Did what I wrote in this thread help you understand/judge what I
>> proposed better? Please ask further questions if you want.
>
> It does help, to some extent.  But I'm still in the dark regarding
> some aspects of this.  I'll keep asking questions, but there's a limit
> to which I feel myself entitled to ask questions without annoying too
> much.  Which is why I suggested to write commentary instead, to get
> some of the basics out of the way.  It doesn't have to be you
> personally who writes the commentary, btw: anyone who knows the
> answers to the questions I posted could do that.  With that in mind,
> let me again post the questions which I'm currently struggling with:
>
>   . what are "roots"?
>   . what is the purpose of each root_create_SOMETHING function in igc.c?
>   . what is the difference between "exact" and "ambiguous" roots, and
>     when should we use each one in Emacs?

Coincidentally, I wrote this today, which might help, and would also be
interesting to get some feedback for. 

* Introduction / Garbage collection

Implementing a programming language like Lisp requires automatic
memory management which frees the memory of Lisp objects like conses,
strings etc. when they are no longer in use. The automatic memory
management used for Lisp is called garbage collection (GC), which is
performed by a garbage collector. Objects that are no longer used are
called garbage or dead, objects that are in use or called live
objects. The process of getting rid of garbage is called the GC.

A large number of GC algorithms and implementations exist which differ
in various dimensions. Emacs has two GC implementations which can be
chosen at compile-time. The traditional (old) GC, which was the only
one until recently, is a so-called mark-sweep, non-copying collector.
The new GC implementation in this file is an incremental,
generational, concurrent (igc) collector based on the MPS library from
Ravenbrook. It is a so-called copying collector. The terms used here
will become clearer in the following.

Emacs' traditional mark-sweep GC works in two phases:

1. The mark phase

   Start with a set of so-called (GC) roots that are
   known to contain live objects. Examples of roots in Emacs are

   - the bytecode stacks 
   - the specpdl (binding) stacks
   - Lisp variables defined in C with DEFVAR
   - the C stacks (aka control stacks)
   - ...

   Roots can be either exact or ambiguous.

   If we know that a root always contains a valid Lisp object
   reference it is called exact. Example for an exact root would be
   the root for a DEFVAR. The DEFVAR variable always contains a valid
   Lisp object.

   If we only know that a root might potentially reference a Lisp
   object, that root is called ambiguous. An example for an ambigupus
   root is the C stack. The C stack can contain integers that look
   like they are a reference to a Lisp object, but actually look like
   that only by happenstance. Ambiguous roots are said to be scanned
   conservatively. We make the conservative assumption that we
   actually have seen a valid reference, even if it is actually not.

   GC scans all roots, conservatively or exact, and marks the Lisp
   objects found in them live, plus all Lisp objects reachable from
   them, recursively. In the end, all live objects are marked, and all
   objects not marked are dead, i.e. garbage.

2. The sweep phase.

   Sweeping means to free all objects that are not marked live. The
   collector iterates over all allocated objects, live or dead, and
   frees the ones that are dead so that their memory can be reused.

The traditional mark-sweep GC implementation is

- Not concurrent. Emacs calls GC explicitly in various places, and
  proceeds only when the GC is done.
- Not incremental. The GC is not done in steps.
- Not generational. The GC doesn't take advantage of the so-called
  generational hypothesis, which says that most objects used by program
  die young, i.e. are only used for a short period of time. Other GCs
  take this hypothesis into account to reduce pause times.
- Not copying. Lisp objects are never copied by the GC. They stay at
  the addresses where they their initial allocation puts them. Special
  facilities like allocation in blocks are implemented to avoid memory
  fragmentation.

In contrast, the new igc collector, using MPS, is

- Concurrent. The GC runs in its own thread. There are no explicit
  calls to start GC, and Emacs doesn't have to wait for the GC to end.
- Incremental. The GC is done in steps.
- Generational. The GC takes advantage of the so-called
  generational hypothesis.
- Copying. Lisp objects are copied by the GC, avoiding memory
  fragmentation. Special care must be taken to take into account that
  the same Lisp object can have different addresses at different
  times.

The goal of igc is to reduce pause times when using Emacs
interactively. The properties listed above which come from leveraging
MPS make that possible.

* MPS

A guide and a reference manual for MPS can be found at
https://memory-pool-system.readthedocs.io.

It is recommended to read at least the Guide. And what else to write I
don't know.

* Registry

MPS provides an API of C functions that an application can use to
interface with the MPS. For example, MPS cannot know what the GC roots
of an application are, or what threads the application considers
relevant for GC. So, MPS provides functions that an application can
use to define its roots and threads.

The MPS functions typically return a handle to an MPS object created
for what is defined by them. For example, when we define a root with
mps_root_create_area, MPS gives us a mps_root_t handle back. The
handles returned can later be used to change or delete what we
created. For example, we use the handle we got from MPS for a root to
destroy the root with mps_root_destroy.

All MPS handles we create, we collect in a global registry of type
struct igc which is stored in the global variable global_igc and can
be accessed from amywhere. 

* Initialization
 - Roots
 - Threads
 - Pools, Object formats
* Lisp Object Allocation
Object Header?
* Malloc with roots
* Memory barriers