Author here, let me know if you have any questions / suggestions for future blog posts. Planning a series around Ruby's GC, definitely with future posts on incremental marking, generational gc and compaction.
Also! Writing a book about managed GC with a focus on Ruby. I'll keep posting updates on twitter @jemmaissroff or you can sign up for updates at https://buttondown.email/jemmaissroff
The tri-color invariant is "obvious" in single-threaded stop-the-world mark and sweep algorithms. There's no need to track color in single-threaded stop-the-world.
----------
The reason why you need to formalize the tri-color invariant is because of __multithreading__ issues. If Thread#2 changes an object from "object.blah = object2", and "object" is black ("already processed" by the garbage collector), then you MUST set object2 to grey or black.
White-objects and grey-objects do NOT need to be processed in this manner. (ex: if "object" is white, then the GC will process object in the future. Ditto if object is grey)
----------
That's the real secret of tri-color mark and sweep. Your explicit color-tracking allows for parallel garbage collection on multicore systems.
Now the method to hold the tri-color invariant depends on a number of decisions: maybe there's a "read barrier", or maybe there's a "write barrier" (not a barrier in a multithreaded sense, but that's the terminology that garbage collector textbooks use).
------------
> There is one more nuance here. As of Ruby 3.0, if auto-compaction is enabled, compaction will actually happen as part of the sweeping phase. A more in depth explanation of how and why this happens will follow in a later post about compaction in this Garbage Collection Deep Dive Series.
That means this is not a Mark-and-Sweep algorithm, but instead a Mark-and-Compact algorithm.
Mark-and-Compact has more technical issues than Mark-and-Sweep. The devil is in the details, so to speak. If you're moving pointers around at the lowest level, you need to have either:
1. A level of indirection on all reads: because the GC may "move" and object while you weren't looking.
2. OR, a way for the GC to set all pointers in all registers, variables, and objects, to the "new correct location" while your code wasn't looking. (Aka: "Stop the world" methodology)
Compaction is great at reducing fragmentation (which makes future "malloc" more efficient... and also causes the code to use less memory). But it does take more effort to compact the heap.
> The reason why you need to formalize the tri-color invariant is because of __multithreading__ issues.
Not specifically "multithreading" issues, but rather concurrency. MRI implements incremental marking and lazy sweeping. The GC and the mutator execute in the same thread, but they execute concurrently. The tri-color algorithm ensures consistency in a single threaded, concurrently executing environment. It allows us to "pause" the GC in the middle of marking and allow the mutator to continue in the same thread.
> 2. OR, a way for the GC to set all pointers in all registers, variables, and objects, to the "new correct location" while your code wasn't looking. (Aka: "Stop the world" methodology)
We're also able to do compaction concurrently with the mutator via a read barrier.
> But it does take more effort to compact the heap.
This is very important to remember. A lot of the time, the incremental GC is still single threaded. The difference is that while a two-color "stop the world" algorithm has to collect everything in one long GC pause, the three-color incremental algorithm can spread the work over a series of smaller pauses.
Alternatively, you can also move the gc "backwards", changing the black object. In Lua, sometimes the write barrier recolors the white child object to grey and sometimes it recolors the black parent object to grey.
IIRC, the motivation for going backwards is that if you assign a large number of white children, recoloring the parent once is faster than recoloring all the children.
Yes. In the Ruby VM, an RVALUE [0] is a union (a "generic type") of structs that represent all the different kinds of Ruby object types and a couple of runtime types.
Rvalue seems to be a 40-byte "Ruby Object". (If an object takes up more than 40-bytes, it gets an additional allocation, and the first 40-bytes go into the rvalue "slot").
Also! Writing a book about managed GC with a focus on Ruby. I'll keep posting updates on twitter @jemmaissroff or you can sign up for updates at https://buttondown.email/jemmaissroff