I built a garbage collector for Rust (2023)
18 points by abhin4v
18 points by abhin4v
I’m not doubting the benchmarks, but I have trouble seeing how this can be fast. Gc::drop runs a (fairly expensive looking) scan whenever the target object's refcount is > 1, which must be pretty common. That’s a significant write barrier. Or did I miss a later step where that gets optimized?
I’ve seen other ref-counting implementations with cycle collectors (e.g. Nim's) and usually they only run the collector periodically (IIRC), not on every release.
oh, hey! Funny to see this making the rounds (I made this the summer before I started grad school).
Dropping a Gc is extremely cheap most of the time, as it just punts the work by storing the pointer in a thread-local set of possibly-lost allocations. The GC only runs periodically.
However the worst-case behavior is really bad, as you have to scan all the available GCs. If I were to go back to this, I’d probably look at making the garbage collection process resumable to allow each Gc operation to do a tiny amount of work to keep performance under control.
However the worst-case behavior is really bad, as you have to scan all the available GCs.
Even plain drop of an owned flat Vec can have bad worst-case behavior from a latency perspective when the buffer gets large enough, and that's a case where the constant factors are about as good as it gets. One of the fundamental issues with synchronous destruction is that you might up build a resource incrementally over time (e.g. it grows linearly as a function of time) and when it's destroyed synchronously you end up paying off all the accrued debt at once, blocking the flow of execution.
You can try to push that work outside the flow of execution to e.g. a worker pool; if so, you still need backpressure to avoid an unbounded backlog, but the backpressure only kicks in when the system is actually throughput limited.
Or you can do what you suggested, paying off an equivalent amount of old debt whenever you accrue new debt. However, that work might not be naturally divisible into small enough chunks, in which case you can still end up eating latency spikes on the mutator path.
So it's really a scheduling problem. When and where should work happen and what's the granularity?
The thing that blew my mind when we were working on this is that it's not just a latency issue: running destructors on a mutator thread (i.e. a "normal computation thread") introduces horrors like deadlocks. Boehm realised this first, of course! I really can divide my life into a "before I was pointed at that paper" and "after I was pointed at that paper"!
I’m a gc noob—why would the drop latency increase for a large vec? I would naively think it’s the same amount of work as a small vec? Isn’t “free” just updating a fixed-size metadata entry?
I’m a gc noob
Just to clarify, that opening example was talking about an owned flat Vec like Vec<i32> (no garbage collection, just Drop of an owned Vec) as a comparison to think about synchronous Drop latency for the existing non-GC baseline.
Isn’t “free” just updating a fixed-size metadata entry?
The norm for general-purpose allocators is that sufficiently large allocations bypass the allocator's usual code paths and get redirected to mmap/munmap. And munmap has a cost proportional to the number of mapped pages in the allocation. There's also a cross-core TLB shootdown since you not only need to rewrite the relevant PTEs but you need to make sure the stale versions are evicted from all TLBs; that part is a fixed but not insignificant cost. For very large allocations the munmap is a macroscopic amount of time where you're blocked.
There is also a deferred cost which is less obvious, and that cost scales per byte rather than per page, albeit with a good constant factor. If you want to recycle a freed page frame, it needs to be zeroed first. On Linux, this is partly done asynchronously by a low-priority background task but ultimately it must be done synchronously when a page needs to be mapped and the zeroed pool is empty. Either way the work has to be done somewhere, so it's a good example of shifting around debts and scheduling work in different places to pay off the debts.
I can't speak to this exact implementation, but as this is basically Bacon-Rajan cycle collection, it's not fast, especially when you use it heavily, and especially when you compare it with a dedicated garbage collector.
There are Rc schemes that are about as fast as a dedicated garbage collector, but those are much, much more involved. The most recent and well known (that I know of) is LXR which builds on several different strategies such as Rc Immix
For me, the goal of garbage collector is that delayed de-allocation and lack of determinism buys you comfort, less mistakes and nicer syntax. Does it apply here?