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

(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:

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:

bzw. in ausführlicher (korrekter) Schreibweise:

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

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

Klassen-Templates für Operationen

Funktions-Template

Beispiel

## Bibliotheken

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