How Garbage Collection Works: Let's Build One From Scratch

Introduction

Your program keeps creating objects. Every function call, every loop iteration, every parsed JSON response produces new ones. You don't manually delete most of them. You've never written a line of code that says "free this memory now." And yet your application doesn't immediately exhaust all available RAM and crash.

So who cleans everything up?

The answer is a garbage collector, a piece of the runtime that runs quietly in the background, deciding what your program no longer needs and reclaiming that memory for future use. Most developers interact with it only when something goes wrong: an unexpected pause, a memory leak, or an out-of-memory error that shouldn't be happening.

Understanding how it actually works turns those confusing moments into solvable problems. And as a bonus, the core algorithm is simple enough to build yourself. We'll do that by the end of this article.

--

1. The Memory Problem

Every time your program creates an object, the runtime allocates a chunk of memory to hold it. A string, a dictionary, a class instance: they all need memory, and that memory has to come from somewhere.

The somewhere is a region called the heap, a pool of memory that the program draws from as it runs. When you create an object, the runtime finds a suitable slot in the heap and reserves it. When that object is no longer needed, that slot should be freed so it can be used for something else.

In languages like C, you manage this manually. You allocate memory when you need it, and you free it when you're done. This gives you control, but it creates two classic failure modes. Free memory too early and you have a dangling pointer, a reference to memory that's now being used for something else. Forget to free it at all and you have a memory leak: the program slowly consumes more and more memory until it runs out.

Automatic memory management exists to eliminate these failure modes. Instead of relying on the programmer to track every allocation and release, the runtime watches what the program is doing and cleans up on its behalf. The question is: how does it know what's safe to clean up?

--

2. The Simplest Idea: Reference Counting

The most intuitive approach is to count how many references point to each object. A reference-counting runtime keeps track of how many references currently point to an object. When that count reaches zero, nothing in the program can reach the object anymore, and the runtime can reclaim its memory immediately.

In CPython, the standard Python implementation, this is the primary mechanism. Every Python object carries a reference count. Each time a new reference to it is created, the count goes up. Each time a reference is removed or goes out of scope, the count goes down. When it hits zero, the memory is released on the spot, without waiting for a separate collection phase.

# Python exposes reference counts via sys.getrefcount()
import sys

x = []
print(sys.getrefcount(x))  # Higher than you might expect: getrefcount
                            # itself creates a temporary reference.

y = x
print(sys.getrefcount(x))  # One higher than before: y is a new reference.

del y
print(sys.getrefcount(x))  # Back to what it was: y's reference is gone.

The exact numbers vary depending on context and interpreter internals, so don't rely on specific values. What matters is the pattern: the count goes up when a new reference is created and down when one is removed.

Reference counting is elegant in its simplicity. It distributes the work of garbage collection across the program's normal execution: every assignment and deletion carries a small bookkeeping cost, but there's no separate "stop everything and collect garbage" moment for objects that die by reference count.

There's just one problem.

--

3. The Problem With Reference Counting

Consider two objects that each hold a reference to the other.

class Node:
    def __init__(self, name):
        self.name = name
        self.other = None

a = Node("A")
b = Node("B")
a.other = b   # A references B
b.other = a   # B references A

del a
del b
# Both reference counts are now 1, not 0.
# Neither object can be freed.

After del a and del b, the variables in your code no longer point to these objects. From your program's perspective, they're gone. But from the runtime's perspective, A still holds a reference to B, and B still holds a reference to A. Each object's reference count is one. Neither will ever reach zero.

This is the circular reference problem. Two objects keeping each other alive, even when the rest of the program has moved on. The memory they occupy is effectively leaked, not because the programmer forgot to delete them, but because pure reference counting has no way to detect or collect cycles.

This is a real limitation in CPython, and it's why CPython includes a second mechanism on top of reference counting: a cyclic garbage collector that periodically searches for isolated reference cycles among container objects and reclaims them. For most programs most of the time, reference counting handles cleanup. The cyclic collector handles the cycles that reference counting cannot. Other Python implementations may handle this differently.

But reference counting is not the only approach to automatic memory management. There's a more general algorithm that handles cycles naturally.

--

4. Mark and Sweep

Instead of tracking reference counts, tracing collectors ask a different question: starting from what the program can currently access, what objects can be reached?

Mark-and-sweep is one concrete way to implement this idea. The idea begins with a concept called roots: the starting points of the reachability search. Roots are the references the program can directly access at a given moment: local variables in active stack frames, global variables, static fields. Anything the program holds onto directly.

From the roots, the collector follows every reference it can find. Object A points to B, so B is reachable. B points to C, so C is reachable. The collector visits every object it can reach and marks it.

Root --> A --> B --> C     (all marked: reachable)

D --> E                    (unmarked: unreachable, garbage)

Then comes the sweep: the collector walks through all known objects. Any object that wasn't marked is unreachable. The program can never access it again. Its memory can be safely reclaimed.

Mark-and-sweep handles circular references cleanly. If D and E reference each other but nothing reachable points to either of them, neither gets marked. Both get swept. The cycle doesn't protect them.

