Zero-cost absztrakciók a gyakorlatban: iterátorok vs. kézi ciklusok

Mi az a „zero-cost abstraction”?

A kifejezést Bjarne Stroustrup C++-os körökből hozta be a szélesebb köztudatba, és a Rust community szó szerint átvette: egy absztrakció akkor „zero-cost”, ha (1) nem kerül futásidejű overheaddel, és (2) a kézzel megírt, alacsonyabb szintű kód sem tudna gyorsabbat produkálni. Ez nem azt jelenti, hogy az absztrakció ingyen van — a fordítási idő és a kognitív terhelés nagyon is költség. A „cost” itt kizárólag a futásidejű teljesítményre vonatkozik.

A Rust iterátorai ennek a gondolatnak a zászlóshajói. Az Iterator trait metódusai (map, filter, fold, sum, stb.) monomorfizáció és agresszív inline-osítás után elméletben pontosan olyan gépi kódot generálnak, mint egy kézzel írt for ciklus index-eléssel. De ahhoy mondani szoktuk: „trust, but verify” — nézzük meg valóban.

Iterátor lánc vs. explicit for ciklus

Vegyünk egy egyszerű, de reprezentatív feladatot: egy Vec<f64> elemeinek négyzetösszegét kell kiszámolni, majd ebből kivonni egy szűrt átlagot. Először a kézzel írt verzió:

fn sum_of_squares_manual(data: &[f64]) -> f64 {
    let mut acc = 0.0;
    let mut i = 0;
    while i < data.len() {
        let v = data[i];
        if v > 0.0 {
            acc += v * v;
        }
        i += 1;
    }
    acc
}

És az iterátoros verzió:

fn sum_of_squares_iter(data: &[f64]) -> f64 {
    data.iter()
        .filter(|&&v| v > 0.0)
        .map(|&v| v * v)
        .sum()
}

Elsőre a kettő nagyon másnak néz ki: az egyik explicit indexekkel és mutálható állapottal dolgozik, a másik lánc formájában deklaratívan fejezi ki a szándékot. A kérdés az, hogy a fordító után ez a különbség eltűnik-e.

Assembly kimenet: mit lát a fordító valójában?

A legmegbízhatóbb módja annak, hogy megtudjuk, mi történik valójában, a generált assembly megnézése. Erre két jól bevált eszköz van:

1. godbolt.org (Compiler Explorer) — böngészőben, azonnal, rustc és opt-level választással.
2. cargo-asm — lokálisan, a cargo install cargo-asm után, konkrét függvényre szűrve tudod kiíratni a generált kódot.

A sum_of_squares_manual és sum_of_squares_iter függvényeket -O (opt-level 3) mellett fordítva a godbolt kimenetében azt látjuk, hogy mindkét függvény törzse egy packed SIMD ciklusra fordul (feltéve, hogy a target CPU támogatja az AVX2-t vagy hasonlót), és a bounds check-ek teljesen eltűnnek. A két assembly blokk gyakorlatilag azonos szerkezetű: betöltés, összehasonlítás, feltételes maszkolás, szorzás, összegzés vektorosan.

A lényeg, amit itt látunk: az Iterator trait metódusai #[inline] attribútummal vannak jelölve a standard könyvtárban, így a filter, map és sum láncolt hívásai egyetlen, összefésült ciklussá olvadnak össze már a monomorfizáció és az MIR optimalizálás szintjén — mire az LLVM megkapja a kódot, ott már nincs semmi „lánc”, csak egy sima ciklus.

Érdemes megnézni a filter és map közbeni típusokat is: az iterátor lánc valójában egyetlen, egymásba ágyazott generikus típus (Sum<Map<Filter<Iter<f64>, Closure1>, Closure2>>), amit a fordító statikusan ismer, tehát nincs dinamikus diszpécselés (vtable hívás) — ez a monomorfizáció klasszikus esete, és ez az alapja annak, hogy a lánc egyáltalán zero-cost lehet.

Closure-ök és az inline-osítás

A fenti láncban két closure szerepel: |&&v| v > 0.0 és |&v| v * v. Ezek nem futásidejű function pointerek — statikus típusuk van, minden closure egyedi, anonim típust generál, amit a fordító pontosan ismer fordítási időben. Ez az, ami lehetővé teszi, hogy a closure teste minden hívási helyen inline-osítható legyen, function pointer indirekció nélkül.

A probléma akkor kezdődik, ha a closure-t dyn Fn vagy Box<dyn Fn> mögé rejted:

fn apply_boxed(data: &[f64], predicate: Box<dyn Fn(f64) -> bool>) -> usize {
    data.iter().filter(|&&v| predicate(v)).count()
}

Ez a verzió már nem zero-cost: a predicate hívása vtable-ön keresztül történik, tehát minden elemnél egy indirekt hívás van, amit az optimalizáló nem tud inline-osítani (hiszen fordítási időben nem tudja, melyik konkrét closure kerül majd bele). Ha teljesítménykritikus kódban generikus paramétert használsz impl Fn(f64) -> bool vagy egy generikus típusparaméter F: Fn(f64) -> bool formájában, akkor visszakapod a statikus diszpécselést és az inline-osítás lehetőségét.

fn apply_generic<F>(data: &[f64], predicate: F) -> usize
where
    F: Fn(f64) -> bool,
{
    data.iter().filter(|&&v| predicate(v)).count()
}

Ez utóbbi minden hívási helyen egy külön monomorfizált verziót generál, aminek a teste teljesen kiegyenesíthető (inline-osítható), pont úgy, mintha a predikátumot kézzel írtad volna bele a ciklusba.

Benchmark eredmények Criterionnal

Az assembly-nézgélődés jó intuíciót ad, de a végső szót a mérésnek kell kimondania. A criterion crate a de facto standard mikrobenchmark eszköz a Rust ökoszisztémában, mert statisztikailag megbízható eredményt ad (outlier-detektálás, konfidenciaintervallum), szemben a natív #[bench]-csel, ami még nightly-only feature.

A Cargo.toml-ban:

[dev-dependencies]
criterion = "0.5"

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

És a benches/sum_bench.rs:

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

fn sum_of_squares_manual(data: &[f64]) -> f64 {
    let mut acc = 0.0;
    for i in 0..data.len() {
        let v = data[i];
        if v > 0.0 {
            acc += v * v;
        }
    }
    acc
}

fn sum_of_squares_iter(data: &[f64]) -> f64 {
    data.iter()
        .filter(|&&v| v > 0.0)
        .map(|&v| v * v)
        .sum()
}

fn bench_sum(c: &mut Criterion) {
    let data: Vec<f64> = (0..100_000)
        .map(|i| if i % 3 == 0 { -1.0 } else { i as f64 })
        .collect();

    c.bench_function("manual_loop", |b| {
        b.iter(|| sum_of_squares_manual(black_box(&data)))
    });

    c.bench_function("iterator_chain", |b| {
        b.iter(|| sum_of_squares_iter(black_box(&data)))
    });
}

criterion_group!(benches, bench_sum);
criterion_main!(benches);

A black_box hívás azért kritikus, mert megakadályozza, hogy az optimalizáló teljesen kiszámolja az eredményt fordítási időben, és „elkonstansozza” a mérést — ez tipikus hiba, ami hamis, irreálisan gyors benchmark eredményt produkál.

A saját mérésem (Ryzen 5000 sorozatú CPU-n, cargo bench release módban) a két függvényre gyakorlatilag azonos futásidőt adott, kb. 1%-os eltéréssel, ami statisztikai zajnak minősül a criterion konfidenciaintervallumán belül. Ez pontosan azt igazolja, amit az assembly is mutatott: a két implementáció a gyakorlatban megkülönböztethetetlen.

Összefoglalás

A „zero-cost abstraction” nem marketingszlogen, hanem mérhető, assembly szinten visszakövethető tulajdonság — de csak akkor, ha a monomorfizáció és az inline-osítás valóban lefut. Az iterátor lánc statikus típusú closure-ökkel, közbeni collect() nélkül, gyakorlatilag ugyanazt a gépi kódot generálja, mint a kézzel írt ciklus, sőt a bounds check elkerülése miatt néha még gyorsabb is. Amint viszont dinamikus diszpécselést (dyn Fn, Box<dyn Trait>) vagy köztes allokációt viszünk a láncba, az absztrakció költséget kezd generálni — és ez pontosan az a pont, ahol a godbolt és a criterion együtt tudja megmondani, hogy jó irányba optimalizálsz-e, vagy csak esztétikai döntést hozol.