How Garbage Collection Works — A History of GC and Language Strategies

In C and C++, developers manage memory themselves with malloc and free. Most modern languages instead rely on a garbage collector (GC) to reclaim memory that is no longer needed.

GC designs split into two families: reference counting, which counts the references to each object, and tracing, which follows pointers from a set of roots to find reachable objects. Tracing collectors have been refined with compaction, generations, and concurrent marking to address fragmentation, full-heap walks, and pause times. Each language combines these techniques according to how it weighs pause time, throughput, and memory use.

Why Do We Need GC?

Manual memory management leads to two classic categories of bugs.

Memory Leaks

If developers forget to free memory after use, it stays allocated and cannot be reused until the program exits.

void leak_example() {
    char *buf = malloc(1024);
    // use buf for processing...
    if (error) return;  // ← forgot to free(buf) before return!
    free(buf);
}

In this example, when error is true, free is never called and 1024 bytes leak. The leak grows with every call, so a long-running server application keeps using more memory until it crashes with an OOM (Out of Memory) error.

Dangling Pointers

Freeing memory that is still in use turns every later access into a Use-After-Free.

void dangling_example() {
    char *a = malloc(64);
    char *b = a;  // a and b point to the same memory
    free(a);
    // b still points to freed memory (dangling pointer)
    strcpy(b, "hello");  // Undefined behavior! Crash or security vulnerability
}

A GC reclaims only objects the program can no longer reach. Because developers never decide when to free memory, they can neither forget to free it (a leak) nor free it while it is still in use (a Use-After-Free).

John McCarthy invented GC for Lisp in 1959. Many of the algorithms described below have been developed and refined since then.

Fundamental GC Strategies

GC algorithms fall into two major families: reference counting and tracing.

⮳ The diagram above simplifies the common combinations. Generational, incremental, and concurrent collection are optimizations independent of the base algorithm, so they can be combined with algorithms other than mark & sweep. For example, Java's Young generation uses copying GC.

Reference Counting

With reference counting, each object keeps a counter of how many references point to it. The counter is incremented when a new reference is created and decremented when a reference is removed. When the counter reaches zero, the object is immediately freed.

Reference Counting in Action

a = Object()   # Object ref_count = 1 (a references it)
b = a           # Object ref_count = 2 (a and b reference it)
a = None        # Object ref_count = 1 (only b references it)
b = None        # Object ref_count = 0 → immediately freed!

Advantages

• The implementation is simple: managing counters is all it takes, so it is easy to understand
• Garbage is reclaimed as soon as its last reference disappears, so latency is predictable
• There is no Stop-The-World pause of the entire application
• Objects are freed as soon as they become unused, keeping peak memory usage low

Disadvantages

• Cannot collect circular references: The biggest weakness. Objects that reference each other, such as A→B→A, are not reclaimed even after nothing outside uses them
• Every pointer assignment requires a counter update. In multithreaded environments, this requires atomic operations (atomic_increment/atomic_decrement), causing cache line contention
• When the root of a large data structure reaches zero, a chain reaction of frees (cascading frees) can cause a temporary latency spike

In the diagram, after the external references are gone, A and B each keep a ref_count of 1 from the other's reference. The counts never reach zero, so both objects leak permanently.

Tracing GC

A tracing GC starts from a root set (stack variables, global variables, registers, and so on), traverses the object graph, and marks reachable objects as "alive." Unreachable objects are collected as garbage.

What Is the Root Set?

In tracing GC, "roots" are pointers the program can access directly, without going through another object. They include:

• Local variables on stack frames (each goroutine's or thread's stack)
• Global variables (package- or module-level variables)
• CPU registers (pointers held by the current thread)

Objects that reference each other are still collected if they cannot be reached from the roots. Handling the circular references that reference counting cannot reclaim is a major advantage of tracing.

Tri-color Mark & Sweep

Tri-color mark & sweep is a fundamental and widely used tracing GC algorithm. Dijkstra et al. proposed it in their 1978 paper "On-the-Fly Garbage Collection: An Exercise in Cooperation".

