Garbage collectors are scary
Garbage collectors are expected to be invisible: if programmers (or even users) notice them, something is wrong. Usually, such problems are are performance problems, but there could be correctness issues as well. This makes implementing them a bit scary.
As a hobby, I am working on a virtual instruction set architecture, mainly to better to understand the nature of computing, and eventually, trade-offs in programming language design. The project stalled for several months because I was reluctant to start working on a garbage collector, which I consider necessary to maintain memory safety. I was a bit puzzled by this, but now I think it is because garbage collectors are scary to work with. Not only are they intended to be largely invisible, but they need to compute a highly non-local property, too: Whether an object is live and cannot yet be deallocated depends on the state of the pointers in all the other object on the heap. Production-grade garbage collectors are very complex, too. So it all seemed very daunting.
This article attempts to document what I did to get unstuck. Most of the ideas below focus on making the garbage collector operation more obvious.
