imported>Pw123456789: /* growthexperiments-addlink-summary-summary:1|0|0 */

2026-04-15T08:37:45Z

growthexperiments-addlink-summary-summary:1|0|0

Neue Seite

'''Expression Templates''' sind eine [[C++-Metaprogrammierung|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.<ref name="veldhuizen95" /> 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 [[Curiously recurring template pattern|CRTP]]). Sie sollten nicht verwendet werden, um dynamisch Code zu generieren, sondern stattdessen um spezialisierte (bzw. optimierte) Berechnungsfunktionen aufzurufen.<ref name="iglberger_et_perf" /> 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 <code>x = c * x + x * y;</code> darstellbar sein, an Stelle von <code>VecAdd(x, VecScale(c, x), VecMul(x, y));</code>
bzw. letztendlich
<syntaxhighlight lang="cpp">
for (size_t i = 0; i < x.size(); ++i)
x[i] = c * x[i] + x[i] * y[i];
</syntaxhighlight>

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

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 [[Inline-Ersetzung|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 <code>x = c * x + x * y;</code> wird dann sukzessive durch den Compiler mit den entsprechenden Templates ersetzt:

{| class="wikitable"
|-
! Ausdruck !! Wird zu …
|-
| <code>c * x</code> ||
<syntaxhighlight lang="cpp">
VecScale<double, double, vector<double>>(c, x)
</syntaxhighlight>
|-
| <code>x * y</code> ||
<syntaxhighlight lang="cpp">
VecMul<double, vector<double>, vector<double>>(x, y)
</syntaxhighlight>
|-
| <code>cx + xy</code> ||
<syntaxhighlight lang="cpp">
VecAdd<double, vector<double>, vector<double>>(cx, xy)
</syntaxhighlight>
|}
(mit <code>cx = c * x</code> und <code>xy = x * y</code>)

Der vollständig ersetzte Ausdruck sieht dann so aus:
<syntaxhighlight lang="cpp">
x = VecAdd<double, vector<double>, vector<double>>(
VecScale<double, double, vector<double>>(c, x),
VecMul<double, vector<double>, vector<double>>(x, y))
);
</syntaxhighlight>

bzw. in ausführlicher (korrekter) Schreibweise:

<syntaxhighlight lang="cpp">
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))
)
</syntaxhighlight>

Als Letztes werden noch die Operator-Templates eingefügt und man erhält
<syntaxhighlight lang="cpp">
for (size_t i = 0; i < x.size(); ++i)
x[i] = c * x[i] + x[i] * y[i];
</syntaxhighlight>

'''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|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 [[Optimierung#Programmierung|Optimierungstechnik]] seien. Dies ist nicht der Fall.

Im [[#Idee|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'''

<syntaxhighlight lang="cpp">
#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; }
};
</syntaxhighlight>

'''Klassen-Templates für Operationen'''

<syntaxhighlight lang="cpp">
// 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(); }
};
</syntaxhighlight>

'''Funktions-Template'''

<syntaxhighlight lang="cpp">
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()));
}

</syntaxhighlight>

'''Beispiel'''
<syntaxhighlight lang="cpp">
Vector<double> x(5000);
Vector<double> y(5000);
const double c = 1.234;

// Initialisieren der Vektoren ...

x = c * x + x * y;
</syntaxhighlight>

== Bibliotheken ==
* [http://www.boost.org/doc/libs/1_47_0/libs/numeric/ublas/doc/index.htm Boost uBLAS]
* {{Webarchiv| url = http://www.oonumerics.org/blitz/whatis.html| wayback= 20110727145248| text = Blitz++}}

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

<references>
<ref name="veldhuizen95">
{{Internetquelle |autor=Todd Veldhuizen |url=http://www10.informatik.uni-erlangen.de/~pflaum/pflaum/ProSeminar/exprtmpl.html |titel=Expression Templates |hrsg=informatik.uni-erlangen.de |datum=1995-06 |archiv-url=https://web.archive.org/web/20130524014316/http://www10.informatik.uni-erlangen.de/~pflaum/pflaum/ProSeminar/exprtmpl.html |archiv-datum=2013-05-24 |offline=1 |abruf=2013-06-07}}
</ref>
<ref name="iglberger_et_perf">
{{Literatur |Autor=Klaus Iglberger, Georg Hager, Jan Treibig, Ulrich Rüde |Titel=Expression Templates Revisited: A Performance Analysis of Current Methodologies |Sammelwerk=SIAM Journal on Scientific Computing |Band=34 |Datum=2012-01 |Seiten=C42–C69 |DOI=10.1137/110830125}}
</ref>
</references>

[[Kategorie:C++]]

Expression Templates - Versionsgeschichte

imported>Pw123456789: /* growthexperiments-addlink-summary-summary:1|0|0 */