Š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
- ^ 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.
- ^ Vandevoorde, David; Josuttis, Nicolai (2002). Šablony C ++: Kompletní průvodce. Addison Wesley. ISBN 0-201-73484-2.
- ^ 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.
- ^ Abrahams, David; Gurtovoy, Aleksey (2004). Metaprogramování šablon C ++: koncepty, nástroje a techniky z Boost and Beyond. Pearson Education.
- ^ https://dlib.net
- ^ https://bitbucket.org/blaze-lib/blaze
- ^ „Uživatelská příručka Blitz ++“ (PDF). Citováno 12. prosince 2015.
- ^ "Zvyšte základní knihovnu lineární algebry". Citováno 25. října 2015.
- ^ Guennebaud, Gaël (2013). Vlastní: C ++ knihovna lineární algebry (PDF). Eurographics / CGLibs.
- ^ 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.
- ^ "Stan dokumentace". Citováno 27. dubna 2016.
- ^ „Vícedimenzionální pole s vysíláním a líným výpočtem“. Citováno 18. září 2017.
- ^ 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.