18.3 Performance and Limitations of Expression Templates

Ru-Brd

To justify the complexity of the expression template idea, we have already invoked greatly enhanced performance on arraywise operations. As you trace what happens with the expression templates, you'll find that many small inline functions call each other and that many small expression template objects are allocated on the call stack. The optimizer must perform complete inlining and elimination of the small objects to produce code that performs as well as manually coded loops . The latter feat is still rare among C++ compilers at the time of this writing.

The expression templates technique does not resolve all the problematic situations involving numeric operations on arrays. For example, it does not work for matrix-vector multiplications of the form

 x = A*x; 

where x is a column vector of size n and A is an n -by- n matrix. The problem here is that a temporary must be used because each element of the result can depend on each element of the original x . Unfortunately, the expression template loop updates the first element of x right away and then uses that newly computed element to compute the second element, which is wrong. The slightly different expression

 x = A*y; 

on the other hand, does not need a temporary if x and y aren't aliases for each other, which implies that a solution would have to know the relationship of the operands at run time. This in turn suggests creating a run-time structure that represents the expression tree instead of encoding the tree in the type of the expression template. This approach was pioneered by the NewMat library of Robert Davies (see [NewMat]). It was known long before expression templates were developed.

Expression templates aren't limited to numeric computations either. An intriguing application, for example, is Jaakko J rvi and Gary Powell's Lambda Library (see [LambdaLib]). This library uses standard library function objects as expression objects. For example, it allows us to write the following:

 void lambda_demo (std::vector<long*> & ones) {      std::sort(ones.begin(), ones.end(), *_1 > *_2);  } 

This short code excerpt sorts an array in increasing order of the value of what its elements refer to . Without the Lambda library, we'd have to define a simple (but cumbersome) special-purpose functor type. Instead, we can now use simple inline syntax to express the operations we want to apply. In our example, _1 and _2 are placeholders provided by the Lambda library. They correspond to elementary expression objects that are also functors. They can then be used to construct more complex expressions using the techniques developed in this chapter.

Ru-Brd