GoKawiilSpeeding Up the Plush Garbage Collector
Those who have been reading this blog or following me on X know that I tend to jump between side-projects. A while back, I made a conscious decision to allow myself to follow my motivation and explore new ideas, because I think it's important for side-projects to feel fun, and never become a chore. That being said, every once in a while I find myself thinking about a project that I set aside a while back, and how I could push it further.
Last year, I wrote a series of blog posts about Plush, which is a toy Lox-like language I created. I put it together to play with different interpreter and virtual machine design ideas. Notably, it has actor-based parallelism, and it's designed so that there is no global VM lock on any critical path, and no situation in which the entire VM has to pause for anything. Later on, I implemented some basic optimizations in the Plush interpreter, and then I wrote a copying Garbage Collector (GC) for the VM. The GC itself is nothing special, but what makes it kind of cool is that each actor has its own fully independent GC. Each actor can run a collection cycle without any synchronization being involved whatsoever. What's a bit unfortunate, though, is that the performance of this GC ended up being pretty disappointing.
I had a personal goal for the Plush GC. I wanted it to be able to collect one million live objects in under 20 milliseconds, with the idea that this would be fast enough to build a 3D game engine in Plush without GC pauses ever being noticeable. I wrote a small gc_many_objs.psh microbenchmark that allocates a linked list with a million nodes and then triggers GC in a loop, but the performance came nowhere near my goal. On my MacBook Air M5, the collection time of this implementation comes to roughly 117ms, which is several times too slow. The reason is that I took a convenient shortcut in implementing my copying GC. A traditional Cheney copying collector copies objects from one memory block (the from-space) to another (the to-space), and it uses a forwarding pointer that lives in the header of each object, while also using the to-space as a work list to transitively traverse the graph of live objects during the copying process.
In Plush, each actor has its own private allocator that it uses to allocate objects, as well as a message allocator that's used as a buffer to receive messages from other actors. When an object is sent as a message, the sender copies it into the receiver's message allocator. This exists to decouple the sender from the receiver. It means the sender and receiver don't have to lock and synchronize for messages to be exchanged. I wanted to be able to reuse one copying algorithm for both the GC and for copying messages into the receiver's message allocator. For that, I didn't want to use forwarding pointers from the sender's heap, which would mutate objects in the sender. Instead, I used a hash map which tracks the correspondence between objects and their copies. I thought this wouldn't have too much of a performance impact, because hashing pointers is fast, but I was wrong.
An actor's two allocators, and the two copies a message goes through.
My friend and colleague Laurent Huberdeau pointed out something basic that I didn't know until that point, which is that the default Rust HashMap uses a secure hashing function, designed specifically to protect against HashDoS. This doesn't affect its functionality, but it does affect performance. Thankfully there's an equivalent FxHashMap in the rustc_hash crate, which is maintained by the rust-lang project and is a drop-in replacement. Laurent also found a redundant hash table lookup which could be avoided. These simple changes made the copying GC run more than twice as fast, down to 43ms on my M5 laptop. Much faster, though still far from my original goal of 20ms.
Profiling shows that most of the overhead still comes from the hash table. There is worse news, though: the forwarding pointer hash table itself takes up more space than the live data being copied during collection. It makes sense if you think about it. We're copying a linked list. The list nodes are pretty small, with only a next pointer and a value field in each. The hash table entries themselves are a pair of pointers, but what's more, a hash map needs some amount of extra capacity (empty slots) to perform well, otherwise you can run into hash collisions and performance collapses. On top of that, hash functions are meant to be unpredictable. The output should appear to have a quasi-random distribution. If you think about it, that's actually terrible from a cache performance perspective. It means that during the GC, we end up touching memory all over the place, more than the data we're copying, in an unpredictable pattern. Not great.
The same copy done two ways: through a hash table, and with a forwarding address.
There are other inefficiencies in this GC. In a traditional Cheney GC, the to-space is traversed linearly and serves as a work list. We use the to-space itself to keep track of which objects we've copied and then we traverse the pointers in these objects to copy other objects that are also live. If you don't have that, then you need to keep a separate work list. This can be a simple dynamic array that serves as a stack. It's not the end of the world, but it can also add extra allocations, extra memory usage and memory accesses, etc. The worst part of my implementation, though, is that after objects were forwarded, I traversed the hash map a second time to go through the forwarded objects and replace pointers to from-space objects with pointers to their copies in the to-space. However, as stated earlier, the hash map stores pointers in a quasi-random order, so now we're accessing the from-space and the to-space in an unpredictable order as well. Welp.
... continue reading