The trade-off is that mark-and-sweep isn't free. During collection, the collector has to traverse potentially large object graphs. Depending on the implementation, this may require pausing the application while it runs.

--

5. Why Generational GC Exists

Here's an observation that turns out to be remarkably consistent across real programs: most objects die young.

A temporary variable inside a function lives for a fraction of a second. A string built to format a log message exists for one call and is never seen again. Meanwhile, a database connection pool or a configuration object might live for the entire lifetime of the application.

This pattern, known as the generational hypothesis, is reliable enough that garbage collectors are specifically designed around it. Instead of collecting all objects together, the heap is divided into generations. New objects start in the youngest generation. If an object survives a collection cycle, it gets promoted to an older generation, which is collected less frequently.

The result is that most collection cycles are fast: they sweep through a small, young generation where most objects are already dead, find a lot of garbage quickly, and finish. Long-lived objects in older generations are rarely disturbed.

Modern Java collectors such as G1 and the current generational ZGC use generational techniques, although the exact implementation varies between collectors and JDK versions. Most JavaScript engines use generational collection as well, with young-generation collection ("scavenging") happening frequently and full collections happening rarely.

--

6. Why GC Can Pause Your Program

A garbage collector needs to understand the state of all objects and all references. If the program is modifying those references while the collector is traversing them, the collector's view of the world becomes inconsistent. An object that was reachable at the start of the traversal might no longer be reachable by the end. A newly allocated object might not get marked at all.

The simplest solution is to pause all application threads while the collector runs: a stop-the-world pause. The application freezes, the collector does its work with a stable view of memory, and then the application resumes. This is reliable but noticeable, especially for latency-sensitive applications.

Modern collectors go to great lengths to reduce or eliminate these pauses. Concurrent collectors do most of their work while the application continues running, using write barriers, small pieces of code inserted around reference assignments, to track changes made during collection. Incremental collectors break up the collection work into small steps interleaved with application execution.

ZGC is designed to perform all expensive collection work concurrently, targeting sub-millisecond pause times even on very large heaps. This is an official design goal stated in the OpenJDK documentation. Shenandoah takes a similar concurrent approach, aiming for consistent short pauses that don't grow with heap size, with a stated goal of keeping pauses under 10ms for large heaps. These are engineering achievements of real sophistication. But the fundamental problem they're solving, making sure the collector and the application agree on the state of the object graph, remains the same.

--

7. Python, Java, and JavaScript

These three runtimes handle memory management differently, and the differences matter for understanding their behavior.

CPython uses reference counting as its foundation. Most objects are freed the moment their reference count drops to zero, without any collection pause. On top of this, CPython's cyclic garbage collector periodically looks for reference cycles among container objects (lists, dicts, classes, and similar types). The cyclic collector can be tuned or disabled for specific use cases.

Java provides several tracing garbage collectors with different performance characteristics. Objects are typically allocated in a region called the young generation and promoted to older regions if they survive. Modern collectors include G1 (the default since Java 9), ZGC, and Shenandoah, each making different trade-offs between throughput, latency, and pause behavior. Which one is best depends on the application's requirements.

JavaScript is a language with multiple engines. V8, used by Node.js and Chrome, uses a generational collector. Its young generation ("new space") is collected frequently and cheaply. Its old generation is collected by a more comprehensive mark-compact collector. V8 also uses incremental and concurrent collection techniques to reduce pauses during page interactions. Other JavaScript engines may use different implementations.

The common thread across all three: no runtime automatically prevents memory leaks. If your code holds a reference to an object it no longer logically needs, the collector cannot reclaim it. The object is still reachable. From the collector's perspective, it's still alive. This is one of the most important things to understand about garbage collection: reachability and usefulness are not the same thing.

--

8. Let's Build a Garbage Collector

Enough theory. Let's build one.

We'll implement a simple mark-and-sweep collector in Python. This is an educational implementation: it manages a simulated object graph, not Python's actual memory. Think of it as the algorithm running in plain sight, without any runtime internals in the way.

Step 1: Represent Objects

class GCObject:
    def __init__(self, name):
        self.name = name
        self.references = []  # Other GCObjects this one points to
        self.marked = False

    def __repr__(self):
        return f"GCObject({self.name})"

Each object has a name for identification, a list of outgoing references, and a marked flag that the collector will use.

Step 2: Build an Object Graph

# Create objects
root = GCObject("Root")
a    = GCObject("A")
b    = GCObject("B")
c    = GCObject("C")
d    = GCObject("D")
e    = GCObject("E")

# Connect them
root.references.append(a)   # Root --> A
a.references.append(b)      # A --> B
b.references.append(c)      # B --> C

d.references.append(e)      # D --> E (unreachable from Root)

# All known objects
heap = [root, a, b, c, d, e]

The graph looks like this:

Root --> A --> B --> C      (reachable)

D --> E                     (unreachable, garbage)

Step 3: Define the Roots

roots = [root]

