Expression templates

Short description: C++ template metaprogramming technique

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][3] it was Veldhuizen who gave them their name.[3] They are a popular technique for the implementation of linear algebra software.[1]

## Contents

* 1 Motivation and example
* 1.1 Example implementation of expression templates
* 1.2 Basic usage
* 2 Applications
* 3 See also
* 4 References

## Motivation and example

Consider a library representing vectors and operations on them. One common mathematical operation is to add two vectors u and v, element-wise, to produce a new vector. The obvious C++ implementation of this operation would be an overloaded `operator+` that returns a new vector object:

import std;

using std::array;

/// @brief class representing a mathematical 3D vector
class Vec3 : public array<double, 3> {
public:
Vec3():
array<double, 3>() {}

/// @brief sum 'u' and 'v' into a new instance of Vec3
Vec3 operator+(Vec3 const& u, Vec3 const& v) {
Vec3 sum;
for (size_t i = 0; i < u.size(); i++) {
sum[i] = u[i] + v[i];

return sum;

Users of this class can now write `Vec3 x = a + b;` where `a` and `b` are both instances of `Vec3`.

A problem with this approach is that more complicated expressions such as `Vec3 x = a + b + c` are implemented inefficiently. The implementation first produces a temporary `Vec3` to hold `a + b`, then produces another `Vec3` with the elements of `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 `operator+` return an object of an auxiliary type, say `Vec3Sum`, that represents the unevaluated sum of two `Vec3`s, or a vector with a `Vec3Sum`, etc. Larger expressions then effectively build expression trees that are evaluated only when assigned to an actual `Vec3` 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 `Vec3`, such as `Vec3 x = a + b + c`, generates a new `Vec3` constructor if needed by template instantiation. This constructor operates on three `Vec3`; it allocates the necessary memory and then performs the computation. Thus only one memory allocation is performed.

### Example implementation of expression templates

An example implementation of expression templates looks like the following. A base class `Vec3Expression` represents any vector-valued expression. It is templated on the actual expression type `E` to be implemented, per the curiously recurring template pattern. The existence of a base class like `VecExpression` is not strictly necessary for expression templates to work. It will merely serve as a function argument type to distinguish the expressions from other types (note the definition of a `Vec3` constructor and `operator+` below).

import std;

template <typename E>
class VecExpression {
public:
static constexpr bool IS_LEAF = false;

nodiscard
double operator[](size_t i) const {
// Delegation to the actual expression type. This avoids dynamic polymorphism (a.k.a. virtual functions in C++)
return static_cast<E const&>(*this)[i];

nodiscard
size_t size() const {
return static_cast<E const&>(*this).size();

The Boolean `is_leaf` is there to tag `VecExpression`s that are "leafs", i.e. that actually contain data. The `Vec3` class is a leaf that stores the coordinates of a fully evaluated vector expression, and becomes a subclass of `VecExpression`.

import std;

using std::array;
using std::initializer_list;

class Vec3 : public VecExpression<Vec3> {
private:
array<double, 3> elems;
public:
static constexpr bool IS_LEAF = true;

nodiscard
double operator[](size_t i) const noexcept {
return elems[i];

double& operator[](size_t i) noexcept {
return elems[i];

nodiscard
size_t size() const noexcept {
return elems.size();

// construct Vec using initializer list
Vec3(initializer_list<double> init) {
std::ranges::copy(init, elems.begin());

// A Vec can be constructed from any VecExpression, forcing its evaluation.
template <typename E>
Vec3(VecExpression<E> const& expr) {
for (size_t i = 0; i != expr.size(); ++i) {
elems[i] = expr[i];

The sum of two `Vec3`s is represented by a new type, `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 `Vec3` expressions. An overloaded `operator+` serves as syntactic sugar for the `VecSum` constructor. A subtlety intervenes in this case: in order to reference the original data when summing two `VecExpression`s, `VecSum` needs to store a const reference to each `VecExpression` if it is a leaf, otherwise it is a temporary object that needs to be copied to be properly saved.

import std;

using std::conditional;

template <typename E1, typename E2>
class Vec3Sum : public VecExpression<Vec3Sum<E1, E2>> {
private:
// cref if leaf, copy otherwise
typename conditional<E1::is_leaf, const E1&, const E1>::type u;
typename conditional<E2::is_leaf, const E2&, const E2>::type v;
public:
static constexpr bool IS_LEAF = false;

Vec3Sum(E1 const& u, E2 const& v):
u{u}, v{v} {
assert(u.size() == v.size());

nodiscard
double operator[](size_t i) const noexcept {
return u[i] + v[i];

nodiscard
size_t size() const noexcept {
return v.size();

template <typename E1, typename E2>
Vec3Sum<E1, E2> operator+(VecExpression<E1> const& u, VecExpression<E2> const& v) {
return Vec3Sum<E1, E2>(*static_cast<const E1*>(&u), *static_cast<const E2*>(&v));

With the above definitions, the expression `a + b + c` is of type

Vec3Sum<Vec3Sum<Vec3, Vec3>, Vec3>

so `Vec3 x = a + b + c` invokes the templated `Vec3` constructor `Vec3(VecExpression<E> const& expr)` with its template argument `E` being this type (meaning `Vec3Sum<Vec3Sum<Vec3, Vec3>, Vec3>`). Inside this constructor, the loop body

elems[i] = expr[i];

is effectively expanded (following the recursive definitions of `operator+` and `operator[]`on this type) to

elems[i] = a.elems[i] + b.elems[i] + c.elems[i];

with no temporary `Vec` objects needed and only one pass through each memory block.

### Basic usage

The following demonstrates basic usage of the above:

import std;

int main() {
Vec3 v0{23.4,  12.5,  144.56};
Vec3 v1{67.12, 34.8,  90.34};
Vec3 v2{34.90, 111.9, 45.12};

// Following assignment will call the ctor of Vec3 which accept type of
// `VecExpression<E> const&`. Then expand the loop body to
// a.elems[i] + b.elems[i] + c.elems[i]
Vec3 sumOfVecType = v0 + v1 + v2;

for (size_t i = 0; i < sumOfVecType.size(); ++i) {
std::println("{}", sumOfVecType[i]);

// To avoid creating any extra storage, other than v0, v1, v2
// one can do the following (Tested with C++11 on GCC 5.3.0)
auto sum = v0 + v1 + v2;
for (size_t i = 0; i < sum.size(); ++i) {
std::println("{}", sum[i]);

// Observe that in this case typeid(sum) will be Vec3Sum<Vec3Sum<Vec3, Vec3>, Vec3>
// and this chaining of operations can go on.

## Applications

Expression templates have been found especially useful by the authors of libraries for linear algebra, that is, for dealing with vectors and matrices of numbers. Among libraries employing expression template are Dlib, 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.

## See also

* Optimizing compiler - Computing tool for optimizing parts of a program

## References

1. ↑ 1.0 1.1 Matsuzaki, Kiminori; Emoto, Kento (2009). "Implementing fusion-equipped parallel skeletons by expression templates". Proc. Int'l Symp. on Implementation and Application of Functional Languages. pp. 72–89.
2. ↑ Vandevoorde, David; Josuttis, Nicolai (2002). C++ Templates: The Complete Guide. Addison Wesley. ISBN 0-201-73484-2.
3. ↑ 3.0 3.1 Veldhuizen, Todd (1995). "Expression Templates". C++ Report 7 (5): 26–31. Archived from the original on 10 February 2005. https://web.archive.org/web/20050210090012/http://osl.iu.edu/~tveldhui/papers/Expression-Templates/exprtmpl.html.
4. ↑ Abrahams, David; Gurtovoy, Aleksey (2004). C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond. Pearson Education. ISBN 9780321623911. https://books.google.com/books?id=4dV9tALro-AC&pg=PT343.
5. ↑ Bitbucket
6. ↑ "Blitz++ User's Guide". https://blitz.sourceforge.net/resources/blitz-0.9.pdf.
7. ↑ "Boost Basic Linear Algebra Library". http://www.boost.org/doc/libs/1_59_0/libs/numeric/ublas/doc/index.html.
8. ↑ Guennebaud, Gaël (2013). "Eigen: A C++ linear algebra library". Eurographics/CGLibs. http://downloads.tuxfamily.org/eigen/eigen_CGLibs_Giugno_Pisa_2013.pdf.
9. ↑ Veldhuizen, Todd (2000). "Just when you thought your little language was safe: "Expression Templates" in Java". Int'l Symp. Generative and Component-Based Software Engineering.
10. ↑ "Stan documentation". http://mc-stan.org/documentation/.
11. ↑ "Multi-dimensional arrays with broadcasting and lazy computing". https://xtensor.readthedocs.io.
12. ↑ Hogan, Robin J. (2014). "Fast reverse-mode automatic differentiation using expression templates in C++". ACM Trans. Math. Softw. 40 (4): 26:1–26:16. doi:10.1145/2560359. http://www.met.reading.ac.uk/~swrhgnrj/publications/adept.pdf.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Expression templates. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Expression_templates&oldid=4228460"