Šablony výrazů - Expression templates - Wikipedia

Šablony výrazů plocha C ++ metaprogramování šablon technika, která vytváří struktury představující výpočet v době kompilace, kde jsou výrazy hodnocena pouze podle potřeby produkovat efektivní kód pro celý výpočet.[1] Šablony výrazů tak umožňují programátorům obejít normální pořadí vyhodnocení jazyka C ++ a dosáhnout optimalizací jako např smyčková fúze.

Šablony výrazů vynalezli nezávisle Todd Veldhuizen a David Vandevoorde;[2][3] byl to Veldhuizen, kdo jim dal své jméno.[3] Jsou populární technikou pro implementaci lineární algebra software.[1]

Motivace a příklad

Zvažte představující knihovnu vektory a operace na nich. Jedna běžná matematická operace je přidání dvou vektorů u a protipo prvcích k vytvoření nového vektoru. Zřejmá implementace této operace v C ++ by byla přetížený operátor + který vrací nový vektorový objekt:

třída Vec {    std::vektor<dvojnásobek> elemy;  veřejnost:    Vec(size_t n) : elemy(n) {}    dvojnásobek &operátor[](size_t i)      { vrátit se elemy[i]; }    dvojnásobek operátor[](size_t i) konst { vrátit se elemy[i]; }    size_t velikost()               konst { vrátit se elemy.velikost(); }};Vec operátor+(Vec konst &u, Vec konst &proti) {    tvrdit(u.velikost() == proti.velikost());    Vec součet(u.velikost());    pro (size_t i = 0; i < u.velikost(); i++) {         součet[i] = u[i] + proti[i];    }    vrátit se součet;}

Uživatelé této třídy nyní mohou psát Vec x = a + b; kde A a b jsou oba případy Vec.

Problémem tohoto přístupu je, že složitější výrazy jako např Vec x = a + b + c jsou implementovány neefektivně. Implementace nejprve vytvoří dočasný vektor k zadržení a + b, potom vytvoří další vektor s prvky C přidáno. I s optimalizace návratové hodnoty toto přidělí paměť alespoň dvakrát a vyžaduje dvě smyčky.

Zpožděné vyhodnocení tento problém řeší a lze jej v C ++ implementovat tak, že to necháme operátor + vrátit objekt vlastního typu, řekněme VecSum, který představuje nevyhodnocený součet dvou vektorů nebo vektoru s a VecSumatd. Větší výrazy se pak efektivně vytvářejí expresní stromy které jsou hodnoceny pouze při přiřazení ke skutečnému Vec proměnná. K tomu je ale třeba projít stromy, aby se provedlo vyhodnocení, což je samo o sobě nákladné.[4]

Šablony výrazů implementují zpožděné vyhodnocení pomocí stromů výrazů, které existují pouze v době kompilace. Každé přiřazení k a Vec, jako Vec x = a + b + c, generuje nový Vec konstruktor v případě potřeby vytvořením instance šablony. Tento konstruktor pracuje na třech Vec; přidělí potřebnou paměť a poté provede výpočet. Provádí se tedy pouze jedno přidělení paměti.

