How Garbage Collection Works: Reference Counting, Mark-and-Sweep and Generations

The problem: knowing when memory is free

MDN describes the memory life cycle in three steps that hold for every language:

1. Allocate the memory you need.
2. Use it by reading and writing.
3. Release it once it is no longer needed.

The first two are easy. The third is the hard one, because "no longer needed" depends on what the program will do in the future. MDN points out that deciding this perfectly is undecidable in general, so every garbage collector uses a safe approximation instead. The two approximations in wide use are "nobody points to it" and "nobody can reach it."

Approach 1: reference counting

The simplest idea is to keep a counter on every object recording how many references point at it. Assigning the object to a variable bumps the count up; when a variable goes out of scope or is reassigned, the count goes down. When it hits zero, the object is freed immediately, and anything it pointed to gets its own count lowered, which can free a whole chain at once.

This is exactly how CPython manages memory day to day. You can even peek at the counter:

import sys

data = []
print(sys.getrefcount(data))   # 2: 'data' plus the temporary argument

alias = data
print(sys.getrefcount(data))   # 3

del alias
print(sys.getrefcount(data))   # back to 2

The weakness: cycles

Reference counting has one famous blind spot. If two objects point at each other, or a list contains itself, their counts never reach zero, even after the rest of the program has forgotten them. MDN's documentation uses a small example where two objects reference one another inside a function: once the function returns, both are useless, yet each still holds a reference to the other. Under pure reference counting, that memory leaks forever.

That's why no modern JavaScript engine relies on reference counting, and why CPython pairs it with a second, separate cycle collector, covered below.

Approach 2: tracing with mark-and-sweep

Tracing collectors flip the question around. Instead of asking "does anyone point to this?", they ask "can the running program still reach this?" The algorithm, called mark-and-sweep, works in two phases:

1. Mark: start from a set of roots, such as global variables and the local variables on each thread's stack, and follow every reference, marking each object you reach.
2. Sweep: walk the heap and reclaim every object that wasn't marked.

Because "unreachable" replaces "unreferenced," cycles stop being a problem. Two objects pointing at each other but cut off from every root are simply never marked, so they get swept. MDN notes that all modern JavaScript engines use a mark-and-sweep collector, and that the fancier techniques they add on top are optimizations of this same idea rather than a new definition of garbage.

Compaction

Sweeping leaves holes where dead objects used to be. Over time the heap can become fragmented, like a parking lot with plenty of single empty spaces but nowhere to fit a bus. Many collectors therefore add an optional compact step that moves surviving objects together. V8's major collector, for instance, is a mark-sweep-compact design that compacts only the pages that have become badly fragmented.

The big optimization: generational garbage collection

Marking the entire heap on every collection gets expensive as programs grow. The trick that nearly every production collector uses is based on an observation the V8 team calls the generational hypothesis: most objects die young. Think of temporary strings, short-lived arrays inside a loop, or the intermediate results of a calculation.

So collectors split the heap into a young generation, collected often and cheaply, and an old generation, collected rarely. Objects that survive a few young collections get promoted to the old one.

• V8 (Chrome and Node.js): new objects land in a nursery. A fast "scavenger" copies survivors between two half-spaces and promotes objects that survive twice. Because it only copies what is alive, its cost depends on how many objects survive, not on how many were allocated.
• CPython: its cycle collector also sorts container objects into generations and examines the youngest most often. On a standard build, gc.get_threshold() returns (700, 10, 10), the default triggers for each generation.
• The JVM: the Parallel collector is generational, and the generational version of ZGC is now what you get when you enable ZGC.

One subtlety: an old object might point to a young one. To avoid scanning the whole old generation during a quick young collection, V8 uses write barriers that record old-to-young references as they are created.

How CPython finds cycles

CPython's cycle detector is a neat twist on tracing. According to its internals documentation, it only looks at container objects like lists, dicts and class instances, since only they can form cycles. For each candidate it copies the reference count, then subtracts one for every reference coming from inside the candidate group. Anything left with a count above zero must be referenced from outside, so it is alive, along with everything it can reach. Whatever remains is an isolated cycle and gets freed.

You can watch it work from the standard gc module:

import gc

class Node:
    pass

a, b = Node(), Node()
a.partner, b.partner = b, a   # a reference cycle
del a, b                      # counts never hit zero

print(gc.collect())           # number of unreachable objects found

Keeping pauses short

The classic complaint about garbage collection is the "stop-the-world" pause, when the program freezes while the collector works. Modern collectors attack this from several directions. V8's Orinoco project describes three:

Today V8 scavenges in parallel and does most of its major marking and sweeping concurrently. Chrome can also schedule GC work in idle gaps between animation frames; the V8 team reported that idle-time collection cut Gmail's JavaScript heap by 45% when the page was idle.

The JVM lets you choose your trade-off. Oracle's tuning guide lists four main collectors:

Garbage collection doesn't prevent every leak

A collector frees what is unreachable, not what is unneeded. If your code keeps a reference by accident, the object stays alive. Common culprits include:

• Caches and maps that grow forever because nothing ever removes entries.
• Event listeners that are registered but never removed.
• Closures that capture large objects longer than intended.
• Global variables used as scratch space.

JavaScript offers WeakMap, WeakSet and WeakRef for cases where you want to attach data to an object without keeping it alive. MDN recommends using WeakRef and FinalizationRegistry sparingly, since the timing of collection is never guaranteed.

If you like learning how everyday tools work under the hood, see our explainers on how database indexes use B-trees and how Git stores commits internally.

Frequently asked questions