Structure of arrays and hot/cold splitting

Deep dive

How it works

In: n records of k fields · Out: k parallel arrays (plus an optional cold table) indexed by one id · State: one Vec per field, all the same length · Cost: a loop over j fields touches j·n·field_size bytes instead of n·record_size.

1. Split: one array per field. Record i is element i of every array; the index is the id, no per-record pointer.
2. Group by heat: fields read together stay together (a Hot { pos, vel } struct or separate arrays); rarely read fields go to a cold array with the same index.
3. AoSoA: tiles of N records (N = vector lanes, e.g. 8 f32 for 256-bit) hold each field as an N-wide mini-array, so one tile load fills one vector register.
4. Batch: one loop per operation over all records, not a method per record. The body touches few arrays, with no calls or per-record branches.
5. Delete: swap_remove(i) in every array moves the last record into slot i; arrays stay dense.
6. Stable references: the swap changes an index, so hold an id plus a generation counter mapped through an index table (Bevy Entity bumps a generation when an index is freed), not a raw index.
7. Padding: a struct is padded to its largest alignment; order fields largest-first or split them. Separate arrays have no padding between fields (documented in Zig MultiArrayList).

Code

Three layouts of the same 88 B record, one pos += vel * dt pass each, black_box on inputs, bit-exact comparison, then a swap-remove. Built with cargo build --release on aarch64-apple-darwin.

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

/// Array of structs: every field of an entity sits together.
#[derive(Clone, Copy)]
struct Entity {
    pos: [f32; 3], vel: [f32; 3],
    mass: f32, health: f32, flags: u32,
    id: u64, owner: u64, spawned: u64, name: [u8; 24],
}
/// Hot/cold split: fields the loop touches vs. fields it never touches.
#[derive(Clone, Copy)]
struct Hot { pos: [f32; 3], vel: [f32; 3] }
#[derive(Clone, Copy)]
#[allow(dead_code)]
struct Cold { mass: f32, health: f32, flags: u32, id: u64, owner: u64, spawned: u64, name: [u8; 24] }

/// Structure of arrays: one Vec per field; index i is the entity id.
struct Soa { px: Vec<f32>, py: Vec<f32>, pz: Vec<f32>, vx: Vec<f32>, vy: Vec<f32>, vz: Vec<f32> }

impl Soa {
    fn step(&mut self, dt: f32) {
        // Disjoint slices of equal length, so LLVM can drop bounds checks and vectorize.
        let n = self.px.len();
        let (px, py, pz) = (&mut self.px[..n], &mut self.py[..n], &mut self.pz[..n]);
        for i in 0..n { px[i] += self.vx[i] * dt; }
        for i in 0..n { py[i] += self.vy[i] * dt; }
        for i in 0..n { pz[i] += self.vz[i] * dt; }
    }
    /// Swap-remove keeps every column dense; the last entity takes the freed slot.
    fn swap_remove(&mut self, i: usize) {
        for c in [&mut self.px, &mut self.py, &mut self.pz, &mut self.vx, &mut self.vy, &mut self.vz] {
            c.swap_remove(i);
        }
    }
}

fn step_aos(v: &mut [Entity], dt: f32) {
    for e in v { for k in 0..3 { e.pos[k] += e.vel[k] * dt; } }
}
fn step_hot(v: &mut [Hot], dt: f32) {
    for e in v { for k in 0..3 { e.pos[k] += e.vel[k] * dt; } }
}

fn bench(name: &str, bytes: usize, mut f: impl FnMut()) {
    let mut t: Vec<f64> = (0..15).map(|_| { let s = Instant::now(); f(); s.elapsed().as_secs_f64() * 1e3 }).collect();
    t.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{name:8} min {:6.2} ms  median {:6.2} ms  stride {bytes} B", t[0], t[t.len() / 2]);
}

fn main() {
    const N: usize = 4_000_000;
    println!("size_of Entity {} B, Hot {} B, Cold {} B", size_of::<Entity>(), size_of::<Hot>(), size_of::<Cold>());
    let mut seed = 1u32;
    let mut rnd = move || { seed = seed.wrapping_mul(1664525).wrapping_add(1013904223); (seed >> 8) as f32 / 16777216.0 };
    let mut aos = Vec::with_capacity(N);
    for i in 0..N {
        aos.push(Entity { pos: [rnd(), rnd(), rnd()], vel: [rnd(), rnd(), rnd()], mass: 1.0, health: 100.0,
            flags: 0, id: i as u64, owner: 0, spawned: 0, name: [0; 24] });
    }
    let mut hot: Vec<Hot> = aos.iter().map(|e| Hot { pos: e.pos, vel: e.vel }).collect();
    let _cold: Vec<Cold> = aos.iter().map(|e| Cold { mass: e.mass, health: e.health, flags: e.flags,
        id: e.id, owner: e.owner, spawned: e.spawned, name: e.name }).collect();
    let col = |k: usize, f: fn(&Entity, usize) -> f32| aos.iter().map(|e| f(e, k)).collect::<Vec<f32>>();
    let mut soa = Soa { px: col(0, |e, k| e.pos[k]), py: col(1, |e, k| e.pos[k]), pz: col(2, |e, k| e.pos[k]),
        vx: col(0, |e, k| e.vel[k]), vy: col(1, |e, k| e.vel[k]), vz: col(2, |e, k| e.vel[k]) };

    bench("AoS", size_of::<Entity>(), || { step_aos(black_box(&mut aos), 0.01); });
    bench("hot/cold", size_of::<Hot>(), || { step_hot(black_box(&mut hot), 0.01); });
    bench("SoA", 4, || { soa.step(black_box(0.01)); black_box(&soa); });

    // All three ran 15 steps from the same start: results must match bit for bit.
    for i in (0..N).step_by(997) {
        assert_eq!(aos[i].pos, hot[i].pos);
        assert_eq!(aos[i].pos, [soa.px[i], soa.py[i], soa.pz[i]]);
    }
    let last = soa.px.len() - 1;
    let id = aos[last].id;
    soa.swap_remove(3);
    assert_eq!(soa.px.len(), N - 1);
    assert_eq!(soa.px[3], aos[last].pos[0]); // entity `id` moved from the end to slot 3
    println!("ok, moved id {id} to slot 3");
}

