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

Idee

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:

Ausdruck	Wird zu …
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)

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

Vor- und Nachteile

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

Geschwindigkeit

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.

Implementierung

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;

Bibliotheken

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

Siehe auch

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

Einzelnachweise

• 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.