14.4 Cache, locality, alignment és false sharing

Két, egyaránt $O(n)$ költségű bejárás futásideje nagyságrendileg eltérhet attól függően, hogyan helyezkednek el az adatok, és milyen függőségi láncot alkotnak a memóriaelérések. Egy szolgáltatás metrikatáblájának feldolgozásakor ezért nemcsak az számít, hány összeadást végzünk, hanem az is, mennyi adatot mozgatunk meg ezekért.

A Padding, alignment és offsetof részben az objektumok nyelvi igazítási követelményeit vizsgáltuk; itt ezeket megkülönböztetjük a cache szempontjából kedvező elhelyezéstől. A láncolt listák bejárási szerződését pedig hardveres költségmodellel egészítjük ki. Végig érvényes az optimalizálóról tanult korlát: a forráskód nem utasításjegyzék, és egy assemblymegfigyelés nem nyelvi garancia.

14.4.1 Cache line, TLB és laplokalitás

Hardvermodell. A cache a memória egyes tartományainak gyorsabban elérhető másolatát tartja. Az adatmozgatás és a koherenciakövetés fontos egysége a cache line, magyarul cache-sor. Mérete nem C-tulajdonság, és a cache-szintek, processzorok viselkedése sem egységes.

A térbeli lokalitás (spatial locality) azt jelenti, hogy egy elérés közelében fekvő adatokat is hamarosan felhasználunk. Az időbeli lokalitás (temporal locality) ugyanannak az adatnak a rövid időn belüli újrafelhasználása. Mindkettő csak az adatok elhelyezésével és a hozzáférési mintával együtt értelmezhető.

Legyen a cache-sor mérete $B$ oktett. Egy $D>0$ oktettes folytonos tartomány, amelynek kezdete az első soron belül $o$ eltolású, összesen

$$N_{\text{line}}=\left\lceil\frac{o+D}{B}\right\rceil$$

sort érint, ahol $0\le o<B$.

Levezetés. A tartomány vége a kezdő cache-sor elejétől $o+D$ távolságra esik. Ezt kell $B$ méretű egységekkel lefedni; a tört utolsó egység is teljes érintett sornak számít. Ez címtartomány-számítás, nem cache-miss-előrejelzés: a sorok már jelen lehetnek valamelyik cache-ben.

A TLB (translation lookaside buffer) címfordításokat gyorsítótáraz. Nem az adatcache helyettesítője: más kérdés, hogy ismert-e a virtuális cím fordítása, és más, hogy rendelkezésre áll-e a kívánt adat.

Egyszerű modellben $E$ használható TLB-bejegyzés és $P$ lapméret mellett a lefedett tartomány nagyságrendje $E\cdot P$. Az asszociativitás, az eltérő lapméretek és a többi memóriaelérés ezt módosítják. Sok lap egy-egy adatának olvasása gyenge laplokalitást (page locality) eredményezhet akkor is, ha kevés hasznos bájtot dolgozunk fel.

A TLB-miss nem azonos a laphibával: szükségessé tehet lapfordítási táblák bejárását anélkül, hogy az operációs rendszer laphibakezelője futna. A nagyobb lapok javíthatják a TLB-lefedettséget, de nem javítják automatikusan az adatcache lokalitását.

14.4.2 Folytonos tömb vagy pointerkövetés?

Folytonos tömbnél a következő elem címe az alaptól és az indextől függ. A processzor és a fordító több későbbi hozzáférést is előkészíthet; a szabályos címfolyam az előbetöltésnek is kedvez.

Láncolt listánál gyakran csak az aktuális csomópont betöltése után ismerjük meg a következő címét. Ez pointerkövetés (pointer chasing): az egymástól függő memóriaelérések korlátozzák a párhuzamosítást. Véletlenszerűen szétszórt csomópontoknál a cache- és TLB-kihagyások késleltetése összeadódhat.

A táblázat nem általános győztest hirdet. Poolból kiosztott, bejárási sorrendben elhelyezett lista lehet cache-barát. Egy tömb véletlenszerű indexelése pedig elveszítheti előnyének jelentős részét. Ismert csomópont gyakori törlésekor a lista algoritmikus előnye fontosabb lehet, mint a ritka teljes bejárás.

