29.5 Execution policy és párhuzamos algoritmusok

A standard algoritmusok jelentős része C++17-től fogad egy úgynevezett végrehajtási policy (execution policy) paramétert, amely a hívó és a könyvtár közötti végrehajtási szerződést rögzíti. A policy nem gyorsítási kapcsoló: azt mondja meg, hogy a könyvtár milyen mértékű párhuzamosítást és milyen vektorizálást feltételezhet, ehhez képest viszont a callback (element access function) oldalán szigorú szinkronizációs és mellékhatás-korlátok érvényesek. Ez az alfejezet a policy-k pontos szemantikáját, a callback-szerződést, a kivételkezelés policy-függő viselkedését, valamint a backend- és linkfüggőségeket, illetve a gyakorlatban gyakran elrontott méretezési és élettartamkérdéseket tárgyalja. Az algoritmusok numerikus definícióját és kiértékelési sorrendjét a Numerikus algoritmusok és kiértékelési sorrend (29.4) rész tárgyalta, a konkurens élettartam-hibák taxonómiáját pedig a Konkurens élettartam és nehéz hibák (15.5) alfejezet; azokra itt csak célzottan hivatkozunk.

A szabályok forrása a forrásjegyzék [C++20] tétele: [execpol], [algorithms.parallel.exec] és [algorithms.parallel.exceptions]. A compiler- és libraryfüggő részleteket külön jelöljük. A seq_terminate.cpp próbát és a backend-megfigyeléseket a lab-gcc profilban futtattuk; a többi részlet a tanuló laborjában ellenőrizendő.

29.5.1 A négy policy és szerződésük

A <execution> fejléc a std::execution névtérben négy jelölőobjektumot definiál, mindegyik egy-egy címkéző típus inline constexpr példánya. A C++17-es alap hármat tartalmaz, a negyedik C++20-ban került be:

A seq alatt az elem-hozzáférések a hívó szálon, szekvenciálisan futnak, mint policy nélkül. A megfigyelhető viselkedés azonban nem teljesen azonos: a callbackből kiszökő kivétel seq alatt is std::terminate-et vált ki, policy nélkül viszont a hívóhoz propagálódik (lásd a kivételszakaszt). A par engedi, hogy a hívások több szálon fussanak, de egy adott szálon belül az elem-hozzáférések sorrendje továbbra is indeterminately sequenced – azaz nem interleave-elődnek, csak a szálak közötti sorrend nem determinisztikus. A par_unseq és az unseq ehhez képest megengedi, hogy a hívások ugyanazon a szálon belül is interleavelődjenek (utasításszintű párhuzamosság, SIMD-vektorizálás). A par és par_unseq esetén a hány szálon és melyik szálon fut egy hívás, a szabvány szerint nem specifikált; a szabvány azt is kimondja, hogy az implementáció ezeket a policy-kat akár szekvenciálisan is végrehajthatja.

Fontos következmény: a policy önmagában nem ígéri, hogy a futás gyorsabb lesz, sőt azt sem, hogy ténylegesen párhuzamosan fut. Ezért a policy megválasztása nem teljesítményoptimalizálás, hanem szemantikai döntés: mit engedhetsz meg a callbackben, és milyen garanciákat vállalsz a hívó oldalán. Egy további korlát: a range-alapú algoritmusok (std::ranges::sort, std::ranges::for_each, …) a C++20-as és C++23-as szabvány szerint nem fogadnak végrehajtási policy-t, csak az iteratorpáros overloadok. Ez a részlet a generálás időpontjában a rendelkezésre álló nyilvános draft állapotán alapul; verzióellenőrzést igényel.

29.5.2 Callback-szerződés: adatverseny és vectorization-unsafe műveletek

