Low-Latency, High-Throughput Garbage Collection [pdf]
users.cecs.anu.edu.au
users.cecs.anu.edu.au
> LXR introduces: i) RC re- membered sets for judicious copying of mature objects; ii) a novel low-overhead write barrier that combines coalescing reference counting, concurrent tracing, and remembered set maintenance; iii) object reclamation while performing a con-current trace; iv) lazy processing of decrements; and v) novel survival rate triggers that modulate pause durations.
There was a thread just recently debating the relative merits of RC & GC, and here we see them combined smartly.
Therefore you apply techniques like Apple's ARC, or deferred-coalesced counter mutation.
Add cycle leak detectors and the RC scheme is looking more and more like a really slow garbage collector, albeit a low latency one.
Note that simple RC is not deterministic or good for real time either because of the possibility of release/destruct cascade. Which looks pretty much like a GC pause (because it is one).
See also “A unified theory of garbage collection” by Bacon, Cheng, and Rajan (OOPSLA ’04) for a discussion of how tracing and RC essentially compute the least and greatest fixed points, respectively, of the “roots and referents” function (the difference between the two being the reference cycles), and of course the Garbage Collection Handbook by Jones, Hosking, and Moss (CRC, 2012), which includes both tracing and RC in its definitions of GC and draws comparisons (barrier costs, heap fragmentation, etc.).
(These are both bog-standard references, the thread above has people know much more about this talking about ideas that aren’t 20 years old.)
Note that as a rule of thumb, tracing garbage collectors need about twice as much memory as live objects, to avoid frequent heap scans. Non-delayed reference counting only keeps around live objects, which can significantly reduce memory usage.
If you have a huge number of live objects that you need to keep around, but infrequently have references to them created (e.g. very large caches), then reference counting is going to out-perform tracing collection, particularly if some of those infrequently used objects might be paged out and you're not using card marking to sometimes avoid needing to trace the paged-out objects. It's convenient that these use cases also tend to work well with reference counting's generally lower peak memory requirements.
On the other hand, if you're rapidly creating and destroying objects, or often updating references, tracing may perform better. Moving collectors (at least using moving or compacting collectors for the young generation) can use bump allocation, resulting in much faster object allocation.
The Garbage Collection Handbook goes into nearly countless variations, hybridizations, and optimizations on these basic collectors.
For over a decade, I helped maintain Goldman's Slang language. Some components had bog standard mark-and-sweep collector, but most of the language uses reference counting. The language uses tight integration with the SecDb globally distributed NoSQL database and pervasively locally caches database objects and memoizes method calls on those objects. I'm sure naive reference counting isn't optimal for the Slang use case, but it's easy to implement and isn't actually that far from optimal. (When I first started at Goldman, some parts of the language used an implementation of Bacon's cycle-detecting concurrent reference counting collector, but there was some rare corner case where someone missed a reference count change on the C++ side, and after a while of trying to find the missing reference count, we just replaced that component with a non-generational mark-and-sweep collector.) (There was a publish-subscribe system that would watch the SecDb transaction logs, so applications could subscribe for cache invalidation notifications. With huge caches, you don't want to use database polling for cache invalidation.)
When a reference count of an object goes to zero, you recursively decrement the reference counts of everything the object points. This leads you to trace the object graph of things whose reference count has gone to zero. You never follow pointers from anything which is live (i.e., has a refcount > 0).
When you are doing the copy phase of a gc, you start with the root set of live objects, and follow pointers from everything that is live. Since anything pointed to by a live object is live, you only follow the pointers of live objects. You never follow pointers from anything which is dead (i.e., garbage).
If object lifetimes are short, most objects will be dead, and so RC will be worse than GC. If object lifetimes are long, most objects will be live, and GC will be worse than RC.
Empirically, the overwhelming majority of objects have a very short lifetime, with only a few objects living a long time. (This is called "the generational hypothesis">) So the optimal memory allocator will GC short-lived objects and RC long-lived objects. Rust/C++ encourages you to do this manually, by stack-allocating things you think will be short-lived, and saving RC for things with an expected long lifetime.
Beyond this, RC has a few really heavy costs.
Reference counting doesn't handle cyclic memory graphs. You need to add tracing to handle those, and if you are going to do tracing anyway, it's tempting to just do tracing really well and skip the refcounts entirely.
This is because the memory overhead of reference counts is high -- empirically, most objects never have more than a single reference to them, and so using a whole word for reference counts is lot of overhead. Moreover, the need to increment/decrement reference counts is really bad for performance: first, mutations are expensive in terms of memory bandwidth (you've got to maintain cache coherence with the other CPUs), and second, in a multicore setting, you have to lock that word to ensure the updates are atomic.
There are tricks to mitigate this (e.g., Rust distinguishes Arc and Rc for objects which can be shared between threads or not), and there are schemes to optimise away RC assignments with static analysis (deferred reference counting), but if you want to do a really good job of reference counting, then you will be implementing a lot of tracing GC machinery.
And vice versa! The algorithm in the link is partly about adding RC to handle old objects (empirically, as part of the generational hypothesis, objects which have lived a long time will live a long time more). In fact, Blackburn and McKinley (two of the three authors of the above paper), pioneered the combination approach with their paper "Ulterior Reference Counting."
It's also not uncommon to have a copying young generation and a mark-sweep-compact tenured generation. That way, you get the advantages of not needing to scan the huge numbers of young dead objects, but the space savings of not needing 2x space for the older generation.
Eagerly updated single-bit reference counts are useful if you have a lot of code that allocates buffers, passes them to helper functions to get filled (potentially defeating static escape analysis), passes them to consuming functions, and then returns. A single bit to track if a reference to that buffer has ever been stored into another object will allow for early collection in the common case.
On a side note, the Garbage Collection handbook (and many practitioners) consider reference counting to be a form of garbage collection. What some people narrowly define as GC is tracing garbage collection.
Yup. The paper you're thinking of is "A Unified Theory of Garbage Collection":
https://courses.cs.washington.edu/courses/cse590p/05au/p50-b...
I have been playing around with low-latency GC strategies in .NET6, and have discovered a similar pattern - If you intentionally run GC as frequently as makes sense (i.e. instead of trying to avoid it or sweep it under some other rug), you can sometimes reach a solution that is far superior to any other.
My example being a toy software rendering engine that is utilized by several concurrent clients. I asked myself "What would happen if I just ran GC right before every single frame"? Turns out, for reasonable scene sizes, the maximum amount of time the GC pause lasted was <5ms, producing a perfect result for my use case. Without intentionally calling GC, I would sometimes see pauses upwards of 3-4 seconds, which clearly has a severe impact on user experience for this type of application.
The way it works in my head - I am happy to pay a small 1~5ms cost for every frame (or batch of frames as the case may be) rather than allowing the .NET runtime to decide when would be most convenient and incur a much longer collection.
"Clean as you go" might be the best way to achieve low latency in any reality. Deferring and hiding is how things build up. Something is gonna have to eventually deal with all that trash unless you are shipping cruise missiles.
Java’s low-latency GC, ZGC moves almost the whole work to parallel threads by accepting the trade-off of slightly slower barriers. But in reward it can decouple the pause time’s length from the heap size which is the key here.
Oberon, if I'm not mistaken, had stupidly simple GC that simply run between every two user interactions. That way you wouldn't notice pauses simply because your fingers move way slower than bytes in memory.
https://www.reddit.com/r/java/comments/ubgyva/comment/i646o4...
> "The beauty is it’s not a Java GC, it’s a generic GC they have evaluated in Java."
Anyway: this paper is mostly about Java, which I rarely use and basically only known from Elasticsearch (where log entries about GC pretty much always seem to indicate 'add more memory'...), but I've never run into any scenarios where .NET CLR GC was a performance issue either (not on the legacy .NET Framework nor in more recent releases, which are a lot better in most performance aspects).
Most GC complaints from the .NET world seem to be from game developers using Unity. Which mostly tells me that there should be a way to have a 'this is the rendering thread, never pause this for GC, unless I really do bad stuff' in Unity...
Thoughts in no particular order:
• A very impressive tour de force. To implement a GC in OpenJDK is hard, to come in competitive with G1 out of the gate doubly so. The approach is a very clever hybrid of both classical GC and RC techniques. They aimed to reinvigorate GC research and appear to have achieved this goal.
• Although advertised as low latency their pause times are comparable to G1. SOTA low latency collection is now <1msec and still falling. Their benchmarks don't really show this because they appear to be overdriving both ZGC and Shenandoah, which then totally collapse (e.g. >800msec pauses) due to the lack of generational collection making it hard for them to keep up with high allocation rates. This is an acknowledged limitation which at least the ZGC developers are working on removing, probably Shenandoah devs too, but the authors only mention this in one sentence right at the end.
In fairness they obviously cannot benchmark against unreleased versions of ZGC, but equally, I was expecting/hoping to see benchmarks run at allocation rates that ZGC/Shenandoah are actually rated for today. What they're mostly proving here is that you need generational collection to handle high throughputs on allocation heavy benchmarks like lusearch, rather than anything special about LXR specifically.
• It would have been nice to see a deeper dive of heap overheads and locality. Traditionally the place RC gets used is in consumer electronics / desktop apps, where you need very stable memory locality and predictable heap management overheads to avoid swapping/spikeyness. What they're doing here is sort of half-GC, half-RC and it's not really clear to what extent this would make LXR more appropriate for things like desktop apps. It'd be interesting to see a benchmark of "normal" apps like IntelliJ where the host OS is deliberately pushed into swapping, then seeing if there's a major performance gap. In theory LXR should win because objects don't move around as much but they don't seem to have tested that.
• Relatedly, the question I'm left with is this: OK, you've got roughly similar perf to G1 but with fewer features. That's kind of impressive from a coding perspective but from an end user perspective, where's the competitive advantage? The opening discussion mentions simplicity in the first paragraph, but no LOC comparisons are provided so it's not obvious that LXR is/would be simpler than G1 when feature parity is achieved. It mentions LXR will provide "sufficient responsiveness" without concurrent evacuation, but the whole reason ZGC/Shenandoah were developed was because for some use cases G1 level pause times - even though they're usually quite low - were not considered sufficient.
Overall I'm wondering if the OpenJDK guys will really want to merge this. For the generic good throughput, reasonably-but-not-insanely-low-pauses market they have G1 which is mature and feature complete. For the markets like HFT where they need pauses so low they may well not exist, but aren't spamming the collector, they have ZGC. Soon they'll have generational ZGC which will ramp the throughput capabilities of ZGC significantly and should prevent collapses like those in the paper, whilst still maintaining sub-1msec pause times.
Integrating and maintaining a new GC is a big effort because they touch so many parts of the system. Without some obviously killer advantage, it may require external maintenance. Maybe better ergonomics on desktop systems where much of the app is paged out can provide this?
This quite a lot. From my experience with ZGC once you push it too hard to cause it to allocation stall you are in for a bad time. But if you manage to keep the load under that (usually by giving it larger a heap or more gc threads) you should expect pause times under 0.1ms.
Hopefully with the generational ZGC that is in the works this gets better and one could run with smaller heaps/less cpu overhead.
They evaluate over a diverse range of 17 benchmarks, though only 4 latency benchmarks. Would have been nice to have more latency benchmarks, I agree.
> It mentions LXR will provide "sufficient responsiveness" without concurrent evacuation, but the whole reason ZGC/Shenandoah were developed was because for some use cases G1 level pause times - even though they're usually quite low - were not considered sufficient.
Right. At the cost of a significantly larger heap size though. Memory is cheap nowadays, yes, but large datacenters want to reduce their (electricity/power) running costs, and so if we can reach similar (or _slightly_ worse) latency requirements (and the paper demonstrates that low pause times do not necessarily translate to low latency) while using less memory, I think that in-of-itself is quite appealing. Also do note that, as mentioned in the paper, LXR is has not seen the benefit of years of tuning and tweaks that production collectors have.
I am quite excited by this new GC and hope to see further work done to improve its performance.
I think you're much better off coming up with some dedicated instructions and/or features to make read and/or write barriers lighter weight. One possibility would be hardware multi-threading, but where the one thread only issues micro-ops when the primary thread would otherwise stall the pipeline. That way, GC could run in the background using the same L1 cache as the application thread.
Yeah, that's what I was trying to chase out of the OP. Running GC on a dedicated core seems like such an obviously bad idea, I'm not sure why anyone would seriously propose it.
Likely, cache line contention just probably never crosses their minds. I don't blame them. I'm largely self-taught. My degree is in mechanical engineering, and I did a bit of dabbling in kernel programming in college, and took a CPU design course, but I had been working in industry for more than 10 years before I had a decent mental model of cache coherency.
There are just so many things to learn. I think few practitioners were exposed to or remember MESI or similar cache coherency protocols unless they've really done a lot of deep optimization in low-level languages or other languages with value types.
Most of your GC languages (particularly those without value types) do so much pointer chasing that cache line contention may often get lost in the noise floor of cache line evictions.
I was under the impression that C4/Zing was doing exactly that. Did I misunderstand what C4/Zing was doing?
Considering actual, real world hardware as you point out, it is not a very good idea.
In that scenario, you wouldn’t want the GC to run on that core, for sure.
> We currently don't have an option for that other than going native.
You mean going manual memory management, I believe. Technically, JIT vs. ahead-of-time native vs. interpreted is orthogonal to manual memory management vs. GC. Yes, most JITs also have garbage collectors, but it's not necessarily the case.
But, your point does stand that when you really care about 99.99th percentile latency, you almost certainly need to go with static native compilation and manual memory management. The long-tail on JIT and/or most GCs is just too high.
In that scenario, you wouldn't want the GC to run at all. If it runs on another core but touches the GC header words on objects used by the application code, it's going to end up stealing cache lines from the application core's L1 cache, resulting in pipeline stalls on the application core.
I've talked with folks who just disabled the garbage collector, were careful to keep down the number of objects allocated per trade, and ran their trading engines on boxes with huge amounts of RAM so that they were very unlikely to run out of memory before the close of the market.
Now, I could see some GC-specific modifications to the cache coherency hardware. For one, it would be useful to have message to set or unset a single bit on a cache line owned by another core, and report the previous value of the bit on the cross-core interconnect, without changing the ownership of the cache line or moving the whole line across the bus. You'd probably also want a variant on the MESIF cache coherency protocol where another core can get a "notify" bit set on a cache line, so when a cache line in the F state with its notify bit set gets naturally evicted from the cache, its contents and ownership would be transferred to the requesting core. I imagine you'd have a small programmable push-down automaton similar to the ESP32's ULP core sitting in the L1 cache. Its stack would be that core's share of the grey set, and it would have a small array of addresses it was waiting on to mark in the background as their cache lines became un-contended. It would undoubtedly be complex, but it seems the cleanest way to do garbage collection in the background without stealing cache lines from cores executing application code.
Really, I think you're best off having Erlang/Elixir/BEAM-like concurrency (but using ahead-of-time native compilation) where most objects are kept in per-actor GC arenas, and maybe only have some types capable of being passed between actors, and allocating those types in separate arenas to keep their cache line contention from harming the happy path non-shared objects. (Yes, last I checked, BEAM had moved from per-actor ("process") GC arenas to shared arenas, but that's largely because they had no way of accurately determining which allocations would later be passed across actors.)
Also, ideally, you'd have static inference of region-based garbage collection to reduce the amount of scanning done. Static inference of Rust-like lifetimes is undecidable, so you'd need a conservative inference algorithm that would leave some performance on the table, but you'd still have your garbage collector as a fall back for objects where lifetime inference fails. I guess you'd short-circuit lifetime inference for most dev builds to keep build times sane.
Yes we did this too for a while. In the end it slowed down dev velocity too much and we could afford to trade off some slight tail latency. Mind you this was back in like 2016, I haven’t used Java in trading for a while..
> it's going to end up stealing cache lines from the application core's L1 cache
This happened but in practice it wasn’t a big deal, it could be pretty effectively mitigated by consistently running the fast-path code to keep the caches hot.
Yet they are useful.
On high level languages one needs to hope that the register allocator does a good job.
They won't do it for extern (i.e. separately compiled) calls, because the ABI wouldn't really allow for anything of the sort. But calls to static (or inline) procedures that only have visibility within a single source file can occur with arbitrary calling conventions, so the compiler is free to optimize register allocation across procedures.
My point was more about how we are willing to trade the optimal performance for something that gets us there most of the time, while offering much more productive tooling.
And caches bring a whole cache line. So for every access, no matter how small, the minimum is 64 bytes are kicked out. Also the prefetch heuristics often bring more (e.g. next cache line).
There are cache control instructions but they are rarely used.
[0] Reducing Garbage Collector Cache Misses (2000) (HP) https://www.hpl.hp.com/techreports/2000/HPL-2000-99.pdf
> Cache misses are currently a major factor in the cost of garbage collection, and we expect them to dominate in the future. Traditional garbage collection algorithms exhibit relatively little temporal locality; each live object in the heap is likely to be touched exactly once during each garbage collection. We measure two techniques for dealing with this issue: prefetch-ongrey, and lazy sweeping. The first of these is new in this context. Lazy sweeping has been in common use for a decade. It was introduced as a mechanism for reducing paging and pause times; we argue that it is also crucial for eliminating cache misses during the sweep phase.
[1] at memory management. I think that it is only a matter of time until machine learning, region-based memory management, and inference of ownership (which really is region-based memory management, tbh) are combined in the right way to get superhuman results.
Will it? malloc/free are slow; gc can allocate faster and free faster. And problems are often dynamic and can't be statically determined.