28.6 Tárolóválasztási és invalidációs labor

A tárolóválasztás a gyakorlatban ritkán dől el pusztán aszimptotikus jelöléssel. Egy connection registry esetében legalább négy kérdésre kell egyszerre válaszolni: mennyi a keresés, a beszúrás és a törlés aránya; mekkora az elem; szükséges-e, hogy egy korábban kiadott hivatkozás érvényes maradjon; és mennyi allokációt engedhetünk meg egy műveletre. Ez az alfejezet egy labor felépítését adja, amelyben ugyanazt a registry-interfészt több háttértárolóval implementáljuk, majd a mérést és az érvényességi szerződést együtt értékeljük. A tárolók egyedi műveleteinek felsorolása nem itt történik: a unordered tárolók és adapterek szerződését az unordered tárolók és container adapterek, a szövegtulajdonlás kérdését a std::string, std::string_view és szövegownership tárgyalta, a diagnosztikai eszközöket pedig az ASan, UBSan, MSan, TSan és Valgrind vezette be. Itt ezekre építünk.

28.6.1 Az érvényességi szerződés rögzítése a mérés előtt

A labor tárgya egy connection registry: olyan asszociatív adatszerkezet, amely egy stabil azonosítóhoz (Key, itt std::uint64_t) egy kapcsolat leíró objektumát rendeli, és támogatja a find, insert, erase műveleteket, valamint a bejárást. A mérés szempontjából a lényeg nem az, hogy milyen gyorsan fut egy for ciklus, hanem hogy milyen megfigyelhető szerződést vállalunk az API-ban.

Pontos definíció: a registry borrowed pointer szerződése azt mondja ki, hogy a find által visszaadott Entry* érvényes marad mindaddig, amíg a hivatkozott bejegyzés létezik, és a hívó nem hajt végre olyan műveletet, amely a tároló dokumentált invalidációs szabályai szerint érvényteleníti. Feltétel: az Entry objektumot a tároló birtokolja (nem a hívó), és a hívó a pointert nem tárolja tovább a bejegyzés törlése után. Ha ezt a szerződést vállaljuk, akkor a std::vector bizonyos műveletek mellett nem alkalmas háttértároló, függetlenül attól, hogy a mérése milyen számot ad.

Ugyanilyen fontos, hogy a laborban három, egymással nem keverhető állítástípus szerepel:

1. szabványos követelmény — például hogy a std::vector elemei folytonosak, vagy hogy a std::map keresése logaritmikus;
2. implementációs viselkedés — például a debug iterator mód konkrét makróneve, vagy egy adott libstdc++/libc++ kiadás rehash-politikája;
3. mért eredmény — az adott laborprofilban, adott gépen, adott műveleti mix mellett kapott szám.

A három különböző bizonyítékerejű, ezért külön naplózandó. A generáláskor nem állt rendelkezésre forrásszöveg és nem futott mérés; az alábbi táblázat a tananyag által összefoglalt követelménykép, amelyet a labornak a kiválasztott szabvány megfelelő szakaszával ellenőriznie kell, a futási számok pedig kiinduló hipotézisek, nem eredmények.

28.6.2 Összehasonlító szerződéstábla

A táblázat olvasata három döntési tengelyt ad. Az első a locality: a vector az egyetlen, amely bejáráskor egyetlen összefüggő memóriaszakaszon halad, ezért iterációra és a teljes registry periodikus feldolgozására akkor is jobb lehet, ha a find lassabb. A második a stabilitás: ha az API pointert ad ki, a vector és a deque középső műveletei kizárják egymást a szerződéssel, a csomópontos tárolók viszont pontosan azt nyújtják, amit a szerződés ígér. A harmadik az allokáció: a stabilitási követelmény a gyakorlatban csomópontonkénti allokációt kényszerít ki, ami elemzési költséget és gyengébb localityt hoz — ez implementációs következmény, nem tételes szabály.

Megjegyzendő, hogy a find oszlopban a sorozattárolóknál lineáris keresést feltételezünk. Rendezve tartott vector esetén a keresés $O(\log n)$ lehetne, de a beszúrás továbbra is $O(n)$ marad, és minden középső beszúrás érvényteleníti a hivatkozásokat — a stabilitási szerződést ez sem teljesíti. A választás tehát nem a keresési komplexitás minimalizálása, hanem a műveleti mix és az érvényességi igény együttes kielégítése.

28.6.3 Kidolgozott példa: egy interfész, három háttértároló

A labor egyetlen fordítható fájlból áll. A számláló allocator és a determinisztikus álvéletlen sorozat együtt biztosítja, hogy az allokációszám is megfigyelhető legyen, ne csak az idő.

// registry_lab.cpp — ISO C++20
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <map>
#include <new>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

namespace mem {
inline std::size_t allocs = 0;
inline std::size_t bytes  = 0;
inline void reset() { allocs = 0; bytes = 0; }
}

template <class T>
struct counting_allocator {
    using value_type = T;
    counting_allocator() = default;
    template <class U> counting_allocator(const counting_allocator<U>&) noexcept {}

    T* allocate(std::size_t n) {
        ++mem::allocs;
        mem::bytes += n * sizeof(T);
        return static_cast<T*>(::operator new(n * sizeof(T)));
    }
    void deallocate(T* p, std::size_t) noexcept { ::operator delete(p); }

    template <class U> bool operator==(const counting_allocator<U>&) const noexcept { return true; }
    template <class U> bool operator!=(const counting_allocator<U>&) const noexcept { return false; }
};

struct Entry {
    std::string   peer;    // "10.0.0.7:5432"
    std::uint16_t weight;
};
using Key = std::uint64_t;
using Pair = std::pair<Key, Entry>;

// Sorozat-alapú háttértároló: lineáris keresés, a végére szúrunk be.
template <class Seq>
class SeqRegistry {
public:
    Entry* find(Key id) {
        auto it = std::find_if(seq_.begin(), seq_.end(),
                               [id](const auto& kv) { return kv.first == id; });
        return it == seq_.end() ? nullptr : &it->second;
    }
    Entry& insert(Key id, Entry e) {
        seq_.emplace_back(id, std::move(e));
        return seq_.back().second;
    }
    std::size_t erase(Key id) {
        return std::erase_if(seq_, [id](const auto& kv) { return kv.first == id; });
    }
    std::size_t size() const { return seq_.size(); }
private:
    Seq seq_;
};

// Asszociatív háttértároló: a find/erase a tároló saját művelete.
template <class Ass>
class AssRegistry {
public:
    Entry* find(Key id) {
        auto it = map_.find(id);
        return it == map_.end() ? nullptr : &it->second;
    }
    Entry& insert(Key id, Entry e) {
        auto [it, inserted] = map_.emplace(id, std::move(e));
        (void)inserted;
        return it->second;
    }
    std::size_t erase(Key id) { return map_.erase(id); }
    std::size_t size() const { return map_.size(); }
private:
    Ass map_;
};

using VecReg  = SeqRegistry<std::vector<Pair, counting_allocator<Pair>>>;
using MapReg  = AssRegistry<std::map<Key, Entry, std::less<Key>,
                                   counting_allocator<std::pair<const Key, Entry>>>>;
using HashReg = AssRegistry<std::unordered_map<Key, Entry, std::hash<Key>, std::equal_to<Key>,
                                   counting_allocator<std::pair<const Key, Entry>>>>;

struct Lcg {                       // determinisztikus, ismételhető
    std::uint64_t s;
    std::uint64_t next() { s = s * 6364136223846793005ULL + 1442695040888963407ULL; return s >> 33; }
};

template <class Reg>
void run(const char* name, std::size_t n_ops, unsigned hit_percent) {
    Reg reg;
    Lcg rng{0xC0FFEEu};
    std::uint64_t next_id = 1;
    std::size_t hits = 0;

    mem::reset();
    auto t0 = std::chrono::steady_clock::now();
    for (std::size_t i = 0; i < n_ops; ++i) {
        std::uint64_t r = rng.next() % 100;
        if (r < hit_percent && reg.size() > 0) {
            if (reg.find(1 + rng.next() % next_id)) ++hits;      // találat vagy tévesztés
        } else if (r < 95) {
            reg.insert(next_id++, Entry{"10.0.0.1:5432", 1});
        } else if (reg.size() > 0) {
            reg.erase(1 + rng.next() % next_id);
        }
    }
    auto t1 = std::chrono::steady_clock::now();
    double ns = std::chrono::duration<double, std::nano>(t1 - t0).count() / double(n_ops);
    std::printf("%-10s live=%zu  %.1f ns/op  hit=%zu  allocs=%zu  bytes=%zu\n",
                name, reg.size(), ns, hits, mem::allocs, mem::bytes);
}

int main() {
    constexpr std::size_t N = 20'000;   // a lineáris változat miatt kicsi
    run<VecReg>("vector",        N, 70);
    run<MapReg>("map",           N, 70);
    run<HashReg>("unordered",    N, 70);
}

g++ -std=c++20 -O2 -Wall -Wextra -o registry_lab registry_lab.cpp
# vagy: clang++ -std=c++20 -O2 -Wall -Wextra -o registry_lab registry_lab.cpp

A kód felépítése szándékosan az API-invariánst állítja előtérbe: mindhárom find Entry*-ot ad, tehát mindhárom ugyanazt a szerződést ígéri. A VecReg ezt az ígéretet csak addig tudja betartani, amíg nem történik újratárolás vagy középső törlés — a következő szakasz pont ezt a rést mutatja meg. A kimenet alakja: élő elemszám, nanoszekundum/művelet, találatszám, allokációszám és allokált byte. A mérés nem futott le a generáláskor, ezért a konkrét számok helyén a labornak kell kitöltenie a saját profilját; az összehasonlítás csak azonos gépen, azonos fordítóval és azonos N-nel értelmes.

28.6.4 Allokációszám és inputeloszlás

A számláló allocator önmagában is tanulságos, de csak akkor, ha ismerjük az eloszlást. Ugyanaz a 70% keresés / 25% beszúrás / 5% törlés mix két különböző terhelést jelent, ha az azonosítók egy szűk, forró halmazból kerülnek ki (sok találat, rövid láncok), és egészen mást, ha egyre növekvő, hideg azonosítótartományból (kevés találat, hosszú láncok a hash-táblában). A find arányt ezért nem elég százalékban rögzíteni: a találati arányt és az azonosító-eloszlást is naplózni kell, különben a mért ns/op két futás között összemérhetetlen.

Vázlat az allokációszámról. Ha a vector kapacitása egy $k$ hosszúságú szakaszon duplázódik, akkor $n$ beszúrás után a növesztések $g$ száma kielégíti a $2^{g} \ge n$ feltételt, azaz $g \le \lceil \log_2 n \rceil$. A teljes allokációszám tehát nagyságrendileg $1 + \lceil \log_2 n \rceil$, nem $n$. Ezzel szemben a referencia-stabil csomópontos tárolók minden beszúrásnál külön csomópontot allokálnak, így az allokációszám lineáris az elemek számában, és a unordered_map ehhez még a bucket-tömb újraépítését is hozzáadja rehashkor. Ez a magyarázat miért fontos: a vector allokációs költsége amortizáltan kicsi, de éppen az újratárolás az, ami a hivatkozásokat érvényteleníti — a két tulajdonság ugyanabból a mechanizmusból ered. Megjegyzendő, hogy a növesztési tényező nem szabályozott, ezért a konkrét lépésszám implementációfüggő, és a labornak rögzítenie kell a használt standard library kiadását.

Az allokációszám mérésekor maga a számláló allocator is torzít: megnöveli az allokációs útvonal költségét, és a map/unordered_map esetében minden csomópont-allokációt megfigyel. Ez elfogadható, ha a naplóban jelezzük, hogy az időeredmény instrumentált; az allokációszám viszont éppen azért hasznos, mert kevésbé zajos, mint az idő.

28.6.5 A dangling példa külön futtatva

A következő fájl szándékosan hibás tanítási példa, nem része a labor helyes megoldásának.

// dangling.cpp — SZÁNDÉKOSAN HIBÁS: nem definiált viselkedés
#include <string>
#include <utility>
#include <vector>

struct Entry { std::string peer; };
std::vector<Entry> g_registry;

Entry* register_peer(std::string peer) {
    g_registry.push_back(Entry{std::move(peer)});
    return &g_registry.back();          // (1) a pointer a vektor egyik elemére mutat
}

int main() {
    Entry* a = register_peer("10.0.0.1:5432");
    Entry* b = register_peer("10.0.0.2:5432");   // (2) újratárolás: az elem elköltözött
    (void)b;
    return a->peer.empty() ? 1 : 0;              // (3) UB: dangling pointer olvasása
}

A hiba mechanizmusa pontos: a push_back a (2) pontban új puffert allokál, az elemeket átmásolja, a régit felszabadítja, így a egy felszabadított tárolóra mutat. Azért kell külön fájlban futtatni, hogy a diagnosztika egyértelmű legyen:

g++ -std=c++20 -g -fsanitize=address -o dangling dangling.cpp && ./dangling

A laborban elvárt diagnosztika tipikusan heap-use-after-free jelentés; a tényleges üzenetet a felhasználó mérése rögzíti, nem ez a szöveg. A hiba latens voltát az magyarázza, hogy ha a kapacitás elegendő lett volna, nem történik újratárolás, és a program „működni látszik”. Ezért a reserve nem javítás: csak elhalasztja a hibát, a szerződést nem teljesíti. Helyes javítások: (a) index vagy stabil azonosító visszaadása pointer helyett, és minden hozzáférésnél újrakeresés; (b) „generációs” handle, amely a törlést is detektálja; (c) olyan háttértároló választása (deque végbeszúrásra, list, map, unordered_map), amelynek a hivatkozás-stabilitása illeszkedik az API-hoz. A find-nak visszaadott pointer csak akkor maradhat, ha a erase és a beszúrás dokumentált hatása összeegyeztethető a szerződéssel.

28.6.6 Debug iterator mód mint implementációs diagnosztika

A libstdc++ _GLIBCXX_DEBUG makróval fordult programban a szabványos tárolók iterátorai ellenőrzöttek: a program futás közben jelez, ha érvénytelenített iterátort használunk, vagy ha két különböző tárolóhoz tartozó iterátort hasonlítunk össze. A laborban ez az az eszköz, amely a szabványos érvénytelenségi szabályokat tesztelhetővé teszi:

g++ -std=c++20 -g -D_GLIBCXX_DEBUG -o registry_dbg registry_lab.cpp

Két korlátot rögzíteni kell. Egyrészt a debug mód ABI-t változtat, ezért egy debug- és egy nem debug-fordítású objektum nem linkelhető össze megbízhatóan — a labor ezt külön buildcélként kezelje, ne keverje a release mátrixba. Másrészt a nyers pointereket és a std::string_view-kat a debug mód nem követi: a dangling.cpp hibája _GLIBCXX_DEBUG alatt is rejtve maradhat, mert az nem iterátorhasználat. A libc++ debug eszközeinek pontos makróneve és viselkedése verziófüggő, ezért a labornak a választott libc++ kiadás dokumentációjában kell ellenőriznie — ez implementációfüggő részlet, nem szabványos követelmény.

28.6.7 Benchmark és API-invariáns együttes értékelése

A döntési eljárás négy lépésből áll, ebben a sorrendben. Először rögzítjük az API-invariánst: ki ad ki pointert, meddig él, mi invalidálja. Másodszor kizárjuk azokat a tárolókat, amelyek a szabványos invalidációs szabályaikkal nem tudják betartani ezt az invariánst — itt a Big-O még nem szerepel. Harmadszor a megmaradt jelölteket a műveleti mix és az inputeloszlás alapján mérjük, és a mérést az allokációszámmal, valamint az instrumentáltság tényével együtt naplózzuk. Negyedszer ellenőrizzük, hogy a mérés nem „javította-e ki” csendben a szerződést: ha a gyorsabb változat csak azért gyors, mert a pointert a hívó tárolja, akkor nem ugyanazt az API-t mértük. Az azonos N hiánya is csapda: a vector lineáris keresése miatt a három implementációt azonos N-en kell összevetni, és külön növelési kísérlettel kell megmutatni, hogyan skálázódik az egyes változat — a nagyobb N-en kapott kisebb ns/op önmagában nem összehasonlítható.

28.6.8 Tipikus hibák

A leggyakoribb hiba, hogy a mérés a szerződés rögzítése előtt indul, és a végén a leggyorsabb változatot választjuk, amely viszont dangling pointert ad. A második, hogy valaki a reserve-t tekinti a stabilitás bizonyítékának. A harmadik, hogy a find lineáris keresését összekeverik a vector keresési komplexitásával, és azt állítják, hogy a vector mindenre $O(n)$. A negyedik, hogy a debug iterátor módot a teljes release buildre kapcsolják, és ABI-inkompatibilitásból eredő hibát diagnosztizálnak. Az ötödik, hogy a benchmark eredményét forrásként idézik: egy mért szám nem szabványos követelmény, és nem érvényes más gépen, más adateloszlással.

28.6.9 Összefoglaló

A tárolóválasztás három, egymástól függetlennek tűnő, valójában összefüggő döntés: mi a műveleti mix, milyen érvényességi szerződést vállal az API, és mennyi allokációt engedhetünk meg. A vector folytonos és olcsón növekszik amortizáltan, de újratároláskor minden hivatkozást érvénytelenít. A deque végbeszúrásnál stabil referenciákat ad. A list, map és unordered_map csomópontos, ezért hivatkozás-stabil, cserébe allokációintenzív és localityben gyengébb. A mérés csak a szerződés rögzítése után, az inputeloszlás naplózásával és az instrumentáltság jelölésével értékes.

28.6.10 Feladatok

1. Magyarázó. Adott egy registry, amelyben 90% keresés, 8% beszúrás, 2% törlés van, az elemek körülbelül 200 bájtosak, és az API Entry*-ot ad ki, amelynek a bejegyzés törléséig érvényesnek kell maradnia. Válasszon tárolót, és indokolja a választást a szerződésből kiindulva, nem Big-O alapján.
2. Kódolási. Javítsa a dangling.cpp hibáját handle-alapú API-vá: a find ne pointert, hanem egy Handle értéket adjon vissza, amelyből a bejegyzés a registry egy get(Handle) műveletével érhető el, és a törölt handle-t a get jelezze. Mutassa meg, hogy a javított változat a vector megtartásával is betartja a szerződést.
3. Diagnosztikai. Egy teszt release módban átmegy, _GLIBCXX_DEBUG alatt viszont elhasal „attempt to use invalidated iterator” üzenettel. Fogalmazza meg, milyen hibaosztályra utal ez, és miért nem jelentené ezt a hibát, ha a program nyers pointerrel dolgozna.
4. Mérés-értelmezési. Két futás: vector, N = 20000, 40 ns/op; unordered_map, N = 2000000, 25 ns/op. Milyen további adat hiányzik ahhoz, hogy ez az összehasonlítás érvényes legyen?

28.6.11 Megoldások

1. megoldás. A döntő feltétel a hivatkozás-stabilitás: a find által adott pointernek a törlésig érvényesnek kell maradnia. A vector ezt nem teljesíti, mert a beszúrás újratároláskor minden hivatkozást érvénytelenít; a reserve csak elhalasztja a problémát, nem szerződés. A deque végbeszúrásnál stabil referenciákat ad, de a középső törlés/beszúrás érvénytelenít, és a find lineáris; a list stabil, de keresése lineáris, ami 90% keresés mellett rossz; ezért a std::unordered_map a természetes jelölt: átlagos $O(1)$ keresés, hivatkozás-stabil, a rehash csak az iterátorokat érvényteleníti. Ellenőrzési feltétel: a válasznak szerepelnie kell benne, hogy a rehash-re vonatkozó állítás a referenciákra és az iterátorokra eltérő, és hogy ez a labor profiljában ellenőrizendő. Ha az API rendezett bejárást is megkövetel, a std::map a helyes választás, ugyanazzal a stabilitási érvvel.

2. megoldás. A lényeg, hogy a hívó ne tárolhasson nyers pointert, hanem egy (azonosító, generáció) párt, és a get a tárban újrakeressen; így a vector újratárolása nem jelent szerződésszegést, mert a handle nem mutat memóriára. Vázlat: struct Handle { Key id; std::uint32_t gen; };, a registry minden bejegyzésnél generációszámlálót tart, erasekor növeli, get(h) pedig megkeresi az azonosítót, és ha a tárolt generáció nem egyezik, nullptr-t ad. Így a törölt handle get-je tévesztést ad, nem dangling olvasást. A find helyett a belső keresés maradhat lineáris; a szerződés a pointer helyett a handle érvényességén nyugszik. Ellenőrzési feltétel: a törölt bejegyzés handle-jével hívott get nullptr, és a vector újratárolása után kiadott régi handle továbbra is a helyes bejegyzést találja meg.

3. megoldás. A „use invalidated iterator” üzenet arra utal, hogy a program egy olyan iterátort (vagy abból származtatott pointert) használt, amelyet egy korábbi beszúrás, törlés vagy rehash érvénytelenített. Ez az iterátor-érvénytelenségi hibaosztály. Nyers pointerrel ez a diagnosztika nem jelentkezne, mert a debug mód a szabványos iterátorokat ellenőrzi, a nyers pointereket nem követi; a pointeres változat ugyanazt a hibát hordozhatja, csak láthatatlanul. Ezért a laborban az iterátor-alapú és a pointer-alapú változatot külön kell futtatni, és a pointeres esetre ASan-t kell használni. Ellenőrzési feltétel: a válasz megkülönbözteti a szabványos érvénytelenségi szabályt, az implementáció diagnosztikai képességét és a mérési megfigyelést.

4. megoldás. Hiányzik legalább: (a) azonos N-en mért érték, vagy növelési görbe mindkét tárolóra; (b) a műveleti mix és a találati arány; (c) az allokációszám és az instrumentáltság ténye; (d) a fordító, a standard library kiadása, az optimalizálási szint és a hardver; (e) a minta szórása, nem egyetlen futás. Ezek nélkül a két szám két különböző kísérlet, nem összehasonlítás. Ellenőrzési feltétel: a válasz kimondja, hogy a nagyobb N-en kapott kisebb ns/op nem bizonyíték a gyorsabb tárolóra.