Output (measured on this Mac, Apple M4 Pro): size_of Entity 88 B, Hot 24 B, Cold 64 B.

Complexity and constants

• Bytes traversed per pass over 4M records (derived): AoS 352 MB read, and every line is dirtied since each holds pos; hot/cold 96 MB; SoA 96 MB read plus 48 MB written.
• Measured on this Mac (Apple M4 Pro), minimum of 15 passes over 3 process runs: AoS 5.04-5.40 ms, hot/cold 2.08-2.16 ms, SoA 1.00-1.11 ms; AoS/SoA about 5× and hot/cold/SoA about 2× (derived).
• The time ratios differ from the byte ratios. Whether store traffic, write-backs or vectorization explains the gap was not profiled here.
• Loops using most of a record see no gain: SoA only adds streams.

Efficiency

• Cost: per record update, 1.3 ns in AoS, 0.52 ns hot/cold, 0.25 ns SoA (derived from the minima above; measured on this Mac, Apple M4 Pro, N = 4M, far beyond cache size). Memory per record is the sum of field sizes. Bound: memory traffic (roofline); not profiled here.
• Levers:
  • SoA for the fields a loop names — 5.0 → 1.0 ms here (measured on this Mac) — wide records, few fields per loop
  • hot/cold split — 5.0 → 2.1 ms here (measured on this Mac) — fields differ sharply in use; keeps the record API
  • pad arrays to a vector multiple: Arrow recommends 64 B padding, which "allows for using SIMD" (Arrow spec) — SIMD kernels
  • reorder fields or use SoA to drop padding — memory savings per Zig MultiArrayList docs, size not stated — mixed-size structs
  • coalesced GPU loads: thread k reads word k of an aligned array (CUDA guide) — GPU kernels
• Naive → standard → state of the art:
  • AoS, all fields in one struct · 5.0 ms per 4M updates
  • hot/cold struct split · 2.1 ms
  • SoA, one pass per array · 1.0 ms (AoSoA tiles: not measured here)

Implementation notes

• Reslice all arrays to one length n before the loop so LLVM can prove the bounds. Vectorization was not checked in the asm here.
• Keep ids dense; most designs add a sparse id-to-index table and a generation array, updated on every swap-remove.
• One buffer sliced by field (Zig MultiArrayList computes field pointers into one block) means one allocation; see arena allocators.
• Split work across threads on cache-line boundaries to avoid false sharing.
• Fields always read together (x, y, z) can stay grouped; the question is what one loop reads together.

Pitfalls

• A loop over many SoA arrays at once creates many streams; group fields that are read together.
• Swap-remove during iteration moves the unvisited last record into the visited slot; iterate backwards or defer removals.
• Stored indices dangle after a swap-remove; use generational ids.
• Sorting by one key must permute every array.
• A benchmark whose data fits in L1 hides the effect.

Variants and alternatives

In production

• Games: entity component systems; Bevy tables are "columnar contiguous blocks of memory, optimized for fast iteration"; Unity Entities groups entities by component set into archetypes.
• Databases and analytics: Apache Arrow's columnar format; DuckDB executes on fixed-size vectors (default 2048 values).
• GPU code: coalesced access to arrays of one field.
• Compilers and systems languages: Zig's MultiArrayList for lists of structs and tagged unions.
• Machine learning: tensors are contiguous arrays with strides, not arrays of records.

Implementations

Sources

• Mike Acton, Data-Oriented Design and C++, CppCon 2014. talk
• Richard Fabian, Data-Oriented Design (online book). book
• Apache Arrow, Columnar Format. spec
• Bevy, bevy_ecs::storage. source
• Zig, std.MultiArrayList. source
• NVIDIA, CUDA C++ Best Practices Guide. guide
• DuckDB, Execution Format. docs
• Unity, Archetypes concepts (Entities 1.3). docs