Garbage collectors, visually

In 2007 I spent the better part of a week chasing a memory leak in a .NET desktop app, and I wrote it up at the time as how to leak memory in .NET. The culprits were a couple of third-party UI components that kept references to our controls in static hashtables, so documents we opened and closed never went away. Along the way I learned WinDbg with SOS, !dumpheap to see what was piling up and !gcroot to ask “what is keeping this object alive?”, though what actually cracked it was a commercial memory profiler that showed where each reference came from.

I didn’t really understand at the time why !gcroot was the right question. I knew the GC “cleans up objects you’re not using”, and I was annoyed that it wasn’t. It took me a while to internalize that a garbage collector has no idea what you’re using. It only knows what’s reachable. Those two are almost the same thing, and the gap between them is where every managed memory leak lives.

So this is the post I’d have wanted then: how the main kinds of collector actually work, drawn out, with .NET as the running example because that’s the one I know best.

Reachability

Every collector starts from the roots: local variables and arguments on each thread’s stack, static fields, CPU registers, and a few special handles. Anything a root points to is alive. Anything a live object points to is alive. Everything else is garbage, by definition, whether or not you’d think of it that way.

My 2007 leak was a static hashtable, which is a root, pointing at our controls, which pointed at their documents. Reachable. Alive. The GC was doing its job perfectly.

Mark-sweep

The simplest tracing collector has two phases. Mark: start at the roots and follow every reference, marking each object you reach. Sweep: walk the whole heap, and anything not marked goes back on the free list.

The C-F-G cycle in that picture is the reason tracing collectors exist at all. With reference counting, which is what COM did and what I spent a good chunk of my Windows SDK years getting wrong (one missing Release() and the object lives forever, one extra and it dies under you), each of those three objects has a count of 1 forever, because each is pointed to by another. Nothing outside can reach them, and refcounting can’t tell. A tracing collector never looks at them, so they’re just gone. (Python does refcounting plus a separate cycle detector, for exactly this reason.)

Plain mark-sweep has two problems. The pause grows with the heap, since marking touches every live object and sweeping touches everything. And it fragments memory. After a few cycles the free space is scattered in holes between live objects, allocation has to search a free list for a hole that fits, and you can be out of memory for a 1 MB array while having 50 MB free in small pieces.

Compacting

The fix for fragmentation is to move things. After marking, slide all the live objects down to one end of the heap and update every reference to point at the new locations. Now the free space is one contiguous block, and allocation becomes almost free: keep a pointer to the start of the free space and bump it forward by the size of each new object. That’s how the .NET and JVM allocators can allocate in a handful of instructions, which still surprises people coming from C++, where malloc is a real function with real work to do.

The cost is the moving itself, and the bookkeeping to fix up every pointer, and the fact that you can’t move an object something outside the runtime has a raw pointer to. That’s what pinning is, fixed in C# or a pinned GC handle when you pass a buffer to native code. A pinned object is a rock in the middle of the heap that the compactor has to work around, and if you pin a lot of objects for a long time you get your fragmentation back.

Generational

The idea that made garbage collection fast enough for everyday use started as an observation about programs: most objects die young. The string you built to log one line, the enumerator in a foreach, the DTO for one request. They’re garbage within microseconds. The objects that survive for a while (caches, configuration, the long-lived parts of the app) tend to survive for a very long time.

So split the heap by age and collect the young part much more often:

A gen 0 collection only has to trace the young objects, and since most of them are dead, there’s very little to mark and very little to move. Survivors get promoted to gen 1, and survivors of a gen 1 collection go to gen 2, which is only collected when it has to be. A healthy .NET app does lots of gen 0 collections, some gen 1s and few gen 2s, and you can watch this in the .NET CLR Memory performance counters, which is the first thing I look at now when someone says a service “has GC problems”.

