Expression Templates

30 Dezember 2016

Expression Templates sind "structures representing a computation at compile time, which structures are evaluated only as needed to produce efficient code for the entire computation" (https://en.wikipedia.org/wiki/Expression_templates). As needed, damit sind wir mitten in der Bedarfsauswertung und in diesem Artikel.

Welches Problem lösen Expression Templates? Expression Templates helfen, überflüssige temporäre Objekte in Ausdrücken zu vermeiden. Was meine ich mit überflüssigen temporäre Objekten? Meine Implementierung der Klasse MyVector.

Die naive Implementierung

MyVector ist ein bewusst einfach gehaltener Wrapper um einen std::vector<T>, der zwei Konstruktoren besitzt (Zeile 12 und 15), seine Länge kennt (Zeile 18 - 20) und den lesenden (Zeile 23 - 25) und schreibenden (Zeile 27 - 29) Indexzugriff erlaubt.

// vectorArithmeticOperatorOverloading.cpp

#include <iostream>
#include <vector>

template<typename T>
class MyVector{
  std::vector<T> cont;   

public:
  // MyVector with initial size
  MyVector(const std::size_t n) : cont(n){}  

  // MyVector with initial size and value
  MyVector(const std::size_t n, const double initialValue) : cont(n, initialValue){}
  
  // size of underlying container
  std::size_t size() const{ 
    return cont.size(); 
  }

  // index operators
  T operator[](const std::size_t i) const{ 
    return cont[i]; 
  }

  T& operator[](const std::size_t i){ 
    return cont[i]; 
  }

};

// function template for the + operator
template<typename T> 
MyVector<T> operator+ (const MyVector<T>& a, const MyVector<T>& b){
  MyVector<T> result(a.size());
  for (std::size_t s= 0; s <= a.size(); ++s){
    result[s]= a[s]+b[s];
  }
  return result;
}

// function template for the * operator
template<typename T>
MyVector<T> operator* (const MyVector<T>& a, const MyVector<T>& b){
   MyVector<T> result(a.size());
  for (std::size_t s= 0; s <= a.size(); ++s){
    result[s]= a[s]*b[s]; 
  }
  return result;
}

// function template for << operator
template<typename T>
std::ostream& operator<<(std::ostream& os, const MyVector<T>& cont){  
  std::cout << std::endl;
  for (int i=0; i<cont.size(); ++i) {
    os << cont[i] << ' ';
  }
  os << std::endl;
  return os;
} 

int main(){

  MyVector<double> x(10,5.4);
  MyVector<double> y(10,10.3);

  MyVector<double> result(10);
  
  result= x+x + y*y;
  
  std::cout << result << std::endl;
  
}

Dank dem überladenen + Operator (Zeile 34 - 41), dem überladenen * Operator (Zeile 44 - 51) und dem überladenen Ausgabeoperator (Zeile 54 - 62) fühlen sich die Objekte x, y und result wie Zahlen an.

vectorArithmeticOperatorOverloading

Warum ist diese Implementierung naiv? Die Antwort liegt in dem Ausdruck result= x+x + y*y. Um den Ausdruck zu evaluieren, werden drei temporäre Objekte benötigt, denn jede arithmetische Operation muss ihr Ergebnis in einer temporären Variable speichern.

Temporaries

Wie lassen sich die temporären Objekte in dem arithmetischen Ausdruck vermeiden? Die Idee ist einfach. Anstelle die Vektoroperationen gierig auszuführen, wird der Expression Tree für result[i] lazy zur Compilezeit erzeugt.

Expression Templates

ExpressionTree

Für den Ausdruck result[i]= x[i]+x[i] + y[i]*y[i] sind keine temporären Variablen notwendig. Erst die abschließende Zuweisung stößt die Auswertung an. Leider ist der Code selbst in diesem einfachen Fall nicht mehr so leichtverdaulich.

// vectorArithmeticExpressionTemplates.cpp

#include <cassert>
#include <iostream>
#include <vector>

template<typename T, typename Cont= std::vector<T> >
class MyVector{
  Cont cont;   

public:
  // MyVector with initial size
  MyVector(const std::size_t n) : cont(n){}

  // MyVector with initial size and value
  MyVector(const std::size_t n, const double initialValue) : cont(n, initialValue){}

  // Constructor for underlying container
  MyVector(const Cont& other) : cont(other){}

  // assignment operator for MyVector of different type
  template<typename T2, typename R2>
  MyVector& operator=(const MyVector<T2, R2>& other){
    assert(size() == other.size());
    for (std::size_t i = 0; i < cont.size(); ++i) cont[i] = other[i];
    return *this;
  }

  // size of underlying container
  std::size_t size() const{ 
    return cont.size(); 
  }

  // index operators
  T operator[](const std::size_t i) const{ 
    return cont[i]; 
  }

  T& operator[](const std::size_t i){ 
    return cont[i]; 
  }

  // returns the underlying data
  const Cont& data() const{ 
    return cont; 
  }

  Cont& data(){ 
    return cont; 
  }
};

// MyVector + MyVector
template<typename T, typename Op1 , typename Op2>
class MyVectorAdd{
  const Op1& op1;
  const Op2& op2;

public:
  MyVectorAdd(const Op1& a, const Op2& b): op1(a), op2(b){}

  T operator[](const std::size_t i) const{ 
    return op1[i] + op2[i]; 
  }

  std::size_t size() const{ 
    return op1.size(); 
  }
};

// elementwise MyVector * MyVector
template< typename T, typename Op1 , typename Op2 >
class MyVectorMul {
  const Op1& op1;
  const Op2& op2;

public:
  MyVectorMul(const Op1& a, const Op2& b ): op1(a), op2(b){}

  T operator[](const std::size_t i) const{ 
    return op1[i] * op2[i]; 
  }

  std::size_t size() const{ 
    return op1.size(); 
  }
};

// function template for the + operator
template<typename T, typename R1, typename R2>
MyVector<T, MyVectorAdd<T, R1, R2> >
operator+ (const MyVector<T, R1>& a, const MyVector<T, R2>& b){
  return MyVector<T, MyVectorAdd<T, R1, R2> >(MyVectorAdd<T, R1, R2 >(a.data(), b.data()));
}

// function template for the * operator
template<typename T, typename R1, typename R2>
MyVector<T, MyVectorMul< T, R1, R2> >
operator* (const MyVector<T, R1>& a, const MyVector<T, R2>& b){
   return MyVector<T, MyVectorMul<T, R1, R2> >(MyVectorMul<T, R1, R2 >(a.data(), b.data()));
}

// function template for < operator
template<typename T>
std::ostream& operator<<(std::ostream& os, const MyVector<T>& cont){  
  std::cout << std::endl;
  for (int i=0; i<cont.size(); ++i) {
    os << cont[i] << ' ';
  }
  os << std::endl;
  return os;
} 

int main(){

  MyVector<double> x(10,5.4);
  MyVector<double> y(10,10.3);

  MyVector<double> result(10);
  
  result= x+x + y*y;
  
  std::cout << result << std::endl;
  
}

Der entscheidende Unterschied zwischen der naiven Implementierung und der Implementierung mit Expression Templates ist es, dass die überladenen + und * Operatoren in zweiten Fall Stellvertreter Objekte zurückgeben. Diese Stellvertreter repräsentieren die Expression Trees (Zeile 93 und 100), die aufgebaut, aber noch nicht ausgewertet werden. Eben lazy. Erst der Zuweisungs-Operator (Zeile 22 - 27) stößt die Evaluierung des Expression Trees an, der ohne temporären Variablen auskommt.

Da Ergebnis ist natürlich dasselbe.

vectorArithmeticExpressionTemplates

Wer meiner Argumentation nicht folgen kann oder will, den kann ich beruhigen. Der Assembler Code des Programms vectorArithmeticExpressionTemplates.cpp bringt die ganze Magie ans Licht.

Unter der Decke

Mit Hilfe des Compiler Explorers auf godbolt.org sind die GCC Assembler Anweisungen schnell erzeugt.

godbolt

Schön ist der Expression Tree in Zeile 60 nicht. Doch mit mehreren scharfen Blicken lässt sich seine Struktur erkennen. Der Übersichtlichkeit halber habe ich auf die Allokatoren std::allocator verzichtet.

Exression

Wie geht's weiter?

Mit dem nächsten Artikel beginne ich meine Aufräumarbeiten. Dazu werde ich alle gut 120 Artikel überarbeiten und neue Artikel schreiben, die die bisherigen Artikel abrunden. Die einfachste Übersicht liefert meine Startseite.

title page small Go to Leanpub/cpplibrary "What every professional C++ programmer should know about the C++ standard library". Hole dir dein E-Book. Unterstütze meinen Blog.