What garbage collection actually costs

Every computer program needs memory. Memory is finite, so a long running program must borrow memory from the operating system when it needs it and release it once it is no longer needed.

The interesting part is who reclaims that memory, and when. Some piece of code has to figure out that a piece of memory is no longer needed and release it, and figuring that out is not trivial. A value might be passed to another function, stored somewhere longer-lived, or shared across threads, and it stays needed as long as anything still refers to it. If it is reclaimed early, we get memory corruption. If it is reclaimed too late, we get memory leaks.

The paradigms

There are two paradigms for memory management, each optimizing for different things.

The first paradigm is to let the language runtime do it. A program allocates memory when it needs it, uses it as long as required, and eventually stops referring to it. A garbage collector figures out what is no longer reachable and reclaims it. Go, Java and a lot of other languages in wide use belong to this category. You give up deciding when memory is freed, but in exchange you cannot free it too early, free it twice, or forget to free it at all. For most software this is a very good compromise. It reduces the cognitive overhead of memory management and you can stay focused on the actual problem. The leaks that come from forgetting to free something go away entirely.

The second paradigm, which must be very evident at this point, is to keep the decision to yourself. In C, you allocate and free by hand, and you own every bug that comes as a result. In Rust you do not write the frees, but you do not hand the decision to a runtime either. The compiler works out at build time where each value’s life ends, reclaims it there, and refuses to build the program if it cannot prove that this is safe. So you still get control over memory and a tighter footprint, but the effort shifts. In C you pay for it by debugging corruption. In Rust you pay for it by arranging your program in a way the compiler can verify.

Sitting in between is reference counting, which is what Swift and Python do. It is really a variant of the first answer rather than a third paradigm, and it is seldom enough on its own. Counts cannot see cycles, so a language has to deal with them some other way. Python bolts on a tracing collector that hunts for cycles. Swift does not, and instead pushes the problem back to you through weak and unowned annotations. Reference counting also has its own running cost, paid on every copy of a pointer you make and every time you drop one.

Which one should you choose? If garbage collection was free, all of us would choose a runtime that manages memory on its own. But it is not free, hence we discuss the performance penalty of GC and whether it matters.

Stack and heap

When a program needs memory it comes from one of two places, the stack or the heap. Stack memory costs the collector nothing. It grows and shrinks as functions are called and return, and the machine just moves a pointer. When the function returns the value is gone, nothing has to reclaim it. Stacks are not entirely invisible to the collector, since it has to scan them as roots to find where the live objects start, but it never has to free anything there.

A value ends up on the heap for one of two reasons. Either it needs to outlive the function that created it, because you returned a reference to it, or stored it somewhere longer-lived. Or its size is not known up front and it can grow. For example, a slice you keep appending to, a buffer sized from user input. Heap allocation is the class of memory which GC monitors and reclaims, and it is what factors into GC costs. We will discuss this in the next section.

The cost of collection

To work out what collection costs you, there are two questions to answer: how often the collector runs, and what a single run costs.

How often a collector runs is determined by how fast you consume bytes. Memory filling up forces the collector to go and rebuild its picture of the live objects.

Every time the collector runs, it has to answer one question. What is still reachable? To answer it, it builds up a graph of your program’s live objects and the references between them, and then reclaims everything the graph does not include. This whole process, waking up, building the graph and reclaiming what is left over, is one GC cycle, and building the graph is the part usually called marking. Building it means walking from the roots and following every reference it finds, and this is what determines the cost of a cycle.

A GC cycle is not really charging you for memory used, it is charging you for objects and references. How much memory sits behind any one of those references never comes into it. Collecting a 4 GB graph of a million small objects pointing at each other is orders of magnitude more expensive than a single 4 GB buffer. Both programs are using the same amount of memory and they are asking for completely different amounts of work. A surprising outcome of this is that in the collection step, the cost is proportional to the live pointers, not the dead pointers or garbage.

There is a second cost associated with marking. While the collector is building its graph, your program is still running and still changing pointers, and it cannot mark a picture that is moving underneath it. To stop the graph going stale, every pointer write your program makes during the walk does a little extra work to report the change. That work is charged to your program, not to the collector, so it does not show up in the GC time you measure. This is another reason pointer-heavy code costs more during GC.

Runtimes then differ a great deal in how they go about all this, every one of them has decades of careful work behind it. Some rebuild the picture from scratch every so often, some keep it up to date as you go along, and some keep a separate picture for young objects on the reasoning that most objects die quickly (Java’s generational GC). Most of them give you a dial somewhere, letting the heap grow further before collecting so that it happens less often but more dead memory sits around in the meantime. All of this matters a lot when you are tuning a particular program on a particular runtime. But what it changes is the constants, and which kinds of allocation profile it optimizes for. It does not change the factors which affect the cost.

