12 ms·

Baffled by generational garbage collection – wingolog

141 points by todsacerdoti 2y ago

cesarb 2y ago
I wonder how much the perceived advantages of generational GC are only due to Java's tendency to generate a lot of short-lived garbage.
- mananaysiempre 2y ago
  “A lot” is relative—I seem to remember a discussion long ago mentioning that Haskell/Scala-style programs were a problem for the JVM because the JVM is not designed for so many objects dying so quickly.
  - kgeist 2y ago
    I remember long time ago JBullet, a physics simulation library, had to maintain an error-prone pool of vectors and matrices because all the calculations involving the creation of temporary vectors and matrices put significant stress on the GC. Today, Minecraft allocates around 600 MB/s for a similar reason (Position3D objects & friends); however, on my PC, I don't notice any pauses.
    - gf000 2y ago
      Is that really error-prone for a physics simulation engine? That's pretty common to only refer to data by indices in other places - sure, there are languages that can deal with it a bit better (e.g. operator overloading, manual memory management and/or value types), but as far as I know this is even often done in Rust, which has the previous properties (it's done to avoid the borrow checker there). Also, Minecraft was famously written famously inefficiently.
      - kgeist 2y ago
        By "error-prone," I mean that if you accidentally stored a reference to a pooled vector and used it after it was returned to the pool, all sorts of unexpected things could happen since everything is by reference. You had to be very careful.
    - hinkley 2y ago
      I had a friend/former mentor who proved that object pools are slower in Java once GenGC was introduced because they create pointers from the old generation to the new. He also authored the fasted XML parser of that era and previously helped me land a project everyone but us and our boss said was impossible because Java Is Too Slow, so I take him at his word. So unless those pools are full of primitive data types, you’re going to cause more frequent full GC pauses, and longer due to all the back pointers.
      - fiddlerwoaroof 2y ago
        If you could add some sort of hint to the object pool instance that it should always be in the new generation, then you wouldn’t have this problem. This could probably be provided generically as a class named something like NurseryCollection. However, I thought the people that really were serious about performance would allocate the pool in memory the GC doesn’t control (back in the day using internal APIs, but I think there are new official APIs for this) such that the object pool and every object in it would just be ignored by the GC.
        hinkley 2y ago
        Looks like an arena allocator is available in JDK 20. But I’m fairly sure it’s been in the RT spec for a lot longer.
      - ickyforce 2y ago
        > So unless those pools are full of primitive data types, you’re going to cause more frequent full GC pauses, and longer due to all the back pointers. If you have enough objects pooled to get low allocation rate then you never trigger full GC. That's what "low latency Java" aims for. I think that the main downside of object pools in Java is that it's very easy to accidentally forget to return an object to a pool or return it twice. It turns out that it's hard to keep track of what "owns" the object and should return it if the code is not a simple try{}finally{}. This was a significant source of bugs at my previous job (algo trading).
        2y ago
  - gf000 2y ago
    The JVM is more than happy with short-lived objects, they are barely more expensive than a normal stack allocation (mostly by the header only). The JVM has a so-called Thread-Local Allocation Buffer, which is basically a simple buffer with a pointer pointing to the next free slot. It can be simply bumped up on a new object's allocation and later on the still alive objects will be evacuated to another generation and the whole thing can be cleared. This is faster than any malloc implementation CPP/rust/whatever might use, besides they also doing arena allocations. Haskell has a few tricks up its sleeve that can help with its kind of allocation patterns, but speaking specifically about Haskell, it's mostly the laziness that makes it quite different.
    - lowbloodsugar 2y ago
      But it’s not as fast as just allocating a structure on the stack instead of checks graph 20 objects on the heap, all pointing to the next with 64bit pointers. I’ve got Rust struct that are 80 bytes and the same structure in Java is 800 bytes.
      - gf000 2y ago
        What's the difference between the stack and a thread-local, constantly hot/in-cache other region of the same memory? Especially that in many cases the objects are allocated right next to each other, so fetching happens from cache again. Not saying that expertly written Rust code can't beat naive Java one, and especially with the object headers Java will have a performance disadvantage in many cases - but that's a tiny disadvantage in most real-world use cases, multiple times offset by its advantages. (Besides, Java has on-stack replacement which can do the exact same thing as rust does, but the JIT-compiler Gods have to be in the correct alignment for that)
        lowbloodsugar 2y ago
        What’s the difference…? 1. The size. 2. I don’t see that happening and I look at the output of the C2 compiler when I’m dealing with hotspots. In aware of the cool shit the JVM can do but done right, areas of code can be as fast as C or Rust. It in general, My experience is that Rust is much faster. Sometimes 10x faster where it matters to me (sustained server load).
- pfdietz 2y ago
  Generational GC was perceived as useful even before Java existed, for example in Lisp.
  - actuallyalys 2y ago
    Funnily enough, my impression is that Clojure, the most popular Lisp on the JVM, creates a lot of garbage—probably more than Java—but I believe that’s due to it using immutable collections and not due to it being a Lisp.
    - fiddlerwoaroof 2y ago
      Yeah, immutable collections have to use structure-sharing to be implemented efficiently and this frequently results in common operations allocating lots of small objects rather than updating some object in-place.
      - zozbot234 2y ago
        You can use a borrow checker to replace immutable objects with update-in-place ("ephemeral") ones where feasible.
        fiddlerwoaroof 2y ago
        And, escape analysis and "dynamic extent" hints can have similar effects by stack-allocating intermediate values. Also, you can design your transformations to compose before handing off to a result builder, which is how modern Clojure reduces this problem.