Mindkét esetben előfeltétel az élő tároló és az érvényes bejárási tartomány. A jobb lokalitás nem tesz helyessé egy dangling pointert.

14.4.3 AoS és SoA: az elrendezést a művelethez válasszuk

Az AoS (array of structures) rekordok tömbje; a SoA (structure of arrays) mezőnként külön tömböket használ.

Vegyünk egy metrikarekordot négy unsigned long mezővel. A következő számpélda profilja Linux, x86-64 System V ABI, LP64, nyolcbites C bájt, továbbá modellfeltevésként 64 oktettes cache-sor. Ez nem minden platformra érvényes layout.

Tegyük fel, hogy csak a requests mezőt összegezzük. Cache-sor-határra igazított kezdés és nyolccal osztható $n$ elemszám mellett:

• AoS esetén egy sor két rekordot, de csak 16 oktett hasznos mezőadatot tartalmaz;
• a SoA megfelelő oszlopában egy sor nyolc hasznos értéket tartalmaz.

Az érintett cache-sorok száma ezért

$$N_{\text{AoS}}=\frac n2, \qquad N_{\text{SoA}}=\frac n8.$$

A hasznosadat-arány AoS esetén $16/64=25\%$, SoA esetén $100\%$. Hideg cache-t és teljes soronkénti adatmozgatást feltételező modellben ez $32n$, illetve $8n$ oktett.

Ez nem négyszeres gyorsulás ígérete. Ha minden rekord összes mezőjét használjuk, az AoS jó lokalitást adhat. Véletlenszerűen kiválasztott teljes rekordok feldolgozásakor a SoA több különálló cache-sort is igényelhet.

14.4.3.1 Fordítható összehasonlítási alap

Az alábbi ISO C17 program helyességi alap, nem kész benchmark. A választott laborprofil GCC 14.2.0 vagy Clang 19.1.7, glibc 2.40, a fenti x86-64 célplatformon; a példát itt nem fordítottuk és nem mértük. A statikus ellenőrzések a feltételezett layout eltérését fordítási hibává teszik.

A SoA-ból csak a művelethez szükséges oszlopot tároljuk.

/* locality.c */
#include <limits.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

struct sample {
    unsigned long requests;
    unsigned long errors;
    unsigned long latency_sum;
    unsigned long reserved;
};

_Static_assert(CHAR_BIT == 8, "8-bit C byte required");
_Static_assert(sizeof(unsigned long) == 8, "LP64 field size required");
_Static_assert(_Alignof(struct sample) == 8, "unexpected alignment");
_Static_assert(sizeof(struct sample) == 32, "unexpected record size");
_Static_assert(offsetof(struct sample, errors) == 8, "unexpected layout");
_Static_assert(offsetof(struct sample, latency_sum) == 16,
               "unexpected layout");
_Static_assert(offsetof(struct sample, reserved) == 24,
               "unexpected layout");

static unsigned long sum_aos(const struct sample *p, size_t n)
{
    unsigned long sum = 0;
    for (size_t i = 0; i < n; ++i)
        sum += p[i].requests;
    return sum;
}

static unsigned long sum_column(const unsigned long *p, size_t n)
{
    unsigned long sum = 0;
    for (size_t i = 0; i < n; ++i)
        sum += p[i];
    return sum;
}

int main(void)
{
    const size_t n = 1000000;
    struct sample *aos = malloc(n * sizeof *aos);
    unsigned long *requests = malloc(n * sizeof *requests);

    if (aos == NULL || requests == NULL) {
        free(requests);
        free(aos);
        return EXIT_FAILURE;
    }

    for (size_t i = 0; i < n; ++i) {
        unsigned long value = (unsigned long)(i % 1000);
        aos[i] = (struct sample){value, 0, 0, 0};
        requests[i] = value;
    }

    unsigned long a = sum_aos(aos, n);
    unsigned long b = sum_column(requests, n);
    int status = a == b ? EXIT_SUCCESS : EXIT_FAILURE;
    printf("%lu %lu\n", a, b);

    free(requests);
    free(aos);
    return status;
}

