Adatelrendezés és hozzáférési lokalitás

Cél és előfeltétel

Sok adat feldolgozásánál nemcsak az algoritmus, hanem az olvasott adatok együttélése is számít. Ebben a leckében ugyanazokat az értékeket rekordokként és külön oszlopokban tárolod. Előfeltétel a structos adatmodellezés, valamint a költségmodell. A cél egy vizsgálható alternatíva kialakítása, nem egyetlen mindig győztes tárolási forma kihirdetése.

Ha a feldolgozás egy rekord minden mezőjét használja, az összetartozó adatok együtt tartása kézenfekvő. Ha sok rekordból csak egy oszlop érdekel, az oszlopos forma más hozzáférési mintát adhat. Ezek hipotézisek. A valós hatást a célgépen, a tényleges munkával kell mérni; a cache viselkedését egy mezősorrend vagy egyetlen size_of eredmény nem bizonyítja.

A logikai szerződés ne vesszen el

A rekordos modellben egy érték és a hozzá tartozó jelző természetesen együtt mozog. Két külön vektor esetén ezt a kapcsolatot már a programnak kell fenntartania. Ha az egyik hosszabb, a zip önmagában csendben elhagyná a túllógó elemeket. Ezért az alternatív reprezentáció helyességi feltétele a hosszúságok ellenőrzése is, nem csupán az azonos sikeres eredmény.

A Rust alapértelmezett structelrendezése nem általános, verziókon át stabil külső bájtszerződés. A fordító bizonyos megkötések mellett megválaszthatja az elrendezést. A repr(C) pontosabb szabályokat kér, de az sem helyettesít egy hálózati protokollt: a célplatform igazítása és bájtsorrendje külön kérdés marad. Biztonságos optimalizálásnál előbb tudd, melyik tulajdonságra támaszkodhatsz ténylegesen.

1. feladat: két reprezentáció, azonos eredmény

Számold össze az engedélyezett rekordok értékeit, majd írd meg ugyanezt külön jelző- és értékoszloppal. Az összegzés legyen ellenőrzött, az eltérő oszlophossz hiányt jelezzen. Vizsgáld az üres bemenetet is. A két függvény eredményét ugyanazon logikai adatokkal hasonlítsd össze.

struct Row { enabled: bool, value: u64 }
fn records(rows: &[Row]) -> Option<u64> {
    rows.iter().filter(|r| r.enabled)
        .try_fold(0_u64, |sum, r| sum.checked_add(r.value))
}
fn columns(enabled: &[bool], values: &[u64]) -> Option<u64> {
    if enabled.len() != values.len() { return None; }
    enabled.iter().zip(values).filter(|(yes, _)| **yes)
        .try_fold(0_u64, |sum, (_, x)| sum.checked_add(*x))
}
fn main() {
    let rows = [Row { enabled: true, value: 4 },
                Row { enabled: false, value: 99 },
                Row { enabled: true, value: 6 }];
    assert_eq!(records(&rows), Some(10));
    assert_eq!(columns(&[true, false, true], &[4, 99, 6]), Some(10));
    assert_eq!(columns(&[true], &[]), None);
    assert_eq!(columns(&[], &[]), Some(0));
    assert_eq!(columns(&[true, true], &[u64::MAX, 1]), None);
}

2. feladat: megfigyelés és garantált kapcsolat

Vizsgáld meg egy repr(C) fejléc méretét és igazítását. Ne várj előre konkrét bájtszámot, amely csak a saját gépeden látszott. Az állítások az összetevők helyigényére és a méret igazítással való összhangjára vonatkozzanak. A kiírt szám megfigyelési adat, nem fájlformátum.

use std::mem::{align_of, size_of};
#[repr(C)]
struct Header { tag: u8, count: u32 }
fn main() {
    let size = size_of::<Header>();
    let alignment = align_of::<Header>();
    assert!(size >= size_of::<u8>() + size_of::<u32>());
    assert_eq!(size % alignment, 0);
    assert!(alignment >= align_of::<u32>());
    println!("meret={size}, igazitas={alignment}");
}

3. feladat: tervezz explicit bájtformátumot

Egy fejléc legyen egy tagbájt és egy little-endian u32 szám. A beolvasó pontosan öt bájtot fogadjon el. Ellenőrizd a várt bájtsorrendet és a hibás hossz elutasítását. Ez a feladat azt mutatja, hogyan kerülheted el a memóriabeli struktúra és a külső reprezentáció összekeverését.

fn encode(tag: u8, count: u32) -> [u8; 5] {
    let n = count.to_le_bytes();
    [tag, n[0], n[1], n[2], n[3]]
}
fn decode(bytes: &[u8]) -> Option<(u8, u32)> {
    if bytes.len() != 5 { return None; }
    let n: [u8; 4] = bytes.get(1..5)?.try_into().ok()?;
    Some((bytes[0], u32::from_le_bytes(n)))
}
fn main() {
    let bytes = encode(7, 0x01020304);
    assert_eq!(bytes, [7, 4, 3, 2, 1]);
    assert_eq!(decode(&bytes), Some((7, 0x01020304)));
    assert_eq!(decode(&[7, 4]), None);
    assert_eq!(decode(&[]), None);
}

Döntés a hozzáférési minta alapján

Mielőtt oszlopokra bontasz egy modellt, írd fel, mely műveletek érintenek teljes rekordot, és melyek csak egyetlen mezőt. A beszúrás, törlés és sorrendváltoztatás összetettebb lehet, ha több tárolót kell együtt kezelni. Az esetleges olvasási előnyt ezért a karbantartás és a hibalehetőségek árával együtt értékeld. A helyességi teszteket a reprezentációcsere előtt érdemes elkészíteni.

A két reprezentáció teszteléséhez válassz olyan adatot is, amelyben minden rekord tiltott. Ekkor a nulla összeg helyes eredmény, nem hiányzó adat. Egy üres és egy hibás hosszúságú oszloppár tehát szándékosan külön visszatérést kap. Ez a részlet fontos, amikor a gyorsabb olvasás érdekében a modell korábban természetes összetartozását több tárolóra bontod szét.

A memóriaelrendezés megfigyelésekor jegyezd fel a célarchitektúrát és a fordítóverziót is. A méret különbsége önmagában nem mutatja meg, hány hasznos mezőt olvasott a feldolgozó, mennyi elágazást végzett vagy milyen más adatokkal osztozott a cache-en. Egy pontos méretadat jó kiindulópont, ha a jelentését megőrzöd; rossz bizonyíték, ha ebből rögtön a teljes alkalmazásra vonatkozó gyorsulást vezetsz le.

Elfogadási feltételek

1. A rekordos és oszlopos változat azonos eredményt ad, a hosszkülönbség és túlcsordulás hibás állapot.
2. A méretellenőrzés dokumentált kapcsolatokra épít, nem egy célgép konkrét számát követeli.
3. Az öt bájtos formátum azonos bájtokat ad és hibás hosszra None eredménnyel tér vissza.

Összefoglaló és továbblépés

A lokalitásról szóló gondolatmenet csak hipotézist adott, nem sebességbizonyítékot. Az Instant és black_box mérési leckében megtanulod, hogyan kell egy ilyen feltevéshez megfelelően korlátozott mérést kapcsolni.