How Garbage Collection Works: Mark-and-Sweep, Generational Collectors, and Pause Times

Garbage collection is the runtime mechanism that finds heap objects a program can no longer reach and reclaims their memory. Manual allocators such as malloc and free put that duty on the programmer. A garbage collector (GC) tracks reachability instead of trusting every call site to pair allocation with deallocation.

This article explains what the collector actually observes, how classic algorithms work, why generational designs dominate production language runtimes, and how pause times appear in real systems. It is not a tour of every JVM flag or a rewrite of process isolation. Processes and threads describe how work is scheduled; virtual memory describes how addresses map to frames. Garbage collection sits above those layers: it decides which heap objects still belong to the program.

What the Collector Is Allowed to See

A collector does not read your intent. It reads roots and pointers.

Roots are locations the runtime treats as definitely live at a given moment. Typical roots include:

• thread stacks and register files
• static or global variables that hold heap references
• JNI or foreign-function handles that pin objects
• internally allocated runtime structures that still point into the heap

From those roots the collector follows pointers. An object is reachable if some chain of pointers from a root leads to it. Unreachable objects are garbage, even if they still contain useful-looking bytes.

This definition is conservative in an important way. If a dead object is still pointed to from a forgotten cache, a cyclic listener list, or a static map, the collector must keep it. Memory leaks in managed languages are almost always leftover references, not missing free calls.

Languages that run on a VM or interpreter expose enough type or layout information for the collector to know which words are pointers. Ahead-of-time compiled languages that add GC, such as Go, generate metadata the collector consults while scanning stacks and heap objects.

Allocation Before Collection

Collection only makes sense if allocation is cheap enough to do often.

Most managed heaps hand out memory from a bump pointer or from thread-local allocation buffers. A thread reserves a small slab, then increments a cursor for each new object. When the slab is full, the thread asks the global allocator for another slab or triggers a collection.

That model is why short-lived objects are inexpensive until the heap fills. The cost is paid later, when the collector must discover which of those objects survived.

Object layout matters here. Headers store type information, hash codes, lock state, or forwarding addresses used during compaction. The collector depends on those headers to walk fields safely.

Mark-and-Sweep

Mark-and-sweep is the algorithm most explanations start with because the two phases match the definition of reachability.

Mark: starting from roots, the collector sets a mark bit or color on every reachable object. The traversal can be recursive, work-list based, or incremental.

Sweep: the collector walks the heap and returns unmarked objects to free lists.

The sweep phase does not move objects. Addresses stay stable, which simplifies conservative collectors and code that stores raw pointers. The cost is fragmentation. After many allocate-and-die cycles, free space is scattered in holes that may be too small for the next large object.

A related variant, mark-compact, slides live objects together after marking so the heap becomes a single contiguous free region again. Compaction updates every pointer that referred to a moved object. That extra work buys bump-pointer allocation after the cycle.

Copying Collectors

A copying collector splits heap space into two semi-spaces: from-space and to-space. Allocation happens in from-space. When it fills, the collector copies every reachable object into to-space and updates pointers to the new addresses. From-space is then considered empty.

Copying collection compacts by construction and only touches live data. Dead objects are never visited during the copy. The price is that half the reserved heap is idle at any moment, and every surviving object pays a memory copy.

Cheney's algorithm implements copying collection with a queue instead of recursion: scan a pointer in to-space, copy children that still live in from-space, and leave a forwarding address in the old object so other pointers can be fixed up in one pass.

Generational Collection

Most objects die young. That empirical rule, the weak generational hypothesis, is why production collectors in the JVM, CLR, V8, and similar runtimes split the heap into generations.

A nursery or young generation is collected frequently with a copying collector. Survivors are promoted to an old generation that is collected less often, usually with mark-compact or a concurrent mark-and-sweep variant.

The hard part is not the nursery. The hard part is pointers from old objects into young objects. If the collector scanned the entire old generation on every minor collection, the generational bet would collapse. Write barriers solve that.

A write barrier is a small piece of code the compiler inserts on pointer stores. When a program writes a young reference into an old object, the barrier records that old object in a remembered set or card table. Minor collections scan those recorded cards instead of the whole old heap.

Card tables divide the old generation into fixed-size cards, often 512 bytes. A dirty card means “something in this range may point to the nursery.” Remembered sets keep more precise entries. Both are approximations that trade extra remembered work for much cheaper minor collections.

Concurrent and Incremental Collectors