gcc -std=c17 -O3 -Wall -Wextra -Wpedantic \
    -march=x86-64 -mtune=generic locality.c -o locality-gcc

clang -std=c17 -O3 -Wall -Wextra -Wpedantic \
    -march=x86-64 -mtune=generic locality.c -o locality-clang

A két allokáció tulajdonosa a main; az összegző függvények csak a hívás idejére kölcsönöznek hozzáférést az élő [0,n) tartományhoz. Pointert nem őriznek meg. A free érvényteleníti a hozzáférést; allokációs hiba sikertelen kilépést eredményez. Hibás pointer vagy túl nagy átadott elemszám nem ellenőrzött hibakimenet, hanem UB-hez vezethet.

A rögzített méretszorzatok a laborprofilban ábrázolhatók; általános bemeneti elemszámhoz túlcsordulás-ellenőrzés kellene. A várt összeg mindkét oldalon $1000\cdot(0+\dots+999)=499\,500\,000$.

14.4.4 Objektumigazítás és false sharing

ISO C17. Az objektum igazítása azt szabályozza, milyen címeken helyezhető el szabályosan. Ettől különböző követelmény, hogy két gyakran írt objektum ne kerüljön ugyanabba a hardveres koherenciaegységbe.

A cache-koherencia (cache coherence) a különböző magok cache-eiben levő másolatok összhangját biztosító hardvermechanizmus. Íráskor a protokoll más magok példányait érvénytelenítheti, illetve írási jogosultságot adhat át.

False sharing, azaz hamis megosztás akkor jelentkezik, amikor különböző végrehajtók logikailag különálló adatokat használnak, de azok közös koherenciaegységben vannak, és legalább az egyik hozzáférési folyam ír. A költség egységszinten jelentkezik, nem a C-mezők határain.

Az előző laborprofilban, 64 oktettes sorhatáron kezdődő tárolónál:

A teljes tömb igazítása tehát nem választja szét az elemeit: a kezdőcím és az elemlépés együtt számít. A padding javíthatja a helyzetet, de növeli a memória-, cache- és TLB-lábnyomot. Túlzott igazítású dinamikus tárolónál a megfelelő allokációs szerződést is biztosítani kell; a közönséges malloc nem általános megoldás minden kiterjesztett igazításra.

Külön skalár objektumok kizárólagos szálankénti írása lehet adatversenymentes, mégis szenvedhet false sharingtől. Fordítva: ugyanazon nem atomikus objektum versengő elérését a padding nem javítja meg. A nyelvi szinkronizációt a Data race, happens-before és publikalás rész tárgyalja.

14.4.5 Prefetch és memória-sávszélesség

Az előbetöltés (prefetch) megpróbálja az adatot a tényleges felhasználás előtt közelebb hozni a végrehajtóhoz. A hardveres előbetöltő gyakran felismer szabályos címfolyamokat. Pointerkövetésnél a következő cím későn válik ismertté, ezért ez nehezebb.

Az előbetöltés nem ingyenes: sávszélességet és cache-helyet használ. Rossz mintánál haszontalan adatokat tölthet be, vagy kiszoríthat hasznos sorokat. A szoftveres prefetch nem hordozható C-alapeszköz; bevezetését mérésnek kell indokolnia.

Ha egy vizsgált memóriaszinten $D$ oktett adatnak kell áthaladnia, és az adott hozzáférési mintához tartozó effektív sávszélesség $W$, akkor egyszerű alsókorlát-modellben

$$T\ge\frac{D}{W}.$$

Ez nem teljes futásidőképlet. Függő cache-miss-eknél a késleltetés, sok független hozzáférésnél inkább a sávszélesség korlátozhat. Több szál nem feltétlenül gyorsít, ha a közös memóriaút már telített.

14.4.6 Mérés: nincs univerzális ciklusszám

Az „egy memóriaolvasás ennyi ciklus” állítás körülmények nélkül értelmetlen. Számít a cache-szint, a TLB állapota, a NUMA-elhelyezés, a konkurens terhelés, az órajel és a párhuzamosan kiszolgálható kérések száma.

A példaprogram teljes futásideje nem izolált AoS/SoA-mérés: allokál, inicializál, kiír, és rögzített sorrendben dolgozik. Egy megbízható laborban:

