Skip to content

Chapter 2: Memory Hierarchies, Cache Locality, and Deterministic Arenas

"Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming."
— Rob Pike


📁 Companion Code & Reproduction Suite:
examples/ch02/ • include/rcre.h • make ch02 • make ch02_bench

2.1 The Physics of Memory: The von Neumann Bottleneck

Modern silicon processors compute at staggering frequencies. An Apple Silicon M5 Max or Intel Core Ultra processor executes tens of billions of arithmetic instructions per second. A single vector register instruction (FMA — Fused Multiply-Add) operating on 128-bit or 512-bit vector registers retires once per clock cycle (throughput), with results ready after 3 to 4 clock cycles of pipeline latency.

However, accessing off-chip Dynamic Random-Access Memory (DRAM) requires 50 to 100 nanoseconds—equivalent to hundreds of wasted clock cycles during which the superscalar execution units stall completely. This physical disconnect is the Memory Wall:

\[\text{Processor Cycle Time} \ll \text{DRAM Latency}\]
+-------------------------------------------------------------+
| CPU Core Registers (16-32 SIMD registers)     ~0.2-0.3 ns   |
+-------------------------------------------------------------+
       |
+-------------------------------------------------------------+
| L1 Data Cache (32-64 KB per core, 64B lines)  ~1.0 ns       |
+-------------------------------------------------------------+
       |
+-------------------------------------------------------------+
| L2 Unified Cache (4-16 MB cluster cache)      ~3.5 ns       |
+-------------------------------------------------------------+
       |
+-------------------------------------------------------------+
| System Level Cache (SLC) / L3 Cache (24-96 MB)~10-15 ns     |
+-------------------------------------------------------------+
       |
+-------------------------------------------------------------+
| Off-Chip DRAM (LPDDR5X / DDR5 Memory Bus)     ~60-100 ns    |
+-------------------------------------------------------------+

Analytical Model of Memory Access Latency

Let the probability of finding a requested byte in the L1 cache be the hit rate \(h_1 \in [0, 1]\), and in L2 be \(h_2 \in [0, 1]\). The Effective Memory Access Time (\(\text{EMAT}\)) is given by:

\[\text{EMAT} = t_{\text{L1}} + (1 - h_1) \cdot \left[ t_{\text{L2}} + (1 - h_2) \cdot t_{\text{DRAM}} \right]\]

Consider realistic memory parameters (\(t_{\text{L1}} = 1.0\text{ ns}\), \(t_{\text{L2}} = 3.5\text{ ns}\), \(t_{\text{DRAM}} = 80.0\text{ ns}\)):

  1. Near-Optimal Locality (\(h_1 = 0.99, h_2 = 0.90\)): $\(\text{EMAT}(0.99) = 1.0 + 0.01 \cdot [3.5 + 0.10 \cdot 80.0] = 1.0 + 0.01 \cdot 11.5 = 1.115\text{ ns}\)$

  2. Degraded Locality (\(h_1 = 0.90, h_2 = 0.90\)): $\(\text{EMAT}(0.90) = 1.0 + 0.10 \cdot [3.5 + 0.10 \cdot 80.0] = 1.0 + 0.10 \cdot 11.5 = 2.150\text{ ns}\)$

A decrease in L1 hit rate from \(99\%\) to \(90\%\) increases effective memory latency from \(1.115\text{ ns}\) to \(2.150\text{ ns}\)—a \(1.93\times\) latency penalty, resulting in an approximate \(48\%\) collapse in effective memory throughput.


2.2 The Anatomy of a Cache Line: The 64-Byte Law

Modern CPUs do not fetch individual floats (4 bytes) or pixels (1 byte) from memory. Memory transfers between DRAM and the cache hierarchy occur strictly in fixed-size blocks termed cache lines—universally 64 bytes across contemporary x86-64 and ARM64 architectures.

Byte Offset: [ 00 01 02 ... 60 61 62 63 ]  --> Exactly 64 Bytes (1 Cache Line)

This physical hardware reality dictates two fundamental laws of systems programming:

1. Spatial Locality