Compare all of this to the manual or compiler managed world. Allocation there is not free either, malloc has its own free lists and its own lock contention. But the cost lives in the instructions to allocate a pointer and then free it. There is no system that has to sweep the entire set to figure out which pointer is reachable and which is not.

What to measure

When we say a program is slow or OOMing because of GC pressure, the thing to go after is not the amount of memory it is using. For any program, in any language, there are three things worth asking instead.

1. How many live objects does it hold?
2. How densely are those objects linked to each other?
3. And how fast is it churning through them?

The measuring happens in three phases. The first one is triage, it only tells you whether any of this is worth your time. The second answers the third question, how fast you are churning. The third answers the first two, how much you are holding and how densely it is linked.

The first is to measure whether the collector is a problem at all. The thing to look for here is CPU, what share of your processor time is going into collection instead of into your program. Every CPU cycle that GC used is a CPU cycle taken away from your program to execute actual work. Go exposes it through the runtime/metrics package, which reports CPU seconds spent on collection against the total available, and Java gives you the same picture from its GC logs or from a profiler. If that share is small, you can stop here, GC is not a problem that needs optimization for your program.

The second is which parts of your code are producing the garbage. This is an allocation profile, you want to measure the number of allocations and the bytes per allocation, attributed to the places they came from. In Go that is a heap profile read through alloc_objects and alloc_space, or allocs/op and B/op if you are working from benchmarks. In Java it is allocation events from a profiler, attributed to stack traces. In most cases, you will find a handful of call sites responsible for most of the churn, and these are the ones to be optimized.

The third is what your program is holding on to. Most of the time, just optimizing the hot allocation paths is enough, and you will not need this. If you do need to go one step further, remember that the cost of a single GC cycle is proportional to the number of live references, not the dead references. An allocation profile tells you what you created and says nothing about what survived, so a program whose real problem is a large structure kept in memory will look completely unremarkable in allocation profile. For that you want the live view instead, which is inuse_objects and inuse_space in Go, or a heap histogram in Java.

Pointer density is the metric nothing reports directly, but we can derive it. Divide live bytes by live objects and look at the average size. Small objects in large numbers is expensive, because it means a lot of references holding them together, and large objects in small numbers is cheap. This signal is rough, rather than a measurement, because average size is a proxy of how many pointers the collector has to follow. If the average moves in the right direction and the pointer counts move with it, you will usually get the optimization you want.

Premature optimization

For the majority of software, worrying about the overhead of GC is a mistake and trying to optimize will be premature optimization.

But there is a certain class of programs for which this equation flips, and allocation behavior can be the thing that makes or breaks them. There is a short checklist to think through here, so that you can bake the decision into the design of your software rather than treating it as a later optimization. Ask yourself the following questions -

How much data moves through the hot path? An allocation per web request might be nothing. The same allocation in a loop over ten million rows might matter.

Does the tail of your latency matter? Not the average latency, the tail. While a collection is running it takes a share of your CPU away from your program. And in a lot of runtimes, Go among them, a thread that allocates while a collection is in progress gets pulled in to help with the marking, so the work it was doing waits while it does that. If an occasional slow response is acceptable, then you do not need to worry about this.

Are you pushing the hardware? Most programs leave the machine mostly idle and spend their time waiting on something else, like the network, a database or a disk. In those cases the collector’s work disappears into the slack. It only surfaces when you are trying to saturate the CPU.

Does the process run long and hold a lot? Think of a service that keeps a large cache in memory, or an index built out of millions of small objects that all point at each other. Every one of those pointers has to be followed on every cycle, for as long as the process is up. And this happens even when the service is doing nothing at all. Allocating less will not help you here, because the cost is in what you are keeping and not in what you are creating.

A data pipeline, a database, a game engine or a high-throughput service might answer yes to several of these. A typical web backend or a CLI tool might not.

What comes next

From practical experience, most of us do not get to choose a paradigm anyway. You join a company and inherit a project, or the internal tooling makes adopting a new language expensive enough that it never happens. The choice was already made years ago.

So the useful question is what you can do from the side you are already standing on. We hinted at GC optimizations, but never discussed what these optimizations are. Go gives you a lot more room here than its reputation suggests, you just need to use the right tools for the right job. You can allocate less, you can reuse what you have already allocated, and you can carve out regions of memory that the collector never has to walk at all. This is what we will be going into next.