Temporäre Objekte vermeiden mit Expression Templates

Modernes C++ Rainer Grimm  –  53 Kommentare

Expression Templates werden typischerweise in der linearen Algebra verwendet und vermeiden temporäre Objekte.

Sie sind laut Wikipedia "structures representing a computation at compile-time, which structures are evaluated only as needed to produce efficient code for the entire computation". Mit anderen Worten: Expression Templates werden nur bei Bedarf ausgewertet.

Temporäre Objekte vermeiden mit Expression Templates

In diesem Artikel stelle ich nur die zentralen Ideen von Expression Templates vor. Um sie einzusetzen, sollte man weitere Inhalte kennen wie

Welches Problem wird mit Expression Templates gelöst? Mit Expression Templates kann man überflüssige temporäre Objekte in Ausdrücken loswerden. Was ich damit meine, zeige ich an meiner Implementierung der Klasse MyVector.

Ein erster naiver Ansatz

MyVector ist ein einfacher Wrapper für einen std::vector<T>. Der Wrapper hat zwei Konstruktoren (1 und 2), kennt seine Länge (3) und unterstützt den Indexzugriff zum Lesen (4) und Schreiben (4) seiner Werte.

// 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){} // (1)

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

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

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

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

};

// function template for the + operator
template<typename T>
MyVector<T> operator+ (const MyVector<T>& a,
const MyVector<T>& b){ // (6)
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)
{ // (7)
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)
{ // (8)
std::cout << '\n';
for (int i = 0; i < cont.size(); ++i) {
os << cont[i] << ' ';
}
os << '\n';
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 << '\n';

}

Dank der überladenen Operatoren + (6) und * (7) und des überladenen Ausgabeoperators (8) verhalten sich die Objekte x, y und result wie Zahlen.

Temporäre Objekte vermeiden mit Expression Templates

Warum ist diese Implementierung naiv? Die Antwort liegt in dem Ausdruck result = x + x + y * y. Um den Ausdruck auszuwerten, werden drei temporäre Objekte benötigt, die das Ergebnis jedes arithmetischen Teilausdrucks enthalten.

Temporäre Objekte vermeiden mit Expression Templates

Wie kann ich diese temporären Objekte loswerden? Die Idee ist einfach: Statt die Vektoroperationen sofort auszuführen, erstelle ich den Ausdruck für result[i] zur Compiletime lazy. Lazy bedeutet, dass ein Ausdruck nur bei Bedarf ausgewertet wird.

Expression Templates

Temporäre Objekte vermeiden mit Expression Templates

Für den Ausdruck result[i] = x[i] + x[i] + y[i] * y[i] werden keine temporären Werte benötigt. Die Zuweisung löst die Auswertung aus. Leider ist der Code selbst in dieser einfachen Anwendung nicht so leicht zu verdauen.

// 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> // (3)
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())); // (1)
}

// 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())); // (2)
}

// function template for < operator
template<typename T>
std::ostream& operator<<(std::ostream& os,
const MyVector<T>& cont){
std::cout << '\n';
for (int i = 0; i < cont.size(); ++i) {
os << cont[i] << ' ';
}
os << '\n';
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 << '\n';

}

Der Hauptunterschied zwischen der ersten naiven Implementierung und dieser Implementierung mit Expression Templates besteht darin, dass die überladenen Operatoren + und * Operatoren im Falle der Ausdrücke Proxyobjekte zurückkehren. Diese Proxys repräsentieren die Ausdrücke (1 und 2). Die Ausdrücke werden nur erstellt, aber nicht ausgewertet: lazy, natürlich. Der Zuweisungsoperator (3) löst die Auswertung des Gesamtausdrucks aus, der keine temporären Objekte benötigt

Die Ergebnisse sind natürlich identisch.

Temporäre Objekte vermeiden mit Expression Templates

Dank des Compiler-Explorers kann ich die Magie des Programms vectorArithmeticExpressionTemplates.cpp offenlegen.

Unter der Haube

Hier sind die wesentlichen Assembler-Anweisungen für die letzte Zuweisung in der Hauptfunktion: result = x + x + y * y.

Temporäre Objekte vermeiden mit Expression Templates

Der Ausdruck in dem Assemblerschnipsel schaut ziemlich kompliziert aus, aber mit einem scharfen Auge erkennt man die Struktur . Der Einfachheit halber habe ich std::allocator in meiner Grafik ignoriert.

Temporäre Objekte vermeiden mit Expression Templates

Wie geht's weiter?

Eine Policy ist eine generische Funktion oder Klasse, deren Verhalten konfiguriert werden kann. Ich werde sie in meinem nächsten Artikel genauer vorstellen.

My English Mentoring Program "Fundamentals for C++ Professionals" is Open for Registration

Temporäre Objekte vermeiden mit Expression Templates

My new mentoring program "Fundamentals for C++ Professionals" starts on April 22nd. Registration is open until April 17nd. Here is more information:

Launch page: https://www.modernescpp.org/

Introduction: https://www.modernescpp.org/my-mentoring-program-fundamentals-for-c-professionals/

Still open questions? Please, call me: info@modernescpp.de