Cache Locality

Modern CPU cores execute arithmetic instructions in under 0.5 ns, whereas fetching a cache line from main DRAM takes ~60–100 ns—a 150x speed gap. Cache locality designs data structures and traversal orders so the CPU's L1/L2/L3 caches and hardware prefetcher always have the next required bytes ready before the execution pipeline stalls.

CPU Memory Hierarchy Latency (Typical 64-Bit Core):
  Registers        :   ~0.3 ns   (Immediate)
  L1 Data Cache    :   ~1.0 ns   (32 - 128 KiB per core)
  L2 Cache         :   ~3.5 ns   (512 KiB - 4 MiB)
  L3 Shared Cache  :  ~12.0 ns   (16 - 64+ MiB)
  Main DRAM        :  ~80.0 ns   (Pointer-chasing cache miss penalty!)

Temporal vs Spatial Locality

1. Spatial Locality: Accessing memory addresses that are physically adjacent (slice[i], slice[i + 1]). Because a single cache fetch loads 64 or 128 contiguous bytes, reading slice[0] automatically brings slice[1..16] (for u32) into L1 cache for free, and linear access triggers the CPU's hardware stride prefetcher!
2. Temporal Locality: Reusing the same small working set of memory addresses repeatedly while it is still resident in L1 or L2 cache.

Why Row-Major Loop Order Outperforms Column-Major Order by 5x–15x

In Rust, a flat 2D grid stored as grid[row * width + col] (or [[f64; W]; H]) lays out elements of the same row contiguously in memory.

• Row-major traversal (for r in 0..height { for c in 0..width } — inner loop increments c by 1) steps through memory sequentially (+8 bytes per step), achieving 100% cache-line utilization and SIMD auto-vectorization.
• Column-major traversal (for c in 0..width { for r in 0..height } — inner loop jumps by +width * 8 bytes per step) skips across cache lines, wasting 7 out of 8 f64 values on every cache line load!

pub struct Matrix {
    rows: usize,
    cols: usize,
    data: Vec<u64>,
}

impl Matrix {
    pub fn new_filled(rows: usize, cols: usize, val: u64) -> Self {
        Self {
            rows,
            cols,
            data: vec![val; rows * cols],
        }
    }

    /// Cache-friendly row-major accumulation: reads contiguous memory sequentially.
    pub fn sum_row_major(&self) -> u64 {
        let mut total = 0u64;
        for row in self.data.chunks_exact(self.cols) {
            for &val in row {
                total = total.wrapping_add(val);
            }
        }
        total
    }

    /// Cache-friendly matrix transpose using cache-oblivious block tiling (`TILE = 16`).
    pub fn transpose(&self) -> Self {
        const TILE: usize = 16;
        let mut out = vec![0u64; self.rows * self.cols];

        for r_block in (0..self.rows).step_by(TILE) {
            for c_block in (0..self.cols).step_by(TILE) {
                let r_end = (r_block + TILE).min(self.rows);
                let c_end = (c_block + TILE).min(self.cols);
                for r in r_block..r_end {
                    for c in c_block..c_end {
                        out[c * self.rows + r] = self.data[r * self.cols + c];
                    }
                }
            }
        }

        Self {
            rows: self.cols,
            cols: self.rows,
            data: out,
        }
    }
}

fn main() {
    let mat = Matrix::new_filled(64, 128, 3);
    let transposed = mat.transpose();

    assert_eq!(mat.sum_row_major(), 64 * 128 * 3);
    assert_eq!(transposed.rows, 128);
    assert_eq!(transposed.cols, 64);
    println!("Row-major sum: {}", mat.sum_row_major());
}

Row-major sum: 24576