The Three Colors

The Tri-color Invariant

The algorithm's correctness relies on this invariant:

A black object never directly references a white object

The GC never scans a black object again. If a white object is referenced only by black objects, it is never scanned and is freed even though it is still alive. As long as a gray object sits between a black and a white object, scanning the gray object will eventually discover the white one.

Algorithm Flow

1. Color all objects white
2. Color the objects pointed to by GC roots gray and push them onto the gray stack (worklist)
3. Pop an object from the gray stack and scan it:
   • Color its white referents gray and push them onto the gray stack
   • Color the object itself black
4. Repeat step 3 until the gray stack is empty (mark complete)
5. Walk the heap and free all objects that remain white (sweep)

The demo below steps through this process one step at a time, showing how each object's color and the gray stack change.

Challenges of Mark & Sweep

Basic mark & sweep has these challenges:

• Fragmentation: Freed objects leave gaps between surviving objects, fragmenting memory. Large object allocations may fail to find contiguous space
• Full heap traversal: Sweeping requires walking the entire heap, with cost proportional to heap size
• Stop-The-World: All application threads must pause during mark and sweep

The improvements in the next section each target one of these. Mark-compact and copying GC address fragmentation, generational GC addresses full-heap traversal, and incremental and concurrent GC address pause times.

Evolution of Tracing GC

Mark-Compact

Mark-compact eliminates memory fragmentation by sliding surviving objects to one end of the heap.

As shown above, compaction fills the gaps left after sweep, creating a contiguous free region at the end of the heap.

Sliding compaction moves objects in address order, preserving their relative order. Two classic sliding algorithms are:

• Lisp 2 algorithm: Three passes over the heap — compute new addresses, update pointers, then move objects
• Threaded compaction: Converts references into linked lists to store temporary information. No extra memory needed but complex

Moving objects and rewriting references is expensive, but because compaction gathers free space in one place, allocation can use a bump pointer (just advance a pointer). Bump-pointer allocation is essentially alloc(size) = ptr; ptr += size, which is faster than free-list allocation, where the allocator must search for a fitting block.

Copying GC (Semispace)

Copying GC splits the heap into two spaces: From space and To space. Objects are allocated in From space. During GC, surviving objects are copied to To space, then From and To are swapped and the old From is freed entirely.

The canonical implementation is Cheney's algorithm (1970), which copies objects in BFS (breadth-first search) order:

scan = free = start of To space
Copy objects referenced by GC roots to To space, advance free
while scan < free:
    For each field of the object at scan:
        If referent is in From space and not yet forwarded:
            copy it to To space, set forwarding pointer at old location, advance free
        Update the field to the referent's To-space address
    Advance scan to next object

• Advantages: Copies are packed together, so the heap does not fragment even without a separate compaction step; bump-pointer allocation is fast; no heap sweep is needed
• Disadvantages: Only half the heap is usable (50% memory efficiency); copying large objects is expensive

Generational GC

Generational GC is an optimization based on the Weak Generational Hypothesis:

Most objects die young (become unreachable shortly after allocation)

The hypothesis comes from real-world observations. According to Wilson's 1992 survey, the share of newly allocated objects that become unreachable within a few million instructions (or before another megabyte has been allocated) varies by language and program but is usually 80–98%.

• Young generation: A small area for new allocations. Minor GC runs frequently but finishes in a few milliseconds, because most objects are already dead. New objects are allocated in Eden, and survivors are copied to Survivor spaces
• Old generation: Objects that survive multiple Minor GCs are promoted here. GC is less frequent but heavier (Major GC / Full GC, tens to hundreds of milliseconds)

A Minor GC examines only the Young generation, but references from the Old generation into the Young generation still keep objects alive. To find those references without scanning the whole Old generation, generational GC records them in a remembered set. The card table approach is common: it divides Old generation memory into ~512-byte cards and marks only cards containing Young pointers as "dirty" for scanning.

Incremental / Concurrent GC

Incremental and concurrent GC shorten Stop-The-World (STW) time by running GC work interleaved with, or at the same time as, the application.

• Stop-The-World GC: Application completely paused during mark and sweep. Simplest implementation but long pause times (proportional to heap size)
• Incremental GC: Splits marking into small steps, interleaved with application execution. Each step's pause is short, but total GC time is longer (write barrier overhead)
• Concurrent GC: Runs marking on separate threads while the application keeps running. The application pauses only at mark start and at the final remark, and both pauses are short

In concurrent GC, the application (mutator) and GC (collector) run simultaneously, so reference relationships can change during marking. Write barriers handle this.

Write Barriers

Write barriers maintain the tri-color invariant in concurrent and incremental GC. Code is inserted wherever the mutator writes a pointer, so that the GC learns about the change.

Why Write Barriers Are Necessary

Without a write barrier, the following sequence frees a live object:

1. GC has scanned object A and colored it black
2. Application executes A.field = C (C is white)
3. Application executes B.field = nil (removes B→C reference; B is gray/white)
4. GC scans B, but C is no longer referenced by B
5. C remains white → freed as garbage → alive object freed!

This is the lost object problem. It occurs when a black→white reference is created (condition ①) and all other paths to that white object are severed (condition ②).

Major Write Barrier Types

When a new referent is written into a pointer, the barrier shades that referent gray.

// Barrier inserted when executing A.field = C
writeBarrier(A, field, C):
    shade(C)      // shade C gray first (prevent black→white reference)
    A.field = C   // then perform the store

The shade runs before the store. If the order were reversed, there would be a window in which black object A references white object C, and a concurrent GC could free C during that window.

Every newly referenced object becomes gray, so it is guaranteed to be scanned. However, because the barrier conservatively shades many objects gray, it tends to increase floating garbage (objects that are actually garbage but won't be collected this cycle).

This barrier shades the object that is losing a reference (the old referent being overwritten) gray. The idea is to preserve a "snapshot" of the object graph as it was when GC started.

// Barrier inserted before A.field changes from old to new
writeBarrier(A, field, new):
    old = A.field
    if old is white:
        shade(old)  // shade old gray
    A.field = new

As a result, every object reachable at GC start is marked.

Go combines Dijkstra and Yuasa barriers into a hybrid write barrier.

writeBarrier(slot, new):
    shade(*slot)  // deletion barrier: shade the overwritten old value gray
    if current stack is gray:
        shade(new) // insertion barrier while the current stack still needs scanning
    *slot = new

This pseudocode follows the comment in Go's mbarrier.go. The deletion barrier always shades the overwritten old value, while the insertion barrier shades the new pointer only while the current goroutine's stack is gray. Once that stack is black, shade(new) is unnecessary.

The main benefit of the hybrid approach is that stack rescanning becomes unnecessary. In Go 1.5–1.7, which used only the Dijkstra barrier, every goroutine stack had to be rescanned at the end of marking, and this was a major contributor to STW time. With the hybrid barrier, Go's STW pauses are typically sub-millisecond, and shorter still for some workloads and platforms.

Memory Allocation Strategies

The GC algorithm determines which allocation strategy can be used. A GC that does not move objects allocates from free lists, while a GC that gathers free space through compaction or copying can use a bump pointer.

Free List

A free-list allocator keeps freed memory blocks in a linked list and, on allocation, searches for a block of suitable size. The search policies include:

• First-fit: Use the first sufficiently large block found
• Best-fit: Use the closest-sized block (less fragmentation)
• Segregated-fit: Maintain separate lists for each size class (used by Go and tcmalloc)

Bump Pointer

Bump-pointer allocation is used with compacted heaps and copying GC. A pointer marks the start of free memory, and allocation simply advances it.

alloc(size):
    result = freePtr
    freePtr += size
    return result

This is extremely fast (effectively one instruction) but requires contiguous free space.

Thread-local / Per-processor Allocation Buffers

Each execution context gets a pre-allocated portion of the heap, which avoids allocation contention in multithreaded environments. Java HotSpot uses TLABs (Thread-Local Allocation Buffers) where each Java thread can allocate with a lock-free bump pointer. Go's allocator takes a different approach: instead of TLABs, it uses an mcache per logical processor (P) and size-class spans.

GC Strategies by Language

Go — Concurrent Tri-color Mark & Sweep

Go's GC is designed to prioritize simplicity and low latency above all else.

Why doesn't Go use generational GC? The Go compiler performs escape analysis and places objects that don't escape their function on the stack. As a result, many short-lived objects never reach the heap, which weakens the premise of generational GC ("many heap objects are short-lived"). In their ISMM 2018 keynote, the Go team explained that making the collector generational would gain little and would not justify the cost of a write barrier that must always be on.

GC Pacer: A "pacer" decides when to start the next GC cycle. With GOGC=100 (the default), the next GC starts when the heap has grown by 100% relative to the live heap after the last GC. GOMEMLIMIT, added in Go 1.19, sets a soft memory limit to prevent OOM in memory-constrained environments.

Green Tea GC (default since Go 1.26): Go's classic marker walks pointers one object at a time, so a heap full of small objects turns marking into a random-access memory workload with poor cache behavior. Green Tea GC instead batches marking work per span (a page of same-size-class objects), improving locality and CPU scalability. It shipped as an experiment in Go 1.25 and became the default in Go 1.26. The official release notes expect a 10–40% reduction in GC overhead for real-world GC-heavy programs, plus roughly another 10% on amd64 CPUs from Intel Ice Lake / AMD Zen 4 onwards, where the collector uses vector instructions to scan small objects. The overall shape of the algorithm (concurrent tri-color mark & sweep, non-generational, non-compacting) is unchanged; what changed is the implementation detail of how marking scans memory.

GC source code lives in runtime/mgc.go.

Java (HotSpot) — Generational + Multiple Collectors

Java (HotSpot) offers several collectors to choose from by use case. In the table, the STW ratings "Long," "Medium," and "Short" compare these collectors with one another.

How G1 GC works: The heap is divided into equal-sized regions (typically 1–32 MB), and each region is assigned to the Young or Old generation dynamically. G1 prioritizes collecting regions with the most garbage (Garbage-First), maximizing reclamation within a given pause time budget. A pause-time target can be set with an option such as -XX:MaxGCPauseMillis=200.

ZGC's Colored Pointers: ZGC embeds GC metadata (mark state, relocation state) in unused bits of object pointers, so it never has to write mark information to object headers. Non-generational ZGC uses colored pointers with load barriers for concurrent marking and relocation; Generational ZGC also uses store barriers to track inter-generational references. With these techniques, ZGC keeps STW pauses under 1 ms even with TB-scale heaps.

Python (CPython) — Reference Counting + Generational Tracing

CPython uses a hybrid approach that combines reference counting with tracing GC.

• Reference Counting (Primary): The main memory reclamation mechanism. When an object's ob_refcnt reaches 0, tp_dealloc is called immediately to free it
• Generational Tracing GC (Auxiliary): Runs a generational tracing GC periodically, triggered by allocation counts, to detect and collect circular references that reference counting cannot handle

Thresholds for the three generations:

The thresholds control how often each generation is collected. An object is promoted from Gen N to Gen N+1 after surviving a single Gen N collection. Check the thresholds with gc.get_threshold() and change them with gc.set_threshold().

Because CPython has a GIL (Global Interpreter Lock), reference count updates don't need atomic operations. The free-threaded build (--disable-gil), which has no GIL, uses biased reference counting: the thread that owns an object updates its count with regular increments and decrements, and only other threads use atomic operations, which keeps reference counting thread-safe without the GIL. The free-threaded build arrived as an experiment in Python 3.13 and became officially supported in Python 3.14 via PEP 779, though it remains an optional build.

The incremental GC introduced and reverted in 3.14: CPython 3.14.0–3.14.4 shipped an incremental cycle collector with only two generations (young and old), aiming to cut worst-case pause times on large heaps by an order of magnitude. After repeated reports of significant memory pressure in production, it was reverted in 3.14.5 back to the 3.13 generational collector. The three-generation design described above is the collector after that revert. As this episode shows, GC design has to weigh shorter pauses in benchmarks against peak memory use under real workloads.

JavaScript (V8) — Generational + Concurrent Marking

V8 (Chrome, Node.js, Deno) uses generational GC.

How Scavenger works: The Young generation is split into two semispaces. New objects are allocated in "From" space. During Minor GC (Scavenge), surviving objects are copied to "To" space. Objects that survive twice are promoted to the Old generation.

Orinoco: The name of V8's GC optimization project. It runs GC work concurrently and in parallel with the main thread to shorten STW time. The main techniques are:

• Concurrent Marking: Worker threads traverse the object graph concurrently with the main thread
• Parallel Scavenging: Multiple worker threads perform Young generation GC in parallel
• Incremental Marking: Makes small marking progress during idle time or between tasks
• Lazy Sweeping: Defers sweep processing to allocation time

.NET (CLR) — Generational Mark & Compact

.NET's GC has two modes: Workstation GC for client apps and Server GC for server workloads.

Large Object Heap (LOH): Objects 85,000 bytes or larger are allocated directly in the LOH. The LOH is not compacted by default, though .NET Framework 4.5.1 and later allow explicit compaction via GCSettings.LargeObjectHeapCompactionMode.

Pinning: Prevents the GC from moving objects during native interop. It is done with fixed statements or GCHandle.Alloc(obj, GCHandleType.Pinned), but overuse causes fragmentation.

Rust — No GC (Ownership System)

Rust doesn't rely on GC. Its compile-time checks of ownership, borrowing, and lifetimes enforce memory safety.

Ownership system → Memory deallocation timing decided at compile time
                 → No GC runtime, so no GC pauses

The RAII (Resource Acquisition Is Initialization) pattern ensures that the type's Drop implementation runs automatically when a variable goes out of scope. The calls are determined at compile time, but the destructor and deallocation work still run at runtime; what Rust avoids is a tracing-GC runtime and GC pauses.

For circular references, Rc<T> / Arc<T> + Weak<T> provide reference counting. Weak<T> is a non-owning reference that doesn't count toward Rc's strong reference count, so making one link of a cycle a Weak<T> breaks the cycle.

Swift — ARC (Automatic Reference Counting)

Swift uses ARC, which inserts reference counting operations at compile time.

• No runtime tracing GC needed
• All retain/release calls are inserted at compile time, making runtime overhead predictable
• Circular references must be explicitly resolved by developers using weak (becomes Optional) / unowned (non-Optional, when the referenced object has the same or a longer lifetime)

Swift's compiler includes ARC optimizations that eliminate redundant retain/release pairs (including Copy-on-Write optimization).

GC Technology Timeline

Summary

In the table's STW column, "Short" means the runtime shortens pauses with concurrent or incremental work.

The choice of GC shapes a language runtime's pause times, throughput, and memory use. Reference counting is simple and reclaims memory immediately but cannot handle cycles. Tracing GC reclaims cycles at the cost of pauses and heap walks. Generational GC reduces that cost by relying on the hypothesis that most objects die young, and concurrent GC shortens pauses in exchange for write-barrier overhead. The differences in the table above reflect which of these trade-offs each language chose for its workloads and requirements.

References

• The Garbage Collection Handbook: The Art of Automatic Memory Management — Richard Jones, Antony Hosking, Eliot Moss, 2011
• Go Blog: Getting to Go — The Journey of Go's Garbage Collector
• Go Blog: A Guide to the Go Garbage Collector
• V8 Blog: Trash talk — The Orinoco garbage collector
• ZGC — Oracle Documentation
• Python GC — CPython Developer Guide
• .NET GC — Microsoft Documentation
• Dijkstra et al., "On-the-Fly Garbage Collection: An Exercise in Cooperation," 1978
• Uniprocessor Garbage Collection Techniques — Paul R. Wilson, 1992