Memory layout and cache behaviour: flat arrays, AoS vs SoA

The obvious way to write a matrix in a language with growable arrays is Vec<Vec<f32>>. It reads well, it indexes as m[r][c], and it is the wrong data structure. Every high-performance numerical library — ndarray, nalgebra, NumPy, BLAS, PyTorch — stores a 2-D array as one flat buffer plus a stride, and this item is about why.

What Vec<Vec<f32>> actually is in memory

One heap allocation for the outer Vec, holding 1000 fat pointers. Then a thousand separate heap allocations, one per row, scattered wherever the allocator happened to have space. A 1000×1000 matrix costs 1001 allocations, 24 KB of pointer overhead, and no guarantee that row 5 sits anywhere near row 6.

pub struct Grid { pub data: Vec<f32>, pub cols: usize }

One allocation. Element (r, c) lives at data[r * cols + c]. Row r is the contiguous slice data[r * cols .. (r + 1) * cols] — a real &[f32] you can hand to anything that takes a slice, with no copying.

What to write

impl Grid {
    pub fn new(rows: usize, cols: usize) -> Grid
    pub fn rows(&self) -> usize
    pub fn get(&self, r: usize, c: usize) -> f32
    pub fn row(&self, r: usize) -> &[f32]
    pub fn transpose(&self) -> Grid
}

new fills element (r, c) with (r * 1000 + c) as f32. rows() is data.len() / cols, and 0 when cols is 0. transpose returns a new grid whose (c, r) is the original’s (r, c) — so its cols is the original’s row count.

The struct fields are fixed and public: the grader constructs a Grid literally, so data and cols must be exactly those names and types.

The gate: allocation counts

A test builds a 1000×1000 grid and transposes it, counting heap allocations around each:

• constructing the grid: at most 1
• transposing it: at most 1

Vec::new() plus a million pushes is about twenty allocations and twenty memcpys of the entire buffer, so it fails. Vec::with_capacity(rows * cols) or vec![0.0; rows * cols] is one, and passes. A Vec<Vec<f32>> design fails at 1001 before you even get to the transpose.

This is the honest gate for this topic, and here is why.

The honest calibration

It is tempting to promise that flat arrays are dramatically faster. Measured, on this toolchain, summing a 1000×1000 matrix:

1.13×. Not nothing, and not the order of magnitude the folklore implies. The workload is memory-bandwidth-bound, and modern prefetchers follow a thousand row pointers perfectly well once they have seen a few.

So do not promise a dramatic speed win. Promise a structural one, because that part is dramatic and it is deterministically testable:

• one allocation instead of 1001, and one free instead of 1001;
• genuine contiguity, which is what lets LLVM auto-vectorise and what lets you pass a row to any &[f32] API without copying;
• no pointer-chasing indirection on every row access;
• the ability to slice, chunk and reshape without touching the data.

Where the timing difference does become large is anything with a strided access pattern — a transpose, a matrix multiply, a stencil. Reading down a column of a flat row-major grid touches a new cache line on every element, and a blocked (tiled) transpose that works on 32×32 sub-blocks can beat the naive one substantially at 4096×4096. That is worth knowing, and worth measuring yourself rather than taking on faith.

AoS and SoA

The same question one level up. An array of structs:

struct Particle { x: f32, y: f32, z: f32, mass: f32 }
let world: Vec<Particle>;

and a struct of arrays:

struct World { x: Vec<f32>, y: Vec<f32>, z: Vec<f32>, mass: Vec<f32> }

If your loop reads every field of every particle, AoS wins: one cache line gives you a whole particle. If your loop only touches x — and physics kernels very often do — AoS drags three unused fields into cache for every element it wants, and SoA gives you a dense, vectorisable &[f32].

Without a crate, SoA means writing the parallel Vecs by hand, and you lose the ability to pass a single “particle” around as one value. That is a real ergonomic cost and it is why the AoS version is written first roughly always.

One more warning: #[repr(C)] disables the field reordering that keeps repr(Rust) structs small, so applying it to your particle can make the array bigger. repr(C) is for FFI and stable layout, not for speed.

Related lints

box_collection (a Box<Vec<T>> is a pointer to a pointer), redundant_allocation, manual_memcpy (an index loop copying one slice into another — use copy_from_slice or extend_from_slice), needless_range_loop, and large_stack_arrays (pedantic — a [f32; 1_000_000] local will blow the stack; that is what Vec is for).

Remember the grade is compile + tests + clippy -D warnings.