A par policy alatt a callback több szálon futhat, ezért a megosztott állapot védelme a hívó felelőssége. A nyelvi definíció ([C++20] [intro.races]): két hozzáférés ütközik, ha ugyanazt a memóriahelyet érik el, és legalább az egyik módosítja. Adatverseny akkor van, ha két ütköző hozzáférés különböző szálakon, egymáshoz képest rendezetlenül (egyik sem happens before a másik) történik, és legalább az egyik nem atomikus; az adatverseny nem definiált viselkedés. Három eset:

• olvasás/olvasás: nem ütközik — a megosztott, közben nem módosuló állapot szinkronizáció nélkül is olvasható;
• olvasás/írás: ütközik — védelem (atomikus típus, mutex vagy happens-before kapcsolat) nélkül adatverseny;
• írás/írás: ütközik — ugyanígy adatverseny.

Egy csak olvasó par callback (például egy előre felépített, változatlan keresőtáblából olvas) tehát szabályos. A gyakori hiba az írás/írás eset:

#include <algorithm>
#include <execution>
#include <vector>

int main() {
    std::vector<int> v(1'000'000, 1);
    int count = 0;
    std::for_each(std::execution::par, v.begin(), v.end(),
                  [&count](int) { ++count; });   // ADATVERSENY
}

A ++count nem oszthatatlan: olvasásból, növelésből és írásból álló olvasás–módosítás–írás, amelynek lépései két szál között összefésülődhetnek. A nyelv szintjén azonban nem az elveszett frissítés a lényeg, hanem az, hogy két szál rendezetlenül, nem atomikusan írja ugyanazt az objektumot: ez adatverseny, tehát nem definiált viselkedés, bármit is mutatna egy konkrét futás.

Buildjegyzőkönyv (lab-gcc profil). Ugyanezt a három esetet std::thread-del, -fsanitize=thread alatt is lefuttattuk (setarch -R-rel, mert a gép ASLR-beállítása mellett a TSan különben nem indul): két szál ugyanazon vektor olvasására a TSan nem jelzett, a két szálból végzett védetlen ++counter-re WARNING: ThreadSanitizer: data race jelentést adott. A std::execution::par a lab-gcc profilban TBB nélkül soros háttérrel fut, ezért ott a TSan nem tudná megmutatni a versenyt — a hiba ettől még a kódban van. A helyes megoldás vagy lokális akkumulátor (a callback csak a saját szála állapotát módosítja, és a végén egy csökkentés összegzi), vagy eleve redukciós algoritmus (std::reduce, std::transform_reduce), amelynél a könyvtár vállalja a részösszegek egyesítését. A par alatt az is megengedett, hogy a callback a saját lokális változóit módosítsa; a tiltás csak a szálak között megosztott állapotra vonatkozik.

A par_unseq (és a C++20-as unseq) ennél szigorúbb: a vektorizálás miatt tilos minden olyan művelet, amely a callback végrehajtását blokkolja, szinkronizálja, vagy ami a SIMD-interleave miatt nem lenne biztonságos. Ide tartozik a mutex, condition_variable, std::lock_guard, std::this_thread::sleep_for, sőt implementációfüggő mértékben az std::atomic használata is. A szabvány ezt úgy fogalmazza meg, hogy a par_unseq/unseq policy alatt az elem-hozzáférési függvény nem hívhat „vectorization-unsafe” műveletet, és a pontos tilalmi lista ellenőrzése a kiválasztott szabvány [algorithms.parallel.exec] szakaszában szükséges. Egy par alatt legális mutex használat tehát par_unseq alatt már UB.

29.5.3 Kivételviselkedés

A kivételkezelésnél két algoritmuscsaládot kell szétválasztani.

A szabvány ([algorithms.parallel.exceptions]) mind a négy szabványos policyra ugyanazt mondja: ha egy elem-hozzáférési függvény kivétellel lép ki, std::terminate hívódik. A szabály tehát nem a szálhatárhoz kötött, a seq sem kivétel. Egyetlen kivétel a könyvtár saját erőforráshiánya: ha az algoritmus nem tud ideiglenes tárolót szerezni a párhuzamos végrehajtáshoz, std::bad_alloc-ot dob, és ezt a hívó elkaphatja. Az implementáció által definiált további policy-k saját szabályt adhatnak. A szabály C++17 óta érvényes, és a C++20 nem lazított rajta. A különbséget egy próba mutatja:

// seq_terminate.cpp — C++20: a seq policy alatt is terminate
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <exception>
#include <execution>
#include <stdexcept>
#include <vector>

int main(int argc, char**) {
    std::set_terminate([] {
        std::puts("terminate");
        std::fflush(stdout);
        std::_Exit(42);
    });
    std::vector<int> v{1, 2, 3};
    auto fail = [](int x) { if (x == 2) throw std::runtime_error("x == 2"); };

    try {
        if (argc > 1)
            std::for_each(v.begin(), v.end(), fail);                       // policy nélkül
        else
            std::for_each(std::execution::seq, v.begin(), v.end(), fail);  // seq policy
    } catch (const std::exception& e) {
        std::printf("caught: %s\n", e.what());
    }
}

Buildjegyzőkönyv (lab-gcc profil, g++ -std=c++20 -Wall -Wextra -Wpedantic -O2). Argumentum nélkül (seq policy) a kimenet terminate, a kilépési kód 42, a külső catch nem fut. Argumentummal (policy nélkül) a kimenet caught: x == 2, a kilépési kód 0.

A gyakorlati következmény: bármely policy-s hívásnál, a seq-et is beleértve, a callbacknek gyakorlatilag noexcept-nek kell lennie. Ha a callback természeténél fogva hibázhat, a hibát a callbacken belül el kell kapni, adatként fel kell jegyezni, és a hívás visszatérése után kell eldönteni, mit tegyünk. Ez a minta illeszkedik az error_code, system_error és expected (25.4) alatt tárgyalt error_code/expected alapú hibapolicy-hoz. A feljegyzés módja viszont policyfüggő:

par_unseq és unseq alatt a mutex, a lock_guard és a blokkoló várakozás tilos. A heap-allokáció (push_back, std::make_exception_ptr, std::string építése) is kerülendő, mert az allokátor belül szinkronizálhat. A hibakódok tárolóját ezért a hívás előtt, a teljes bemenet méretére kell lefoglalni, és mindegyik elem csak a saját helyére írhat. Ha ez nem elég, például mert a hibához szöveges üzenetet vagy kivételt kell megőrizni, akkor par-ra vagy policy nélküli algoritmusra kell váltani.

// unseq_errors.cpp — C++20: hibagyűjtés par_unseq alatt, szinkronizáció nélkül
#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <execution>
#include <functional>
#include <numeric>
#include <vector>

enum class Err : std::uint8_t { ok = 0, negative, too_large };

// Nem dob, nem allokál, nem szinkronizál: par_unseq alatt is megengedett.
Err validate(int x) noexcept {
    if (x < 0) return Err::negative;
    if (x > 1000) return Err::too_large;
    return Err::ok;
}

int main() {
    const std::vector<int> in{5, -1, 7, 2000, 3, -4};
    std::vector<Err> codes(in.size());   // kapacitás a hívás ELŐTT lefoglalva

    // Minden elem a SAJÁT kimeneti helyére ír: nincs megosztott állapot.
    std::transform(std::execution::par_unseq, in.begin(), in.end(),
                   codes.begin(), validate);

    // Az összesítés a párhuzamos szakasz után, a hívó szálon.
    const auto failed = std::count_if(codes.begin(), codes.end(),
                                      [](Err e) { return e != Err::ok; });
    std::printf("failed=%td first_bad_index=%td\n", failed,
                std::find_if(codes.begin(), codes.end(),
                             [](Err e) { return e != Err::ok; }) - codes.begin());
}

Buildjegyzőkönyv (lab-gcc profil, g++ -std=c++20 -Wall -Wextra -Wpedantic -O2). A kimenet failed=3 first_bad_index=1, ASan/UBSan builddel is. (A lab-gcc profilban TBB nélkül a soros backend fut, így ez a futás a szerződés betartását, nem a párhuzamos végrehajtást igazolja.)

29.5.4 Backend, linkelés és támogatás

A szabvány előírja, hogy ezek a policy-k elérhetők, de a mögöttes végrehajtómotor implementációfüggő. A GCC/libstdc++ esetén a <execution> és a párhuzamos algoritmusok a Threading Building Blocks (TBB) könyvtárra épülnek; TBB nélkül a program vagy nem linkel, vagy a futás során csendben seq-re esik vissza – ez implementáció- és verziófüggő. A Clang/libc++ hasonlóan külső backendre támaszkodhat, az MSVC belső szálmedencét használ. A lab-gcc profilban (GCC 13.3, telepített TBB nélkül) ezt mértük: a <execution> lefordul, a libstdc++ a _PSTL_PAR_BACKEND_SERIAL soros backendet választja, mert a <tbb/tbb.h> nem érhető el. Egy par policyval futó for_each ilyenkor egyetlen szálon fut, és -ltbb nélkül is linkel; a -ltbb kapcsoló viszont cannot find -ltbb hibát ad. TBB-vel telepített környezetben a linkeléshez a fordításhoz hozzá kell adni a megfelelő könyvtárat:

# GCC + libstdc++, TBB-vel
g++ -std=c++20 -O2 par_sum.cpp -ltbb -o par_sum

# C++17 alternatíva ugyanahhoz a forráshoz
g++ -std=c++17 -O2 par_sum.cpp -ltbb -o par_sum

A támogatás ellenőrzésére a __cpp_lib_execution feature-test makró használható; ennek értéke jelzi, hogy a választott library melyik C++-verzió policy-készletét támogatja. A __has_include(<execution>) csak header-létezést jelez, nem azt, hogy a párhuzamos futtatás tényleg működik. A laborprofilban rögzíteni kell a compiler, a libstdc++/libc++ és a TBB pontos verzióját; e nélkül a „párhuzamosan fut” állítás nem reprodukálható.

29.5.5 Oversubscription és grain size

A par alatt a könyvtár jellemzően egy belső szálmedencét használ, amelynek mérete nagyságrendileg a std::thread::hardware_concurrency() értékéhez igazodik, de ezt a szabvány nem írja elő. Ha a par algoritmust egy már szálmedencében futó taskból hívjuk (például egy std::async-ból vagy egy szerver kérésfeldolgozó szálából), vagy ha a folyamat CPU-korlátos konténerben fut, akkor a medence és a hívó szálai egymással versengenek: ez az oversubscription, ami a teljesítményt a szekvenciális változat alá is viheti.

A másik véglet a grain size kérdése. Ha egy elemre jutó munka túl kicsi, a hívások szétdobálásának, a részeredmények egyesítésének és a szálak felébresztésének költsége nagyobb, mint a számítás. A policy mögötti könyvtár általában néhány mikroszekundum nagyságrendű per-task munkát tekint gazdaságosnak, de ez nem szabványos garancia, hanem empirikus megfigyelés. A helyes hozzáállás: először mérni, utána dönteni; és ha a mérés nem mutat javulást, a seq policy a helyes választás. A mérési protokollt a Profilozás, benchmark és cost model (37.4) alatt tárgyalt benchmark-módszertan szerint kell felépíteni, mert a puszta time parancs oversubscription és gyorsítótár-melegítés mellett félrevezető lehet.

29.5.6 Sorrendfüggő állapot és pointer lifetime

A par nem garantálja a feldolgozási sorrendet a szálak között; a par_unseq és az unseq még egy szálon belül sem. Ezért tilos a callback eredményét sorrendtől függően egy megosztott objektumba fűzni (push_back egy std::vector-ba par alatt adatverseny, par_unseq alatt UB). A pointer- és referencia-lifetime szempontból a par és par_unseq ugyanazt a fegyelmet kéri, mint bármelyik aszinkron hívás: a lambdában elfogott pointernek vagy referenciának az algoritmus teljes futása alatt érvényesnek kell maradnia, nem csak a hívás kiadásáig. Egy gyakori csapda, hogy a felhasználó egy lokális std::vector-ra mutató pointert fog el, miközben a vektort egy másik szálon felszabadítja; ez a Konkurens élettartam és nehéz hibák (15.5) alatt tárgyalt konkurens élettartam-hibák egy példánya, és az algoritmus semmilyen diagnosztikát nem ad rá. C++20-tól a std::span használható arra, hogy a callback ne pointer–méret párost kapjon, hanem hosszal rendelkező, nem tulajdonló nézetet; ez nem oldja meg az élettartamot, de legalább a félreértett méretezést kizárja.

29.5.7 Kidolgozott példa

A következő példa egyesített összeget számol par policyval. A redukció asszociatív és kommutatív műveletet (+) használ, az std::int64_t tartomány elegendő az 1..1 000 000 összegéhez (kb. $5 \cdot 10^{11}$), így túlcsordulás nem fenyeget. A printf a hívás után fut, nem a callbackben.

// par_sum.cpp
#include <cstdint>
#include <cstdio>
#include <execution>
#include <numeric>
#include <vector>

int main() {
    std::vector<std::int64_t> v(1'000'000);
    for (std::int64_t i = 0; i < static_cast<std::int64_t>(v.size()); ++i) {
        v[static_cast<std::size_t>(i)] = i + 1;
    }

    const std::int64_t s = std::reduce(
        std::execution::par, v.begin(), v.end(), std::int64_t{0});
    std::printf("sum = %lld\n", static_cast<long long>(s));
}

A reduce C++17-es, iteratoralapú overloadja fogad policy-t; a std::reduce(seq, ...) ugyanazt adja, mint a std::accumulate. TBB nélküli környezetben a program lefuthat, de a párhuzamosság nem garantált; a viselkedés verziófüggő. Egy header-szintű fallback:

#if defined(__cpp_lib_execution)
#  include <execution>
#  define BOOK_EXEC_PAR std::execution::par,
#else
#  define BOOK_EXEC_PAR
#endif

A makró bevezetése után std::reduce(BOOK_EXEC_PAR v.begin(), v.end(), std::int64_t{0}); mind C++17 előtt, mind C++17 után fordítható formát ad, bár a régi ágon a hívás szekvenciális marad.

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

A leggyakoribb tévedés, hogy a par policy-t automatikus gyorsításként kezeljük: kis vektorokon, dominánsan memóriafüggő műveleteknél (pl. nagy struktúrák másolása par transform-mal) vagy oversubscribed környezetben a szekvenciális változat gyorsabb lehet. A második gyakori hiba a callbacken belüli mutex vagy std::atomic használata par_unseq alatt – ez UB, nem „lassabb”. A harmadik: referencia szerint elfogott számláló növelése par alatt, ami adatverseny. A negyedik: kivétel dobása a callbackből par alatt, ami std::terminate-hez vezet, és nem ahhoz, hogy a hívó elkaphatja. Az ötödik: linkelés -ltbb nélkül, amit a fordító csak linkeléskor, nem fordításkor jelez.

29.5.9 Feladatok

1. feladat (diagnosztikai). Az alábbi kódrészlet par policyval fut. Add meg, mi a hiba, pontos nyelvi terminológiával, és mit tenne a program, ha a hiba „csak” logikai lenne.

std::vector<int> v(1'000'000, 1);
int acc = 0;
std::for_each(std::execution::par, v.begin(), v.end(),
              [&acc](int x) { acc += x; });

2. feladat (kódolási). Írj par policyval működő, kivételbiztos szimmetrikus összeget egy std::vector<std::int64_t>-re, ahol az elemek értéke legfeljebb $10^4$, a vektor hossza $10^6$. A callback ne dobjon kivételt, és ne használjon mutexet vagy atomot. Indokold az összeg típusválasztását és a policy-választást.

3. feladat (tervezési). Ugyanazt a feladatot oldd meg par_unseq policyval. Adj egy konkrét kódrészletet, amely par alatt legális, par_unseq alatt viszont UB, és magyarázd el, miért.

29.5.10 Megoldások

1. megoldás. A ++acc nem atomi művelet: a nyelvi memóriamodell [intro.races] definíciója szerint két szál ugyanazon objektumot egyszerre, nem synchronized módon olvassa és írja, ami data race. Adatverseny esetén a program viselkedése nem definiált: nem „elveszett frissítés”, hanem bármi megtörténhet, a fordító optimalizálhatja a ciklust, és a végeredmény nem reprodukálható. A helyes javítás std::reduce(std::execution::par, v.begin(), v.end(), 0LL) vagy lokális akkumulátor használata. Ellenőrzési feltétel: a javított kód minden futáson ugyanazt az összeget adja, és -fsanitize=thread alatt nem jelez.

2. megoldás. Az összeg maximuma $10^6 \cdot 10^4 = 10^{10}$, ami belefér std::int64_t-be, std::int32_t-be nem feltétlenül (LP64 alatt long is 64 bites, ILP32 alatt 32 bites – ezért int64_t). A megoldás:

std::int64_t s = std::reduce(std::execution::par, v.begin(), v.end(),
                             std::int64_t{0}, std::plus<>{});

A reduce asszociatív és kommutatív műveletet vár, a + az egész tartományon az. A callback noexcept: nem dob, nem hív lockot. Indoklás: par választása azért helyes, mert az összeg nagy, a művelet lokális és jól particionálható; seq választása is helyes lenne, ha a vektor kicsi.

3. megoldás. Ugyanaz a hívás par_unseq policyval megengedett, feltéve, hogy a callback vectorization-safe. Ami par alatt legális, de par_unseq alatt UB, az például:

std::mutex m;
std::for_each(std::execution::par, v.begin(), v.end(),
              [&m](std::int64_t x) {
                  std::lock_guard<std::mutex> lk(m);   // par alatt OK
                  global_vec.push_back(x);             // par_unseq alatt UB
              });

par alatt a lockolás megengedett (bár lassú); par_unseq alatt a SIMD-interleave miatt a lockolt szakasz nem vectorizable, és a szabvány szerint a callback nem hívhat vectorization-unsafe műveletet. A helyes megoldás par_unseq-hez: nincs globális mutex, nincs push_back egy megosztott tárolóba; a callback tisztán lokális eredményt ad vissza, amit std::transform_reduce vagy egy saját redukció egyesít. Ellenőrzési feltétel: -fsanitize=thread tiszta, és a policy cseréje nem változtatja meg az eredményt.

29.5.11 Összefoglaló

A végrehajtási policy négy értéke közül a seq a szekvenciális, a par a több szálon, de szálon belül rendezett, a par_unseq (C++17) és unseq (C++20) a vektorizált végrehajtást engedi meg. A policy megválasztása szemantikai vállalás: par alatt a callbacket meg kell védeni az adatverseny ellen, par_unseq/unseq alatt semmilyen blokkoló vagy szinkronizáló primitív nem használható. Mind a négy szabványos policynál, a seq-et is beleértve, a callbackből kiszökő kivétel std::terminate-hez vezet (csak a policy nélküli hívásnál propagálódik), ezért a hibát a callbacken belül adatként kell kezelni. A paralelizmust a backend (GCC/libstdc++ esetén TBB, -ltbb), az oversubscription és a grain size együtt határozza meg; a policy önmagában nem gyorsítási ígéret. Az algoritmus eredményét soha nem szabad sorrendfüggően, egy megosztott tárolóba írni, és a callbackben elfogott pointernek az algoritmus teljes futása alatt érvényesnek kell maradnia – ezek a szabályok a Konkurens élettartam és nehéz hibák (15.5) konkurens élettartam-szabályainak specializációi a párhuzamos algoritmusokra.