What garbage collection actually costs · Shivanshu AgrawalSkip to content<br>On this pageEvery computer program needs memory. Memory is finite, so a long running program<br>must borrow memory from the operating system when it needs it and release it<br>once it is no longer needed.
The interesting part is who reclaims that memory, and when. Some piece of code<br>has to figure out that a piece of memory is no longer needed and release it, and<br>figuring that out is not trivial. A value might be passed to another function,<br>stored somewhere longer-lived, or shared across threads, and it stays needed as<br>long as anything still refers to it. If it is reclaimed early, we get memory<br>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<br>memory when it needs it, uses it as long as required, and eventually stops<br>referring to it. A garbage collector figures out what is no longer reachable and<br>reclaims it. Go, Java and a lot of other languages in wide use belong to this<br>category. You give up deciding when memory is freed, but in exchange you cannot<br>free it too early, free it twice, or forget to free it at all. For most software<br>this is a very good compromise. It reduces the cognitive overhead of memory<br>management and you can stay focused on the actual problem. The leaks that come<br>from forgetting to free something go away entirely.
The second paradigm, which must be very evident at this point, is to keep the<br>decision to yourself. In C, you allocate and free by hand, and you own every bug<br>that comes as a result. In Rust you do not write the frees, but you do not hand<br>the decision to a runtime either. The compiler works out at build time where<br>each value’s life ends, reclaims it there, and refuses to build the program if<br>it cannot prove that this is safe. So you still get control over memory and a<br>tighter footprint, but the effort shifts. In C you pay for it by debugging<br>corruption. In Rust you pay for it by arranging your program in a way the<br>compiler can verify.
Sitting in between is reference counting, which is what Swift and Python do. It<br>is really a variant of the first answer rather than a third paradigm, and it is<br>seldom enough on its own. Counts cannot see cycles, so a language has to deal<br>with them some other way. Python bolts on a tracing collector that hunts for<br>cycles. Swift does not, and instead pushes the problem back to you through<br>weak and unowned annotations. Reference counting also has its own running<br>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<br>choose a runtime that manages memory on its own. But it is not free, hence we<br>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<br>heap. Stack memory costs the collector nothing. It grows and shrinks as<br>functions are called and return, and the machine just moves a pointer. When the<br>function returns the value is gone, nothing has to reclaim it. Stacks are not<br>entirely invisible to the collector, since it has to scan them as roots to find<br>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<br>the function that created it, because you returned a reference to it, or stored<br>it somewhere longer-lived. Or its size is not known up front and it can grow.<br>For example, a slice you keep appending to, a buffer sized from user input. Heap<br>allocation is the class of memory which GC monitors and reclaims, and it is what<br>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<br>often the collector runs, and what a single run costs.
How often a collector runs is determined by how fast you consume bytes. Memory<br>filling up forces the collector to go and rebuild its picture of the live<br>objects.
Every time the collector runs, it has to answer one question. What is still<br>reachable? To answer it, it builds up a graph of your program’s live objects and<br>the references between them, and then reclaims everything the graph does not<br>include. This whole process, waking up, building the graph and reclaiming what<br>is left over, is one GC cycle, and building the graph is the part usually called<br>marking. Building it means walking from the roots and following every reference<br>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<br>objects and references. How much memory sits behind any one of those references<br>never comes into it. Collecting a 4 GB graph of a million small objects pointing<br>at each other is orders of magnitude more...