Temporäre Objekte vermeiden mit Expression Templates
Expression Templates werden typischerweise in der linearen Algebra verwendet und vermeiden temporäre Objekte.
Expression Templates werden typischerweise in der linearen Algebra verwendet und vermeiden temporäre Objekte.
Sie sind laut Wikipedia [1] "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.
In diesem Artikel stelle ich nur die zentralen Ideen von Expression Templates vor. Um sie einzusetzen, sollte man weitere Inhalte kennen wie
- C++ Templates: The Complete Guide von David Vandervoorde, Nicolai M. Josuttis, und Douglas Gregor (http://www.tmplbook.com/ [2])
- Boost Basic Linear Algebra Library (https://www.boost.org/doc/libs/1_59_0/libs/numeric/ublas/doc/index.html [3])
- Expression Templates Revisited von Klaus Iglberger (https://www.youtube.com/watch?v=hfn0BVOegac [4]). Klaus demystifiziert in seinem Vortrag viele Performanzmythen rund um Expression Templates.
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.
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.
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
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.
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.
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.
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
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/ [5]
Introduction: https://www.modernescpp.org/my-mentoring-program-fundamentals-for-c-professionals/ [6]
Still open questions? Please, call me: info@modernescpp.de [7] ( [8])
URL dieses Artikels:
https://www.heise.de/-6546908
Links in diesem Artikel:
[1] https://en.wikipedia.org/wiki/Expression_templates
[2] http://www.tmplbook.com/
[3] https://www.boost.org/doc/libs/1_59_0/libs/numeric/ublas/doc/index.html
[4] https://www.youtube.com/watch?v=hfn0BVOegac
[5] https://www.modernescpp.org/
[6] https://www.modernescpp.org/my-mentoring-program-fundamentals-for-c-professionals/
[7] mailto:info@modernescpp.de
[8] mailto:rainer@grimm-jaud.de
Copyright © 2022 Heise Medien