37.3 Object layout, EBO és adatközpontú tervezés

A korábbi részekben felépítettük a C memóriamodell alignment- és padding-szabályait (Padding, alignment és offsetof (9.2)), a cache-viselkedés és a false sharing hardveres hátterét (Cache, locality, alignment és false sharing (14.4)), valamint azt, hogy a C++ objektumlayout ABI-szerződés, nem nyelvi absztrakció (Névtorzítás, layout és C++ runtime ABI (36.1)). A dinamikus allokáció oldaláról a pmr és a region-élettartam adta meg a keretet (pmr, memory_resource és region lifetime (37.2)). Ez az alfejezet ezeket kapcsolja össze: hogyan lesz a C padding- és cache-tudásból C++ kompozíciós és polimorfikus döntés, és hogyan lehet ezt mérésből levezetett cost modellel kezelni a helyességi szerződés megsértése nélkül.

Az alapállítás, amelyre minden további épül: a C++ szabvány a layoutról keveset garantál, viszont az implementáció (ABI) sokkal többet rögzít. A kettőt következetesen szét kell választani. Amit a szabvány megkövetel, az minden konform implementáción igaz; amit az ABI rögzít, az az adott target és compiler-párosítás mellett igaz, és a következő minor verzióban megváltozhat.

37.3.1 A layout, amit a szabvány garantál, és amit nem

A szabvány annyit mond ki, hogy egy nem üres osztály objektuma legalább annyi bájtot foglal, amennyi a nem statikus adattagjai összege, plusz az igazításból és a bázisosztály-részekből adódó kitöltés; továbbá hogy két, egyidejűleg létező, nem potenciálisan átfedő hasonló típusú részobjektumnak különböző címe kell legyen. A pontos offseteket, a padding helyét és méretét, a virtuális táblára mutató rejtett pointer helyét, valamint azt, hogy egy üres bázis egyáltalán nulla méretű-e, a szabvány nem rögzíti. Ezeket az ABI írja le — x86-64-en az Itanium C++ ABI System V változata —, tehát a konkrét számok mellett mindig meg kell nevezni a targetet, a compilert és a nyelvi módot.

A tipikus (nem garantált, de a mainstream ABE-kben követett) elrendezési szabály a következő. Legyen a tagok sorrendje m1,…,mnm_1,\dots,m_n, méretük sis_i, igazításuk aia_i. Az offset rekurzívan:

o1=0,oi+1=⌈oi+siai+1⌉⋅ai+1o_1 = 0, \qquad o_{i+1} = \left\lceil \frac{o_i + s_i}{a_{i+1}} \right\rceil \cdot a_{i+1}

ahol aia_i kettőhatvány, ezért a felfelé kerekítés bitművelettel is kifejezhető:

round_up(x,a)=(x+a−1)&∼(a−1)\operatorname{round\_up}(x, a) = (x + a - 1)\ \&\ \sim(a - 1)

A struktúra igazítása maxiai\max_i a_i, a mérete pedig round_up(on+sn,maxiai)\operatorname{round\_up}(o_n + s_n, \max_i a_i). Ez a levezetés magyarázza, miért nem kommutatív a tagok sorrendje.

Vegyük a következő két típust, azonos tagokkal:

struct Order1 { char c; int i; double d; };
struct Order2 { int i; double d; char c; };
Tag Típus Méret Igazítás Offset (Order1) Offset (Order2)
c char 1 1 0 16
i int 4 4 4 0
d double 8 8 8 8

Order1-ben a c után 3 bájt hézag kerül, a d a 8-as offsetre esik, a végén nincs farokpadding: round_up(16,8)=16\operatorname{round\_up}(16, 8) = 16. Order2-ben az i után 4 bájt hézag, a d után a c a 16. offsetre kerül, a végét 24-re kerekíti a szerkezet 8-as igazítása. Ugyanaz a három tag tehát 16 és 24 bájtos típust ad — a sorrend nem esztétikai kérdés.