There’s a catch, and it’s a nice piece of engineering. To collect gen 0 without tracing gen 2, you need to know about every reference from an old object to a young one, because that young object is alive even if no root points to it directly. Scanning all of gen 2 to find them would defeat the whole point. So the runtime adds a write barrier: every time your code stores a reference into an object’s field, a few extra instructions mark the corresponding chunk of memory as dirty in a card table. A gen 0 collection then only has to scan the dirty cards of the old generation. You pay a tiny bit on every reference write to make young collections cheap, and it’s a good trade.

The large object heap

Objects of 85,000 bytes or more skip all this and go straight to the large object heap, because copying big objects around during compaction is expensive. The LOH is collected only with gen 2, and historically it was never compacted, so it fragments. Since .NET 4.5.1 you can ask for a one-off compaction with GCSettings.LargeObjectHeapCompactionMode, which is a good sign that enough people got bitten.

We got bitten earlier this year. A service of ours that generated reports was allocating a fresh byte[] of a few hundred KB for every request. Every one of those went to the LOH, the LOH filled up, and each time it did it triggered a full gen 2 collection, under load, every few seconds. The p99 latency graph had a sawtooth with a period of about four seconds. The fix was to stop allocating: rent buffers from ArrayPool<byte>.Shared and return them when done. Gen 2 collections went from about fifteen a minute under load to a couple an hour. Nothing about our logic changed, only how often we asked the runtime for big new chunks of memory.

Not stopping the world

Everything so far is “stop the world”: pause all your threads, collect, resume. For gen 0 that’s fine, but a full gen 2 collection on a big heap can take a long time. So most production collectors do as much as they can concurrently, marking while your threads keep running. .NET has had background GC since 4.0, which does gen 2 marking on a separate thread while gen 0 and 1 collections keep happening. On servers, <gcServer enabled="true"/> gives you a heap and a GC thread per core, which is much better throughput for a busy service and uses a lot more memory, and it’s worth checking which one your service is actually running with. Ours wasn’t what we thought.

Concurrent marking is subtle, because your code is changing the object graph while the collector is walking it. The standard way to think about it is tri-color marking: white objects haven’t been seen, gray ones have been seen but their references haven’t been scanned, black ones are done. The invariant the collector has to keep is that a black object never points to a white one, and when your code stores a white object’s reference into a black object, a write barrier has to step in and shade something gray. Get that wrong and the collector frees a live object, which is the worst bug a runtime can have.

Go went the other way

The interesting outlier is Go. Its collector is concurrent tri-color mark-sweep, and it’s not generational and not compacting. That sounds like it’s ignoring 30 years of research, and I was skeptical. But they chose to optimize for one number, pause time, and since Go 1.8, early last year, typical pauses are under a millisecond, even on large heaps. Rick Hudson’s keynote at ISMM in June, which the Go blog published last month as Getting to Go, goes through why. Part of it is that Go has value types and stack allocation, so fewer short-lived objects end up on the heap than in Java or C#, and the generational hypothesis has less to work with. Part of it is that they did try a (non-moving) generational design, and the write barrier it needed cost more than it saved. And the price is real: Go’s collector trades throughput and memory overhead for those short pauses.

Java, meanwhile, made G1 the default in Java 9 last year, which is generational and compacting and works on regions of the heap rather than whole generations at a time, with a pause time target you can set. Which approach is right depends on whether you care more about throughput or about worst-case latency, and I’m not convinced there’s one answer.

Back to 2007

The thing I wish I’d known then is that every managed leak is a reachability question, and there are only a few usual suspects: statics and singletons, event handlers (the publisher holds a reference to every subscriber until you unsubscribe), caches without eviction, and timers. When memory grows in a .NET app now, I take a dump, run !dumpheap -stat to see what type is piling up, pick one instance and run !gcroot on it. The answer is almost always one of those four, and in 2007 it was the first two: statics inside somebody else’s DLL, plus a few event handlers on things like Application.Idle that we’d never unhooked.