Stop-the-world collection pauses every application thread, walks the graph, and then resumes. That is simple and correct if the snapshot of roots is consistent. It is also visible as a latency spike.

Incremental collectors break the work into slices interleaved with mutator threads (the application). Concurrent collectors perform most marking while the mutator keeps running.

Concurrency creates the tricolor invariant problem. Objects can be thought of as white (not yet visited), gray (visited but children not yet scanned), and black (visited and children scanned). If a mutator installs a pointer from a black object to a white object, the collector can miss that white object unless a barrier records the new edge.

Different collectors pick different barriers:

• Insertion (Yuasa-style snapshot) barriers record the old value of a slot.
• Deletion or Steele-style barriers record the new value.
• SATB (snapshot-at-the-beginning) barriers, used by collectors such as G1 and Shenandoah in various forms, treat the heap graph as it existed at the start of the mark and log overwritten references.

The details differ. The shared idea is the same: once marking and mutation overlap, the collector needs help from every pointer write.

Why Pauses Still Happen

Even concurrent collectors pause. They pause to get a consistent root set, to process remaining gray objects, to relocate objects when compacting, or to remap pointers after a region is evacuated.

Pause length depends on:

• heap size and live-set size, not allocation rate alone
• how many dirty cards or remembered-set entries a minor collection must scan
• whether the collector must compact or can tolerate fragmentation
• thread count, because root scanning and copying can scale, but safepoint coordination has a fixed cost
• huge object allocations that skip the nursery and pressure the old generation immediately

Allocation rate still matters. A program that allocates a gigabyte of short-lived garbage per second will force frequent young collections. Those collections can stay short if almost nothing survives. They become long when the nursery fills with objects that are still reachable because they sit in a queue, a cache, or an unbounded list.

This is why GC tuning often starts with allocation profiles rather than with a larger heap. A larger heap delays collections; it does not fix a live set that grows without bound.

Reference Counting, Cycles, and Hybrids

Reference counting stores a count on each object and frees it when the count hits zero. Immediate reclamation is attractive for predictable memory use. Two problems dominate:

• Every pointer write updates a count, which is expensive and unfriendly to caches.
• Cycles never reach zero. A doubly linked list or a parent-child pair with back pointers leaks unless a cycle collector runs on the side.

Python's CPython uses reference counting plus a periodic cyclic GC for container objects. Swift and Objective-C use reference counting with explicit weak and unowned references to break cycles. Most high-throughput server runtimes prefer tracing collectors and accept pauses or concurrent marking instead of paying a count update on every store.

What Developers Actually Control

You rarely implement the collector. You still influence it.

Keep object graphs shallow when objects are short-lived. A young object pointed to from a long-lived cache is no longer young in any useful sense.

Avoid mid-life objects that survive one or two collections and then die. They pay promotion cost and then become old-generation garbage, which is the expensive kind.

Watch hidden allocations: boxed primitives, intermediate strings, iterator objects, and ORM entities pulled into a session that outlives the request.

When a latency budget is tight, measure time-to-safepoint and pause histograms, not only throughput. A collector can look excellent on a throughput benchmark and still violate a tail-latency SLO.

Manual pooling is sometimes justified for huge, homogeneous buffers. It is rarely justified as a general replacement for the allocator. Pools that forget to drop references become the leak they were meant to prevent.

How This Fits Next to Other Runtime Machinery

Threads execute code that allocates. The collector must stop or coordinate those threads at safepoints so stacks are readable. Virtual memory backs the heap; a collection that shrinks committed memory or releases empty regions talks to the operating system, not only to free lists. Compilers decide where write barriers go and which values live in registers that the collector must treat as roots.

These adjacent articles cover the surrounding layers:

• Processes vs Threads Explained covers the execution units the collector must pause or scan.
• How Virtual Memory Works explains pages, page tables, and faults underneath the heap.
• Compiler vs Interpreter examines how source becomes the instruction stream and metadata a runtime collector depends on.

Takeaways

Garbage collection is reachability analysis plus a policy for when and how to reclaim. Mark-and-sweep finds live objects and frees the rest in place. Copying collectors move survivors and get compaction for free. Generational collectors exploit the fact that most objects die young, and they need write barriers so minor collections stay cheap. Concurrent designs shrink pause times but never eliminate coordination with mutator threads.

When memory grows without a matching live working set, look for leftover references. When pauses grow, look at live-set size, remembered-set scan work, and promotion rates. The collector is doing what the graph tells it to do.