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

Ha valaha optimalizáltál már forró ciklust, biztos találkoztál a jelenséggel: az algoritmus papíron ugyanaz, mégis kétszer-háromszor lassabb, mint elvárnád. A bűnös legtöbbször nem a CPU, hanem a memóriaelrendezés. Nézzük végig, hogyan gondolkodjunk erről Rustban.

A CPU cache-sorok és a memóriaelrendezés alapjai

A mai CPU-k nem egyesével olvasnak be byte-okat a RAM-ból, hanem cache-sorokban (cache line), amik jellemzően 64 bájtosak. Amikor egy adatra szükség van, a CPU betölti az egész sort tartalmazó blokkot az L1 cache-be. Ha a program úgy van megírva, hogy egymás után következő memóriacímeket olvas, akkor egy cache-sor betöltésével több adatot is "ingyen" megkapunk. Ezt hívjuk jó lokalitásnak (spatial locality).

Ha viszont az adataink szétszórva vannak a memóriában, minden egyes elem eléréséhez új cache-sort kell betölteni, ami több tíz vagy száz ciklusnyi késleltetést jelenthet. Ez a cache miss büntetése.

A klasszikus Array of Structs minta és hátrányai

A legtermészetesebb megközelítés, amikor egy entitást leíró struktúrát hozunk létre, és ezekből tömböt (vagy Vec-et) építünk:

struct Particle {
    position: [f32; 3],
    velocity: [f32; 3],
    mass: f32,
    active: bool,
}

fn update_positions_aos(particles: &mut [Particle], dt: f32) {
    for p in particles.iter_mut() {
        if p.active {
            p.position[0] += p.velocity[0] * dt;
            p.position[1] += p.velocity[1] * dt;
            p.position[2] += p.velocity[2] * dt;
        }
    }
}

Ez az Array of Structs (AoS) minta: egy Vec<Particle>-ben minden elem egymás után helyezkedik el a memóriában, de minden elem tartalmazza az összes mezőt is, amit épp nem használunk. A fenti ciklusban csak a position, velocity és active mezőkre van szükség, a mass mégis minden egyes elemnél betöltődik a cache-be, feleslegesen foglalva helyet.

Ha a Particle struct mondjuk 32 bájt, és egy cache-sorba 2 fér el, akkor egy 64 bájtos cache-sor betöltésekor csak a fele adat lesz hasznos a mi konkrét számításunkhoz. Minél több mezőt tartalmaz a struct, és minél kevesebbet használunk belőle egy adott ciklusban, annál rosszabb az arány.

Struct of Arrays átalakítás lépésről lépésre

A Struct of Arrays (SoA) minta lényege, hogy nem entitásonként, hanem mezőnként tároljuk az adatokat: minden mezőhöz külön tömb tartozik.

struct ParticlesSoA {
    position_x: Vec<f32>,
    position_y: Vec<f32>,
    position_z: Vec<f32>,
    velocity_x: Vec<f32>,
    velocity_y: Vec<f32>,
    velocity_z: Vec<f32>,
    mass: Vec<f32>,
    active: Vec<bool>,
}

impl ParticlesSoA {
    fn update_positions(&mut self, dt: f32) {
        let len = self.active.len();
        for i in 0..len {
            if self.active[i] {
                self.position_x[i] += self.velocity_x[i] * dt;
                self.position_y[i] += self.velocity_y[i] * dt;
                self.position_z[i] += self.velocity_z[i] * dt;
            }
        }
    }
}

Itt a position_x, position_y, position_z és velocity_x/y/z tömbök mindegyike homogén f32 adatokat tartalmaz, egymás után a memóriában. Amikor a CPU betölt egy cache-sort a position_x-ből, abban 16 darab f32 érték fér el (64 / 4 bájt), és mindegyikre szükség lesz a ciklusban. Ez sokkal jobb kihasználtság, mint az AoS esetben.

Emellett a SoA elrendezés lehetővé teszi, hogy a fordító (vagy kézzel írt SIMD kód) hatékonyabban vektorizálja a ciklust, mert az adatok egyenletes stride-dal, azonos típusúan következnek egymás után.

Fontos, hogy a active: Vec<bool> helyett gyakran érdemesebb bitmaszkot használni (Vec<u64> bitenkénti flag-ekkel), mert egy bool Rustban 1 bájtot foglal, de egy u64-ben 64 aktivitási flag fér el egyetlen cache-sorban. Ez egy további finomítási lépés, amit érdemes megfontolni, ha az active mező szűrése kritikus útvonalon van.

