Expression Templates

Expression Templates

Expression Templates sind eine C++-Metaprogrammiertechnik und waren ursprünglich nicht im C++-Standard vorgesehen. Sie werden verwendet, um bereits zur Kompilierzeit 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]. Z. B. sollte ein Expression Template für eine Matrix-Matrix-Multiplikation besser einen speziellen Kernel wie dgemm oder einen OpenCL-Kernel aufrufen, der die eigentliche Berechnung durchführt.

Inhaltsverzeichnis

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

Beispiel

Vector<double> x(5000);
Vector<double> y(5000);
const double c = 1.234;
 
// Initialisieren der Vektoren ...
 
x = c * x + x * y;

Bibliotheken

Siehe auch

Einzelnachweise

  • Lippman, S. B.: C++ Gems
  • Vandevoorde, D., Josuttis, N. M.: C++ Templates
  1. Veldhuizen, Todd (June 1995): Expression Templates [1]. Abgerufen 29. Juli 2011.
  2. Iglberger, K., et al.: Expression Templates Revised: A Performance Analysis of the Current Expression Template Methodology [2]

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Expression Encoder — Desarrollador Microsoft Sitio Oficial Español Información general Última versión estable …   Wikipedia Español

  • Microsoft Expression Encoder — 4 on Wind …   Wikipedia

  • TAL Expression Syntax — Die Template Attribute Language Expression Syntax (TALES) beschreibt die Syntax für die Auswertung der von der Template Attribute Language (TAL) und Macro Expansion Template Attribute Language (METAL) für Attributwerte verwendeten Ausdrücke. Die… …   Deutsch Wikipedia

  • Template Attribute Language Expression Syntax — Die Template Attribute Language Expression Syntax (TALES) beschreibt die Syntax für die Auswertung der von der Template Attribute Language (TAL) und Macro Expansion Template Attribute Language (METAL) für Attributwerte verwendeten Ausdrücke. Die… …   Deutsch Wikipedia

  • Parsing expression grammar — A parsing expression grammar, or PEG, is a type of analytic formal grammar that describes a formal language in terms of a set of rules for recognizing strings in the language. A parsing expression grammar essentially represents a recursive… …   Wikipedia

  • Microsoft Expression Blend — 3 Screenshot …   Wikipedia

  • DNA gene-expression microarray — A DNA gene expression microarray is a process that allows thousands of pieces of DNA that are fixed to a glass slide to be analyzed at one time. It is used to identify the genes (pieces of DNA) in specific cells or tissue that are actively used… …   Wikipedia

  • Zope Page Templates — „Zope Page Templates“ (ZPT) sind von Zope verwendete Seitenschablonen, die zur Generierung von HTML , XHTML und XML Seiten verwendet werden. Sie verwenden folgende für Zope entwickelte Technologien: Template Attribute Language (TAL) TALES (TAL… …   Deutsch Wikipedia

  • Turbo C++ — Infobox Software name = Turbo C++ caption = collapsible = author = developer = Borland released = February 28, 1991 latest release version = 2006 latest release date = September 5, 2006 latest preview version = latest preview date = frequently… …   Wikipedia

  • Spirit Parser Framework — The Spirit Parser Framework is an object oriented recursive descent parser generator framework implemented using template metaprogramming techniques. Expression templates allow users to approximate the syntax of Extended Backus Naur Form (EBNF)… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”