Amit a szabvány ebből ténylegesen garantál, az két traitben fogható meg. A std::is_standard_layout<T> azt jelenti, hogy a típus layoutja kiszámítható, C-vel kompatibilis módon írható le, és offsetof legális rajta. A std::is_trivially_copyable<T> azt jelenti, hogy az objektum bájtonként másolható, tehát std::memcpy-vel átvihető. Egyik sem garantálja a padding hiányát vagy konkrét offseteket: a sizeof(Order1) == 16 állítás nem szabványos, hanem ABI-megfigyelés.

37.3.2 Empty base optimization és a [[no_unique_address]]

Egy üres osztálynak is van mérete: sizeof(Empty) >= 1, különben két különböző objektum azonos címre esne. Amikor viszont üres osztály bázis-részobjektumként jelenik meg, a szabvány megengedi, hogy nulla méretű legyen és egy más típusú részobjektummal azonos címen osztozzon. Ezt nevezi a szakirodalom empty base optimizationnak (EBO). Fontos: a szabvány megengedi, nem kötelezővé teszi — a tényleges alkalmazás implementációfüggő, a gyakorlatban azonban minden elterjedt ABI végrehajtja.

Az EBO nem stílus kérdése, hanem az allokátor-, comparator- és deleter-alapú tervezés alapja. Ha egy std::vector<T, MyAlloc<T>> allokátora állapotmentes (csak típusparamétert hordoz, adattagot nem), akkor EBO nélkül minden vektorobjektum feleslegesen hízna egy bájttal plusz paddinggel. Az EBO teszi lehetővé, hogy az állapotmentes policy ne kerüljön semmibe.

C++20-tól ugyanez adattagra is kérhető:

struct Empty {};
struct AsMember   { Empty e; int x; };
struct AsBase     : Empty { int x; };
struct AsNoUnique { [[no_unique_address]] Empty e; int x; };
struct AsTwoNoUnique { [[no_unique_address]] Empty a;
                       [[no_unique_address]] Empty b; int x; };

LP64 x86-64-en AsMember mérete 8 (Empty 1 bájtja + 3 bájt padding), AsBase és AsNoUnique 4, AsTwoNoUnique viszont 8. Az utóbbi nem hiba: a szabvány két azonos típusú, nulla méretű részobjektumra is megköveteli a különböző címet, így azok nem fedhetik át egymást. A [[no_unique_address]] tehát nem univerzális tömörítő eszköz, hanem különböző típusú tagok átfedését teszi lehetővé. A tag típusa továbbra is std::is_empty, csak a címhasználat változik meg: ha a címét veszed, az más taggal azonos lehet — erre akkor figyelj, ha pointert vagy referenciát tárolsz rá.

37.3.3 Virtuális objektum és type-erased wrapper költsége

Egy virtuális függvényt tartalmazó osztály példánya rejtett pointert hordoz a virtuális táblára (vptr). Az Itanium ABI x86-64-en ezt a 0. offsetre teszi, mérete 8 bájt; a tábla maga az offset-to-top, a típusazonosító és a virtuális függvények pointereit tartalmazza, és fordítási egységenként egy példányban keletkezik. Következmény: struct Base { virtual ~Base() = default; }; esetén sizeof(Base) == 8, egy int tagot hordozó leszármazott esetén 16 (vptr + int + 4 bájt farokpadding).

A virtuális hívás költsége nem a tranzisztorszám, hanem az, hogy a hívásindirekció miatt a fordító nem tud inline-olni, így elveszik a konstans-propagáció és a vektorizálás lehetősége a hívott függvényben. C++20-tól a fordító bizonyos esetekben devirtualizálhat (ha a dinamikus típus lokálisan ismert, vagy ha az osztály final), de ez nem garantált, és LTO-t igényelhet. Amit a szabvány rögzít: a virtuális hívás szemantikája; amit nem: hogy mekkora a költsége, vagy hogy egyáltalán nincs-e költsége.

