Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |
Perhaps the most powerful application of templates is a
technique discovered independently in 1994 by Todd Veldhuizen and Daveed
Vandevoorde: expression
templates. Expression templates enable extensive compile-time optimization
of certain computations that result in code that is at least as fast as
hand-optimized Fortran, and yet preserves the natural notation of mathematics
via operator overloading. Although you wouldn t be likely to use this technique
in everyday programming, it is the basis for a number of sophisticated,
high-performance mathematical libraries written in C++.
To motivate the need for expression templates, consider typical
numerical linear algebra operations, such as adding together two matrices or
vectors, such as in the
following:
In naive implementations, this expression would result in a
number of temporaries one for A+B, and one for (A+B)+C. When
these variables represent immense matrices or vectors, the coincident drain on
resources is unacceptable. Expression templates allow you to use the same
expression without temporaries.
The following program defines a MyVector class to
simulate mathematical vectors of any size. We use a non-type template argument
for the length of the vector. We also define a MyVectorSum class to act
as a proxy class for a sum of MyVector objects. This allows us to use
lazy evaluation, so the addition of vector components is performed on demand
without the need for temporaries.
//: C05:MyVector.cpp
// Optimizes away temporaries via templates.
#include <cstddef>
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;
// A proxy class for sums of vectors
template<class, size_t> class MyVectorSum;
template<class T, size_t N> class MyVector {
T data[N];
public:
MyVector<T,N>& operator=(const
MyVector<T,N>& right) {
for(size_t i = 0; i < N; ++i)
data[i] = right.data[i];
return *this;
}
MyVector<T,N>& operator=(const
MyVectorSum<T,N>& right);
const T& operator[](size_t i) const { return
data[i]; }
T& operator[](size_t i) { return data[i]; }
};
// Proxy class hold references; uses lazy addition
template<class T, size_t N> class MyVectorSum {
const MyVector<T,N>& left;
const MyVector<T,N>& right;
public:
MyVectorSum(const MyVector<T,N>& lhs,
const MyVector<T,N>& rhs)
: left(lhs), right(rhs) {}
T operator[](size_t i) const {
return left[i] + right[i];
}
};
// Operator to support v3 = v1 + v2
template<class T, size_t N> MyVector<T,N>&
MyVector<T,N>::operator=(const
MyVectorSum<T,N>& right) {
for(size_t i = 0; i < N; ++i)
data[i] = right[i];
return *this;
}
// operator+ just stores references
template<class T, size_t N> inline
MyVectorSum<T,N>
operator+(const MyVector<T,N>& left,
const MyVector<T,N>& right) {
return MyVectorSum<T,N>(left, right);
}
// Convenience functions for the test program below
template<class T, size_t N> void
init(MyVector<T,N>& v) {
for(size_t i = 0; i < N; ++i)
v[i] = rand() % 100;
}
template<class T, size_t N> void
print(MyVector<T,N>& v) {
for(size_t i = 0; i < N; ++i)
cout << v[i] << ' ';
cout << endl;
}
int main() {
srand(time(0));
MyVector<int, 5> v1;
init(v1);
print(v1);
MyVector<int, 5> v2;
init(v2);
print(v2);
MyVector<int, 5> v3;
v3 = v1 + v2;
print(v3);
MyVector<int, 5> v4;
// Not yet supported:
//! v4 = v1 + v2 + v3;
} ///:~
The MyVectorSum class does no computation when it is
created; it merely holds references to the two vectors to be added. Calculations
happen only when you access a component of a vector sum (see its operator[ ]( )).
The overload of the assignment operator for MyVector that takes a MyVectorSum
argument is for an expression such as:
v1 = v2 + v3;
// Add two vectors
When the expression v1+v2 is evaluated, a MyVectorSum
object is returned (or actually, inserted inline, since that operator+( )
is declared inline). This is a small, fixed-size object (it holds only
two references). Then the assignment operator mentioned above is invoked:
v3.operator=<int,5>(MyVectorSum<int,5>(v2,
v3));
This assigns to each element of v3 the sum of the
corresponding elements of v1 and v2, computed in real time. No
temporary MyVector objects are created.
This program does not support an expression that has more
than two operands, however, such as
The reason is that, after the first addition, a second
addition is attempted:
which would require an operator+( ) with a first
argument of MyVectorSum and a second argument of type MyVector.
We could attempt to provide a number of overloads to meet all situations, but
it is better to let templates do the work, as in the following version of the
program:
//: C05:MyVector2.cpp
// Handles sums of any length with expression templates.
#include <cstddef>
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;
// A proxy class for sums of vectors
template<class, size_t, class, class> class
MyVectorSum;
template<class T, size_t N> class MyVector {
T data[N];
public:
MyVector<T,N>& operator=(const
MyVector<T,N>& right) {
for(size_t i = 0; i < N; ++i)
data[i] = right.data[i];
return *this;
}
template<class Left, class
Right> MyVector<T,N>&
operator=(const
MyVectorSum<T,N,Left,Right>& right);
const T& operator[](size_t i) const {
return data[i];
}
T& operator[](size_t i) {
return data[i];
}
};
// Allows mixing MyVector and MyVectorSum
template<class T, size_t N, class Left, class
Right>
class MyVectorSum {
const Left& left;
const Right& right;
public:
MyVectorSum(const Left& lhs, const Right&
rhs)
: left(lhs), right(rhs) {}
T operator[](size_t i) const {
return left[i] + right[i];
}
};
template<class T, size_t N>
template<class Left, class Right>
MyVector<T,N>&
MyVector<T,N>::
operator=(const MyVectorSum<T,N,Left,Right>&
right) {
for(size_t i = 0; i < N; ++i)
data[i] = right[i];
return *this;
}
// operator+ just stores references
template<class T, size_t N>
inline
MyVectorSum<T,N,MyVector<T,N>,MyVector<T,N> >
operator+(const MyVector<T,N>& left,
const MyVector<T,N>& right) {
return
MyVectorSum<T,N,MyVector<T,N>,MyVector<T,N> >
(left,right);
}
template<class T, size_t N, class Left, class
Right>
inline MyVectorSum<T, N,
MyVectorSum<T,N,Left,Right>,
MyVector<T,N> >
operator+(const MyVectorSum<T,N,Left,Right>&
left,
const MyVector<T,N>& right) {
return
MyVectorSum<T,N,MyVectorSum<T,N,Left,Right>,
MyVector<T,N> >
(left, right);
}
// Convenience functions for the test program below
template<class T, size_t N> void
init(MyVector<T,N>& v) {
for(size_t i = 0; i < N; ++i)
v[i] = rand() % 100;
}
template<class T, size_t N> void
print(MyVector<T,N>& v) {
for(size_t i = 0; i < N; ++i)
cout << v[i] << ' ';
cout << endl;
}
int main() {
srand(time(0));
MyVector<int, 5> v1;
init(v1);
print(v1);
MyVector<int, 5> v2;
init(v2);
print(v2);
MyVector<int, 5> v3;
v3 = v1 + v2;
print(v3);
// Now supported:
MyVector<int, 5> v4;
v4 = v1 + v2 + v3;
print(v4);
MyVector<int, 5> v5;
v5 = v1 + v2 + v3 + v4;
print(v5);
} ///:~
The template facility deduces the argument types of a sum
using the template arguments, Left and Right, instead of
committing to those types ahead of time. The MyVectorSum template takes
these extra two parameters so it can represent a sum of any combination of
pairs of MyVector and MyVectorSum.
The assignment operator is now a member function template.
This allows any <T, N> pair to be coupled with any <Left,
Right> pair, so a MyVector object can be assigned from a MyVectorSum
holding references to any possible pair of the types MyVector and MyVectorSum.
As we did before, let s trace through a sample assignment to
understand exactly what takes place, beginning with the expression
Since the resulting expressions become quite unwieldy, in
the explanation that follows, we will use MVS as shorthand for MyVectorSum,
and will omit the template arguments.
The first operation is v1+v2, which invokes the
inline operator+( ), which in turn inserts MVS(v1, v2) into
the compilation stream. This is then added to v3, which results in a
temporary object according to the expression MVS(MVS(v1, v2), v3). The
final representation of the entire statement is
v4.operator+(MVS(MVS(v1,
v2), v3));
This transformation is all arranged by the compiler and
explains why this technique carries the moniker expression templates. The template
MyVectorSum represents an expression (an addition, in this case), and
the nested calls above are reminiscent of the parse tree of the left-associative
expression v1+v2+v3.
An excellent article by Angelika Langer and Klaus Kreft explains how this technique can be extended to more complex computations.
Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |