Why Caching Fails to Speed Up Mark-and-Sweep Garbage Collection

In software engineering, caching is frequently treated as the default silver bullet for latency and throughput bottlenecks. Whether precomputing expensive queries, pulling disk blocks into RAM, or storing frequently accessed data in CPU caches, the intuition is consistent: keep hot data closer to the processor so future requests are served faster.

However, caching is not universally effective. A cache delivers performance benefits only when the workload satisfies specific memory access patterns. Applying caching to algorithms that do not exhibit these patterns yields no performance improvement—and can even introduce overhead.

A classic example is the Mark-and-Sweep Garbage Collector (GC). While GC is CPU-intensive and developers instinctively look for ways to optimize it via caching, classical mark-and-sweep fundamentally resists standard caching optimizations.

---

Refresher: The Mark-and-Sweep Algorithm

Mark-and-Sweep is a foundational tracing garbage collection algorithm designed to reclaim unused heap memory. It operates in two distinct phases:

flowchart TD
    subgraph Root Nodes
        R1[Global Variables]
        R2[Active Thread Stacks]
        R3[CPU Registers]
    end

    subgraph Heap Memory
        A[Object A - Reachable]
        B[Object B - Reachable]
        C[Object C - Reachable]
        D[Object D - Unreachable/Garbage]
        E[Object E - Unreachable/Garbage]
    end

    R1 --> A
    A --> B
    B --> C
    
    classDef live fill:#2ecc71,stroke:#27ae60,stroke-width:2px,color:#fff;
    classDef dead fill:#e74c3c,stroke:#c0392b,stroke-width:2px,color:#fff;
    class A,B,C live;
    class D,E dead;

1. Mark Phase:

   • Starts at the root set (global variables, local variables on thread stacks, CPU registers).
   • Traverses the reference graph using standard graph traversal (typically Depth-First Search or Breadth-First Search).
   • For every reachable object encountered, the collector sets a marked bit (or color flag) to indicate it is alive.
   • Objects unreachable from roots remain unmarked.

2. Sweep Phase:

   • Scans the entire heap linearly.
   • Any object whose marked bit is not set is considered garbage and reclaimed (added to a free-list or deallocated).
   • Marked bits on live objects are cleared in preparation for the next GC cycle.

Because GC steals CPU cycles that would otherwise execute application business logic, minimizing GC pause times is critical. But why can’t a cache simply store recently visited objects or reference paths to accelerate this traversal?

---

The Foundations of Caching

To understand why mark-and-sweep resists caching, consider the physical and structural invariants that make caches work in the first place.

A cache stores data in faster, more expensive storage closer to the execution engine. In modern hardware, the latency hierarchy is stark:

Storage Tier	Typical Latency	Speed Relative to RAM
L1 Cache	~1 ns	~50x faster
L2 Cache	~5 ns	~10x faster
L3 Cache	~10 ns	~5x faster
Main Memory (DRAM)	~50–100 ns	Baseline (1x)
Disk / SSD	Microseconds to Milliseconds	Thousands of times slower

Regardless of whether a cache sits between CPU registers and DRAM (hardware caches) or between an application server and a database (e.g., Redis), it only provides a speedup if the workload satisfies at least one of two fundamental properties:

1. Temporal Locality

If a specific data location is accessed at time $t$, it is highly likely to be accessed again at time $t + \Delta t$ in the near future.

• Example: In a web application, a user viewing their own profile page is likely to reload or navigate related subpages immediately. Caching the user’s profile entity in Redis avoids redundant DB lookups.

2. Spatial Locality

If a specific data location is accessed at address $A$, adjacent or nearby memory locations ($A + 1, A + 2, \dots$) are highly likely to be accessed soon.

• Example: Iterating over a contiguous array or scanning database rows stored contiguously in a disk block. When the first item is read, the hardware or OS prefetches the surrounding block into cache, making subsequent sequential reads near-instantaneous.

graph LR
    subgraph Memory Access Patterns
        A[Temporal Locality] -->|Requires| B[Repeated access to same address]
        C[Spatial Locality] -->|Requires| D[Sequential access to adjacent addresses]
    end
    B --> E{Cache Hit / Pre-fetch Effective?}
    D --> E

If an access pattern exhibits neither temporal nor spatial locality, caches fail. They suffer continuous cache misses, and the overhead of maintaining the cache degrades overall system performance.

---

Why Mark-and-Sweep Violates Both Principles

1. Mark-and-Sweep Lacks Temporal Locality

During the mark phase, the garbage collector traverses the object graph using DFS. When the traversal encounters an object:

1. It reads the object header to check if the marked bit is set.
2. If unmarked, it flips the marked bit to 1.
3. It inspects all pointers/references inside the object and enqueues child references onto its traversal stack.
4. It moves on.

Once an object is marked, the traversal never needs to visit or mutate that object again within the same GC cycle. The mark phase processes each live object exactly once.

Furthermore, during the subsequent sweep phase, live objects are simply bypassed (or have their mark bit reset), without needing the object payload. By the time the next GC cycle runs, thousands of instructions have passed, rendering any CPU cache lines that held previously marked objects cold and evicted. Storing an object in a cache during marking is completely useless because there is no immediate re-access.

2. Mark-and-Sweep Lacks Spatial Locality

Spatial locality requires adjacent memory addresses to be read in sequence. In managed runtimes, the heap does not store logical object relationships contiguously:

• Consider an object Student that contains a reference pointer to an object School.
• Student might be allocated at address 0x0040A100.
• School might have been allocated much earlier or later, residing at 0x07F81B20.
• A third reference inside Student might point to address 0x012B8900.

Heap Memory Layout:
[0x0040A100: Student] ---> (Pointer to 0x07F81B20)
[0x0040A120: Float Matrix (Unrelated)]
...
[0x012B8900: Course Object]
...
[0x07F81B20: School Object]

Traversing the heap via pointers is a series of random pointer chases across non-contiguous memory addresses.

When the CPU loads Student into the L1/L2 cache, hardware prefetchers notice the cache line (e.g., 64 bytes) and automatically pull the physically adjacent memory addresses (Student + 64 bytes) into the cache. But that adjacent memory often holds unrelated allocations—not the School object. The prefetched data is discarded without ever being used, resulting in pervasive CPU cache pollution.

To prefetch effectively during pointer chasing, one would need explicit software-directed prefetching instructions (_mm_prefetch), but pointer-chasing dependencies (where address $B$ cannot be known until address $A$ is loaded and dereferenced) severely limit how much latency hardware prefetchers can hide.

---

The Edge Case: Where Caching Can Help GC

While general object traversal lacks locality, real-world runtimes (such as CPython, the JVM, or Google’s V8) feature an asymmetrical, skewed object distribution: low-cardinality, high-reference metadata objects.

Every instance in an object-oriented runtime references shared runtime definitions:

classDiagram
    class TypeObjectStudent {
        +name: "Student"
        +methods: [...]
        +size: 64
    }
    class StudentInstance1 {
        +type_ptr
        +id: 101
    }
    class StudentInstance2 {
        +type_ptr
        +id: 102
    }
    class StudentInstanceN {
        +type_ptr
        +id: N
    }

    StudentInstance1 --> TypeObjectStudent : type_ptr
    StudentInstance2 --> TypeObjectStudent : type_ptr
    StudentInstanceN --> TypeObjectStudent : type_ptr

Low-Cardinality Type Objects

• In CPython, every integer instance points to PyLong_Type, and every string points to PyUnicode_Type.
• In custom domain models, thousands of Student instances reference a single Student class descriptor/vtable.
• During garbage collection, every instance dereferences its class pointer to inspect its field layouts and reference offsets.

Because thousands of individual instances repeatedly access the exact same metadata address, type descriptors exhibit extreme temporal locality.

Modern runtimes optimize for this:

1. Class definitions, shape descriptors (V8 Hidden Classes / Maps), and static type definitions are pinned in fast, hot cache lines.
2. Runtimes segregate metadata from instance payload data so that the collector does not evict frequently read metadata during deep heap traversals.

This specific caching optimization provides marginal latency improvements, but it optimizes class metadata resolution—not the traversal of the dynamic object graph itself.

---

Summary and Core Takeaways

1. Locality Dictates Cache Viability: Caching is only effective if an access pattern exhibits temporal locality (frequent re-access of the same data) or spatial locality (predictable access to physically contiguous data).
2. Mark-and-Sweep Defeats Temporal Locality: Each live node in the object graph is visited once during the mark phase to set a bit, eliminating immediate read/write repetition.
3. Pointer Chasing Defeats Spatial Locality: Dynamic heap graphs are linked via scattered references rather than sequential arrays. Hardware prefetchers cannot predict arbitrary memory jumps, resulting in wasted cache lines.
4. Selective Caching Works for Metadata: While dynamic instances resist caching during GC, low-cardinality, highly referenced runtime metadata (like type pointers, vtables, and object layout descriptors) exhibit high temporal locality and benefit from being kept hot.