A type erasure (típusonkénti törlés) ugyanezt a kérdést más alakban teszi fel. A std::function<void()> egy kis, lokális puffert (small buffer) tart, és ha a becsomagolt callable belefér, nem allokál; ha nem, heap-re kerül. A puffer mérete és a sizeof(std::function) implementációfüggő — libstdc++-on x86-64-en jellemzően 32 bájt, libc++-on eltérő. Ezért a std::function méretére és allokációmentességére nem lehet API-szerződést építeni. Ahol a szerződés számít, ott a C-szerű void* context + void (*fn)(void*) pár két pointer, allokáció nélkül — cserébe elveszik a típusbiztonság és a lambda-kényelem.

37.3.4 AoS, SoA és folytonos tárolás

A cache-viselkedés (Cache, locality, alignment és false sharing (14.4)) közvetlen következménye az adatközpontú tervezés. Tekintsünk egy részecske-rendszert:

struct AoS { float x, y, z, vx, vy, vz; };   // 24 bájt

Egy AoS-tömbön végigmenve egy 64 bájtos cache-line-ból körülbelül 2 egész részecske fér el. Ha a forró ciklus csak a pozíciókat frissíti, a betöltött bájtok jelentős része kihasználatlan: a sebességvektorok is bekerülnek a cache-be. A SoA (structure of arrays) elrendezésben hat párhuzamos std::vector<float> van; a pozíciókra futó ciklus csak a három pozíciótömböt érinti, a stride 1, így a hardver-prefetcher és a SIMD-egység is hatékonyabban dolgozik.

Elrendezés Egy elem tárolt bájtja Egy elemhez tartozó, használt bájt Egymást követő elemek egy 64 bájtos vonalon
AoS (csak pozíció olvasva) 24 12 ~2.6
SoA (csak pozíció olvasva) 12 12 ~5.3

Az arány körülbelül 2:1 a betöltött bájtokban — ez számított érték a méretekből, nem mérés. A valós gyorsulás ennél kisebb vagy nagyobb is lehet, mert függ a ciklus egyéb költségeitől, a memóriaszinttől és attól, hogy a fordító vektorizál-e.

A folytonosság nem esztétikai tulajdonság: a std::vector és a std::array garantálja, hogy az elemek egy összefüggő tömbben vannak, ezért pointerrel bejárhatók és data()-val átadhatók C API-nak. A std::deque és a std::list ezt nem garantálja; a list csomópontjai szétszórtan helyezkednek el, ami minden bejárásnál cache-miss-t okoz. A tárolóválasztás így teljesítménykérdés is, nem csak interface-kérdés (Tárolóválasztási és invalidációs labor (28.6)).

37.3.5 Small-buffer optimalizálás mint implementációs részlet

A std::string small-string optimizationja (SSO) ugyanabba a kategóriába esik: a rövid stringeket a string objektum saját tárhelyén tárolja, elkerülve az allokációt. A küszöb azonban implementációfüggő: libstdc++-ban jellemzően 15 karakter (32 bájtos objektum mellett), libc++-ban más, MSVC alatt megint más. Ezért:

A mérés helyes módja nem a sizeof bámulása, hanem a tényleges allokációk számlálása: cseréld le a globális operator new-ot egy számlálóra a teszt binárisban, és mérd, hány hívás történik egy adott műveletsor alatt. Az eredmény target- és stdlib-verziófüggő, ezért a laborprofil mellé kell rögzíteni.

37.3.6 Alignment, false sharing és per-thread állapot

A false sharing akkor lép fel, amikor két szál két különböző változót ír, de azok ugyanazon a cache-line-on vannak: a hardver koherencia-protokollja a line-t ide-oda mozgatja, noha nincs valódi adatmegosztás. A javítás elválasztás, nem szinkronizáció:

struct Counters {
    alignas(64) std::atomic<long> a{0};
    alignas(64) std::atomic<long> b{0};
};

A C++17-es std::hardware_destructive_interference_size kifejezi ezt a szándékot, de az értéke implementációfüggő, és publikus headerben használva ODR- és ABI-kockázatot jelent, ha két fordítási egység eltérő értéket lát — ezért ABI-stabil határon inkább explicit, dokumentált konstansot használj.

