Cache-barát adatszerkezetek: Struct of Arrays vs Array of Structs

A Rust ownership rendszere és a zero-cost abstraction filozófiája miatt sokan elfelejtik, hogy a nyelv adta biztonság mellett a memória-elrendezés még mindig rajtunk, fejlesztőkön áll. Ma egy olyan optimalizációról beszélünk, ami nem a compiler trükkjeiről szól, hanem arról, hogyan gondolkodunk az adatainkról.

A CPU cache röviden

A modern CPU-k nem közvetlenül a RAM-ból olvasnak minden adatot – ez túl lassú lenne. Helyette több szintű cache-t használnak (L1, L2, L3), amik egyre nagyobbak, de egyre lassabbak. Amikor a processzor egy memóriacímet kér, nem csak azt az egy byte-ot tölti be, hanem egy teljes cache line-t, ami tipikusan 64 byte.

Ez azt jelenti, hogy ha a memóriában szomszédos adatokat olvasunk sorban (szekvenciális hozzáférés), a cache line-ok jól kihasználtak lesznek. Ha viszont ugrálunk a memóriában, minden hozzáférés potenciálisan egy új cache line betöltését igényli – ez a cache miss, ami akár 100-200 ciklust is elvehet, szemben az L1 cache 1-4 ciklusos elérési idejével.

Array of Structs (AoS)

Az Array of Structs a "természetes" gondolkodásmód: minden entitáshoz tartozó adatot egy struct-ba pakolunk, és ezekből a struct-okból csinálunk egy tömböt vagy Vec-et.

#[derive(Clone, Copy)]
struct ParticleAoS {
    x: f32,
    y: f32,
    z: f32,
    vx: f32,
    vy: f32,
    vz: f32,
    mass: f32,
}

fn update_aos(particles: &mut [ParticleAoS], dt: f32) {
    for p in particles.iter_mut() {
        p.x += p.vx * dt;
        p.y += p.vy * dt;
        p.z += p.vz * dt;
    }
}

Ez teljesen olvasható, idiomatikus Rust kód, és a legtöbb esetben pont ezt írnánk le először. A probléma akkor jelentkezik, ha csak bizonyos mezőket használunk gyakran. A mass mező itt csak elfoglalja a helyet a cache line-ban, miközben az update_aos függvény egyáltalán nem olvassa – vagyis feleslegesen "szennyezi" a betöltött cache line-t.

Struct of Arrays (SoA)

A SoA elrendezésnél megfordítjuk a logikát: minden mezőhöz külön tömböt tartunk, és az entitás "létezik" implicit módon, az index alapján.

struct ParticlesSoA {
    x: Vec<f32>,
    y: Vec<f32>,
    z: Vec<f32>,
    vx: Vec<f32>,
    vy: Vec<f32>,
    vz: Vec<f32>,
    mass: Vec<f32>,
}

impl ParticlesSoA {
    fn update(&mut self, dt: f32) {
        let n = self.x.len();
        for i in 0..n {
            self.x[i] += self.vx[i] * dt;
            self.y[i] += self.vy[i] * dt;
            self.z[i] += self.vz[i] * dt;
        }
    }
}

Itt az update függvény csak azokat a tömböket érinti, amikre valóban szükség van (x, y, z, vx, vy, vz), a mass tömb pedig egyáltalán nem kerül a cache-be feleslegesen. Ráadásul mivel minden tömb homogén f32 adatot tartalmaz, a compiler sokkal könnyebben tudja auto-vektorizálni a ciklust SIMD utasításokra.

Benchmark Criterionnal

A legjobb módja annak, hogy megbizonyosodjunk az elmélet helyességéről, egy valódi benchmark. Használjuk a criterion crate-et, amit a Cargo.toml-ban dev-dependency-ként adunk hozzá:

[dev-dependencies]
criterion = "0.5"

[[bench]]
name = "soa_vs_aos"
harness = false

A benchmark kód:

use criterion::{black_box, criterion_group, criterion_main, Criterion};

