Expression templates

from Wikipedia, the free encyclopedia

Expression templates are a C ++ metaprogramming technique and were not originally intended in the C ++ standard. They are used to replace certain expressions with template code at translation time .

Todd Veldhuizen introduced this technique in June 1995. It should avoid the loss of speed caused by temporary variables in the event of operator overload, while at the same time maintaining a simple notation.

Basically, expression templates represent an abstraction technique that makes it possible to “hide” a complex operation behind a simple-looking expression (see also CRTP ). They should not be used to generate code dynamically, but instead to call specialized (or optimized) calculation functions. For example, an expression template for a matrix multiplication should better call a special kernel such as dgemm or an OpenCL kernel, which does the actual calculation.

idea

In the field of scientific computing, for example simulations, recurring operations are used on vectors or matrices. Here it is required that the source text is easy to read - and therefore also maintainable - and that the most efficient code is generated.

Example : Operations on vectors should be representable in the simple form x = c * x + x * y;, instead of VecAdd(x, VecScale(c, x), VecMul(x, y)); or ultimately 

for (size_t i = 0; i < x.size(); ++i)
   x[i] = c * x[i] + x[i] * y[i];

(Note: Let x, y vectors (here:) std::vector<double>and c be a scalar (here:) double.)

Operator overloading was originally intended for such cases. However, temporary variables are created here, which later have to be copied into the target variable, and there is also a function call that interrupts the linear program sequence. (This can partially be circumvented by inlining , but it is not guaranteed and creates other problems.) Allocating and constructing temporary variables is very time-consuming, especially with complex data types.

The idea is now to design a series of templates that replace a simple expression (as above) with the - usually more extensive - source code that calculates the desired result.

To do this, remember that the above expression can also be represented as a tree: 

     +
   /   \
  *     *
 / \   / \
c   x x   y

You now need a wrapper class that represents a single expression (here: a node) and the associated function. Then you only have to create a template class for the respective operation and its operation template (see example below).

The expression x = c * x + x * y;is then successively replaced by the compiler with the corresponding templates:

Expression Becomes …
c * x 
VecScale<double, double, vector<double>>(c, x)
x * y 
VecMul<double, vector<double>, vector<double>>(x, y)
cx + xy 
VecAdd<double, vector<double>, vector<double>>(cx, xy)

(with cx = c * xand xy = x * y)

The fully replaced expression then looks like this: 

x = VecAdd<double, vector<double>, vector<double>>(
       VecScale<double, double, vector<double>>(c, x),
       VecMul<double, vector<double>, vector<double>>(x, y))
    );

or in detailed (correct) notation: 

x = Vector< VecAdd<double, vector<double>, vector<double>> >(VecAdd<double, vector<double>, vector<double>>(
       Vector< double, VecScale<double, double, vector<double>> >(VecScale<double, double, vector<double>>(c, x)),
       Vector< double, VecMul<double, vector<double>, vector<double>> >)(VecMul<double, vector<double>, vector<double>>(x, y))(x, y))
)

Finally, the operator templates are inserted and you get 

for (size_t i = 0; i < x.size(); ++i)
   x[i] = c * x[i] + x[i] * y[i];

Caution : This is a simple, positive example of the use of expression templates . Generally, this technique results in the contest of operations not to success (see section speed ).

Advantages and disadvantages

advantages

  • clear semantics, thereby better readability and greatly simplified maintainability of the code
  • enables generic programming

disadvantage

  • no speed improvement (compared to a handwritten, optimized function)
  • Enlargement of the source text through template structures
  • longer compilation time, as additional code is inserted when the templates are replaced

speed

Its inventor, Todd Veldhuizen , originally invented it to get high-performance code with a simple notation. Since those days the myth that expression templates are an optimization technique has persisted . This is not the case.

In the example above , the simple replacement of expressions still works well, since these are simple operations and consecutive memory areas are only accessed linearly.

Modifying the above example (naively) for matrices only results in catastrophic execution times. This is due to the element-wise calculation of each individual cell. Simply replacing expressions with template code does not generally result in high-performance code.

implementation

Wrapper class template 

#include <vector>

using namespace std;

template< typename T, typename R = vector<T> >
class Vector {
private:
   R r;   // data representation

public:
   Vector(const size_t n) : r(n) {}

   Vector(const size_t n, const double initialValue) : r(n, initialValue) {}

   // copy constructor
   Vector(const R &other) : r(other) {}

   // assignment operator: same type
   T& operator=(const T &other)
   {
      for (size_t i = 0; i < r.size(); ++i)
         r[i] = other[i];

      return *this;
   }

   // assignment operator: other type
   template< typename T2, typename R2 >
   Vector& operator=(const Vector<T2, R2> &other)
   {
      for (size_t i = 0; i < r.size(); ++i)
         r[i] = other[i];

      return *this;
   }

   size_t size() const
   { return r.size(); }

   T operator[](const size_t i) const
   { return r[i]; }

   T& operator[](const size_t i)
   { return r[i]; }

   const R& data() const
   { return r; }

   R& data()
   { return r; }
};

Class templates for operations 

// Addition
template< typename T, typename Op1 , typename Op2 >
class VecAdd {
private:
   const Op1 &op1;
   const Op2 &op2;

public:
   VecAdd(const Op1 &a, const Op2 &b ) :
      op1(a), op2(b) {}

   T operator[](const size_t i) const
   { return op1[i] + op2[i]; }

   size_t size() const
   { return op1.size(); }
};

// Multiplikation (elementweise)
template< typename T, typename Op1 , typename Op2 >
class VecMul {
private:
   const Op1 &op1;
   const Op2 &op2;

public:
   VecMul(const Op1 &a, const Op2 &b ) :
      op1(a), op2(b) {}

   T operator[](const size_t i) const
   { return op1[i] * op2[i]; }

   size_t size() const
   { return op1.size(); }
};

Function template 

template< typename T, typename R1, typename R2 >
Vector< T, VecAdd< T, R1, R2 > >
operator+(const Vector<T, R1> &a, const Vector<T, R2> &b)
{
   return Vector<T, VecAdd< T, R1, R2 > >(VecAdd< T, R1, R2 >(a.data(), b.data()));
}

template< typename T, typename R1, typename R2 >
Vector< T, VecMul< T, R1, R2 > >
operator*(const Vector<T, R1> &a, const Vector<T, R2> &b)
{
   return Vector<T, VecMul< T, R1, R2 > >(VecMul< T, R1, R2 >(a.data(), b.data()));
}

example 

Vector<double> x(5000);
Vector<double> y(5000);
const double c = 1.234;

// Initialisieren der Vektoren ...

x = c * x + x * y;

Libraries

See also

Individual evidence

  • Lippman, SB: C ++ Gems
  • Vandevoorde, D., Josuttis, NM: C ++ Templates
  1. ^ Todd Veldhuizen: Expression Templates . informatik.uni-erlangen.de. June 1995. Archived from the original on May 24, 2013. Info: The archive link was automatically inserted and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. Retrieved June 7, 2013. @1@ 2Template: Webachiv / IABot / www10.informatik.uni-erlangen.de
  2. ↑ Klaus Iglberger, Georg Hager, Jan Treibig, Ulrich Rüde: Expression Templates Revisited: A Performance Analysis of Current Methodologies . In: SIAM Journal on Scientific Computing . 34, Jan 2012, pp. C42-C69. doi : 10.1137 / 110830125 .