In a real runtime, roots include all local variables in active stack frames and global variables. Here we keep it simple: just one root object.

Step 4: Mark

We start from the roots and visit every reachable object. If we've already marked an object, we don't visit it again (which prevents infinite loops in cyclic graphs).

def mark(obj):
    if obj.marked:
        return  # Already visited
    obj.marked = True
    for ref in obj.references:
        mark(ref)  # Recursively mark everything reachable

This recursive approach works well for our small example. A production implementation would use an explicit stack or queue instead, to avoid hitting Python's recursion limit on deeply nested object graphs.

We call this for each root:

for root_obj in roots:
    mark(root_obj)

After marking, root, a, b, and c all have marked = True. d and e are still False.

Step 5: Sweep

Now we walk the entire heap and reclaim anything that wasn't marked.

def sweep(heap):
    reachable = []
    collected = []

    for obj in heap:
        if obj.marked:
            obj.marked = False  # Reset for the next collection cycle
            reachable.append(obj)
        else:
            collected.append(obj)
            print(f"Collecting: {obj}")

    return reachable

heap = sweep(heap)

Running this prints:

Collecting: GCObject(D)
Collecting: GCObject(E)

Our collector has removed d and e from the simulated heap. Python itself has not reclaimed those objects, because the variables d and e still reference them. This is intentionally a simulation of the algorithm, not a real Python memory manager. root, a, b, and c remain in the heap and are considered live.

The Complete Collector

class GCObject:
    def __init__(self, name):
        self.name = name
        self.references = []
        self.marked = False

    def __repr__(self):
        return f"GCObject({self.name})"


def mark(obj):
    if obj.marked:
        return
    obj.marked = True
    for ref in obj.references:
        mark(ref)


def sweep(heap):
    reachable = []
    for obj in heap:
        if obj.marked:
            obj.marked = False
            reachable.append(obj)
        else:
            print(f"Collecting: {obj}")
    return reachable


def collect(roots, heap):
    for root_obj in roots:
        mark(root_obj)
    return sweep(heap)


# Build the graph
root = GCObject("Root")
a, b, c = GCObject("A"), GCObject("B"), GCObject("C")
d, e    = GCObject("D"), GCObject("E")

root.references.append(a)
a.references.append(b)
b.references.append(c)
d.references.append(e)

heap = [root, a, b, c, d, e]
roots = [root]

print("Before collection:", heap)
heap = collect(roots, heap)
print("After collection:", heap)

Output:

Before collection: [GCObject(Root), GCObject(A), GCObject(B), GCObject(C), GCObject(D), GCObject(E)]
Collecting: GCObject(D)
Collecting: GCObject(E)
After collection: [GCObject(Root), GCObject(A), GCObject(B), GCObject(C)]

That's mark-and-sweep. Mark everything reachable. Sweep everything that isn't. Around forty lines of Python to express the core idea.

--

9. Our Tiny Collector vs Real Garbage Collectors

What we built captures the essential logic. What it doesn't capture is everything that makes production garbage collectors genuinely hard to build.

Concurrency. Our collector runs while nothing else is happening. A real collector has to contend with application threads that are constantly creating and discarding references, requiring careful synchronization or concurrent traversal techniques.

Compaction. After sweeping, the heap can become fragmented: reachable objects interspersed with holes where garbage used to be. Real collectors often compact the heap, moving live objects together to eliminate fragmentation. This requires updating every reference that points to a moved object.

Generations. Our collector treats all objects equally. Generational collectors maintain separate regions and collect the young generation far more often than the old, because that's where most of the garbage is.

Allocation. We didn't implement object allocation at all. Real runtimes maintain complex free lists or bump-pointer allocators to carve up heap memory efficiently.

Pause reduction. Our collector stops everything while it works. Reducing or eliminating those pauses is one of the central challenges of modern collector design.

The gap between our forty-line implementation and a production garbage collector is vast. But the conceptual foundation is the same: find what's reachable, reclaim what isn't.

--

Conclusion

We started with a question: if the program doesn't manually free memory, how does the runtime know what it can safely delete?

The answer is reachability. Tracing collectors start from a set of known roots, determine which objects remain reachable, and reclaim those that don't. Mark-and-sweep is one concrete way to implement that idea, and that's what we built.

Reference counting is a simpler approach that works immediately and locally, freeing memory the moment it becomes unreachable. But it fails on circular references, which is why CPython supplements it with a cyclic collector.

Generational collection makes the practical observation that most objects die young and builds the collector around that pattern, spending most of its energy where most of the garbage is.

GC pauses exist because the collector needs a consistent view of the object graph, and modern runtimes invest heavily in making those pauses shorter and less frequent.

And memory leaks can still happen in garbage-collected languages, not because the collector failed, but because the program still holds a reference to something it no longer needs. Reachability and usefulness aren't the same thing. The collector can only see the first one.

The next time you see a GC pause in production, or wonder why a long-running service's memory keeps growing, you now have the mental model to start asking the right questions.

The garbage collector has been doing its job invisibly this whole time. Now you know how.