A thread_local változó szálanként külön példány, ami természetesen megszünteti a false sharinget, de a hozzáféréshez TLS-modell kell (initial-exec vagy general-dynamic), ami plusz indirekció lehet, különösen megosztott könyvtárból. A dinamikus inicializálású thread_local objektumok élettartama a szálhoz kötött (Statikus és thread-local objektumok életciklusa (20.5)) — ez a döntés tehát élettartam-kérdés is, nem csak teljesítménykérdés.

37.3.7 Kidolgozott példa: layout-próba és locality-kapu

Az alábbi program a fenti állításokat teszi ellenőrizhetővé. Nem állítom, hogy lefuttattam: a megadott kimenet illusztratív, a tanuló laborjában mérendő.

// layout_probe.cpp
// build: g++ -std=c++20 -O2 -Wall -Wextra layout_probe.cpp -o layout_probe
//        clang++ -std=c++20 -O2 -Wall -Wextra layout_probe.cpp -o layout_probe
#include <cstddef>
#include <cstdio>
#include <functional>
#include <string>
#include <vector>

struct Empty {};
struct Order1 { char c; int i; double d; };
struct Order2 { int i; double d; char c; };
struct AsMember   { Empty e; int x; };
struct AsBase     : Empty { int x; };
struct AsNoUnique { [[no_unique_address]] Empty e; int x; };
struct Base { virtual ~Base() = default; };
struct DerivedV : Base { int x; };

int main() {
    std::printf("sizeof(Empty)                  = %zu\n", sizeof(Empty));
    std::printf("sizeof(Order1)                 = %zu\n", sizeof(Order1));
    std::printf("sizeof(Order2)                 = %zu\n", sizeof(Order2));
    std::printf("offsetof(Order1, d)            = %zu\n", offsetof(Order1, d));
    std::printf("sizeof(AsMember)               = %zu\n", sizeof(AsMember));
    std::printf("sizeof(AsBase)                 = %zu\n", sizeof(AsBase));
    std::printf("sizeof(AsNoUnique)             = %zu\n", sizeof(AsNoUnique));
    std::printf("sizeof(Base)                   = %zu\n", sizeof(Base));
    std::printf("sizeof(DerivedV)               = %zu\n", sizeof(DerivedV));
    std::printf("sizeof(std::function<void()>)  = %zu\n", sizeof(std::function<void()>));
    std::printf("sizeof(std::string)            = %zu\n", sizeof(std::string));
    std::printf("sizeof(std::vector<int>)       = %zu\n", sizeof(std::vector<int>));
}

Várható, illusztratív kimenet x86-64 LP64-en, GCC/Clang + libstdc++ mellett: Empty=1, Order1=16, Order2=24, offset d=8, AsMember=8, AsBase=4, AsNoUnique=4, Base=8, DerivedV=16, function=32, string=32, vector=24. Minden eltérés azt jelzi, hogy más ABI-n vagy más standard library-n fut a mérés — ami önmagában is tanulságos.

A locality-kapu egy összehasonlító mérés, amelynek elsődleges követelménye nem a gyorsaság, hanem hogy a két elrendezés ugyanazt számolja:

// locality_gate.cpp
// build: g++ -std=c++20 -O2 -Wall -Wextra locality_gate.cpp -o locality_gate
#include <chrono>
#include <cmath>
#include <cstdio>
#include <vector>

constexpr std::size_t N = 1u << 20;

struct AoS { float x, y, z, vx, vy, vz; };
struct SoA {
    std::vector<float> x, y, z, vx, vy, vz;
    explicit SoA(std::size_t n) : x(n), y(n), z(n), vx(n), vy(n), vz(n) {}
};

void step_aos(std::vector<AoS>& p, float dt) {
    for (auto& q : p) { q.x += q.vx * dt; q.y += q.vy * dt; q.z += q.vz * dt; }
}

void step_soa(SoA& s, float dt) {
    for (std::size_t i = 0; i < s.x.size(); ++i) {
        s.x[i] += s.vx[i] * dt;
        s.y[i] += s.vy[i] * dt;
        s.z[i] += s.vz[i] * dt;
    }
}

double checksum_aos(const std::vector<AoS>& p) {
    double s = 0.0;
    for (const auto& q : p) s += q.x + q.y + q.z;
    return s;
}

double checksum_soa(const SoA& s) {
    double acc = 0.0;
    for (std::size_t i = 0; i < s.x.size(); ++i) acc += s.x[i] + s.y[i] + s.z[i];
    return acc;
}

int main() {
    std::vector<AoS> aos(N, AoS{0.f, 0.f, 0.f, 1.f, 2.f, 3.f});
    SoA soa(N);
    for (std::size_t i = 0; i < N; ++i) {
        soa.x[i] = 0.f; soa.y[i] = 0.f; soa.z[i] = 0.f;
        soa.vx[i] = 1.f; soa.vy[i] = 2.f; soa.vz[i] = 3.f;
    }

    const float dt = 0.01f;
    const auto t0 = std::chrono::steady_clock::now();
    for (int k = 0; k < 100; ++k) step_aos(aos, dt);
    const auto t1 = std::chrono::steady_clock::now();
    for (int k = 0; k < 100; ++k) step_soa(soa, dt);
    const auto t2 = std::chrono::steady_clock::now();

    const double ca = checksum_aos(aos);
    const double cs = checksum_soa(soa);

    std::printf("aos  = %.6f\n", ca);
    std::printf("soa  = %.6f\n", cs);
    std::printf("diff = %.6e\n", std::fabs(ca - cs));
    std::printf("aos  ms = %.3f\n",
        std::chrono::duration<double, std::milli>(t1 - t0).count());
    std::printf("soa  ms = %.3f\n",
        std::chrono::duration<double, std::milli>(t2 - t1).count());
}

A kapu feltétele: a diff a lebegőpontos összegzési sorrend miatt nem nulla, de kicsi; a helyes ellenőrzés relatív tolerancia (diff / max(|aos|, 1.0) < 1e-5), nem bitazonosság. Csak ezután szabad az időket összevetni — és akkor is tudni kell, hogy a két ciklus nem feltétlenül azonos mértékben vektorizálódott. A mért idő önmagában nem bizonyíték semmire, ha a kapu nem teljesül.

37.3.8 Tipikus hibák és javításuk

  1. sizeof egyenlőnek feltételezése a tagok összegével. A padding miatt nem az; a helyes kiindulás az alignment round-up képlet és a offsetof/sizeof próba.
  2. EBO-ra épített API-szerződés. Az EBO és a [[no_unique_address]] is implementációs szinten érvényesül; stabil ABI-határon mérd és dokumentáld, ne feltételezd.
  3. Azonos típusú [[no_unique_address]] tagok átfedésének feltételezése. A szabvány különböző címeket követel, tehát nem fedhetnek át; a tömörítés elmarad.
  4. std::function allokációmentességének feltételezése. A puffer mérete implementációfüggő; allokációszámlálóval ellenőrizd.
  5. std::hardware_destructive_interference_size használata publikus headerben. Két TU eltérő értéket láthat, ami ODR-problémát okoz.
  6. AoS→SoA refaktor numerikus következmény nélkül. Az összegzési sorrend megváltozik; ha a determinizmus követelmény, a refaktor viselkedésváltozás, nem csak optimalizálás.

37.3.9 Összefoglaló

A C++ objektumlayout két rétegből áll: a szabvány szemantikai minimumából (nem nulla méret, megkülönböztethető címek, standard-layout és trivially copyable traitek) és az ABI konkrét szabályaiból (offsetek, padding, vptr, EBO alkalmazása). Az optimalizálás ezért mindig mérésből indul: layout-próbával ellenőrizzük a méreteket, allokációszámlálóval a rejtett heap-használatot, és correctness-kapuval a viselkedés azonosságát. Az EBO, a [[no_unique_address]], az SSO, a vptr és a small buffer mind implementációs részlet: lehet rájuk támaszkodni az adott laborprofilban, de nem lehet rájuk szerződést építeni. Az AoS/SoA döntés nem univerzális győztes, hanem a forró ciklus hozzáférési mintájából levezetett választás.

