140. Struct of arrays in Rust by hand

The same particles, a new language

In chapter 103 Viscosity turned const ps = [] into a generated class whose fields were columns:

this.x = new Float64Array(cap);
this.vx = new Float64Array(cap);

No compiler will do that for you in Rust. But Rust lets you write the columns yourself, in about twenty lines, and the type system makes the result pleasant to use. First, though, look at what you start from.

Vec<Particle> is already flat

#[derive(Clone, Copy)]
struct Particle {
    x: f64, y: f64,
    vx: f64, vy: f64,
    mass: f64, health: f64,
}
let ps: Vec<Particle> = ...;

Chapter 139 measured a Particle at 48 bytes, no padding. A Vec<Particle> keeps them back to back in one buffer: no object headers, no pointer per element, no boxed numbers. That is much closer to Part II’s “packed Float64Array” layout than to a JavaScript array of objects (chapter 22). So in Rust the array of structs starts out good. What it still wastes is the fields a loop doesn’t touch:

Columns by hand

struct Particles {
    x: Vec<f64>,
    y: Vec<f64>,
    vx: Vec<f64>,
    vy: Vec<f64>,
    mass: Vec<f64>,
    health: Vec<f64>,
}

impl Particles {
    fn step(&mut self, dt: f64) {
        for i in 0..self.x.len() {
            self.x[i] += self.vx[i] * dt;
            self.y[i] += self.vy[i] * dt;
        }
    }
}

Particle i is index i of every column. The loop is the same update-xy loop as Part II’s benchmark, and it reads four columns and never touches mass or health.

What Rust checks, and what it doesn’t

Two things work in your favour. self.x[i] += self.vx[i] * dt borrows self.x mutably and self.vx for reading in the same statement, and that’s fine: they are different fields, so the borrow checker sees two separate borrows. (Two elements of the same Vec would conflict, as chapter 138 showed.) And if the fields are private to their module (chapter 135), nobody outside can push to just one column.

One thing doesn’t. Nothing checks that push writes every column. Forget self.vx.push(p.vx) and it compiles; the first get of the last particle panics with an index out of bounds. In Part VII, Viscosity generated push and proved every access was rewritten. Here, tests do that job.

Getting a particle back is materialization (chapter 106): get(i) builds a Particle from the columns and returns it by value. There is no Particle in memory to hand out a &Particle to, and changing the copy changes nothing in the columns.

Measuring it

Here is the update-xy comparison as a program you can run:

use std::hint::black_box;
use std::time::Instant;

const DT: f64 = 0.016;
const N: usize = 1_000_000;

#[derive(Clone, Copy)]
struct Particle {
    x: f64,
    y: f64,
    vx: f64,
    vy: f64,
    mass: f64,
    health: f64,
}

struct Particles {
    x: Vec<f64>,
    y: Vec<f64>,
    vx: Vec<f64>,
    vy: Vec<f64>,
    mass: Vec<f64>,
    health: Vec<f64>,
}

fn step_aos(ps: &mut [Particle]) {
    for p in ps.iter_mut() {
        p.x += p.vx * DT;
        p.y += p.vy * DT;
    }
}

fn step_soa(s: &mut Particles) {
    for i in 0..s.x.len() {
        s.x[i] += s.vx[i] * DT;
        s.y[i] += s.vy[i] * DT;
    }
}

// Median ns per particle of 11 runs.
fn time(mut f: impl FnMut()) -> f64 {
    let mut ts = Vec::new();
    for _ in 0..11 {
        let t = Instant::now();
        f();
        let ns = t.elapsed().as_nanos();
        ts.push(ns as f64 / N as f64);
    }
    ts.sort_by(|a, b| a.total_cmp(b));
    ts[5]
}

fn main() {
    let p = Particle {
        x: 0.0, y: 0.0, vx: 1.0,
        vy: 0.5, mass: 1.0, health: 1.0,
    };
    let mut aos = vec![p; N];
    let col = |v: f64| vec![v; N];
    let mut soa = Particles {
        x: col(0.0), y: col(0.0),
        vx: col(1.0), vy: col(0.5),
        mass: col(1.0),
        health: col(1.0),
    };
    let a = time(|| {
        step_aos(black_box(&mut aos))
    });
    let s = time(|| {
        step_soa(black_box(&mut soa))
    });
    println!("aos {a:.2} ns/particle");
    println!("soa {s:.2} ns/particle");
    println!("same: {}",
        aos[7].x == soa.x[7]);
}

