Cache Locality and Memory Layout: Squeezing Peak Flops in C and Rust

Modern CPU cores operate at frequencies in excess of 4 GHz, capable of issuing multiple instructions per clock cycle. However, fetching a single cache line from main memory (DRAM) requires roughly 60 to 100 nanoseconds—equivalent to hundreds of idle clock cycles where the CPU stalls doing nothing.

At Kone Academy's Systems Engineering division, we teach that performance is no longer about raw algorithmic Big-O operation counts alone; it is dictated by cache-conscious memory layout.

⚡ 1. The Memory Wall and the Memory Hierarchy

A modern processor core sits atop a cascading pyramid of cache levels:

|---|---|---|---|

| CPU Registers | ~1-2 KB | 0-1 cycles | ~0.25 ns |

| L1 Data Cache (L1d) | 32-64 KB | 4-5 cycles | ~1 ns |

| L3 Shared Cache | 16-64 MB | 35-50 cycles | ~10-15 ns |

| Main Memory (DRAM)| 16-64 GB | 150-250 cycles | ~60-100 ns |

The processor transfers data between main memory and caches in fixed chunks termed Cache Lines (almost universally 64 bytes in x86-64 and ARM64). If your program requests a 4-byte integer, the hardware fetches the entire 64-byte aligned chunk into L1.

🔄 2. Spatial vs. Temporal Locality

Temporal Locality: If a memory location is accessed once, it is likely to be accessed again in the near future (e.g., loop counters, local variables).
Spatial Locality: If a memory location is accessed, adjacent memory locations are likely to be accessed soon (e.g., contiguous array traversals).

Consider iterating over a 2D matrix in Row-Major order (C/C++/Rust) vs Column-Major order:

// Fast: High Spatial Locality (Sequential 64-byte cache line reads)
for (size_t r = 0; r < ROWS; ++r) {
    for (size_t c = 0; c < COLS; ++c) {
        sum += matrix[r][c];
    }
}

// Catastrophically Slow: Cache Thrashing (Stride-N cache misses)
for (size_t c = 0; c < COLS; ++c) {
    for (size_t r = 0; r < ROWS; ++r) {
        sum += matrix[r][c];
    }
}

The column-major traversal can be 10x to 40x slower simply because every single memory read evicts an existing cache line and induces a DRAM stall.

🏗️ 3. Array of Structures (AoS) vs. Structure of Arrays (SoA)

Object-oriented design naturally produces Array of Structures (AoS):

// Array of Structures (AoS) - Cache Inefficient for Batch Iteration
struct Particle {
    pos_x: f32,
    pos_y: f32,
    pos_z: f32,
    vel_x: f32,
    vel_y: f32,
    vel_z: f32,
    mass:  f32,
    id:    u32,
    color: [u8; 4],
}

let particles: Vec<Particle> = Vec::with_capacity(1_000_000);

If an engine loop only updates pos_x += vel_x * dt, loading each Particle wastes cache lines on unused attributes (mass, id, color).

The Data-Oriented Design (DoD) Solution: Structure of Arrays (SoA)

// Structure of Arrays (SoA) - Cache Friendly & SIMD Vectorizable
struct ParticleSystem {
    pos_x: Vec<f32>,
    pos_y: Vec<f32>,
    pos_z: Vec<f32>,
    vel_x: Vec<f32>,
    vel_y: Vec<f32>,
    vel_z: Vec<f32>,
    mass:  Vec<f32>,
    id:    Vec<u32>,
}

With SoA:

Every 64-byte cache line loaded contains 16 contiguous f32 coordinates.
The hardware prefetcher recognizes the linear stride instantly.
The LLVM compiler auto-vectorizes the loop using AVX2 or NEON SIMD instructions, processing 8 floats in a single CPU cycle.

🚫 4. False Sharing in Concurrent Threads

When multiple threads concurrently mutate variables that happen to reside on the same 64-byte cache line, the MESI (Modified, Exclusive, Shared, Invalid) cache coherence protocol forces constant invalidation across CPU cores.

use std::sync::atomic::{AtomicU64, Ordering};
use std::thread;

// DANGEROUS: Both counters reside in the same 64-byte cache line!
struct UnpaddedCounters {
    thread_a_counter: AtomicU64,
    thread_b_counter: AtomicU64,
}

// OPTIMIZED: Cache-line aligned (No false sharing)
#[repr(align(64))]
struct CacheAlignedCounter(AtomicU64);

struct PaddedCounters {
    thread_a: CacheAlignedCounter,
    thread_b: CacheAlignedCounter,
}

Benchmarking this on an 8-core CPU demonstrates that eliminating false sharing can speed up multi-threaded counters by 300% to 800%.

🎓 Curriculum Connection at Kone Academy

In our Kone Code & Kone Lab Systems Tracks, students learn low-level profiling with Linux perf, cache-miss counters (perf stat -e L1-dcache-load-misses), and modern memory allocation strategies that turn theoretical algorithms into industrial-grade systems.

Cache Locality and Memory Layout: Squeezing Peak Flops in C and Rust