• az allokációt és a lapok első érintését különítsük el a vizsgált bejárástól;
• több munkahalmazméretet használjunk, ne csak egy cache-be férő esetet;
• váltogassuk a változatok sorrendjét, és ismételt mérések eloszlását közöljük;
• rögzítsük a CPU-, NUMA-, fordító- és optimalizálási profilt;
• ellenőrizzük, hogy az optimalizáló valóban meghagyta-e a mérendő munkát.

A visszaadott összeg elfogyasztása szükséges, de nem mindig elég: ismételt, változatlan bemenetű számítást a fordító összevonhat. A volatile rutinszerű hozzáadása viszont megváltoztatná a vizsgált műveletet.

False-sharing-mérésnél külön kontroll legyen az egy szál, a közeli és az elkülönített számláló, valamint a magok elhelyezése. A padding utáni gyorsulás önmagában még nem bizonyítja az okot.

14.4.7 Feladatok

1. Magyarázó: A fenti modellben $n=8192$, a kezdőcímek 4096 oktettes laphatáron vannak. Hány cache-sort és lapot érint a kizárólagos requests-bejárás AoS és SoA esetén?

2. Kódolási: Írj AoS-függvényt, amely mind a négy mezőt összegzi! Miért nem tisztességes ezt az egyetlen SoA-oszlop összegzésével összehasonlítani?

3. Diagnosztikai: Két szál külön unsigned long tömbelemeket ír. A tömb kezdetét 64-re igazítják, de nincs gyorsulás. Adj elrendezési magyarázatot és ellenőrzési tervet!

14.4.8 Megoldások

14.4.8.1 Cache-sorok és lapok

AoS esetén $8192/2=4096$ cache-sort érintünk; a rekordtömb mérete $262\,144$ oktett, vagyis 64 lap. Minden lapról olvasunk mezőt.

SoA esetén $8192/8=1024$ cache-sort és $65\,536/4096=16$ lapot érintünk.

Ellenőrzési feltétel a megadott igazítás, sor- és lapméret. Ezek érintett egységek, nem garantált miss-számok.

14.4.8.2 Azonos művelet összehasonlítása

A következő C17-részlet az eredeti fájlba, a main elé illeszthető; ugyanazzal a buildparanccsal fordítható:

static unsigned long sum_all(const struct sample *p, size_t n)
{
    unsigned long sum = 0;
    for (size_t i = 0; i < n; ++i) {
        sum += p[i].requests;
        sum += p[i].errors;
        sum += p[i].latency_sum;
        sum += p[i].reserved;
    }
    return sum;
}

A kölcsönzési szerződés azonos a sum_aos szerződésével. Az általános eredmény unsigned long szerinti moduláris összeg; matematikai összeghez külön értékkorlát kell.

Érvényes összehasonlításkor a SoA-változatnak ugyanazon négy mezőt kell feldolgoznia. Ellenőrzéshez a tesztadatok mindegyik mezőjét töltsük nem nulla értékekkel, és vessük össze az eredményeket.

14.4.8.3 Az igazítás nem elemenkénti elkülönítés

A két elem eltolása továbbra is 0 és 8: a közös kezdőcím igazítása nem változtatja meg az elemlépést. Külön, megfelelően igazított és méretezett slotokkal kell kontrollváltozatot készíteni.

Ellenőrizzük a sizeof és _Alignof értékeket, a tényleges címkülönbséget, a szálak elhelyezését és a generált írásokat. Előbb igazoljuk az adatverseny-mentességet; utána több munkamennyiséggel mérjük a közeli és elkülönített változatot. Nem garantált, hogy a false sharing lesz a domináns költség.

14.4.9 Rövid összefoglaló

A memóriaelérés költségét az elrendezés, a hozzáférési minta és a hardverállapot együtt határozza meg. A folytonos tárolás és a SoA gyakran csökkenti a fölösleges adatmozgatást, de nem minden műveletnél előnyös. Az objektumigazítás nyelvi helyességi követelmény; a cache-line-elkülönítés teljesítménytervezési döntés. A modellt számolással, a programot helyességi ellenőrzéssel, a teljesítményállítást pedig dokumentált méréssel kell alátámasztani.