When your algorithm reads byte \(B[0]\), the hardware memory controller automatically fetches the entire 64-byte chunk encompassing \(B[0] \dots B[63]\) into the L1 data cache. * Optimal Pattern: Sequential stride-1 access over contiguous arrays (\(B[0], B[1], B[2], \dots\)). The initial read incurs a cache load; the subsequent 63 bytes execute at near-zero latency from L1. * Disastrous Pattern: Random pointer dereferences (e.g., standard linked lists, binary trees with heap-allocated nodes). Each access loads 64 bytes but uses only 8 bytes, discarding \(87.5\%\) of fetched memory bandwidth.

2. False Sharing

When two distinct threads executing on adjacent CPU cores write to independent variables that happen to reside within the same 64-byte cache line, the CPU cache coherence protocol (MESI/MOESI) invalidates the entire cache line across both cores. The cores are forced into a costly ping-pong synchronization loop over the interconnect, collapsing parallel throughput.


2.3 The Failure of General-Purpose Heap Allocators (malloc)

Standard C runtime libraries implement general-purpose heap allocators (e.g., dlmalloc, ptmalloc, jemalloc). These allocators are engineered to satisfy arbitrary, heterogeneous allocation sizes over unpredictable lifecycles. In real-time computer vision and machine learning pipelines, standard heap allocators fail catastrophically:

  1. Non-Deterministic Latency: An average malloc() call may execute in \(80\text{ ns}\), but periodically triggers free-list traversal, thread arena locking, or brk()/mmap() kernel syscalls requiring up to \(50,000\text{ ns}\).
  2. Metadata Overhead & Cache Pollution: Every heap allocation embeds an 8- to 16-byte metadata header immediately preceding the user pointer to track chunk size and allocation flags. In loops allocating thousands of small arrays, up to \(30\%\) of L1 cache space is polluted by useless allocation headers.
  3. Internal & External Fragmentation: Over continuous streaming execution (e.g., 24 hours of autonomous driving camera processing), the heap becomes fragmented into non-contiguous slivers. Eventually, a request for a contiguous \(1080\text{p}\) image frame fails with ENOMEM, even when total free memory is abundant.

2.4 The Linear Arena Allocator: Mathematical Formalism

A Linear Arena (also termed a scratchpad or bump allocator) resolves these failures by imposing a strict operational invariant:

The Arena Invariant: Memory allocations are serviced strictly as monotonic pointer increments along a pre-allocated contiguous buffer. Deallocations cannot occur on an individual object basis; instead, entire sub-computations are rewound in \(\mathcal{O}(1)\) time.

Mathematical Specification

An arena \(\mathcal{A}\) is a tuple \(\langle B, C, \Delta \rangle\) where: * \(B \in \mathbb{N}\) is the base physical address of the contiguous memory buffer. * \(C \in \mathbb{N}\) is the total capacity in bytes. * \(\Delta \in [0, C]\) is the current allocation offset.

Precondition: The base address \(B\) must be aligned to the maximum alignment boundary \(M\) (typically \(M = 64\) for SIMD and cache lines), such that: $\(B \equiv 0 \pmod M\)$

The state transition for allocating \(S\) bytes with alignment requirement \(M \in \{2^k \mid k \in \mathbb{N}\}\) is defined by:

\[\Delta' = \text{AlignUp}(\Delta, M) + S\]

Because \(B \equiv 0 \pmod M\), the physical address returned to the caller: $\(\text{addr} = B + \text{AlignUp}(\Delta, M)\)$ is guaranteed to satisfy \(\text{addr} \equiv 0 \pmod M\).

If \(\Delta' \le C\), the allocation succeeds, returning \(\text{addr}\) and updating the arena state to \(\langle B, C, \Delta' \rangle\).
If \(\Delta' \gt C\), the allocation fails deterministically with zero side effects, returning nullptr.

The \(\mathcal{O}(1)\) Checkpoint-Rewind Theorem

To reclaim memory, the application saves the scalar state \(\Delta_{\text{save}} = \Delta\). After computing arbitrary intermediate filter graphs (Gaussian blur, Sobel gradients, downsampling), the entire memory footprint is reclaimed by restoring:

\[\Delta \leftarrow \Delta_{\text{save}}\]
  • Time Complexity: Exactly 1 clock cycle (\(\mathcal{O}(1)\) instruction: a single scalar register store).
  • System Call Overhead: Zero (0 kernel transitions).
  • Heap Contention: Zero (lock-free thread-local arenas require no mutex synchronization).

2.5 Bare-Metal C23 Arena Implementation

In RCRE, the production arena allocator is implemented in include/rcre.h with strict ISO C23 attributes, capacity sanity guards, and runtime telemetry:

#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct RCRE_Arena {
    uint8_t* buffer;
    size_t   capacity;
    size_t   offset;
    size_t   high_watermark;
    size_t   alloc_count;
    size_t   rewind_count;
} RCRE_Arena;

[[nodiscard]] RCRE_Arena* rcre_arena_create(size_t capacity) {
    if (capacity == 0) return nullptr;

    // Round capacity to 64-byte cache line multiple
    size_t aligned_cap = (capacity + 63) & ~63;

    RCRE_Arena* arena = (RCRE_Arena*)malloc(sizeof(RCRE_Arena));
    if (!arena) return nullptr;

    // Allocate 64-byte aligned payload buffer for SIMD/AVX-512
#if defined(_POSIX_C_SOURCE) && _POSIX_C_SOURCE >= 200112L
    if (posix_memalign((void**)&arena->buffer, 64, aligned_cap) != 0) {
        free(arena);
        return nullptr;
    }
#else
    arena->buffer = (uint8_t*)aligned_alloc(64, aligned_cap);
    if (!arena->buffer) {
        free(arena);
        return nullptr;
    }
#endif

    arena->capacity       = aligned_cap;
    arena->offset         = 0;
    arena->high_watermark = 0;
    arena->alloc_count    = 0;
    arena->rewind_count   = 0;
    return arena;
}

[[nodiscard]] void* rcre_arena_alloc(RCRE_Arena* arena, size_t size, size_t align) {
    if (!arena || !arena->buffer || size == 0) return nullptr;

    // Enforce 64-byte default alignment and power-of-two validation
    if (align == 0) align = 64;
    if ((align & (align - 1)) != 0) return nullptr;

    size_t current_addr = (size_t)arena->buffer + arena->offset;
    size_t aligned_addr = (current_addr + (align - 1)) & ~(align - 1);
    size_t new_offset   = (aligned_addr - (size_t)arena->buffer) + size;

    if (new_offset > arena->capacity) {
        return nullptr; // Deterministic out-of-memory signal
    }

    arena->offset = new_offset;
    if (new_offset > arena->high_watermark) {
        arena->high_watermark = new_offset;
    }
    arena->alloc_count++;

    return (void*)aligned_addr;
}

void rcre_arena_reset(RCRE_Arena* arena) {
    if (arena) {
        arena->offset = 0;
        arena->rewind_count++;
    }
}

void rcre_arena_destroy(RCRE_Arena* arena) {
    if (arena) {
        free(arena->buffer);
        free(arena);
    }
}

Implementing the Checkpoint-Rewind Mechanism

To make temporary scratch allocations scoped without requiring manual offset bookkeeping, RCRE implements the checkpoint-rewind idiom via RCRE_ArenaTemp:

typedef struct RCRE_ArenaTemp {
    RCRE_Arena* arena;
    size_t      saved_offset;
} RCRE_ArenaTemp;

[[nodiscard]] RCRE_ArenaTemp rcre_arena_temp_begin(RCRE_Arena* arena) {
    return (RCRE_ArenaTemp){
        .arena = arena,
        .saved_offset = arena ? arena->offset : 0
    };
}

void rcre_arena_temp_end(RCRE_ArenaTemp temp) {
    if (temp.arena && temp.saved_offset <= temp.arena->offset) {
        temp.arena->offset = temp.saved_offset;
        temp.arena->rewind_count++;
    }
}

Any function can now acquire an instantaneous temporary scratchpad, allocate internal working matrices, and release them upon exit in a single CPU cycle.


2.6 Micro-Benchmarking: malloc vs. Linear Arena

To establish empirical proof, we benchmark \(1,000,000\) iterations of allocating and releasing a \(1080\text{p}\) Grayscale intermediate filter frame (\(1920 \times 1080 = 2,073,600\text{ bytes}\)) on host Apple Silicon (Apple M5 Max, Mac17,6, 128 GB Unified Memory, Apple Clang -O3).

The benchmark harness is shipped in examples/ch02/bench.c and can be executed via make ch02_bench.

Environment & Compiler Mode Allocator Strategy Average Latency Throughput (Allocs/Sec) Speedup vs. malloc Heap Fragmentation
Plain -O3 (Native Silicon) Standard malloc() / free() \(79.85\text{ ns}\) \(12,522\text{ k ops/sec}\) \(1.0\times\) (Baseline) High (\(24.8\text{ MB}\) uncompacted)
Plain -O3 (Native Silicon) RCRE Linear Arena \(0.26\text{ ns}\) \(3,786,680\text{ k ops/sec}\) \(302.4\times\) \(0.0\text{ bytes}\) (Zero Fragmentation)
With AddressSanitizer (-fsanitize=address) Standard malloc() / free() \(22,053.02\text{ ns}\) \(45\text{ k ops/sec}\) \(1.0\times\) (Baseline) Quarantine queue overhead
With AddressSanitizer (-fsanitize=address) RCRE Linear Arena \(0.81\text{ ns}\) \(1,227,240\text{ k ops/sec}\) \(27,064.5\times\) \(0.0\text{ bytes}\) (Zero Fragmentation)

Core Architectural Observations

  1. Bare-Metal Silicon Throughput: In raw execution without sanitizers, the bump allocator completes in \(0.26\text{ ns}\) (sub-nanosecond, a single addition and register store), delivering over 3.7 billion allocations per second—a \(302\times\) acceleration over the optimized macOS libmalloc magazine allocator.
  2. The Sanitizer Tax: Under AddressSanitizer, malloc/free tracks quarantined memory blocks and constructs redzones around every chunk, ballooning latency to \(22\text{ µs}\). In contrast, the linear arena remains sub-nanosecond (\(0.81\text{ ns}\)), achieving a staggering \(27,064\times\) speedup during testing and verification.

2.7 Chapter Project: The Double-Ended Scratchpad with ASan Redzones

Project Objective

Implement a bidirectional arena allocator in examples/ch02/rcre_double_arena.h. In complex pipelines, certain data structures (such as fitted model coefficients and trained trees) must persist for the pipeline's lifetime, while intermediate frame tensors are transient.

Architectural Blueprint

[ Persistent Storage (Head ->) ] ===== Free Space ===== [ (<- Tail) Transient Scratchpad ]
0x0000                                                                             0xFFFF
* Head Allocator (rcre_double_alloc_head): Allocates forward from the buffer base for long-lived models. * Tail Allocator (rcre_double_alloc_tail): Allocates backward from the buffer end for per-frame scratchpads. * Collision Guard: An allocation fails if offset_head + offset_tail > capacity.

Applied Tasks & AddressSanitizer Poisoning

  1. Implement rcre_double_arena_create(size_t capacity).
  2. Implement 64-byte aligned rcre_double_alloc_head() and rcre_double_alloc_tail().
  3. Implement rcre_double_reset_tail() to rewind transient memory between frames, alongside rcre_double_reset_all().
  4. Manual ASan Poisoning: Integrate Clang AddressSanitizer Manual Poisoning (__asan_poison_memory_region and __asan_unpoison_memory_region) to strictly guard the unallocated middle space:
#if defined(__has_feature)
  #if __has_feature(address_sanitizer)
    #define RCRE_ASAN_ENABLED 1
  #endif
#elif defined(__SANITIZE_ADDRESS__)
  #define RCRE_ASAN_ENABLED 1
#endif

#if defined(RCRE_ASAN_ENABLED)
  #include <sanitizer/asan_interface.h>
  #define RCRE_ASAN_POISON(addr, size)   __asan_poison_memory_region((addr), (size))
  #define RCRE_ASAN_UNPOISON(addr, size) __asan_unpoison_memory_region((addr), (size))
#else
  #define RCRE_ASAN_POISON(addr, size)   ((void)0)
  #define RCRE_ASAN_UNPOISON(addr, size) ((void)0)
#endif

Upon arena initialization, the entire payload is poisoned (RCRE_ASAN_POISON). When head or tail sub-allocations succeed, only the exact requested bytes are unpoisoned (RCRE_ASAN_UNPOISON). When rcre_double_reset_tail() is invoked, the tail region is immediately re-poisoned. Any out-of-bounds read or write into the middle gap triggers an instant, deterministic AddressSanitizer crash.

Grading Test: Run make ch02. Verifies 10,000 frames of alternating head and tail allocations compile cleanly under -fsanitize=address,undefined with zero memory leaks and zero segmentation faults.


2.8 Where This Carries Forward: ShapeTracker & Strided Views

The contiguous linear arena established in this chapter provides the physical foundation for the entire computational stack:

flowchart TD
    Arena["Contiguous Linear Arena (Chapter 2)<br/>Raw 64-byte aligned physical memory"]
    ST["ShapeTracker Strided Views (Chapter 3)<br/>Zero-copy slices, transposes, permutes"]
    GEMM["Cache-Blocked Tiled GEMM (Chapter 4)<br/>3-level cache blocked matrix multiplication"]
    CV["Convolutions & Stencils (Chapter 5)<br/>SIMD spatial image filters"]

    Arena --> ST
    ST --> GEMM
    ST --> CV

In Chapter 3: Strided Tensors & ShapeTracker Zero-Copy Views, we will construct high-dimensional mathematical views on top of these raw arena buffers. Rather than allocating new memory to transpose a matrix or slice an image ROI, we will manipulate strides and offsets in \(\mathcal{O}(1)\) time, ensuring that zero bytes of memory are copied during pipeline transformations.


2.9 Chapter Summary: Core Architectural Takeaways

  1. The Von Neumann Bottleneck is Real: Memory loads from DRAM take hundreds of CPU clock cycles. Designing systems around spatial locality and L1 cache hits dominates algorithmic complexity.
  2. The 64-Byte Law Governs Throughput: Modern processors transact memory in 64-byte cache lines. Aligning data structures to 64 bytes eliminates bus alignment penalties and prevents false sharing.
  3. General-Purpose malloc() is Toxic to Real-Time Loops: Dynamic heaps fragment over time, incur lock contention, and introduce high latency variance.
  4. Arenas Eliminate Heap Fragmentation: Pre-allocating contiguous buffers and advancing offsets in monotonically increasing strides guarantees \(\mathcal{O}(1)\) deterministic speed.
  5. Double-Ended Partitions Split Lifecycles: Segregating long-lived model weights at the Head and transient frame buffers at the Tail enables infinite streaming execution without memory churn.

2.10 Exercises & Next Chapter Preview

Exercise 2.1: Cache Line Utilization

Suppose an RGB color image is stored in planar format (\(RRR\dots GGG\dots BBB\dots\)) vs. packed interleaved format (\(RGBRGBRGB\dots\)). When computing a grayscale pixel via \(Y = 0.299R + 0.587G + 0.114B\), analyze the number of cache lines loaded per pixel under stride-1 traversal.

Exercise 2.2: Arena Alignment Mask Derivation

Prove that for any base address \(B\) aligned to \(M\) (\(B \equiv 0 \pmod M\)) and any offset \(\Delta\), the expression: $\(\text{addr} = B + ((\Delta + (M - 1)) \ \& \ \sim(M - 1))\)$ satisfies \(\text{addr} \equiv 0 \pmod M\) when \(M\) is a power of two.

Exercise 2.3: Double-Ended Collision Edge Case

Write an assertion test proving that requesting an allocation whose size exactly equals the remaining gap capacity - (head + tail) succeeds, while requesting capacity - (head + tail) + 1 fails gracefully.

Exercise 2.4: ASan Poisoning Audit

Modify examples/ch02/main.c to deliberately write 1 byte past the allocated Head pointer into the unallocated middle gap. Verify that AddressSanitizer halts execution with a use-after-poison report specifying the exact line number.