Read the result with suspicion. In the page it runs on the Rust Playground as a debug build, unoptimized. On this machine the debug build made SoA several times slower (about 6× in three runs: roughly 18 ns per particle against 3), because every s.x[i] paid for an unoptimized bounds check. Built with -C opt-level=3, the same program flipped to about 1.2 ns for SoA against 1.9 for AoS. Layout comparisons only mean something with cargo build --release (chapter 121).

The other ingredient is std::hint::black_box. The optimizer is free to delete work whose result nobody uses (chapter 24), or to precompute it from data it can see. black_box(&mut aos) hides the data from it, so the loop really runs each time. The standard library calls it a best-effort hint that can generally be relied on for benchmarking^[2]; chapter 142 covers it properly.

The numbers below come from a fuller version of this harness: a release build (opt-level 3) timing three loops, each warmed up and then run in 31 samples of about 20 million particle updates, keeping the median. The whole run was repeated three times on the same kind of shared cloud VM as the book’s Node benchmarks, so expect noise. Ranges are across the three runs, in nanoseconds per particle:

                       AoS      SoA
n = 1,000
  update-xy            0.3–0.4  0.3
  sum-one-field        0.6      0.6
  read-all             0.9–1.1  0.9–1.0
n = 1,000,000
  update-xy            2.2–2.3  1.2–1.3
  sum-one-field        1.9–2.0  0.7–0.8
  read-all             2.3–2.5  1.6–1.7

With a thousand particles (48 KB) there was no difference at all: the data stays in cache, so wasted bytes cost nothing. With a million, SoA was roughly 1.8× faster for update-xy and 2.4–2.9× for summing one field. It also came out ahead when reading all six fields, which this chapter can’t fully explain; don’t lean on that row. Now compare the same loop in JavaScript, from this book’s Node run:

Rust’s AoS was already in the neighbourhood of JavaScript’s SoA. Most of what Viscosity wins in JavaScript is getting away from objects, and a Rust struct was never an object in that sense. What remains, in both languages, is not fetching fields you don’t use.

Your turn

#[derive(Clone, Copy, Debug, PartialEq)]
struct Particle {
    x: f64,
    vx: f64,
}

// One Vec per field. Invariant:
// x and vx have the same length.
struct Particles {
    x: Vec<f64>,
    vx: Vec<f64>,
}

impl Particles {
    fn new() -> Self {
        Particles {
            x: Vec::new(),
            vx: Vec::new(),
        }
    }

    fn push(&mut self, p: Particle) {
        todo!()
    }

    fn len(&self) -> usize {
        todo!()
    }

    // x += vx * dt, for every particle.
    fn step(&mut self, dt: f64) {
        todo!()
    }

    // Rebuild particle i: a copy.
    fn get(&self, i: usize)
        -> Particle {
        todo!()
    }
}

#[derive(Clone, Copy, Debug, PartialEq)]
struct Particle {
    x: f64,
    vx: f64,
}

struct Particles {
    x: Vec<f64>,
    vx: Vec<f64>,
}

fn from_aos(ps: &[Particle])
    -> Particles {
    todo!()
}

fn to_aos(s: &Particles)
    -> Vec<Particle> {
    todo!()
}

What you learned

• A Vec<Particle> is already flat: structs back to back, with no headers or pointers. Its only waste is the fields a loop skips.
• A Rust struct of arrays has one Vec<f64> per field. Keep the columns the same length, and keep the fields private.
• Borrowing two different columns at once is fine; get returns a rebuilt copy, not a reference.
• Time layouts only in release builds, with black_box around the data. In this chapter’s runs SoA was about 1.8–2.9× faster at a million particles, and no faster at a thousand.
• A hand-written Vec<f64> column is the Rust form of the Float64Array columns Viscosity generates.