Speeding Up the Plush Garbage Collector

August 17th, 2026 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. I think that somewhere in my mind I kind of got used to the assumption that hash maps are an efficient data structure. Introductory CS classes will teach you that you can get O(1) time complexity on average. They work well for so many uses. If you're trying to optimize memory usage and cache-friendliness for maximum throughput, though, it turns out that maybe they're not. I originally said that the reason I didn't want to use forwarding pointers is that I was using the same copying algorithm to copy objects when sending messages, and I didn't want to overwrite objects (or object headers) from the sender's heap during that process. There's a simple solution for that problem though, which is that for this special case, we can keep a list of forwarded objects, and come back to undo the forwarding pointer writes after copying. Sounds inefficient, but in practice, messages sent to other actors are probably not massive graphs of objects most of the time, and normal GC use can just skip this step. At this point I decided to rewrite the Plush GC to simply follow the traditional Cheney copying algorithm, with a toggle that allows us to store an undo-list to remove forwarding pointers and restore object headers for the message send special case. This brings our GC time for a million live objects all the way down to 7ms, which is about 16.7x as fast as the naive implementation we started with. That's an amazing performance improvement, and it's well below my 20ms goal. In fact, I have an example program that renders a rotating cityscape with about 2200 polygons. It triggers GC regularly because it does 3D vector and matrix operations and allocates tons of temporary objects. For this program in particular, the GC time is below 1ms. Just for historical context, Cheney published a paper about what is now known as the Cheney algorithm in 1970. At the time, he was working on a Ferranti Atlas 2 computer. This was a transistorized supercomputer from the early 1960s. It occupied an entire large room, used core memory, and surprisingly, already had an early form of cache. Regardless of cache efficiency though, memory was a precious resource back then, and using a forwarding pointer is much more memory-efficient than using an auxiliary data structure. I hope that this conclusion isn't too underwhelming, because we've sort of gone full circle to the conclusion that the original Cheney GC algorithm with forwarding pointers is much more efficient. Another indication that we should respect the wisdom of our elders and their sacred publications. Still, I think it's good to understand what, exactly, makes something efficient or not, and how much of a difference things like cache efficiency and predictable memory access patterns can make. It's also good to know that Rust's HashMap traded a security footgun for somewhat of a performance footgun. Typical Atlas 2 Installation, from the Ferranti Computer Systems brochure. In addition to making the GC run faster, I made another improvement, which serves both to remove a restriction in Plush and to reduce memory usage. Previously, I didn't have any logic to grow an actor's message allocator. This meant that message size was limited to 16MB, a hardcoded constant. The message allocator uses bump pointer allocation like a normal GC heap, and it's slightly tricky to resize it because if you reallocate the backing storage, that invalidates pointers to queued messages. This means you can only reallocate the backing storage when the queue is empty, and all messages have been consumed by the receiver. That, in turn, requires senders and the receiver to coordinate. If one actor is trying to send a large message, it would need to communicate to the receiver that its message allocator needs to be upsized, and meanwhile, all other senders would have to wait. There's a simpler solution though.