Baffled by generational garbage collection – wingolog

https://wingolog.org/archives/2025/02/09/baffled-by-generational-garbage-collection

by todsacerdoti • 1 year ago

141 121 1 year ago

cesarb• 1 year 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• 1 year 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.

kgeist6• 1 year 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.

gf00013• 1 year 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.

pfdietz• 1 year ago

Generational GC was perceived as useful even before Java existed, for example in Lisp.

actuallyalys• 1 year 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.

davidgay• 1 year 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• 1 year ago

And the stack the heap with Cheney on the MTA.

steveklabnik• 1 year 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• 1 year 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.

hu32• 1 year ago

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

zozbot2343• 1 year ago

Doesn't Golang use concurrent GC anyway, and shouldn't that lead to significantly lower latency compared to more traditional approaches?

hu32• 1 year ago

Yes, it's optimized for 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.

lern_too_spel• 1 year ago

You need to understand the object lifetime distribution.

ComputerGuru2• 1 year 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• 1 year ago

You actually can change .NET GC! https://news.ycombinator.com/item?id=42851061

ComputerGuru2• 1 year 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• 1 year 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.

caspper694• 1 year 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.

neonsunset9• 1 year 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.

caspper694• 1 year ago

Your comment posted as I was making my edit re: Go.

Thank you for the detailed clarification.

schmichael2• 1 year 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.

cyberax2• 1 year ago

There are some discussions to add optional generational regions to Go: https://github.com/golang/go/discussions/70257

whitehexagon• 1 year ago

I spent quite some years performance tuning large Java systems, pre-warming server JVMs and then many hours staring at visualgc, a small Sun engineers tool for watching the various memory pools including generational GC, it was very satisfying work, and also pretty useful for uncovering bugs and race conditions when the systems were under load.

The GC advances that came along helped a lot, especially over the stop-the-world early days of Java GC, along with all the JVM tuning parameters that were gradually exposed for tweaking. But visualgc allowed for a real feel for how the generational GC was running just by watching the saw-tooth shaped graphs. Interestingly most of the garbage was string copying, especially with one companies system that had more abstractions than a Spring Oak has leaves, say no more least I have nightmares.

citrin_ru• 1 year ago

Go creates less garbage (more allocated on stack) so generational GC is less essential.

mjburgess• 1 year 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• 1 year 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• 1 year 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• 1 year 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• 1 year 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• 1 year 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.

hinkley6• 1 year 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• 1 year 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.

kazinator2• 1 year ago

In these systems it might make sense to have the image start with GC disabled, and the application will turn it on past a certain point in its initialization, and do a full GC at that point to compact everything to the mature generation.

fweimer• 1 year ago

That's probably it. I found a weird Java version of the benchmark here:

https://github.com/newspeaklanguage/benchmarks/blob/master/S...

At least for some parameters, non-generational Shenandoah is faster than generational G1 (both overall run time and time spent in the benchmark phase, and overall CPU usage). But I expect it's possible to get wildly varying benchmark behavior depending on the parameter choices (the defaults are of course much too low).

dan-robertson• 1 year ago

So maybe it would be interesting if allocations could be tracked better for the test? Maybe see the distribution of allocation life in terms of how many minor GCs are survived (perhaps you need to hack in some whole-heap liveness checking each time there’s a minor gc, for the purposes of the experiment). I think it would be nice to be able to rule out ‘most objects are promoted but have short lives’ as a cause.

CyberDildonics• 1 year ago

This is exactly why so much garbage collection optimization is apples and oranges. It is trying to mitigate the performance problems from things you shouldn't do in the first place if you care about speed.

Heap allocation, heap deallocation and the pointer chasing that comes along with the memory fragmentation are possibly the biggest killers of speed outside of scripting languages but java was designed in a way that it forces people into way of programming. As a result, enormous research has gone into trying to deal with something that could have been avoided completely.

bjourne4• 1 year 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.

rurban2• 1 year 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.

naasking3• 1 year 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• 1 year 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?

milesrout3• 1 year 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

rurban2• 1 year 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/

milesrout3• 1 year 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.

sfink2• 1 year 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.)

bjourne4• 1 year 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• 1 year 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.

kazinator2• 1 year 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• 1 year 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.

Baffled by generational garbage collection – wingolog

Related Stories