How Garbage Collection works in Crafting Interpreters

Crafting Interpreters is an awesome book by Robert Nystrom about interpreters, compilers, and programming languages. I love this book, because it teaches you how to build 2 interpreters line-by-line: a tree-walking interpreter in Java and then a bytecode virtual machine in C.

In Chapter 26, he builds a mark-and-sweep garbage collector and does a fantastic job explaining the algorithm with detailed diagrams and illustrations.

But I also wanted to understand how our implementation of mark-and-sweep worked, not just the algorithm. So in this post, I’m going to clarify how the garbage collector works as implemented, by examining a small toy-example he gives in the book and by going through a slightly-larger program that actually collects some garbage.

First up, let’s walk through an early example he shares in the chapter:

var a = "first value";
a = "updated";
// GC here.
print a;

Robert explains that the string "first value" could be collected because there is no variable referring to that value when the garbage collection runs on the 3rd line (and the string isn’t on the virtual machine’s stack).

It’s true in an abstract sense that "first value" could be collected without causing a problem, but the implementation works different¹:

1. "first value" is never collected:
   • the compiler creates a top-level function (referred to as <script>) that saves "first value" in the constants table during compilation. The compiler functions are explicitly marked in markCompilerRoots, so the constants won’t be collected.
   • After compilation, that function is converted to a closure and pushed on the virtual machine’s stack. All stack variables are also marked, so "first value" will really never be collected.
2. garbage collection runs on object allocation, not between statements:
   • garbage collection is called in reallocate, either on every allocation if DEBUG_STRESS_GC is set, or when vm.bytesAllocated > vm.nextGC.
3. "updated" is never allocated (at runtime):
   • like "first value", "updated" is allocated at compile time and put in the constants table. So the reassignment at runtime wouldn’t cause a new allocation anyway.

Let’s take a look at an example where garbage needs to be collected:

fun makeCounter(init) {
  var count = init;
  fun counter() {
    count = count + 1;
    return count;
  }

  return counter;
}

var c = makeCounter(0);
print c();

c = makeCounter(10);
print c();

c = makeCounter(20); // `makeCounter(0)` closure collected here.
print c();

Each time makeCounter is called, the following bytecode is executed:

== makeCounter ==
0000    2 OP_GET_LOCAL        1
0002    6 OP_CLOSURE          0 <fn counter>
0004      |                     local 2
0006    8 OP_GET_LOCAL        3
0008    | OP_RETURN
0009    9 OP_NIL
0010    | OP_RETURN

OP_CLOSURE allocates a new closure on the heap, pushing the value on the stack (safe from gc) until it is assigned to the variable c via OP_SET_GLOBAL in <script>:

      case OP_CLOSURE: {
        ObjFunction* function = AS_FUNCTION(READ_CONSTANT());
        ObjClosure* closure = newClosure(function);
        push(OBJ_VAL(closure));
        ...

So we want to check each call to makeCounter to see if anything is being collected.²

First, we don’t expect any garbage to be collected when c is initialized. c has no prior value that could go unreferenced, and this is the first time makeCounter is called.

c = makeCounter(10); is more subtle. We know it allocates an object, but is anything collected? You might think that the closure returned from makeCounter(0) would be collected. To know for sure, we need to examine the order the statement is executed. Luckily, we can refer to bytecode logging:

0017   14 OP_GET_GLOBAL       7 'makeCounter'
0019    | OP_CONSTANT         8 '10'
0021    | OP_CALL             1
0023    | OP_SET_GLOBAL       6 'c'
0025    | OP_POP

OP_CALL will run the makeCounter bytecode which will run OP_CLOSURE and allocate an object. This happens before we assign the new closure to c. So deep in markRoots when we call markTable(&vm.globals), c is still associated with the closure returned by makeCounter(0). So both are marked and are safe from collection.

Therefore, nothing is collected!

A similar thing happens with c = makeCounter(20);.³ At the time of collection, c is associated with the closure from makeCounter(10), so that one is is not collected. But the closure from makeCounter(0) is not marked as safe, so it’s collected and freed!

And that’s what we see in the gc logs:

0x131704b50 free type 4
0x131704b20 free type 0
-- gc end
   collected 96 bytes (from 2084 to 1988) next at 397

type 0 is the 0th ObjType enum which refers to closures. We also see an object of type 4, which is the upValue used by the closure (an ObjUpvalue wrapping the Value 0).

A recurring theme in the book is the difference between an abstract specification of the language and the real implementation. It is cool to see a small slice of this in two small examples.

It was also really fun to work through Lox’s mark-and-sweep implementation in detail, because I love stepping through functions with a debugger and tracing the path through a program. I always learn so much about the program and the language when I do that.

Note in makeCounter, the starting value of the counter can be set with init. This is a helpful way to see why you need to allocate new closures on each call, even though the underlying function counter is the same: each one “closes” around a different value.