fn bench_aos(c: &mut Criterion) {
    let mut particles: Vec<ParticleAoS> = (0..100_000)
        .map(|i| ParticleAoS {
            x: i as f32,
            y: 0.0,
            z: 0.0,
            vx: 1.0,
            vy: 0.5,
            vz: 0.2,
            mass: 1.0,
        })
        .collect();

    c.bench_function("update_aos", |b| {
        b.iter(|| update_aos(black_box(&mut particles), 0.016))
    });
}

fn bench_soa(c: &mut Criterion) {
    let n = 100_000;
    let mut soa = ParticlesSoA {
        x: (0..n).map(|i| i as f32).collect(),
        y: vec![0.0; n],
        z: vec![0.0; n],
        vx: vec![1.0; n],
        vy: vec![0.5; n],
        vz: vec![0.2; n],
        mass: vec![1.0; n],
    };

    c.bench_function("update_soa", |b| {
        b.iter(|| soa.update(black_box(0.016)))
    });
}

criterion_group!(benches, bench_aos, bench_soa);
criterion_main!(benches);

A saját gépemen (egy tipikus 2023-as x86-64 laptop, AVX2 támogatással) az cargo bench futtatása után ehhez hasonló eredményeket kaptam 100 000 részecskére:

update_aos    time:   [412.34 µs 415.12 µs 418.03 µs]
update_soa    time:   [178.21 µs 179.55 µs 181.02 µs]

Ez körülbelül 2,3x-os gyorsulás a SoA elrendezés javára, tisztán a cache-hatékonyabb hozzáférés miatt – anélkül, hogy egyetlen sor unsafe kódot írtunk volna, vagy explicit SIMD intrinsic-eket használtunk volna.

Mikor éri meg SoA-ra váltani

A SoA nem ezüstgolyó. Van néhány konkrét helyzet, amikor egyértelműen megéri:

• Nagy adatmennyiség, kevés mező hozzáférés: ha egy hatalmas kollekcióban minden elemből csak 1-2 mezőt olvasol egy hot loop-ban (mint a fenti fizikai szimulációban), a SoA drasztikusan csökkenti a felesleges cache line betöltéseket.
• SIMD/vektorizáció: a homogén tömbök könnyebben auto-vektorizálhatók, és ha explicit SIMD-et (pl. std::simd, ami még nightly-only ezen a napon) tervezel később bevezetni, a SoA elrendezés eleve kompatibilis vele.
• Batch feldolgozás: ECS (Entity Component System) architektúrákban, ahol rendszeresen csak bizonyos komponenseket iterálsz végig sok entitáson keresztül, a SoA természetesen illik a mintázatba.

Ugyanakkor van, amikor az AoS marad a jobb választás:

• Random access egyedi entitásokra: ha gyakran kell egy adott "objektum" összes mezőjét egyszerre olvasnod/írnod (pl. egy játékbeli szereplő teljes állapotát), az AoS egyetlen cache line-ba tömöríti ezt, míg a SoA 7 különböző memóriaterületet érintene.
• Kód olvashatósága és karbantarthatósága: a SoA gyakran bonyolítja az API-t, mert elveszik az "egy dolog = egy struct" intuíció. Kisebb projekteknél ez felesleges komplexitás.
• Kis adatmennyiség: ha csak néhány száz elemed van, a cache-hatás elhanyagolható, és a mikrooptimalizáció nem éri meg a kódminőség árát.

Összefoglalás

A Struct of Arrays vs Array of Structs döntés klasszikus példája annak, hogy a Rust type system biztonsága mellett a teljesítmény optimalizálása gyakran a memória-elrendezésen áll vagy bukik. A Vec<T> és a struct-ok kombinálása nem az egyetlen út – ha a hot path-eid csak bizonyos mezőket érintenek nagy mennyiségben, a SoA komoly, mérhető gyorsulást adhat, ráadásul unsafe kód nélkül, tisztán idiomatikus Rust-tal.

A lényeg: ne találgass, mérj. A Criterion pontosan ehhez lett kitalálva – pár perc alatt beállítható, és statisztikailag megbízható eredményeket ad, amikkel eldönthető, hogy egy adott adatszerkezet-váltás valóban megéri-e a plusz komplexitást a te konkrét projektedben.