How tracing garbage collectors work

A tracing collector starts from the roots and follows pointers to find everything that is still reachable. Everything else is garbage. The algorithms differ in how they do the marking, how they handle the leftover memory, and how much of the work runs while your program is still going.

Mark-sweep

The original algorithm dates from John McCarthy's 1960 Lisp. It has two phases:

1. Mark: walk the object graph from the roots and set a mark bit on everything you reach.
2. Sweep: walk the whole heap and put every unmarked object on the free list.

It is simple and does not move objects. Over time the heap becomes fragmented. Lots of small holes sit between live objects, so a large allocation can fail even though enough total memory is free.

Compaction and copying

Mark-compact adds a third phase that slides live objects together. That leaves one contiguous free region, so allocation is a pointer bump again and locality improves. Moving objects means updating every pointer to them.

Copying collectors, from Cheney's 1970 semispace algorithm, split memory into two halves. They copy the live objects from one half to the other. The whole old half is then free. Their cost depends on the amount of live data, not on the heap size, which is ideal when most objects are dead. The drawback is that half the space is always reserved.

The generational idea

Most objects die young. Request-scoped buffers and temporary strings live for microseconds. Caches and connection pools live for hours. Generational collectors use this. New objects go into a small young generation that is collected often with a fast copying collector. Because most of it is garbage, each collection copies little. Objects that survive a few collections are promoted to an old generation, which is collected rarely.

The JVM collectors (G1, Parallel, generational ZGC), V8 and .NET are all generational. Go is notably not. Its designers chose a non-moving, non-generational collector and rely on escape analysis to keep short-lived objects on the stack.

Concurrent marking and write barriers

The simplest collectors stop the world. They pause every thread, collect, then resume. With a 10 GB heap, a full stop-the-world mark and compact can take seconds. Modern collectors do most of their work concurrently, while your code keeps running. They stop the world only for short phases, such as scanning thread stacks.

Concurrent marking uses Dijkstra's tri-color abstraction:

• White: not yet seen. At the end of marking, white objects are garbage.
• Grey: reachable, but its outgoing pointers are not yet scanned.
• Black: reachable, and all its pointers are scanned.

Marking starts with the roots grey. The collector picks a grey object, greys its white children, and blackens it, until no grey objects remain.

The danger is that your code keeps changing pointers during marking. If it stores a pointer to a white object into a black object, and removes the only other path to that white object, the collector never revisits the black object. It would free a live object. To prevent that, the compiler inserts a write barrier: a few extra instructions on each pointer store during marking. The barrier turns the affected object grey. Write barriers are part of the CPU cost of concurrent GC.

Walking through it: a small heap

Take a heap with objects Config, Session and two dead Request objects. Roots point to Config and Session. Session points to User.

Mark:   Config (black), Session (black), User (black)
        Request, Request: never reached, still white
Sweep:  free both Request objects

A copying collector on the same heap would copy the three live objects to fresh space and leave the two dead ones behind. Its work would not depend on how many dead objects there were.

Common mistakes

• Assuming a GC stops the program for its whole run. Modern collectors pause only briefly, but their barriers and background threads still cost CPU.
• Expecting cycles to leak. A tracing collector frees unreachable cycles.
• Thinking all collectors are generational. Go is not, and that choice shapes how it behaves.

Check yourself

• Why does a generational collector make cheap young-generation collections? Most young objects are already dead, so the copying collector moves little.
• What would go wrong without a write barrier during concurrent marking? A live object could be stored in an already-scanned object and then freed.

Key takeaways

• Mark-sweep finds reachable objects and frees the rest, but it fragments the heap.
• Compaction and copying remove fragmentation. Copying costs depend on live data, not heap size.
• The generational hypothesis holds that most objects die young, so young collections are cheap.
• Concurrent marking uses tri-color marking and write barriers to keep programs running during collection.

Further learning

Next, see how these design choices show up as latency spikes, and what you can tune, in GC pauses and tuning.

Getting to Go: The Journey of Go's Garbage Collector explains why Go chose a non-generational design.