Příklad implementace šablon výrazů vypadá následovně. Základní třída VecExpression představuje libovolný výraz s vektorovou hodnotou. Je zadán do šablony pro skutečný typ výrazu E které mají být provedeny podle podivně se opakující vzor šablony. Existence základní třídy, jako je VecExpression, není nezbytně nutná pro fungování šablon výrazů. Bude sloužit pouze jako typ argumentu funkce k rozlišení výrazů od jiných typů (všimněte si definice konstruktoru a operátoru Vec + níže).

 1 šablona <typename E> 2 třída VecExpression { 3   veřejnost: 4     dvojnásobek operátor[](size_t i) konst  5     { 6         // Delegování na typ skutečného výrazu. Tím se zabrání dynamickému polymorfismu (aka virtuální funkce v C ++) 7         vrátit se static_cast<E konst&>(*tento)[i]; 8     } 9     size_t velikost()               konst { vrátit se static_cast<E konst&>(*tento).velikost(); }10 };

The Vec třída stále ukládá souřadnice plně vyhodnoceného vektorového výrazu a stává se podtřídou VecExpression.

třída Vec : veřejnost VecExpression<Vec> {    std::vektor<dvojnásobek> elemy;  veřejnost:    dvojnásobek operátor[](size_t i) konst { vrátit se elemy[i]; }    dvojnásobek &operátor[](size_t i)      { vrátit se elemy[i]; }    size_t velikost() konst               { vrátit se elemy.velikost(); }    Vec(size_t n) : elemy(n) {}    // konstrukce vektoru pomocí seznamu inicializátorů     Vec(std::initializer_list<dvojnásobek> inic) : elemy(inic) {}    // Vec může být vytvořen z libovolného VecExpression, vynuceného jeho vyhodnocení.    šablona <typename E>    Vec(VecExpression<E> konst& expr) : elemy(expr.velikost()) {        pro (size_t i = 0; i != expr.velikost(); ++i) {            elemy[i] = expr[i];        }    }};

Součet dvou vektorů je reprezentován novým typem, VecSum, který je v šabloně na typech levé a pravé strany součtu, takže jej lze použít na libovolné páry vektorových výrazů. Přetížený operátor + slouží jako syntaktický cukr pro VecSum konstruktor.

 1 šablona <typename E1, typename E2> 2 třída VecSum : veřejnost VecExpression<VecSum<E1, E2> > { 3     E1 konst& _u; 4     E2 konst& _proti; 5  6 veřejnost: 7     VecSum(E1 konst& u, E2 konst& proti) : _u(u), _proti(proti) { 8         tvrdit(u.velikost() == proti.velikost()); 9     }10 11     dvojnásobek operátor[](size_t i) konst { vrátit se _u[i] + _proti[i]; }12     size_t velikost()               konst { vrátit se _proti.velikost(); }13 };14   15 šablona <typename E1, typename E2>16 VecSum<E1, E2>17 operátor+(VecExpression<E1> konst& u, VecExpression<E2> konst& proti) {18    vrátit se VecSum<E1, E2>(*static_cast<konst E1*>(&u), *static_cast<konst E2*>(&proti));19 }

S výše uvedenými definicemi výraz a + b + c je typu

VecSum<VecSum<Vec, Vec>, Vec>

tak Vec x = a + b + c vyvolá templát Vec konstruktor s tímto typem jako jeho E argument šablony. Uvnitř tohoto konstruktoru je tělo smyčky

elemy[i] = expr[i];

je efektivně rozšířen (podle rekurzivních definic operátor + a operátor[] u tohoto typu) až

elemy[i] = A.elemy[i] + b.elemy[i] + C.elemy[i];

bez nutnosti dočasných vektorů a pouze jeden průchod každým paměťovým blokem.

Základní použití:

 1 int hlavní() { 2     Vec v0 = {23.4,12.5,144.56,90.56}; 3     Vec v1 = {67.12,34.8,90.34,89.30}; 4     Vec v2 = {34.90,111.9,45.12,90.5}; 5      6     // Následující přiřazení zavolá ctor Vec, který přijímá typ  7     // `VecExpression  const &`. Poté rozbalte tělo smyčky na  8     // a.elems [i] + b.elems [i] + c.elems [i] 9     Vec sum_of_vec_type = v0 + v1 + v2; 10 11     pro (size_t i=0; i<sum_of_vec_type.velikost(); ++i)12         std::cout << sum_of_vec_type[i] << std::konec;13 14     // Aby se zabránilo vytváření jakéhokoli dalšího úložiště, kromě v0, v1, v215     // lze provést následující (Testováno s C ++ 11 na GCC 5.3.0)16     auto součet = v0 + v1 + v2;17     pro (size_t i=0; i<součet.velikost(); ++i)18         std::cout << součet[i] << std::konec;19     // Pozorujte, že v tomto případě bude typid (součet) VecSum , Vec>20     // a toto zřetězení operací může pokračovat.21 }

Aplikace

Autoři knihoven shledali šablony výrazů obzvláště užitečné pro lineární algebru, tj. Pro práci s vektory a matice čísel. Mezi knihovnami využívajícími expresní šablony jsou Dlib,[5] Pásovec, Požár,[6] Blitz ++,[7] Zvýšit uBLAS,[8] Vlastní,[9] POOMA,[10] Stan Matematická knihovna,[11] a xtensor.[12] Šablony výrazů mohou také urychlit C ++ automatické rozlišení implementace,[13] jak je ukázáno v Adept knihovna.

Mimo vektorové matematiky je Spirit parser framework používá k vyjádření šablony výrazů formální gramatiky a sestavit je do analyzátorů.

Reference

  1. ^ A b Matsuzaki, Kiminori; Emoto, Kento (2009). Implementace paralelních skeletů vybavených fúzí pomocí šablon výrazů. Proc. Int'l Symp. o implementaci a aplikaci funkčních jazyků. 72–89.
  2. ^ Vandevoorde, David; Josuttis, Nicolai (2002). Šablony C ++: Kompletní průvodce. Addison Wesley. ISBN  0-201-73484-2.
  3. ^ A b Veldhuizen, Todd (1995). „Šablony výrazů“. Zpráva v C ++. 7 (5): 26–31. Archivovány od originál dne 10. února 2005.
  4. ^ Abrahams, David; Gurtovoy, Aleksey (2004). Metaprogramování šablon C ++: koncepty, nástroje a techniky z Boost and Beyond. Pearson Education.
  5. ^ https://dlib.net
  6. ^ https://bitbucket.org/blaze-lib/blaze
  7. ^ „Uživatelská příručka Blitz ++“ (PDF). Citováno 12. prosince 2015.
  8. ^ "Zvyšte základní knihovnu lineární algebry". Citováno 25. října 2015.
  9. ^ Guennebaud, Gaël (2013). Vlastní: C ++ knihovna lineární algebry (PDF). Eurographics / CGLibs.
  10. ^ Veldhuizen, Todd (2000). Právě když jste si mysleli, že váš malý jazyk je bezpečný: „Šablony výrazů“ v Javě. Int'l Symp. Generativní a komponentové softwarové inženýrství. CiteSeerX  10.1.1.22.6984.
  11. ^ "Stan dokumentace". Citováno 27. dubna 2016.
  12. ^ „Vícedimenzionální pole s vysíláním a líným výpočtem“. Citováno 18. září 2017.
  13. ^ Hogan, Robin J. (2014). "Rychlá reverzní automatická diferenciace pomocí šablon výrazů v C ++" (PDF). ACM Trans. Matematika. Softw. 40 (4): 26:1–26:16.