programmingconcepts

§ 5.3 · Memory

Garbage collection

Automatic memory management that finds objects the program can no longer reach and frees them, so you never call free yourself.

Garbage collection automatically frees memory the program can no longer reach. Starting from roots such as local and global variables, a mark-and-sweep collector marks every object it can reach through references, then frees everything unmarked. Unlike plain reference counting, it also frees cycles of objects that only refer to each other. The costs are CPU time, pauses and spare memory.

Live means
Reachable from a root
Mark and sweep
O(live objects) to mark, O(heap) to sweep
Frees cycles
Yes, unlike plain reference counting
Cost
CPU time, pauses, spare memory
Requires
Stack vs heapPointers and references
def collect(heap, roots):
    # heap maps each object to the objects it refers to.
    marked = set()
    stack = list(roots)
    while stack:
        obj = stack.pop()
        if obj in marked:
            continue
        marked.add(obj)
        for ref in heap[obj]:
            if ref not in marked:
                stack.append(ref)
    freed = [obj for obj in heap if obj not in marked]
    for obj in freed:
        del heap[obj]
    return freed

8 objects on the heap. The roots are the variables on the stack: they refer to A and B. Anything the program can't reach from a root is garbage.

step 0 / 0on the mark stackmarked: reachablefreed

Fig. 5.3. Circles are objects on the heap and arrows are references between them. The root is the program's variables. Blue objects wait on the mark stack, black ones are marked reachable, and dashed ones are freed.

Intuition

Clearing out a shared fridge. You can’t ask every item whether it’s still wanted, so you start from the shopping lists stuck on the door (the roots). Everything a list mentions is kept, and so is anything those items mention (“the sauce for the pasta”). Whatever nobody’s list leads to goes in the bin, even two leftovers labelled as belonging to each other.

How it works

An object is live if the program could still use it: there is a chain of references to it from a root. Everything else is garbage, because no code can ever reach it again.

Mark and sweep finds the garbage in two passes:

  1. Mark. Push the objects the roots refer to onto a stack. Pop one; if it isn’t marked yet, mark it and push everything it refers to. Repeat until the stack is empty. Every marked object is reachable.
  2. Sweep. Walk the whole heap. Free each unmarked object and clear the marks on the rest, ready for next time.

Marking costs time in proportion to the live objects; sweeping, to the size of the heap.

Reference counting

The other classic approach keeps a count on each object of how many references point at it, and frees the object the moment the count drops to zero. Memory comes back immediately and predictably, but a cycle is never freed: in the figure, E and F each have a count of 1 (from each other) even though the program can’t reach either. Systems that use reference counting either add a cycle detector (Python), or ask the programmer to break cycles with weak references (Swift, Rust’s Rc).

In each language

Language How memory is reclaimed
Python Reference counting frees most objects at once; a generational cycle collector finds unreachable cycles. gc.collect() runs it on demand.
JavaScript Tracing collectors. V8 splits the heap into a young generation, collected often and quickly, and an old one, marked mostly in parallel with your code.
Go A concurrent mark-and-sweep collector that runs alongside your goroutines with short pauses. GOGC trades memory for collector CPU time.
Java Several tracing collectors to choose from; G1 is the default since Java 9, and ZGC aims for pauses under a millisecond.
Rust No garbage collector. Each value has one owner and is freed when the owner goes out of scope. Rc and Arc add reference counting where sharing is needed, and can leak cycles.
C Manual: malloc and free. Forgetting free leaks; freeing twice, or using memory after freeing it, is undefined behaviour.

The costs

  1. Pauses. Some collectors stop your program while they mark. Modern ones do most work concurrently, but latency-sensitive code still notices.
  2. Memory headroom. A tracing collector works best with spare memory: a heap often runs at 1.5 to 2 times the live data.
  3. No timing guarantee. You can’t know exactly when an object is freed, so don’t rely on garbage collection to close files or sockets. Use with (Python), try/finally, defer (Go) or Drop (Rust).
  4. Leaks still happen. A cache or global list that keeps references holds objects alive forever: they are reachable, so they aren’t garbage.

Check yourself

Check yourself

Object G refers to a live object H, but nothing refers to G. Is G freed?

Check yourself

Two objects refer only to each other. Which approach frees them on its own?

Sources

  • Richard Jones, Antony Hosking and Eliot Moss, The Garbage Collection Handbook, 2nd ed., chapters 2 (mark-sweep) and 5 (reference counting).
  • Python documentation, gc module.
  • The Go blog, “Getting to Go: The Journey of Go’s Garbage Collector”.
  • V8 blog, “Trash talk: the Orinoco garbage collector”.

Newsletter

One new concept each week, by email.

Signup opens soon.