Expression templates are a C++ template metaprogramming technique that builds structures representing a computation at compile time, where expressions are evaluated only as needed to produce efficient code for the entire computation.[1] Expression templates thus allow programmers to bypass the normal order of evaluation of the C++ language and achieve optimizations such as loop fusion.
Expression templates were invented independently by Todd Veldhuizen and David Vandevoorde;[2]{{rp|341}}[3] it was Veldhuizen who gave them their name.{{r|TMP02}}{{rp|341}} They are a popular technique for the implementation of linear algebra software.{{r|matsuzaki}}
Motivation and example
Consider a library representing vectors and operations on them. One common mathematical operation is to add two vectors {{math|u}} and {{math|v}}, element-wise, to produce a new vector. The obvious C++ implementation of this operation would be an overloaded {{mono|operator+}} that returns a new vector object:
assert(u.size() == v.size()); Vec sum(u.size()); for (size_t i = 0; i < u.size(); i++) { sum[i] = u[i] + v[i]; } return sum;
}
Users of this class can now write {{mono|Vec x {{=}} a + b;}} where {{mono|a}} and {{mono|b}} are both instances of {{mono|Vec}}.
A problem with this approach is that more complicated expressions such as {{mono|Vec x {{=}} a + b + c}} are implemented inefficiently. The implementation first produces a temporary vector to hold {{mono|a + b}}, then produces another vector with the elements of {{mono|c}} added in. Even with return value optimization this will allocate memory at least twice and require two loops.
Delayed evaluation solves this problem, and can be implemented in C++ by letting {{mono|operator+}} return an object of a custom type, say {{mono|VecSum}}, that represents the unevaluated sum of two vectors, or a vector with a {{mono|VecSum}}, etc. Larger expressions then effectively build expression trees that are evaluated only when assigned to an actual {{mono|Vec}} variable. But this requires traversing such trees to do the evaluation, which is in itself costly.[4]
Expression templates implement delayed evaluation using expression trees that only exist at compile time. Each assignment to a {{mono|Vec}}, such as {{mono|Vec x {{=}} a + b + c}}, generates a new {{mono|Vec}} constructor if needed by template instantiation. This constructor operates on three {{mono|Vec}}; it allocates the necessary memory and then performs the computation. Thus only one memory allocation is performed.
An example implementation of expression templates looks like the following. A base class {{mono|VecExpression}} represents any vector-valued expression. It is templated on the actual expression type {{mono|E}} to be implemented, per the curiously recurring template pattern.
// construct vector using initializer list Vec(std::initializer_listinit){ for(auto i:init) elems.push_back(i); }
// A Vec can be constructed from any VecExpression, forcing its evaluation. template Vec(VecExpression const& vec) : elems(vec.size()) { for (size_t i = 0; i != vec.size(); ++i) { elems[i] = vec[i]; } }
};
The sum of two vectors is represented by a new type, {{mono|VecSum}}, that is templated on the types of the left- and right-hand sides of the sum so that it can be applied to arbitrary pairs of vector expressions. An overloaded {{mono|operator+}} serves as syntactic sugar for the {{mono|VecSum}} constructor.
With the above definitions, the expression {{mono|a + b + c}} is of type
VecSum, Vec>
so {{mono|Vec x {{=}} a + b + c}} invokes the templated {{mono|Vec}} constructor with this type as its {{mono|E}} template argument. Inside this constructor, the loop body
elems[i] = vec[i];
is effectively expanded (following the recursive definitions of {{mono|operator+}} and {{mono|operator[]}} on this type) to
elems[i] = a.elems[i] + b.elems[i] + c.elems[i];
with no temporary vectors needed and only one pass through each memory block.
Basic Usage :
int main(){
Vec v0 = {23.4,12.5,144.56,90.56}; Vec v1 = {67.12,34.8,90.34,89.30}; Vec v2 = {34.90,111.9,45.12,90.5}; // Following assignment will call the ctor of Vec which accept type of // `VecExpression const&`. Then expand the loop body to // a.elems[i] + b.elems[i] + c.elems[i] Vec sum_of_vec_type = v0+v1+v2;
for(int i=0;i
}
Applications
Expression templates have been found especially useful by the authors of libraries for linear algebra, i.e., for dealing with vectors and matrices of numbers. Among libraries employing expression template are Armadillo, Blaze[5], Blitz++[6], Boost uBLAS[7], Eigen[8], POOMA[9], Stan Math Library[10], and xtensor[11]. Expression templates can also accelerate C++ automatic differentiation implementations[12], as demonstrated in the Adept library.
Outside of vector math, the Spirit parser framework uses expression templates to represent formal grammars and compile these into parsers.
References
1. ^{{cite conference |first1=Kiminori |last1=Matsuzaki |first2=Kento |last2=Emoto |title=Implementing fusion-equipped parallel skeletons by expression templates |conference=Proc. Int'l Symp. on Implementation and Application of Functional Languages |year=2009 |pages=72–89}} 2. ^{{cite book | last1 = Vandevoorde | first1 = David | last2 = Josuttis | first2 = Nicolai | title = C++ Templates: The Complete Guide | publisher = Addison Wesley | year = 2002 | isbn = 0-201-73484-2}} 3. ^{{cite journal |last=Veldhuizen |first=Todd |title=Expression Templates |journal=C++ Report |volume=7 |issue=5 |year=1995 |pages=26–31 |url=http://osl.iu.edu/~tveldhui/papers/Expression-Templates/exprtmpl.html |archiveurl=https://web.archive.org/web/20050210090012/http://osl.iu.edu/~tveldhui/papers/Expression-Templates/exprtmpl.html |archivedate=10 February 2005}} 4. ^{{cite book |title=C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond |first1=David |last1=Abrahams |first2=Aleksey |last2=Gurtovoy |publisher=Pearson Education |year=2004 |url=https://books.google.com/books?id=4dV9tALro-AC&pg=PT343}} 5. ^https://bitbucket.org/blaze-lib/blaze 6. ^{{cite web| url = http://blitz.sourceforge.net/resources/blitz-0.9.pdf| title = Blitz++ User's Guide| access-date = December 12, 2015}} 7. ^{{cite web| url = http://www.boost.org/doc/libs/1_59_0/libs/numeric/ublas/doc/index.html| title = Boost Basic Linear Algebra Library| access-date = October 25, 2015}} 8. ^{{cite conference |title=Eigen: A C++ linear algebra library |first=Gaël |last=Guennebaud |year=2013 |conference=Eurographics/CGLibs |url=http://downloads.tuxfamily.org/eigen/eigen_CGLibs_Giugno_Pisa_2013.pdf}} 9. ^{{cite conference |first=Todd |last=Veldhuizen |title=Just when you thought your little language was safe: "Expression Templates" in Java |year=2000 |conference=Int'l Symp. Generative and Component-Based Software Engineering |citeseerx=10.1.1.22.6984}} 10. ^{{cite web | url = http://mc-stan.org/documentation/ | title = Stan documentation | access-date = April 27, 2016}} 11. ^{{cite web | url = https://xtensor.readthedocs.io | title = Multi-dimensional arrays with broadcasting and lazy computing | access-date = September 18, 2017}} 12. ^{{cite journal|last=Hogan|first=Robin J.|title=Fast reverse-mode automatic differentiation using expression templates in C++|journal=ACM Trans. Math. Softw.|year=2014|volume=40|issue=4|pages=26:1–26:16|url=http://www.met.reading.ac.uk/%7Eswrhgnrj/publications/adept.pdf}}