Valós mérés Criterion-nal: mekkora a különbség?

Elmélet helyett nézzünk számokat. A criterion crate a de facto standard benchmarkoláshoz Rustban, statisztikailag megbízható méréseket ad, és szép HTML riportot generál.

Először a Cargo.toml-ban:

[dev-dependencies]
criterion = "0.5"

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

A benchmark fájl (benches/particles.rs):

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

fn bench_aos(c: &mut Criterion) {
    let mut particles: Vec<Particle> = (0..100_000)
        .map(|i| Particle {
            position: [0.0; 3],
            velocity: [1.0, 2.0, 3.0],
            mass: 1.0,
            active: i % 2 == 0,
        })
        .collect();

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

fn bench_soa(c: &mut Criterion) {
    let n = 100_000;
    let mut soa = ParticlesSoA {
        position_x: vec![0.0; n],
        position_y: vec![0.0; n],
        position_z: vec![0.0; n],
        velocity_x: vec![1.0; n],
        velocity_y: vec![2.0; n],
        velocity_z: vec![3.0; n],
        mass: vec![1.0; n],
        active: (0..n).map(|i| i % 2 == 0).collect(),
    };

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

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

Saját gépemen (egy néhány éves x86-64 laptop, cargo bench release módban futtatva) durván ilyen eredményeket kaptam 100 000 elemre:

• aos_update: ~185 µs
• soa_update: ~95 µs

Ez közel kétszeres gyorsulás, kizárólag a memóriaelrendezés megváltoztatásával, egyetlen algoritmikus sor módosítása nélkül. A pontos szám természetesen architektúrafüggő, a struct mérete és a mezők száma is befolyásolja, de a tendencia — SoA javára — tipikusan konzisztens ilyen jellegű, szelektív hozzáférésű ciklusoknál.

Mikor éri meg és mikor nem ezt az optimalizációt bevezetni

A SoA nem ingyen jön. Az átalakítás komoly árat követel az API ergonómiájában: egyetlen entitást most nem tudsz egyszerűen visszaadni referenciaként, mert az adatai szétszórva vannak a különböző Vec-ekben. Ha kódod gyakran dolgozik egyetlen entitással (pl. get_particle(i) -> &Particle), a SoA jelentősen megnehezíti az életedet — vagy egy ideiglenes struktúrát kell összeraknod minden híváskor, vagy indexeket kell mindenhol átadnod.

Érdemes a SoA-t bevezetni, ha:

• Nagy elemszámú (több ezres, tízezres) kollekciókon dolgozol forró ciklusban.
• A hozzáférési minta szelektív: egyszerre csak néhány mezőt használsz az egész struktúrából.
• Profilozással (pl. perf vagy cargo flamegraph) igazoltad, hogy a cache miss valóban bottleneck.
• SIMD-vektorizációt tervezel, mert a SoA elrendezés ehhez elengedhetetlen előfeltétel.

Nem éri meg, ha:

• A kollekció kicsi (néhány tucat vagy száz elem), ahol a cache hatás elenyésző.
• A kód olvashatósága és karbantarthatósága fontosabb, mint a mikrooptimalizáció — egy játékmotor belső fizikai magja más prioritás, mint egy admin felület backend logikája.
• Nem mérted meg előre, hogy tényleg ez a bottleneck. A korai optimalizáció ugyanolyan csapda Rustban, mint bármely más nyelvben.

Összefoglalás

A cache-barát adatszerkezetek nem varázslat, hanem a hardver működésének tudatos figyelembevétele. Az Array of Structs minta intuitív és jól karbantartható, de szelektív, nagy volumenű hozzáférés esetén komoly cache miss büntetést szenvedhet el. A Struct of Arrays átalakítás ezt kiküszöböli azzal, hogy homogén adatot tesz egymás mellé a memóriában, cserébe bonyolultabb API-t és nehezebb karbantarthatóságot eredményez.

A legfontosabb tanács: mérj, mielőtt optimalizálsz. A criterion crate pontosan erre való — ne a megérzéseidre, hanem konkrét számokra alapozd a döntést, hogy megéri-e feláldozni a kód egyszerűségét a nyers teljesítményért.