Expression Templates

Expression Templates sind eine C++-Metaprogrammiertechnik und waren ursprünglich nicht im C++-Standard vorgesehen. Sie werden verwendet, um bereits zur Übersetzungszeit bestimmte Ausdrücke durch Templatecode zu ersetzen.

Todd Veldhuizen stellte diese Technik im Juni 1995 vor.^[1] Sie sollte die Geschwindigkeitseinbußen durch temporäre Variablen bei Operator-Überladung vermeiden, gleichzeitig jedoch eine einfache Schreibweise beibehalten.

Im Grunde stellen Expression Templates vielmehr eine Abstraktionstechnik dar, die es ermöglicht, hinter einem einfach aussehenden Ausdruck eine komplexe Operation zu „verstecken“ (vgl. auch CRTP). Sie sollten nicht verwendet werden, um dynamisch Code zu generieren, sondern stattdessen um spezialisierte (bzw. optimierte) Berechnungsfunktionen aufzurufen.^[2] Zum Beispiel sollte ein Expression Template für eine Matrizenmultiplikation besser einen speziellen Kernel wie dgemm oder einen OpenCL-Kernel aufrufen, der die eigentliche Berechnung durchführt.

Gerade im Bereich des wissenschaftlichen Rechnens, beispielsweise Simulationen, werden immer wiederkehrende Operationen auf Vektoren oder Matrizen angewandt. Hier wird gefordert, dass der Quelltext einerseits leicht lesbar – und somit auch wartbar – ist und andererseits maximal effizienter Code generiert wird.

Beispiel: Operationen auf Vektoren sollen in der einfachen Form x = c * x + x * y; darstellbar sein, an Stelle von VecAdd(x, VecScale(c, x), VecMul(x, y)); bzw. letztendlich

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

(Anmerkung: Seien x, y Vektoren (hier: std::vector<double>) und c ein Skalar (hier: double).)

Ursprünglich war die Technik der Operator-Überladung für solche Fälle gedacht. Allerdings werden hier temporäre Variablen angelegt, die später in die Zielvariable kopiert werden müssen, und es findet zusätzlich noch ein Funktionsaufruf statt, der den linearen Programmablauf unterbricht. (Dies kann teilweise durch Inlining umgangen werden, ist jedoch nicht garantiert und kreiert wiederum andere Probleme.) Gerade das Allozieren und Konstruieren der temporären Variablen ist sehr zeitaufwändig, besonders bei komplexen Datentypen.

Die Idee ist nun, eine Reihe Templates zu entwerfen, die einen einfachen Ausdruck (wie oben) durch den – meist umfangreicheren – Quelltext ersetzen, der das gewünschte Ergebnis berechnet.

Hierzu ruft man sich in Erinnerung, dass der obige Ausdruck auch als Baum dargestellt werden kann:

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

Nun benötigt man eine Wrapper-Klasse, die einen einzelnen Ausdruck (hier: ein Knoten) darstellt und die zugehörige Funktion unterlegt. Dann muss man nur noch eine Template-Klasse für die jeweilige Operation und deren Operations-Template anlegen (siehe Beispiel weiter unten).

Der Ausdruck x = c * x + x * y; wird dann sukzessive durch den Compiler mit den entsprechenden Templates ersetzt:

VecScale<double, double, vector<double>>(c, x)

VecMul<double, vector<double>, vector<double>>(x, y)

VecAdd<double, vector<double>, vector<double>>(cx, xy)

(mit cx = c * x und xy = x * y)

Der vollständig ersetzte Ausdruck sieht dann so aus:

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

bzw. in ausführlicher (korrekter) Schreibweise:

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))
)

Als Letztes werden noch die Operator-Templates eingefügt und man erhält

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

Vorsicht: Dies ist ein einfaches, positives Beispiel für den Einsatz von Expression Templates. Im Allgemeinen führt diese Technik des Ausschreibens von Operationen nicht zum Erfolg (siehe Abschnitt Geschwindigkeit).

Vorteile

• klare Semantik, dadurch bessere Lesbarkeit und stark vereinfachte Wartbarkeit des Codes
• ermöglicht generische Programmierung

Nachteile

• keine Geschwindigkeitsverbesserung (im Vergleich zu einer handgeschriebenen, optimierten Funktion)
• Vergrößerung des Quelltextes durch Template-Strukturen
• längere Übersetzungszeit, da beim Ersetzen der Templates zusätzlicher Code eingefügt wird

Ihr Erfinder, Todd Veldhuizen, erfand sie ursprünglich, um performanten Code bei dennoch einfacher Schreibweise zu erhalten. Seit diesen Tagen hält sich hartnäckig der Mythos, dass Expression Templates eine Optimierungstechnik seien. Dies ist nicht der Fall.

Im Beispiel oben funktioniert das einfache Ersetzen von Ausdrücken noch gut, da es sich um einfache Operationen handelt und nur linear auf aufeinanderfolgende Speicherbereiche zugegriffen wird.

Wandelt man das obige Beispiel lediglich (naiv) für Matrizen ab, erhält man katastrophale Ausführungszeiten. Dies rührt von der elementweisen Berechnung jeder einzelnen Zelle her. Das einfache Ersetzen von Ausdrücken durch Template-Code führt also im Allgemeinen nicht zu performantem Code.

Wrapper Klassen-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; }
};

Klassen-Templates für Operationen

// 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(); }
};

Funktions-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()));
}

Beispiel

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

// Initialisieren der Vektoren ...

x = c * x + x * y;

• Boost uBLAS
• Blitz++ (Memento vom 27. Juli 2011 im Internet Archive)

• Template (Programmierung)
• Boost (C++-Bibliothek)

• S. B. Lippman: C++ Gems. Cambridge Univ. Press, Cambridge 2003, ISBN 0-13-570581-9.
• D. Vandevoorde, N. M. Josuttis: C++ Templates. Addison-Wesley, 2003, ISBN 0-201-73484-2.

1. ↑ Todd Veldhuizen: Expression Templates. informatik.uni-erlangen.de, Juni 1995, archiviert vom Original (nicht mehr online verfügbar) am 24. Mai 2013; abgerufen am 7. Juni 2013. 
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. Band 34, Januar 2012, S. C42–C69, doi:10.1137/110830125.