8 ms·
Low-Latency, High-Throughput Garbage Collection [pdf]
- infogulch 5y agoBased on the abstract it looks like it's a combination of reference counting and tracing GC that brings improvements in both tail latency and throughput compared to G1 and Shenandoah. > 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.
- brrrrrm 5y agoDo you have a link to that thread? I’ve never quite understood the value of GC over RC save for vague claims of developer efficiency.
- vnorilo 5y agoSimple implementation of RC with multithreading implies a lot of atomic counter updates which clog a multicore cpu fast. 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).
- mananaysiempre 5y agoChris Lattner on garbage collection vs. Automatic Reference Counting (2017), https://news.ycombinator.com/item?id=31139610 https://news.ycombinator.com/item?id=31139610 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.)
- KMag 5y agoExcellent answer. I would just add a brief summary, that naive reference counting does work proportional to the rate at which references are created and destroyed, and naive tracing collectors do work proportional to either the full heap size or the number of live objects on the heap. 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.)
- neel_k 5y agoThe short answer is: reference counting walks the dead part of the heap, and tracing gc walks the live part of the heap. 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."
- eru 5y agoIn theory, GC can be faster than RC. (Because tracing GC only pays an overhead proportional to what's still alive after a while, once in time. RC pays an overhead for every operation.)
- KMag 5y agoIt's been a little while, but as I remember, the Garbage Collection Handbook (an excellent read if you're into this sort of thing) outlines and cites some external work showing tracing garbage collection as a lazily evaluated form of reference counting (using a saturating 1-bit counter) taken to the limit. (Some reference counting systems use a small number of bits for a reference count, and if that reference count hits its max value, then never decrement a counter. Many reference counting systems also incorporate tracing major collections to avoid the cycle problem. If you're going to have a tracing collector, and you assume your high-reference-count objects are likely to be long-lived, then reserving only a small number of bits for the reference count makes sense. Your backup tracing major collector will handle both the cycle problem and the saturating counter problem at no extra cost.) 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.
- munificent 5y ago> cites some external work showing tracing garbage collection as a lazily evaluated form of reference counting (using a saturating 1-bit counter) taken to the limit. Yup. The paper you're thinking of is "A Unified Theory of Garbage Collection": https://courses.cs.washington.edu/courses/cse590p/05au/p50-bacon.pdf https://courses.cs.washington.edu/courses/cse590p/05au/p50-b...
- alecco 5y agoNo matter how fast, Garbage Collection will always cause a performance knock-on effect by kicking useful stuff out of cache.
- pjmlp 5y agoNo matter how productive, high level languages will always cause a performance knock-on effect by kicking useful stuff out of instruction cache and internal registers. Yet they are useful.
- sebastianconcpt 5y agoRight, the cost of maintaining systems would be exponentially high for a marginally irrelevant gain on an edge case.
- pjmlp 5y agoDeveloper salary per hour * time developing the feature * time spent bug fixing * number of team members + hardware infrastructure cost
- titzer 5y agoWhat high-level language feature causes inherently increased register pressure?
- pjmlp 5y agoAssembly allows to use all of them, and there is no need to reserve any for ABI, other than syscalls or specific opcode requirements. On high level languages one needs to hope that the register allocator does a good job.
- titzer 5y agoHa, well. I just spent a fair bit of time writing an interpreter in assembly and hand-optimized the regalloc to the limit. But I was surprised by my competitors written in C and how well gcc, in particular, could regalloc hairy interpreter loops. Compilers are very good at register allocation at the right granularity; they just generally don't do it across procedures.
- gavinray 5y agoChris Seaton pointed out something very interesting in his Reddit comment here: https://www.reddit.com/r/java/comments/ubgyva/comment/i646o4o/?utm_source=reddit&utm_medium=web2x&context=3 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." Important bit of info there.
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- mike_hearn 5y agoThanks. Just finished reading the whole paper. 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?
- snarfy 5y agoI'm still waiting for a lock-free, zero latency GC that runs on its own core. I believe this might exist for java but not .net.
- jeffbee 5y agoWhy would running the GC on its own core be a good idea? Don't you want it to happen wherever it would be most efficient, i.e. on the same core where the memory in question was most recently accessed?
- sanxiyn 5y agoBecause you don't want GC to interfere with cache.
- jeffbee 5y agoWhich cache are we talking about? Are you saying the GC blows out the icache, or ?
- alecco 5y agoL1
- KMag 5y agoAs the GC running on its own core sets mark bits in a mark-sweep or mark-sweep-compact collector, it's going to get exclusive cache line access to the line holding the GC word for every live object. That's going to force more traffic on the cross-core communication lanes and cause cache line invalidation on the cores running your application code. A dedicated GC core is basically a core dedicated to flooding the cross-core interconnect, and invalidating lots of cache lines for your cores running application code. 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.
- muizelaar 5y agoImplementation is here: https://github.com/wenyuzhao/mmtk-core/tree/lxr https://github.com/wenyuzhao/mmtk-core/tree/lxr
- mdb31 5y agoMost interesting observation here: Short GC pauses do not assure low latency. 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...
- mangokiwi 5y agoWell, the framework they use (mmtk: https://github.com/mmtk/mmtk-core https://github.com/mmtk/mmtk-core), is language runtime agnostic. They just used Java because Java is one of the most mature and well-research managed languages. If you make a port for C#/.net (assuming all the required features are implemented), you could pretty much use the same GC.
- bob1029 5y ago> A key design insight for LXR is that regular brief STW pauses provide a highly-efficient, low-latency approach to garbage collection. 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.
- zozbot234 5y agoOf course, the limiting case of "clean as you go" is either fully manual memory management, or at least deterministic deallocation (as seen in reference counting systems). With some exceptions for small bursts of especially low-latency, high-throughput work, that can be modeled in a "manual" system by arenas, or higher-scoped references if using reference counting.
- eru 5y agoAlas, reference counting and C-style manual memory management can still require doing arbitrary amounts of work from time to time.
- deleted 5y ago[deleted]
- kaba0 5y ago
- jimjimjim 5y agoLow-Latency, High-Throughput Garbage Collection... twitter?