Branch Prediction and Cache Friendly Code in Rust Explained

Two programs with the same algorithm and the same instruction count can differ many times over in speed because of how they use memory. The CPU is far faster than main memory, so it wins by predicting what you will read next. Everything here applies to Rust 1.90; the principles are about hardware and the effects should be measured on your machine, not taken from this post.

Memory is slow and caches are small

A read that hits the L1 cache takes a few cycles; one that goes to main memory takes a few hundred. The CPU loads memory in cache lines (64 bytes on common x86 and Arm parts), and a hardware prefetcher guesses the next lines when you walk memory in order. Code that does that, runs from cache. Code that jumps around, waits.

Contiguous beats pointer chasing

use std::collections::LinkedList;

fn sum_vec(v: &[u64]) -> u64 {
    v.iter().sum()
}

fn sum_list(l: &LinkedList<u64>) -> u64 {
    l.iter().sum()
}

fn sum_boxes(v: &[Box<u64>]) -> u64 {
    v.iter().map(|b| **b).sum()
}

sum_vec reads sequential memory. sum_list follows pointers to nodes allocated at different times, and sum_boxes follows one pointer per element. For large inputs the first is typically several times faster, and it can also be vectorized by the compiler. The standard library documentation itself recommends Vec or VecDeque over LinkedList for nearly all uses.

Flatten nested vectors

struct Grid {
    width: usize,
    cells: Vec<f32>,
}

impl Grid {
    fn new(width: usize, height: usize) -> Self {
        Grid { width, cells: vec![0.0; width * height] }
    }
    fn at(&self, x: usize, y: usize) -> f32 {
        self.cells[y * self.width + x]
    }
    fn set(&mut self, x: usize, y: usize, v: f32) {
        self.cells[y * self.width + x] = v;
    }
}

One allocation and rows next to each other, against one allocation per row for Vec<Vec<f32>>. Iterate in the order the data is laid out (row by row here); iterating down columns strides across lines and wastes most of each load.

Struct of arrays

struct ParticlesAos {
    items: Vec<Particle>,
}

struct Particle {
    x: f32,
    y: f32,
    mass: f32,
    name: [u8; 32],
}

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

fn total_mass(p: &ParticlesSoa) -> f32 {
    p.mass.iter().sum()
}

If a loop reads only mass, the array of structs pulls in x, y and the 32 byte name along with it, wasting most of every cache line. The struct of arrays loads only masses. It is more code to maintain and worth it only for hot loops over large collections (game entity systems and numeric kernels use it widely, see data oriented design).

Branch prediction

A conditional branch is fast when the CPU guesses it right and costs a pipeline flush when it guesses wrong. Random data makes the guess wrong about half the time:

fn count_big(v: &[u32]) -> usize {
    v.iter().filter(|&&x| x >= 128).count()
}

Run on random values it is slower than on the same values sorted, because the sorted version has one long run of "no" and then one long run of "yes". The compiler often turns such a loop into branchless code (conditional moves or vector instructions), which removes the effect, so the only way to know is to benchmark both (benchmark tools). Writing arithmetic instead of branches (count += (x >= 128) as usize) is a hand-made branchless form.

What to do with this

1. Choose Vec and slices by default. 2. Flatten nested collections that are traversed often. 3. Split hot and cold fields when a profile shows cache misses. 4. Leave branch tricks until a profile points at a data dependent branch. 5. Use hardware counters (perf stat -e cache-misses,branch-misses) to confirm.

Related costs are in bounds checks and reducing allocations.