fasterMes: 02: garbage collection and preserve/releaseHEADmaster

1 files changed, 274 insertions, 0 deletions

diff --git a/content/fasterMes/02_garbage_collector.md b/content/fasterMes/02_garbage_collector.md
new file mode 100644
index 0000000..8b7ee26
--- /dev/null
+++ b/content/fasterMes/02_garbage_collector.md
@@ -0,0 +1,274 @@
+Title: GNU Mes and garbage collection
+Date: 2025-09-17
+Category:
+Tags: GNU Mes interpreter speedup
+Slug: fasterMes2
+Lang: en
+Summary: How does the GNU Mes garbage collector work and how to improve it.
+
+In our previous blogpost in the series we described how GNU Mes' scheme
+interpreter handles evaluation and how fast it was. There were some details
+that weren't really obvious, though: why does it really do all that magic to
+emulate function calls? Is it just to make it look like scheme?
+
+In this blog post we'll explain how does the garbage collector work in GNU Mes,
+try to take a new look to the `eval_apply` function from the perspective of the
+garbage collector, and propose an improvement that would enable a different
+style of programming.
+
+### GNU Mes' garbage collection
+
+GNU Mes' scheme interpreter has a very simple approach to memory management. It
+allocates a big chunk of memory when the interpreter is run and that is used
+for every scheme value. All scheme values are represented with the same
+`struct`, called `struct scm`, and every `make_`whatever function returns a
+pointer to an `struct scm` bump-allocated in that big chunk of memory which
+we'll call *arena*.
+
+The bump-allocation is very easy to do, and doesn't require much computation.
+It's just in increase in the pointer to the first free element in the *arena*.
+
+If we just had this, our scheme interpreter would just eat memory and never
+release or reuse the space we allocated for the scheme values we are not using
+anymore. This is a possible approach, really, but GNU Mes does provide garbage
+collection so the memory is reused and we don't run out of our precious
+resource.
+
+Mes uses a stop-the-world copying garbage collector. Similar to the one
+described in the "Structure and Interpretation of Computer Programs" (aka SICP)
+book or the one described in [This Wikipedia entry about Cheney's garbage
+collection algorithm based on a paper from 1970][cheney-wiki]. It starts in few
+scheme values and copies them from the current arena to some other piece of
+memory, one after the other. It also check their internal values like elements
+in a list, a vector or so on, and copies those too, adjusting the pointers that
+refer to them. When a scheme value is copied, its memory representation is
+tagged with a *broken heart* (this appears in SICP), something that identifies
+that value as already processed, and the pointer to the new location replaces
+its value. Now, it can check if an object that is being copied points to a
+value that has been already copied, and in that case, it only needs to update
+the pointer of its reference.
+
+[cheney-wiki]: https://en.wikipedia.org/wiki/Cheney%27s_algorithm
+
+Once all the objects and its references have been processed, what we have is a
+new memory space that contains only the objects in use, one after the other,
+with no empty spaces in between. This is why this process is called also a
+compacting garbage collector.
+
+In Mes, once the new piece of memory is set up, it is moved back to the
+original position, element by element (remember all elements are the same
+size). In a process that in Mes is called `flip`. The goal of the flip is to
+keep the memory footprint low, only requiring a maximum memory of the twice of
+the current memory usage (and oftentimes way less) which, potentially, is
+smaller than having two fixed semi-spaces as this kind of garbage collectors
+often have.
+
+But now two things are left to explain: when is this whole process run and how
+it is kickstarted.
+
+The garbage collector is run during the interpreter execution. When the
+interpreter's programmer decides to (by adding a call to the garbage collection
+function, `gc_check`). This function will check if the memory usage is large
+enough so the garbage collecting is worth the effort and, in affirmative case,
+then run the garbage collector process.
+
+The first thing the garbage collection process does is copy a group of objects
+that will kickstart the copying of the rest of the *live* objects, meaning
+those objects that the running scheme program still has access to. Those
+objects are called *roots*, and they are fundamental to understand how this
+whole thing can be improved. The roots, more than being a great hip hop band,
+are easy to deduce what they can be in the interpreter: the current
+*environment*, the *stack*, the known symbols, and such.
+
+Currently in Mes the roots are fixed, meaning they are hardcoded in the code,
+like so:
+
+``` clike
+  struct scm *new_cell_nil = g_free;
+  struct scm *s;
+  for (s = cell_nil; s < g_symbol_max; s = s + M2_CELL_SIZE)
+    gc_copy (s);
+
+  g_symbols = gc_copy (g_symbols);
+  g_macros = gc_copy (g_macros);
+  g_ports = gc_copy (g_ports);
+  scm_hash_table_type = gc_copy (scm_hash_table_type);
+  scm_variable_type = gc_copy (scm_variable_type);
+  M0 = gc_copy (M0);
+  M1 = gc_copy (M1);
+
+  long i;
+  for (i = g_stack; i < STACK_SIZE; i = i + 1)
+    copy_stack (i, gc_copy (g_stack_array[i]));
+
+  gc_loop (new_cell_nil);
+```
+
+### The issues
+
+This kind of copying garbage collectors have a really two very obvious
+problems that affect the way we write our C code.
+
+Consider this code:
+
+``` clike
+struct scm *val = make_number (10); // Makes a scheme value = 10
+gc_check ();                        // May garbage collect
+val->value;                         // What do we have there?
+```
+
+If we make a number like in the example and then garbage collect, the number
+will be allocated in the *arena*, but during garbage collection it won't have
+anything pointing to it so it would be cleaned from the memory. Interestingly
+enough, it won't probably produce a segfault or any kind of error like that,
+because it will try to access to the *arena*, and that's valid memory, but
+it would still explode in very dirty ways afterwards, maybe after some other
+garbage collection loops. Nasty stuff.
+
+Also, even if you keep the variable from being collected, it would be moved by
+the garbage collector, which will give you a very low chance of the value
+falling in the same spot, so your pointer would be outdated, and you wouldn't
+have any way to know where the variable is now.
+
+Do you want an easy solution?
+
+First, register that `val` as another root in the garbage collector, so it's
+not lost in each loop. The current garbage collector in Mes needs to hardcode
+the roots, so if this example were just a local variable for a function, you'd
+need to make it global for the garbage collector to find it. Of course, you
+shouldn't do this for every single variable in your code, but if you make sure
+you only need a couple of temporaries you could call them `R1` and `R2` and use
+those all the time for everything[^oh-yes].
+
+[^oh-yes]: Oh! Yes! I know what you are thinking. Trust me.
+
+That would leave you with the moving problem. After a garbage collector run,
+your variables `R1` and `R2` could potentially point to a memory location where
+they are not anymore, because of the copying.
+
+At this point if you were really inspired, you could implement a stack of those
+lets call them "*registers*" (`R1`, `R2`...), register it as a root, and there
+you would have emulated a function call system that respects your garbage
+collector. Oh! *But isn't that what we described in the previous blog post?*
+
+Implementing a stack that knows where to push and where to pop (those global
+registers) would make every single piece of your code keep your pointers to the
+variables coherent in the C world. You would just need to refer to `R1` or
+whatever, and it would always point to the proper memory location after the pop
+is run.
+
+But of course this is a little bit of a Henry Ford situation here: *"everybody
+will have a car of the color they like as long as it is black"*. So you can
+have all the variables you want as long as they are `R0`, `R1`...
+
+
+### One solution
+
+Consider this code:
+
+``` clike
+struct scm *
+macro_expand_program (struct scm *program)
+{
+  struct scm *cursor = program;
+  gc_preserve (&program);
+  for (cursor = program; cursor != cell_nil; cursor = cursor->cdr)
+    {
+      gc_preserve (&cursor);
+      cursor->car = macro_expand_expr (cursor->car); // May GC
+      gc_release (1); // cursor
+    }
+  gc_release (1); // program
+  return program;
+}
+```
+
+In this piece of code we can see how `macro_expand_expr` could try to garbage
+collect and make us lose references to our local variables. By calling
+`gc_preserve` we register them as roots, and we can release them later, when we
+don't need them anymore. We send the address to the pointer to the garbage
+collector so it's able to fix the pointers when the copying is done.
+
+This looks boring and boilerplatey, but we would only need it for those
+variables that would cross the function barrier to functions that we know that
+may garbage collect. The rest of the cases we can just use an ordinary C
+variable without preservation.
+
+The improvements I see here is we can call the variables whatever we want, use
+as many as we want and actually use C function calls without all the `goto` and
+`push_cc` ceremony we described in the previous article, which is also
+extremely confusing to me.
+
+Also, we could get rid of all the other global roots pushing them first and
+never releasing them.
+
+#### How is this thing implemented
+
+I have to admit it's not the greatest solution in the world but it works well
+enough if you are careful.
+
+First, I added a new scheme value type for roots, that can store a reference to
+an scheme value and the address of the pointer to update. It just covers the
+simplest case.
+
+The `gc_preserve` function adds a root to a global list of preserved roots. The
+`gc_release` function removes the top `n` elements from the list of preserved
+roots.
+
+With that ready, the garbage collector only needs to handle that global list as
+any other hardcoded root we mentioned before, but after the `gc_flip` the
+pointers stored in the roots themselves are updated. This means the pointers in
+our C code would be updated when we exit the garbage collection operation,
+keeping our C pointers consistent with the memory.
+
+So, that leaves us with this copy step:
+
+``` diff
+@@ -647,6 +695,8 @@ gc_ ()
+     gc_copy (s);
+
+   g_symbols = gc_copy (g_symbols);
++  if (g_preserved != NULL)
++    g_preserved = gc_copy (g_preserved);
+   g_macros = gc_copy (g_macros);
+   g_ports = gc_copy (g_ports);
+   scm_hash_table_type = gc_copy (scm_hash_table_type);
+```
+
+And this flip step:
+
+``` diff
+@@ -464,6 +503,15 @@ gc_flip ()
+   long dist = g_news - g_cells;
+   g_free = g_free - dist;
+   g_symbols = g_symbols - dist;
++  if (g_preserved != NULL)
++    {
++      g_preserved = g_preserved - dist;
++      /* Update the preserved pointers */
++      struct scm *s;
++      for (s = g_preserved; s != cell_nil; s = s->cdr)
++        *(s->car->ptr) = s->car->car;
++    }
++
+   g_macros = g_macros - dist;
+   g_ports = g_ports - dist;
+   scm_hash_table_type = scm_hash_table_type - dist;
+```
+
+As my roots are copied and flipped the values they point at are also copied and
+flipped. That way I only need to update the pointers using the new address of
+the pointed objects.
+
+And that's it.
+
+The only thing missing is to use the `gc_preserve` and `gc_release` properly.
+It's easy to misuse them and overrelease or overpreserve.
+
+I'm writing a macro expander using this and happens to be somewhat comfortable,
+at least way more comfortable than the goto and `push_cc` style. I was having a
+very hard time with that one.
+
+We'll see how it goes.
+
+Cheers!