Cache, layout and false sharing

A modern processor does not read a byte from memory; it reads a line of sixty-four bytes into a cache and works from there. The cost of the first read of a line is a hundred times the cost of a value already in the cache, so the arrangement of the data matters as much as the algorithm: a loop that touches every byte of a line is fast, and a loop that uses one byte out of each line waits for memory.

This lesson arranges the same data two ways, measures the padding the compiler inserts, shows two threads fighting over one cache line, walks a matrix in both directions, and ends with the panic that a struct of arrays returns when one array is shorter than the other.

Arrays of structs and structs of arrays

A Vec<Point> stores a point per element, so a loop that reads only x drags every y through the cache with it. Two vectors, one of x and one of y, store the same numbers and let the loop over x read only what it uses.

The program builds both shapes from the same thousand points and sums x in each. The comparison at the end is true, because the two layouts hold the same numbers in a different order.

#[derive(Clone, Copy)] struct Point { x: f64, y: f64, } fn sum_aos(points: &[Point]) -> f64 { let mut total = 0.0; for point in points { total += point.x; } total } fn sum_soa(xs: &[f64]) -> f64 { xs.iter().sum() } fn main() { let points: Vec<Point> = (0..1000).map(|i| Point { x: i as f64, y: 0.5 }).collect(); let xs: Vec<f64> = points.iter().map(|p| p.x).collect(); let ys: Vec<f64> = points.iter().map(|p| p.y).collect(); let aos_total = sum_aos(&points); println!("{} {} {}", aos_total, sum_soa(&xs), ys.iter().sum::<f64>() == 500.0); }

rustc --edition 2024 aos.rs
./aos

499500 499500 true

The two sums are the same number, and the third field says that a thousand half-values add up to five hundred, which proves that y was read from somewhere. The arrays-of-structs form reads sixteen bytes per point and uses eight of them; the struct-of-arrays form reads eight bytes and uses all of it. On a large vector that is the difference between one memory read per point and two.

The lesson on structs covers the type itself. The rule of thumb is to pick the layout of the loop that runs most: a program that prints a point wants the fields together, and a program that sums one field wants them apart.

The padding between the fields

size_of reports the bytes a value occupies, and that number includes the gaps the compiler inserts so that each field starts at an address that is a multiple of its alignment. A u64 wants eight bytes of alignment, so a u8 before it leaves seven bytes unused.

A plain Rust struct is free to reorder its fields, and it puts the wide ones first to waste less. The same fields with #[repr(C)] keep the order they were written in, which is what a C header expects and what costs the padding back.

use std::mem::size_of; #[allow(dead_code)] struct Loose { a: u8, b: u64, c: u8, } #[allow(dead_code)] #[repr(C)] struct CLoose { a: u8, b: u64, c: u8, } #[derive(Clone, Copy)] struct Point { x: f64, y: f64, } fn main() { println!("{} {} {}", size_of::<Point>(), size_of::<Loose>(), size_of::<CLoose>()); println!("{} {}", size_of::<[Point; 3]>(), size_of::<Vec<Point>>()); }

rustc --edition 2024 layout.rs
./layout

16 16 24
48 24

Sixteen for the plain struct and twenty-four for the C one: the compiler moved the u64 to the front, so the two bytes of the small fields fit inside the tail padding, and the C layout had to keep the order and pay eight bytes of gap. The last line says that an array of three points is its element size times three, while a Vec is three words whatever it holds: a pointer, a capacity and a length, because its points live on the heap.

The lesson on memory layout adds align_of, repr(transparent) and the offsets inside a struct. The number to remember is that size_of is not the sum of the fields, so a buffer sized as count * size_of::<Field>() is right while a buffer sized as the sum of the field sizes is not.

Two counters on one cache line

Two atomic counters in one struct sit in the same cache line, and two threads that write them fight over that line: every increment of one invalidates the copy the other thread holds. The counters are unrelated and the arithmetic is right, but the hardware moves the line between two cores on every write. The effect has a name, false sharing, and the fix is to put each counter in a line of its own.

#[repr(align(64))] on a wrapper makes every wrapper start at a multiple of sixty-four bytes, so two wrappers cannot share a line. The program times five million increments in each shape with two threads.

