Garbage Collection
Automatic memory management: the runtime finds objects nothing can reach any more and reclaims them.
Level: intermediate
What is it?
Garbage collection (GC) frees heap objects the program can no longer reach. Reference counting keeps a count of pointers to each object and frees it at zero (CPython, Swift). Tracing collectors start from roots — stack variables and globals — mark everything reachable, and sweep the rest (Java, Go, JavaScript). Generational collectors exploit the fact that most objects die young.
Why does it matter?
GC removes whole classes of bugs — use after free, double free — and lets you write code without tracking ownership. It also introduces costs: pauses, extra memory, and leaks that come from references you forgot to drop. Knowing how it works lets you reason about all three.
Mental model
A cleaning crew that only throws out what nobody can still walk to. Start at the front door (the roots), follow every hallway you can reach, and tag what you see. Anything untagged is behind a locked door with no key — it is safe to clear.
How it works
- An object is garbage when it is unreachable from any root, not when you 'stop using' it. A forgotten reference in a cache or listener list keeps it alive.
- Reference counting frees immediately and predictably but cannot reclaim cycles without an extra cycle detector.
- Mark-and-sweep handles cycles. Compacting and copying collectors also reduce fragmentation.
- Generational GC: young objects are collected often and cheaply; survivors are promoted to an older generation collected rarely.
- Stop-the-world pauses suspend the program. Concurrent and incremental collectors shorten them.
- Without a GC there are alternatives: manual free (C), RAII and smart pointers (C++), or ownership rules checked at compile time (Rust).
Steps
- Start from the roots
- Mark reachable objects
- Sweep the unmarked ones
- Reuse or compact the space
- Resume the program
Code example: A reference cycle needs the cycle collector
import gc, weakref
class Node:
pass
a, b = Node(), Node()
a.other, b.other = b, a # a reference cycle
probe = weakref.ref(a)
del a, b # the counts never reach zero
print(probe() is not None) # True: the cycle keeps both alive
gc.collect() # the cycle collector reclaims them
print(probe() is None) # TrueComplexity and trade-offs
Time: Tracing cost is proportional to live objects; allocation is usually a pointer bump
Space: Often 1.5–2× the live data to keep collections infrequent
Trade-offs
- Safety and convenience against pauses and memory overhead
- Reference counting: immediate, predictable frees; but cycles and per-assignment cost
- Tracing: handles cycles and is throughput-friendly; but pauses and non-deterministic timing
Real-world usage
- Managed runtimes: JVM, .NET, Go, JavaScript engines, CPython
- Tuning heap size and collector choice for latency-sensitive services
- Finding leaks with heap dumps and retained-size analysis
Common mistakes
- Assuming a GC language cannot leak: static caches, listeners, and closures keep objects alive.
- Relying on finalizers to release files or sockets; use explicit close or with blocks.
- Allocating millions of short-lived objects in a hot loop without measuring.
Interview questions
How does a tracing garbage collector decide what to free?
It starts from roots (stack variables, globals), marks everything reachable by following references, and reclaims everything unmarked.
What is a memory leak in a garbage-collected language?
Objects that are still reachable — from a cache, a static field, or a listener list — but no longer needed. The GC cannot free what the program can still reach.
Why is generational collection effective?
Empirically most objects die young, so collecting a small young generation frequently reclaims much garbage cheaply, and only the survivors pay for full collections.