- davidgay 2y ago
  You've clearly never observed the allocation behaviour of a continuation-based compiler (every function call causes a short-lived heap allocation - the heap is the "stack")...
  - wbl 2y ago
    And the stack the heap with Cheney on the MTA.
- steveklabnik 2y ago
  I have long suspected that there is some sort of deeper truth here. It’s not really about Java. If you squint hard enough, a C program has the stack as its nursery, and the heap as a singular old generation. The stack is even arena allocated, of sorts! This is of course a bit hand-wavy, I haven’t had the time to truly try and investigate this in a more rigorous way.
  - jerf 2y ago
    In general, memory management needs to be understood as a continuum and not a binary "uses GC or uses manual memory management". Per the very discussion we're having, GC is not an atomic thing, and on the other end, what is commonly called "manual memory management" is itself not. malloc still makes non-trivial decisions, as evidenced by the fact that some programs can be greatly benefited or harmed by switching out the malloc it uses. Beyond what most people call "manual memory management" lies "arena allocation", and in the really extreme case, fully static memory layout with no allocation at all. The latter is how NES games were generally written and sufficiently small embedded projects still get written that way today. Further pushing this into a "continuum" rather than a binary flag is that programs can and do freely mix and match. Nothing stops a program from using two mallocs, some arenas, GC for certain values, and static allocations for yet others. The Memory Management Police do not come along and arrest you for having Impure Designs or anything. There are languages like (I believe) Zig where the ability to cleanly do this is more-or-less a first-class language feature.
hu3 2y ago
I always thought Go used generational garbage collector but alas it's not: https://tip.golang.org/doc/gc-guide https://tip.golang.org/doc/gc-guide
- zozbot234 2y ago
  Doesn't Golang use concurrent GC anyway, and shouldn't that lead to significantly lower latency compared to more traditional approaches?
  - hu3 2y ago
    Yes, it's optimized for latency: https://tip.golang.org/doc/gc-guide#Latency https://tip.golang.org/doc/gc-guide#Latency So, for example, network code gets better p99. This, along with other sensible tradeoffs, is why Go ate a large slice of network software market.
    - kgeist 2y ago
      IIRC Go has "GC assist" which forces goroutines that allocate too frequently to assist in GC work (share CPU time, i.e. they're slowed down), and I've never seen anything like that described for Java/C#. Interesting approach.
      - gf000 2y ago
        In other words, it slows down the user's code randomly. I wouldn't call that a necessarily good tradeoff.
        kgeist 2y ago
        It's a back-pressure mechanism. I think slightly slower code on average is better than unexpected long GC pauses.
        gf000 2y ago
lern_too_spel 2y ago
You need to understand the object lifetime distribution.
ComputerGuru 2y ago
C# (and .NET at large) use generational GV to great effect and there are some good writeups on the different modes you can run the GC in and its performance profiles. .NET has been generational GC since forever and you can’t swap out the GC engine so you won’t be able to find an analogous comparison, but it’s probably the current generational GC SOTA for a one-size-fits-all (with admittedly two different allocation/cleanup roles: server and workstation; and with (new to .NET 9) a new option to configure the GC to act as if it were running alone on the system (the old default, i.e. not sharing resources with other apps on the same os) or to more cooperatively try to manage allocation patterns. Just mentioning this in case someone wants to read up on a different GC and play around with benchmarks. There is a fair amount of inner workings info and real-world results to dive into.
- lostmsu 2y ago
  You actually can change .NET GC! https://news.ycombinator.com/item?id=42851061 https://news.ycombinator.com/item?id=42851061
  - ComputerGuru 2y ago
    Thanks for sharing that; now I have something to add to my list of things to play with when I get a chance!
snikeris 2y ago
I think the idea is to reduce the set of memory that needs to be frequently collected. Long lived objects age to the old generation which can be large and infrequently collected. I've used this kind of collector in the past for applications which held a large and mostly static dataset in memory.
caspper69 2y ago
His blog post is based upon the premise that his generational gc allocator doesn't seem to provide the performance benefits that generational gc is claimed to provide vs other more traditional gc approaches (e.g. mark and sweep- also his implementation). My initial take is that either his implementations are deficient in some way (or not sufficiently modern), there's some underlying latent issue that arises from the Scheme to C compiler or the kind of C code it generates, or perhaps the benchmarks he is using are not indicative of real-world workloads. But- I am out of my depth to analyze those things critically, and he seems to write about GC quite a bit, so maybe he's very in tune with the SOTA and he has uncovered an unexpected truth about generational gc. It certainly wouldn't be the first time that an academic approach failed to deliver the benefits (or perhaps I should say the benefits weren't as great in as many scenarios as originally opined). As an idiot programmer, my understanding is that Java, .NET & Go all have generational GC that is quite performant compared to older approaches, and that steady progress is made regularly across those ecosystems' gc (multiple gcs in the case of Java). P.S. and now I see in a comment below (or maybe above now) that Go doesn't use a generational gc. I'm surprised.
- neonsunset 2y ago
  Go has somewhat "exotic" non-generational design optimized for latency. As a result it has poor throughput and performs quite badly outside the scenarios it was designed for. But on moderate to light allocation traffic it is really nice. Just not very general-purpose. Java has by far the most advanced GC implementations (it lives and dies by GC perf/efficiency after all) with .NET being a very close competitor.
  - caspper69 2y ago
    Your comment posted as I was making my edit re: Go. Thank you for the detailed clarification.
  - schmichael 2y ago
    Go optimizing for latency over throughput means the GC very rarely interferes with my applications SLO at the cost (literally $) of presumably requiring more total compute than a GC that allows more fine tuned tradeoffs between latency and throughput. As someone who is not directly paying the bills but has wasted far too much of my life staring at JVM GC graphs and carefully tuning knobs, I vastly prefer Go’s opinionated approach. Obviously not a universally optimal choice but I’m so thankful it works for me! I don’t miss pouring over GC docs and blog posts for days trying to save my services P99 from long pauses.
mjburgess 2y ago
I'd imagine generational GCs are perform better on OO languages, especially ones where almost everything is boxed. I have recently prototyped my own non-OO, multifn-style polymorphic language using tagged pointers (60 bit payload, 4 bit tag) -- you can fit a float32, int/uint, etc. into 60bits -- as well as a case-insensitive 12 char alphanumeric string. Where various unboxed container types are available (eg., matrix of doubles, etc.) --- you can do a lot with just allocating to a local arena for a given scope, then resetting the arena. In this case, I lean to wards a very simple GC for all the heap stuff, since its probably going to be mostly large long-lived objects.
- GMoromisato 2y ago
  BTW, I'm using NaN boxing, and it's great--I can fit a float64 into 8 bytes and have bits left over for tagging pointers, ints, etc. Basically, the idea is to encode all non-float values into the NaN representation. The NaN value in a float64 leaves 52-bits undefined. You can use those to encode the other values.
mike_hearn 2y ago
It does work, at least for imperative languages that allocate things on the heap a lot. Look at the evolution of Java's open source pauseless GCs. Both ZGC and Shenandoah started out non-generational for ease of implementation reasons. They both now went fully generational, with big improvements in real world and benchmark performance (throughput as they were pauseless already).
nobodyandproud 2y ago
My guess: In real world scenarios, there’s overhead such swap space and virtual memory, analogous to a cache miss. A full mark—and-sweep GC would have deal with this extra overhead. Whereas a generational GC would reduce the amount of a miss because it only considers a subset of objects; and the least likely bit of memory in the disk/slower swap space are the most recently allocated objects.
pizlonator 2y ago
I think it’s the choice of benchmarks. GenGC is an improvement if you have: - High allocation rate. I think his benchmarks do have high allocation rate so this part is fine. - Large heap. I think splay has a large heap so this part is fine. - Lots of objects in that large heap that simply survive one GC after another, while the allocation rate is mostly due to objects that die immediately. This is the part that splay doesn’t have. Splay churns all of its large heap. Empirically, really big software written in GC’d languages have all three of these qualities. They have heaps that are large enough for GenGC to be profitable. They allocate at a high enough rate. And most of the allocated objects die almost immediately, while most of the objects that survive GC survive for many GC cycles. You need that kind of test for it to be worth it, and you would have such a test if you had big enough software to run.
- oorza 2y ago
  I remember back in the before times... when escape analysis debuted for the JVM - which allows it to scalar replace or stack allocate small enough short-lived objects that never escape local scope and therefore bypass GC altogether - our Spring servers spent something like 60% less time in garbage collection. Saying enterprise software allocates a ton of short lived objects is quite an understatement.
- hinkley 2y ago
  One of the hallmarks of pure functional languages is that each “edit” of a data collection creates a new structure that refers back to part of the original. Which should be showcased well in a reasonable benchmark. But I haven’t looked at Scheme in 32 years and I was angry about it then so I’m not going to start today. So I will just agree that something is up.
- titzer 2y ago
  Another thing big programs have is a huge ramp-up phase where they construct the main guts of their massive heap. Splay, for example, benefits from have an enormous nursery in the beginning because for the startup phase the generational hypothesis doesn't really hold; most objects survive. So the first copy or couple of copies are a waste. V8 had at one time a "high promotion mode" that would kick in for such programs at the start, using various heuristics. In high promotion mode, entire pages are simply promoted en masse to the old gen, and nursery size gets quickly enlarged.
bjourne 2y ago
Maybe it is about the safe points? In a conventional generational gc every thread has its own nursery (plus semi-space for copying collection), so you can collect one thread's garbage without stopping any other thread (so data threads share must not be allocated in the nursery). > So, for this test with eight threads, on my 8-core Ryzen 7 7840U laptop, the nursery is 16MB including the copy reserve, which happens to be the same size as the L3 on this CPU. Sounds way too small. Speed of copying collection is proportional to the number of survivors and with only 16 mb you risk having lots of false survivors.
rurban 2y ago
I was in his FOSDEM GC talk about whippet and found out that he doesn't know anything about the really good GC strategies. He only knows and implemented about dirt-slow mark-sweep, which is only needed for pointer stability from C callbacks, and then inmix which is the slow variant of a copying GC, just without the double heap requirement. But a conventional Cheney copying collector with 1-2 generations for minor sweeps is far better than those. Until he adds a proper GC to whippet I don't trust anything he says about GC's. He even has the luxury for a precise GC because scheme carries the types along with its values. And he doesn't know about colored pointers, using 2-5 bits for the GC state, nor nan-tagging. Probably neither about forwarding pointers.
- naasking 2y ago
  Immix is not a slow variant of a copying GC. It's pretty state of the art for copying GCs in fact, do claiming he doesn't know anything and hasn't implemented a "proper" GC is just incorrect.
- NeutralForest 2y ago
  I was at his talk as well and I found it interesting. Maybe you could open an issue in the Whippet repo to point at possible improvements?
- milesrout 2y ago
  You can see from his blog archives (and this post) that the author is well aware of GC strategies other than mark-sweep including Cheney copying. He has posted about conservative GC (contrary to your implication he has only implemented precise GC). Maybe "forwarding pointers" is overloaded but given he has a post about a semispace collectors which uses something he refers to as forwarding pointers I don't see how he can be said not to know about it. He also has posts referring to NaN-tagging and pointer tagging unless my memory betrays me. https://wingolog.org/tags/garbage%20collection https://wingolog.org/tags/garbage%20collection
  - rurban 2y ago
    Well, that would be good, because when we asked him in the Q&A at FOSDEM he had no idea about colored pointers and did not mention semi-space collectors at all, and had no plan to add it. I initially thought about using whippet, but I will stay clear and rather use MPS https://memory-pool-system.readthedocs.io/en/latest/ https://memory-pool-system.readthedocs.io/en/latest/
milesrout 2y ago
The issue of the generational hypothesis is interesting. Of course if a benchmark doesn't exhibit "generational" behaviour then it won't be a good test of a generational collector. But taken too far, that creates a bias: you are selecting benchmarks that fit what you know a generational collector is good at. The question then is: are real world programs as generational as we think? This might depend on whether we assume are are using a generational collector. If you assume shortlived object allocation is ~free then you will produce software conforming to the generational hypothesis but that is not good evidence that the generational hypothesis is true. It is a bit like saying "caches are important because of locality of reference" and exhibiting as evidence code optimised to make good use of caches. We have to be careful that we are not just measuring things designed around themselves.
sfink 2y ago
My understanding is that splay is more of a benchmark that you try to make generational GC not hurt too much. It allocates lots of long-lived objects that it holds onto for the full test, and for JS at least it then hangs strings off of those objects. It's pretty easy to make a generational GC just add an extra copy for no benefit with splay. In SpiderMonkey, we had to add pretenuring in order to avoid slowing down splay too much. As in, identify specific allocation sites that create long-lived allocations, and allocate them directly from the older generation instead of having them go through the nursery. It's sort of selectively disabling generational GC on an allocation site granularity. (Also, make sure you're not storing nursery strings inside of tenured objects. While it's possible they'll be quickly overwritten by different strings, it's much more likely that they're going to last as long as the object does.) Within Octane, the RegExp subtest had the biggest gain from allocating strings in the nursery. (But that's going from generational objects -> generational objects and strings. Non-generational objects -> generational objects might show up more on something else.)
- bjourne 2y ago
  Wouldn't be very difficult to know a priori whether the object allocated at a callsite is likely to be long-lived? The object has to be allocated before you can make some other object reference it. So when you do, even if you know that the reference is from an old-gen object "the mistake has already been made" and the new object has been allocated in the nursery.
  - rcxdude 2y ago
    I think the idea is you can then adjust future allocations from the same callsite, assuming that object lifetime is fairly well correlated with allocating callsite.
    - sfink 2y ago
      Exactly. During minor GC, you update the promotion rate of each callsite. If it gets too high, you start allocating things from that callsite directly from the tenured heap, since your statistics are telling you that the things allocated at that callsite are usually going to end up living long enough that you're just wasting time scanning and copying them from the nursery to the tenured heap. And yes, it assumes that lifetime is correlated pretty well with allocating callsite. Also that the correlation persists over time. The latter part often doesn't hold, so it's helpful to have a mechanism for changing the decision if you're finding a lot of dead stuff in the tenured heap that came from a pretenured callsite. But it's a delicate tradeoff: tracking the allocation sites costs time and memory, and so you might only want to do that for nursery allocations, but then you don't have a way to associate dead tenured objects with their allocation sites in case you need to stop pretenuring... lots of possibilities in the design space.
kazinator 2y ago
To see a benefit from generational garbage collection, you need a lot of mature data in the heap of your test case. If there's not a big difference between a full traversal and a partial traversal, the benefit won't be realized. I suspect it's a huge win in most modern manage application settings, because application images are huge with a lot of cruft in them. If your algorithm is churning away allocating lots of temporary objects, and it's sitting in the middle of a behemoth image, generational GC is a big win. In dynamic languages, the functions themselves are objects that can be garbage collected and the function bindings have to be traversed in a full GC. It functions rarely change. Quickly recede into the mature generation. You can investigate generational vs simple mark-and-sweep with my TXR Lisp. At compile time you can configurate to disable generational GC. This is not being regularly tested but I did check it for regressions fairly recently. It is not a copying collector. Objects stay where they are. The nursery is just a global array of pointers. There are two other arrays that help with the old pointing to young mutation. Resetting these arrays costs almost nothing: we just set their fill indices to zero. You can easily tune their sizes and there's a configuration for a small memory which changes several defaults at the same time.
barrkel 2y ago
Generational GC is based on the assumption that most objects die young, and objects that survive are around for a long time - a kind of bathtub object lifetime curve. This assumption is approximately true for GUI apps, and a lot more true for server apps. The idea is that all the objects allocated during an event dispatch or a server request are dead when control returns to the event loop. To make those assumptions fit the program better, the size of the generations should be tuned (manually or automatically) such that for the rate of allocation this assumption holds true. You need three generations: the first, where objects are born and only a few survive long enough to get out; the second, for objects which are destined to die young, but happen to still be alive when you collect the first generation; and the third, for objects that hopefully never die, so you never have to collect it. The first generation should be sized to fit in something close to a CPU cache, so it’s really quick to scan. The second generation should be sized so that it is not collected often enough to have live objects in it - it should outlive the longest event / request dispatch you’ve got, and then a little bit more. If your application doesn’t feel like a GUI or a server app that dispatches events or requests, generational GC probably isn’t the right choice for you.

141 points by todsacerdoti 2y ago

I wonder how much the perceived advantages of generational GC are only due to Java's tendency to generate a lot of short-lived garbage.

mananaysiempre 2y ago
“A lot” is relative—I seem to remember a discussion long ago mentioning that Haskell/Scala-style programs were a problem for the JVM because the JVM is not designed for so many objects dying so quickly.
- kgeist 2y ago
  I remember long time ago JBullet, a physics simulation library, had to maintain an error-prone pool of vectors and matrices because all the calculations involving the creation of temporary vectors and matrices put significant stress on the GC. Today, Minecraft allocates around 600 MB/s for a similar reason (Position3D objects & friends); however, on my PC, I don't notice any pauses.
  - gf000 2y ago
    Is that really error-prone for a physics simulation engine? That's pretty common to only refer to data by indices in other places - sure, there are languages that can deal with it a bit better (e.g. operator overloading, manual memory management and/or value types), but as far as I know this is even often done in Rust, which has the previous properties (it's done to avoid the borrow checker there). Also, Minecraft was famously written famously inefficiently.
    - kgeist 2y ago
      By "error-prone," I mean that if you accidentally stored a reference to a pooled vector and used it after it was returned to the pool, all sorts of unexpected things could happen since everything is by reference. You had to be very careful.
  - hinkley 2y ago
    I had a friend/former mentor who proved that object pools are slower in Java once GenGC was introduced because they create pointers from the old generation to the new. He also authored the fasted XML parser of that era and previously helped me land a project everyone but us and our boss said was impossible because Java Is Too Slow, so I take him at his word. So unless those pools are full of primitive data types, you’re going to cause more frequent full GC pauses, and longer due to all the back pointers.
    - fiddlerwoaroof 2y ago
      If you could add some sort of hint to the object pool instance that it should always be in the new generation, then you wouldn’t have this problem. This could probably be provided generically as a class named something like NurseryCollection. However, I thought the people that really were serious about performance would allocate the pool in memory the GC doesn’t control (back in the day using internal APIs, but I think there are new official APIs for this) such that the object pool and every object in it would just be ignored by the GC.
      - hinkley 2y ago
        Looks like an arena allocator is available in JDK 20. But I’m fairly sure it’s been in the RT spec for a lot longer.
    - ickyforce 2y ago
      > So unless those pools are full of primitive data types, you’re going to cause more frequent full GC pauses, and longer due to all the back pointers. If you have enough objects pooled to get low allocation rate then you never trigger full GC. That's what "low latency Java" aims for. I think that the main downside of object pools in Java is that it's very easy to accidentally forget to return an object to a pool or return it twice. It turns out that it's hard to keep track of what "owns" the object and should return it if the code is not a simple try{}finally{}. This was a significant source of bugs at my previous job (algo trading).
      - 2y ago
- gf000 2y ago
  The JVM is more than happy with short-lived objects, they are barely more expensive than a normal stack allocation (mostly by the header only). The JVM has a so-called Thread-Local Allocation Buffer, which is basically a simple buffer with a pointer pointing to the next free slot. It can be simply bumped up on a new object's allocation and later on the still alive objects will be evacuated to another generation and the whole thing can be cleared. This is faster than any malloc implementation CPP/rust/whatever might use, besides they also doing arena allocations. Haskell has a few tricks up its sleeve that can help with its kind of allocation patterns, but speaking specifically about Haskell, it's mostly the laziness that makes it quite different.
  - lowbloodsugar 2y ago
    But it’s not as fast as just allocating a structure on the stack instead of checks graph 20 objects on the heap, all pointing to the next with 64bit pointers. I’ve got Rust struct that are 80 bytes and the same structure in Java is 800 bytes.
    - gf000 2y ago
      What's the difference between the stack and a thread-local, constantly hot/in-cache other region of the same memory? Especially that in many cases the objects are allocated right next to each other, so fetching happens from cache again. Not saying that expertly written Rust code can't beat naive Java one, and especially with the object headers Java will have a performance disadvantage in many cases - but that's a tiny disadvantage in most real-world use cases, multiple times offset by its advantages. (Besides, Java has on-stack replacement which can do the exact same thing as rust does, but the JIT-compiler Gods have to be in the correct alignment for that)
      - lowbloodsugar 2y ago
        What’s the difference…? 1. The size. 2. I don’t see that happening and I look at the output of the C2 compiler when I’m dealing with hotspots. In aware of the cool shit the JVM can do but done right, areas of code can be as fast as C or Rust. It in general, My experience is that Rust is much faster. Sometimes 10x faster where it matters to me (sustained server load).
pfdietz 2y ago
Generational GC was perceived as useful even before Java existed, for example in Lisp.
- actuallyalys 2y ago
  Funnily enough, my impression is that Clojure, the most popular Lisp on the JVM, creates a lot of garbage—probably more than Java—but I believe that’s due to it using immutable collections and not due to it being a Lisp.
  - fiddlerwoaroof 2y ago
    Yeah, immutable collections have to use structure-sharing to be implemented efficiently and this frequently results in common operations allocating lots of small objects rather than updating some object in-place.
    - zozbot234 2y ago
      You can use a borrow checker to replace immutable objects with update-in-place ("ephemeral") ones where feasible.
      - fiddlerwoaroof 2y ago
        And, escape analysis and "dynamic extent" hints can have similar effects by stack-allocating intermediate values. Also, you can design your transformations to compose before handing off to a result builder, which is how modern Clojure reduces this problem.
davidgay 2y ago
You've clearly never observed the allocation behaviour of a continuation-based compiler (every function call causes a short-lived heap allocation - the heap is the "stack")...
- wbl 2y ago
  And the stack the heap with Cheney on the MTA.
steveklabnik 2y ago
I have long suspected that there is some sort of deeper truth here. It’s not really about Java. If you squint hard enough, a C program has the stack as its nursery, and the heap as a singular old generation. The stack is even arena allocated, of sorts! This is of course a bit hand-wavy, I haven’t had the time to truly try and investigate this in a more rigorous way.
- jerf 2y ago
  In general, memory management needs to be understood as a continuum and not a binary "uses GC or uses manual memory management". Per the very discussion we're having, GC is not an atomic thing, and on the other end, what is commonly called "manual memory management" is itself not. malloc still makes non-trivial decisions, as evidenced by the fact that some programs can be greatly benefited or harmed by switching out the malloc it uses. Beyond what most people call "manual memory management" lies "arena allocation", and in the really extreme case, fully static memory layout with no allocation at all. The latter is how NES games were generally written and sufficiently small embedded projects still get written that way today. Further pushing this into a "continuum" rather than a binary flag is that programs can and do freely mix and match. Nothing stops a program from using two mallocs, some arenas, GC for certain values, and static allocations for yet others. The Memory Management Police do not come along and arrest you for having Impure Designs or anything. There are languages like (I believe) Zig where the ability to cleanly do this is more-or-less a first-class language feature.

hu3 2y ago

I always thought Go used generational garbage collector but alas it's not: https://tip.golang.org/doc/gc-guide https://tip.golang.org/doc/gc-guide

zozbot234 2y ago
Doesn't Golang use concurrent GC anyway, and shouldn't that lead to significantly lower latency compared to more traditional approaches?
- hu3 2y ago
  Yes, it's optimized for latency: https://tip.golang.org/doc/gc-guide#Latency https://tip.golang.org/doc/gc-guide#Latency So, for example, network code gets better p99. This, along with other sensible tradeoffs, is why Go ate a large slice of network software market.
  - kgeist 2y ago
    IIRC Go has "GC assist" which forces goroutines that allocate too frequently to assist in GC work (share CPU time, i.e. they're slowed down), and I've never seen anything like that described for Java/C#. Interesting approach.
    - gf000 2y ago
      In other words, it slows down the user's code randomly. I wouldn't call that a necessarily good tradeoff.
      - kgeist 2y ago
        It's a back-pressure mechanism. I think slightly slower code on average is better than unexpected long GC pauses.
        gf000 2y ago

lern_too_spel 2y ago

You need to understand the object lifetime distribution.

ComputerGuru 2y ago

C# (and .NET at large) use generational GV to great effect and there are some good writeups on the different modes you can run the GC in and its performance profiles. .NET has been generational GC since forever and you can’t swap out the GC engine so you won’t be able to find an analogous comparison, but it’s probably the current generational GC SOTA for a one-size-fits-all (with admittedly two different allocation/cleanup roles: server and workstation; and with (new to .NET 9) a new option to configure the GC to act as if it were running alone on the system (the old default, i.e. not sharing resources with other apps on the same os) or to more cooperatively try to manage allocation patterns. Just mentioning this in case someone wants to read up on a different GC and play around with benchmarks. There is a fair amount of inner workings info and real-world results to dive into.

lostmsu 2y ago
You actually can change .NET GC! https://news.ycombinator.com/item?id=42851061 https://news.ycombinator.com/item?id=42851061
- ComputerGuru 2y ago
  Thanks for sharing that; now I have something to add to my list of things to play with when I get a chance!

snikeris 2y ago

I think the idea is to reduce the set of memory that needs to be frequently collected. Long lived objects age to the old generation which can be large and infrequently collected. I've used this kind of collector in the past for applications which held a large and mostly static dataset in memory.

caspper69 2y ago

His blog post is based upon the premise that his generational gc allocator doesn't seem to provide the performance benefits that generational gc is claimed to provide vs other more traditional gc approaches (e.g. mark and sweep- also his implementation). My initial take is that either his implementations are deficient in some way (or not sufficiently modern), there's some underlying latent issue that arises from the Scheme to C compiler or the kind of C code it generates, or perhaps the benchmarks he is using are not indicative of real-world workloads. But- I am out of my depth to analyze those things critically, and he seems to write about GC quite a bit, so maybe he's very in tune with the SOTA and he has uncovered an unexpected truth about generational gc. It certainly wouldn't be the first time that an academic approach failed to deliver the benefits (or perhaps I should say the benefits weren't as great in as many scenarios as originally opined). As an idiot programmer, my understanding is that Java, .NET & Go all have generational GC that is quite performant compared to older approaches, and that steady progress is made regularly across those ecosystems' gc (multiple gcs in the case of Java). P.S. and now I see in a comment below (or maybe above now) that Go doesn't use a generational gc. I'm surprised.

neonsunset 2y ago
Go has somewhat "exotic" non-generational design optimized for latency. As a result it has poor throughput and performs quite badly outside the scenarios it was designed for. But on moderate to light allocation traffic it is really nice. Just not very general-purpose. Java has by far the most advanced GC implementations (it lives and dies by GC perf/efficiency after all) with .NET being a very close competitor.
- caspper69 2y ago
  Your comment posted as I was making my edit re: Go. Thank you for the detailed clarification.
- schmichael 2y ago
  Go optimizing for latency over throughput means the GC very rarely interferes with my applications SLO at the cost (literally $) of presumably requiring more total compute than a GC that allows more fine tuned tradeoffs between latency and throughput. As someone who is not directly paying the bills but has wasted far too much of my life staring at JVM GC graphs and carefully tuning knobs, I vastly prefer Go’s opinionated approach. Obviously not a universally optimal choice but I’m so thankful it works for me! I don’t miss pouring over GC docs and blog posts for days trying to save my services P99 from long pauses.

mjburgess 2y ago

I'd imagine generational GCs are perform better on OO languages, especially ones where almost everything is boxed. I have recently prototyped my own non-OO, multifn-style polymorphic language using tagged pointers (60 bit payload, 4 bit tag) -- you can fit a float32, int/uint, etc. into 60bits -- as well as a case-insensitive 12 char alphanumeric string. Where various unboxed container types are available (eg., matrix of doubles, etc.) --- you can do a lot with just allocating to a local arena for a given scope, then resetting the arena. In this case, I lean to wards a very simple GC for all the heap stuff, since its probably going to be mostly large long-lived objects.

GMoromisato 2y ago
BTW, I'm using NaN boxing, and it's great--I can fit a float64 into 8 bytes and have bits left over for tagging pointers, ints, etc. Basically, the idea is to encode all non-float values into the NaN representation. The NaN value in a float64 leaves 52-bits undefined. You can use those to encode the other values.

mike_hearn 2y ago

It does work, at least for imperative languages that allocate things on the heap a lot. Look at the evolution of Java's open source pauseless GCs. Both ZGC and Shenandoah started out non-generational for ease of implementation reasons. They both now went fully generational, with big improvements in real world and benchmark performance (throughput as they were pauseless already).

nobodyandproud 2y ago

My guess: In real world scenarios, there’s overhead such swap space and virtual memory, analogous to a cache miss. A full mark—and-sweep GC would have deal with this extra overhead. Whereas a generational GC would reduce the amount of a miss because it only considers a subset of objects; and the least likely bit of memory in the disk/slower swap space are the most recently allocated objects.

pizlonator 2y ago

I think it’s the choice of benchmarks. GenGC is an improvement if you have: - High allocation rate. I think his benchmarks do have high allocation rate so this part is fine. - Large heap. I think splay has a large heap so this part is fine. - Lots of objects in that large heap that simply survive one GC after another, while the allocation rate is mostly due to objects that die immediately. This is the part that splay doesn’t have. Splay churns all of its large heap. Empirically, really big software written in GC’d languages have all three of these qualities. They have heaps that are large enough for GenGC to be profitable. They allocate at a high enough rate. And most of the allocated objects die almost immediately, while most of the objects that survive GC survive for many GC cycles. You need that kind of test for it to be worth it, and you would have such a test if you had big enough software to run.

oorza 2y ago
I remember back in the before times... when escape analysis debuted for the JVM - which allows it to scalar replace or stack allocate small enough short-lived objects that never escape local scope and therefore bypass GC altogether - our Spring servers spent something like 60% less time in garbage collection. Saying enterprise software allocates a ton of short lived objects is quite an understatement.
hinkley 2y ago
One of the hallmarks of pure functional languages is that each “edit” of a data collection creates a new structure that refers back to part of the original. Which should be showcased well in a reasonable benchmark. But I haven’t looked at Scheme in 32 years and I was angry about it then so I’m not going to start today. So I will just agree that something is up.
titzer 2y ago
Another thing big programs have is a huge ramp-up phase where they construct the main guts of their massive heap. Splay, for example, benefits from have an enormous nursery in the beginning because for the startup phase the generational hypothesis doesn't really hold; most objects survive. So the first copy or couple of copies are a waste. V8 had at one time a "high promotion mode" that would kick in for such programs at the start, using various heuristics. In high promotion mode, entire pages are simply promoted en masse to the old gen, and nursery size gets quickly enlarged.

bjourne 2y ago

Maybe it is about the safe points? In a conventional generational gc every thread has its own nursery (plus semi-space for copying collection), so you can collect one thread's garbage without stopping any other thread (so data threads share must not be allocated in the nursery). > So, for this test with eight threads, on my 8-core Ryzen 7 7840U laptop, the nursery is 16MB including the copy reserve, which happens to be the same size as the L3 on this CPU. Sounds way too small. Speed of copying collection is proportional to the number of survivors and with only 16 mb you risk having lots of false survivors.

rurban 2y ago

I was in his FOSDEM GC talk about whippet and found out that he doesn't know anything about the really good GC strategies. He only knows and implemented about dirt-slow mark-sweep, which is only needed for pointer stability from C callbacks, and then inmix which is the slow variant of a copying GC, just without the double heap requirement. But a conventional Cheney copying collector with 1-2 generations for minor sweeps is far better than those. Until he adds a proper GC to whippet I don't trust anything he says about GC's. He even has the luxury for a precise GC because scheme carries the types along with its values. And he doesn't know about colored pointers, using 2-5 bits for the GC state, nor nan-tagging. Probably neither about forwarding pointers.

naasking 2y ago
Immix is not a slow variant of a copying GC. It's pretty state of the art for copying GCs in fact, do claiming he doesn't know anything and hasn't implemented a "proper" GC is just incorrect.
NeutralForest 2y ago
I was at his talk as well and I found it interesting. Maybe you could open an issue in the Whippet repo to point at possible improvements?
milesrout 2y ago
You can see from his blog archives (and this post) that the author is well aware of GC strategies other than mark-sweep including Cheney copying. He has posted about conservative GC (contrary to your implication he has only implemented precise GC). Maybe "forwarding pointers" is overloaded but given he has a post about a semispace collectors which uses something he refers to as forwarding pointers I don't see how he can be said not to know about it. He also has posts referring to NaN-tagging and pointer tagging unless my memory betrays me. https://wingolog.org/tags/garbage%20collection https://wingolog.org/tags/garbage%20collection
- rurban 2y ago
  Well, that would be good, because when we asked him in the Q&A at FOSDEM he had no idea about colored pointers and did not mention semi-space collectors at all, and had no plan to add it. I initially thought about using whippet, but I will stay clear and rather use MPS https://memory-pool-system.readthedocs.io/en/latest/ https://memory-pool-system.readthedocs.io/en/latest/

milesrout 2y ago

The issue of the generational hypothesis is interesting. Of course if a benchmark doesn't exhibit "generational" behaviour then it won't be a good test of a generational collector. But taken too far, that creates a bias: you are selecting benchmarks that fit what you know a generational collector is good at. The question then is: are real world programs as generational as we think? This might depend on whether we assume are are using a generational collector. If you assume shortlived object allocation is ~free then you will produce software conforming to the generational hypothesis but that is not good evidence that the generational hypothesis is true. It is a bit like saying "caches are important because of locality of reference" and exhibiting as evidence code optimised to make good use of caches. We have to be careful that we are not just measuring things designed around themselves.

sfink 2y ago

My understanding is that splay is more of a benchmark that you try to make generational GC not hurt too much. It allocates lots of long-lived objects that it holds onto for the full test, and for JS at least it then hangs strings off of those objects. It's pretty easy to make a generational GC just add an extra copy for no benefit with splay. In SpiderMonkey, we had to add pretenuring in order to avoid slowing down splay too much. As in, identify specific allocation sites that create long-lived allocations, and allocate them directly from the older generation instead of having them go through the nursery. It's sort of selectively disabling generational GC on an allocation site granularity. (Also, make sure you're not storing nursery strings inside of tenured objects. While it's possible they'll be quickly overwritten by different strings, it's much more likely that they're going to last as long as the object does.) Within Octane, the RegExp subtest had the biggest gain from allocating strings in the nursery. (But that's going from generational objects -> generational objects and strings. Non-generational objects -> generational objects might show up more on something else.)

bjourne 2y ago
Wouldn't be very difficult to know a priori whether the object allocated at a callsite is likely to be long-lived? The object has to be allocated before you can make some other object reference it. So when you do, even if you know that the reference is from an old-gen object "the mistake has already been made" and the new object has been allocated in the nursery.
- rcxdude 2y ago
  I think the idea is you can then adjust future allocations from the same callsite, assuming that object lifetime is fairly well correlated with allocating callsite.
  - sfink 2y ago
    Exactly. During minor GC, you update the promotion rate of each callsite. If it gets too high, you start allocating things from that callsite directly from the tenured heap, since your statistics are telling you that the things allocated at that callsite are usually going to end up living long enough that you're just wasting time scanning and copying them from the nursery to the tenured heap. And yes, it assumes that lifetime is correlated pretty well with allocating callsite. Also that the correlation persists over time. The latter part often doesn't hold, so it's helpful to have a mechanism for changing the decision if you're finding a lot of dead stuff in the tenured heap that came from a pretenured callsite. But it's a delicate tradeoff: tracking the allocation sites costs time and memory, and so you might only want to do that for nursery allocations, but then you don't have a way to associate dead tenured objects with their allocation sites in case you need to stop pretenuring... lots of possibilities in the design space.

kazinator 2y ago

To see a benefit from generational garbage collection, you need a lot of mature data in the heap of your test case. If there's not a big difference between a full traversal and a partial traversal, the benefit won't be realized. I suspect it's a huge win in most modern manage application settings, because application images are huge with a lot of cruft in them. If your algorithm is churning away allocating lots of temporary objects, and it's sitting in the middle of a behemoth image, generational GC is a big win. In dynamic languages, the functions themselves are objects that can be garbage collected and the function bindings have to be traversed in a full GC. It functions rarely change. Quickly recede into the mature generation. You can investigate generational vs simple mark-and-sweep with my TXR Lisp. At compile time you can configurate to disable generational GC. This is not being regularly tested but I did check it for regressions fairly recently. It is not a copying collector. Objects stay where they are. The nursery is just a global array of pointers. There are two other arrays that help with the old pointing to young mutation. Resetting these arrays costs almost nothing: we just set their fill indices to zero. You can easily tune their sizes and there's a configuration for a small memory which changes several defaults at the same time.

barrkel 2y ago

Generational GC is based on the assumption that most objects die young, and objects that survive are around for a long time - a kind of bathtub object lifetime curve. This assumption is approximately true for GUI apps, and a lot more true for server apps. The idea is that all the objects allocated during an event dispatch or a server request are dead when control returns to the event loop. To make those assumptions fit the program better, the size of the generations should be tuned (manually or automatically) such that for the rate of allocation this assumption holds true. You need three generations: the first, where objects are born and only a few survive long enough to get out; the second, for objects which are destined to die young, but happen to still be alive when you collect the first generation; and the third, for objects that hopefully never die, so you never have to collect it. The first generation should be sized to fit in something close to a CPU cache, so it’s really quick to scan. The second generation should be sized so that it is not collected often enough to have live objects in it - it should outlive the longest event / request dispatch you’ve got, and then a little bit more. If your application doesn’t feel like a GUI or a server app that dispatches events or requests, generational GC probably isn’t the right choice for you.