37.3.10 Feladatok

1. feladat (magyarázó). Számítsd ki kézzel a következő típus offsetjeit, sizeof-ját és igazítását x86-64 LP64-en: struct Rec { bool active; double value; int count; char tag; };. Majd rendezd át a tagokat, hogy a méret minimális legyen, és indokold az eredményt a round-up képlettel.

2. feladat (kódoló). Írj egy programot, amely eldönti egy adott callable-ről, hogy belefér-e a std::function kis pufferébe, allokációszámláló globális operator new segítségével. Mérd meg három különböző méretű lambdára, és rögzítsd a laborprofilban a sizeof(std::function<...>) értékét is.

3. feladat (diagnosztikai). Adott egy négyzetrácsos szimuláció std::vector<Cell> tárolóval, ahol egy szál a sejtek energy mezőjét, egy másik a temperature mezőjét frissíti, és a futásidő a szálszám növelésével nem javul. Fogalmazz meg két lehetséges okot, és adj mindkettőre javítást úgy, hogy a helyességi feltétel (a két mező frissítése között nincs adatverseny) megmaradjon.

37.3.11 Megoldások

1. megoldás. Az active offsetje 0, mérete 1. A value igazítása 8, ezért o=round_up(0+1,8)=8o = \operatorname{round\_up}(0+1, 8) = 8; a value a 8–15. bájtot foglalja. A count igazítása 4, o=round_up(16,4)=16o = \operatorname{round\_up}(16, 4) = 16. A tag a 20. bájtra kerül, a szerkezet vége 21, a szerkezet igazítása max(1,8,4,1)=8\max(1,8,4,1)=8, ezért sizeof=round_up(21,8)=24\operatorname{sizeof} = \operatorname{round\_up}(21, 8) = 24. Átrendezve { double value; int count; char tag; bool active; }: value 0–7, count 8–11, tag 12, active 13, vége 14, round_up(14,8)=16\operatorname{round\_up}(14, 8) = 16. Ellenőrzési feltétel: a sizeof 24-ről 16-ra csökken, miközben a tagok halmaza változatlan; a program offsetof-fal igazolja az offseteket.

2. megoldás. A globális operator new(std::size_t) és operator delete(void*) felülírása egy atomikus számlálóval (a globális változatot a program elején, a standard header-ek include-olása után definiáljuk). A mérés: a számlálót nullázzuk, létrehozunk egy std::function<void()>-t a vizsgált lambdából, majd kiolvassuk a számlálót. A std::function konstrukciója allokálhat, ha a callable nem fér a pufferbe; a másolás is allokálhat. Értelmezés: ha a számláló 0, a callable belefért; ha 1, heap-re került. Ellenőrzési feltétel: a mért sizeof(std::function<void()>) és a küszöbérték együtt konzisztens a számlálóval — ha nem, a mérés hibás (pl. a lambda zárójelben más objektumot is másol). Korlát: az eredmény target- és stdlib-verziófüggő, ezért a laborprofil része.

3. megoldás. Első ok: a Cell objektumok mindkét mezője ugyanabban a cache-line-ban van, tehát a két szál írása false sharinget okoz — a koherencia-protokoll pingpongoztatja a line-t. Javítás: a két mezőt külön tömbre bontjuk (SoA-jellegű felosztás), és a két tömböt alignas-szal cache-line határra igazítjuk. Második ok: a std::vector<Cell> átméretezése vagy a Cell nagy mérete miatt a bejárás memóriasávszélesség-korlátos, és a szálak ugyanazokat a line-okat olvassák — ez olvasási megosztás, ami nem adatverseny, de nem skálázódik. Javítás: particionálás tartományokra úgy, hogy minden szál külön, nem átfedő szeleten dolgozzon, vagy a mezők szétválasztása mellett blokkolt bejárás. Mindkét javításnál az ellenőrzési feltétel: a két mező frissítése továbbra is elkülönül (nincs szinkronizálatlan írás ugyanarra az objektumra), és a numerikus eredmény a tolerancián belül azonos a referencia-implementációval.