use std::sync::atomic::{AtomicUsize, Ordering}; use std::thread; use std::time::Instant; struct Packed { left: AtomicUsize, right: AtomicUsize, } #[repr(align(64))] struct Padded(AtomicUsize); struct Apart { left: Padded, right: Padded, } const ROUNDS: usize = 5_000_000; fn main() { let packed = Packed { left: AtomicUsize::new(0), right: AtomicUsize::new(0) }; let start = Instant::now(); thread::scope(|scope| { scope.spawn(|| for _ in 0..ROUNDS { packed.left.fetch_add(1, Ordering::Relaxed); }); scope.spawn(|| for _ in 0..ROUNDS { packed.right.fetch_add(1, Ordering::Relaxed); }); }); let packed_ms = start.elapsed().as_millis(); let apart = Apart { left: Padded(AtomicUsize::new(0)), right: Padded(AtomicUsize::new(0)) }; let start = Instant::now(); thread::scope(|scope| { scope.spawn(|| for _ in 0..ROUNDS { apart.left.0.fetch_add(1, Ordering::Relaxed); }); scope.spawn(|| for _ in 0..ROUNDS { apart.right.0.fetch_add(1, Ordering::Relaxed); }); }); let apart_ms = start.elapsed().as_millis(); println!("packed {} ms, apart {} ms", packed_ms, apart_ms); println!("{} {}", packed.left.load(Ordering::Relaxed), apart.right.0.load(Ordering::Relaxed)); }

rustc --edition 2024 -O sharing.rs
./sharing

packed 253 ms, apart 50 ms
5000000 5000000

The same number of increments took five times as long when the two counters shared a line, and the second line shows that both reached five million, so the work was identical. The exact milliseconds change with the machine and with the number of cores that take part; the direction does not. A run with -O is the one to compare, because a debug build spends its time elsewhere.

The lesson on scoped threads explains the thread::scope that lets both closures borrow the struct without an Arc. Padding is the cheap fix here, and a counter that only one thread writes needs no atomic at all: the allocator lesson uses a padded counter for the same reason.

The order of the loop

A matrix stored row by row is a vector of rows. Walking it row by row reads memory from the start to the end, one cache line after another, and the hardware prefetcher guesses the next line before the loop asks for it. Walking the same matrix column by column jumps a thousand elements at a time and every read misses.

The program fills a thousand by a thousand grid and sums it both ways. Both sums are the same, and the comparison of the two durations shows which loop the cache likes.

use std::time::Instant; const N: usize = 1000; fn main() { let mut grid = vec![0u64; N * N]; for i in 0..N { for j in 0..N { grid[i * N + j] = (i + j) as u64; } } let start = Instant::now(); let mut rows = 0u64; for i in 0..N { for j in 0..N { rows += grid[i * N + j]; } } let row_time = start.elapsed(); let start = Instant::now(); let mut cols = 0u64; for j in 0..N { for i in 0..N { cols += grid[i * N + j]; } } let col_time = start.elapsed(); println!("{} {} {}", rows == cols, row_time < col_time, cols / 1_000_000); }

rustc --edition 2024 order.rs
./order

true true 999

Both loops add the same nine hundred and ninety-nine million, which is the average of the grid times its size, and the row loop finished first. The grid is eight megabytes, far larger than the cache, so the column loop reads a new line for every element while the row loop uses all eight numbers of each line. The fix for a program that must walk by columns is a blocked loop or a transposed copy, not a faster processor.

The same reasoning applies to a Vec<Vec<u64>>, which stores every row on the heap behind a pointer and costs one more indirection per access. A flat vector with an index computed by hand is the layout a numeric kernel wants.

The second array is shorter

A struct of arrays has no type that keeps the arrays the same length. The compiler checks the type of each vector, not its number of elements, and an index that is valid for one array may be out of range for the other. The program below walks by the length of the first array and reaches one element past the end of the second.

fn main() { let xs = vec![1, 2, 3]; let ys = vec![10, 20]; let mut total = 0; for i in 0..xs.len() { total += xs[i] + ys[i]; } println!("{total}"); }

rustc --edition 2024 bounds.rs
./bounds

thread 'main' (1344) panicked at bounds.rs:6:28:
index out of bounds: the len is 2 but the index is 2
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

The panic is the checked index paying for itself: there is no way to read the third element of a vector of two, and the message names both numbers. The process id changes on every run. The fix is ys.get(i).copied().unwrap_or(0), which makes the missing value explicit, or a zip over the two arrays, which stops at the shorter one: xs.iter().zip(&ys).map(|(x, y)| x + y).sum::<i32>().

The lesson on vectors covers get and the checked accessors. The next lesson moves work of this kind out of run time altogether: a function the compiler calls while it builds the program.

Exercises

1. Turn the point vector into a struct of arrays and time the sum of x in both shapes.
2. Print size_of of a struct with a bool, an u32 and an u8, then add repr(C) and print it again.
3. Run the false-sharing program with one thread and with four, and explain the two numbers.

The code on this page was built with rustc 1.96.1 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev