Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Programming
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Databases
Mail Systems
openSolaris
Eclipse Documentation
Techotopia.com
Virtuatopia.com

How To Guides
Virtualization
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions
Privacy Policy

  




 

 

Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

Expression templates

Perhaps the most powerful application of templates is a technique discovered independently in 1994 by Todd Veldhuizen[79] and Daveed Vandevoorde:[80] 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++.[81]

To motivate the need for expression templates, consider typical numerical linear algebra operations, such as adding together two matrices or vectors,[82] such as in the following:

D = A + B + C;
 

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

v4 = v1 + v2 + v3;
 

The reason is that, after the first addition, a second addition is attempted:

(v1 + v2) + v3;
 

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

v4 = v1 + v2 + v3;
 

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.[83]

Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

 
 
   Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire