The RAM Model vs Modern CPU Cache Hierarchy

The Von Neumann Bottleneck & The 64-Byte Cache Line Quantum

In the theoretical Word-RAM model of computation (formalized by Sheperdson & Sturgis and popularized by CLRS), memory is an infinite flat array of $w$-bit words ($w = 64$ on modern x86-64 and ARM64 architectures), and dereferencing any address $A[i]$ incurs a uniform cost $c = 1$. However, since 1980, CPU clock frequencies and multi-issue execution pipelines have scaled exponentially faster than DRAM capacitor discharge and sense-amplifier latencies—a divergence known as the Memory Wall.

To bridge this gap, modern processors interpose a hierarchy of Static RAM (SRAM) caches between the execution cores and Dynamic RAM (DRAM). Crucially, the unit of transfer across the memory bus is not a byte or a 64-bit word, but an aligned 64-byte Cache Line (128 bytes on Apple M-series silicon):

• Spatial Locality: Reading a single int64_t at address 0x1000 automatically pulls the entire 64-byte block [0x1000 .. 0x103F] (eight consecutive 64-bit integers) into L1d cache. The subsequent 7 reads in a stride-1 array scan cost ~4 cycles each instead of 200 cycles.
• Temporal Locality: Recently accessed cache lines remain resident in L1/L2 under pseudo-LRU replacement policies. Re-reading hot loop variables or small lookup tables never touches the memory bus.
• Hardware Stream Prefetching: The L1/L2 hardware prefetcher monitors memory access strides. When it detects a constant sequential stride ($+1$, $+2$, or $-1$ cache lines), it speculatively issues DRAM requests 4–8 cache lines ahead of the instruction pointer, hiding DRAM latency completely.
• TLB (Translation Lookaside Buffer) Reach: Every virtual memory address must be translated to a physical page frame (typically 4 KB pages). A random pointer chase across a 1 GB structure spans $262{,}144$ pages, thrashing the L1 dTLB (64 entries) and L2 TLB (1536 entries) and triggering costly 4-level page-table walks (+30 to 100 cycles per TLB miss).

Visualizing CPU Cache Hierarchy & Stride Locality

The diagram below illustrates how a single L1 cache line fill fetches 8 contiguous 64-bit elements simultaneously during a vector scan, whereas a linked list traversal fetches 7 useless adjacent heap objects on every single pointer dereference.

Benchmarking Spatial Locality: Contiguous Array vs Strided Access vs Heap List

The C++20 benchmark below demonstrates how to eliminate pointer chasing by storing graph or list nodes inside a contiguous arena pool (std::vector<Node>) indexed by 32-bit integer offsets rather than raw 64-bit heap pointers. This halves pointer memory footprint and restores spatial cache locality.

// C++20: Defeating Pointer Chasing with Contiguous Arena Pool & 32-bit Index Handles
#include <cstdint>
#include <vector>

// Anti-pattern: 24-byte heap node + 16-byte malloc header = 40B scattered across RAM
struct HeapListNode {
    int64_t payload;
    HeapListNode* next; // 8-byte pointer; dereferencing stalls ROB for ~200 cycles
};

// Systems Pattern: 12-byte packed struct inside a contiguous std::vector<ArenaNode>
// 5+ nodes fit inside a single 64-byte L1 cache line!
struct ArenaNode {
    int64_t payload;
    int32_t nextIdx; // -1 represents null; 4B index instead of 8B pointer
};

class ContiguousArenaList {
    std::vector<ArenaNode> pool_;
    int32_t head_ = -1;

public:
    explicit ContiguousArenaList(size_t reserveCount) {
        pool_.reserve(reserveCount);
    }

    int32_t pushFront(int64_t val) {
        int32_t idx = static_cast<int32_t>(pool_.size());
        pool_.push_back(ArenaNode{val, head_});
        head_ = idx;
        return idx;
    }

    // Traverses in allocation order or index order with L1/L2 hardware prefetcher active
    int64_t sumAll() const noexcept {
        int64_t total = 0;
        for (int32_t curr = head_; curr != -1; curr = pool_[curr].nextIdx) {
            total += pool_[curr].payload;
        }
        return total;
    }
};