Template expressions

Template expressions are type manipulations used to guide the compiler to produce optimised code. We illustrate their use on the addition of vectors. Consider for instance the following instruction:

   v = v1 + v2 + v3;

where v, v1,v2, v3 are vectors (say of type Vector). Usual implementations would defined the operator. Usual implementations would defined the operator

   Vector & operator+(const Vector & v1, Vector & v2);

so that the previous instruction will produce the temporary vector (say tmp1) for the addition of v1 and v2, another one (say vtmp2) for the addition of vtmp1 and v3 and will use the operator

   Vector & Vector::operator=(const Vector & v);

to assign v to the value of vtmp2, using the loop

   for(index_type i=0; i< v.size(); ++i) v[i] = vtmp2[i];

In such an implementation, two temporary vectors are allocated and deleted, which is time and memory consuming, especially if the vectors are of large size. A more optimised implementation would consist in writing the code

   for(index_type i=0; i<v.size(); ++i) v[i] = v1[i]+v2[i]+v3[i];

This code can be generated directly, at compilation time, using template expression techniques. Instead of defining the operator +, as before, we define it with the following signature:

VAL<OP<'+',Vector,Vector> > operator+(const Vector & v1, Vector & v2);

where VAL<OP<'+',Vector,Vector> > is the type of a data-structure which contains references to the two vectors v1, v2, but which does not compute the sum of this two vectors. The instruction v1+v2+v3 we are considering, produces a data of type

   VAL<OP<'+',Vector, VAL<OP,'+',Vector,Vector> > >;

Now, the assignment

   v = v1+v2+v3;

will involve the operator

   template<class R> Vector & operator=(const VAL<R> & v);

which is implemented as

   for(index-stype i=0; i<v.size(); ++i) (*this)[i] = _elem(v,i);

The key point is that the compiler will expand the call to the inline function _elem(v,i) into v1[i]+v2[i]+v3[i], because the ith element of an element v of type VAL<OP<'+',...,...> > is the sum of the ith of its two components.

Here are the arithmetic operations implemented with {{template expressions}} and their meaning:

• OP<'+',A,B>, sum of two terms.

• OP<'-',A,B>, substraction of two terms.

• OP1<'-',A>, opposite of a term.

• OP<'*',A,B>, multiplication of two terms.

• OP<'.',A,B>, multiplication of the term of type A by a scalar of type B.

• OP<'/',A,B>, division of two terms.

• OP<'%',A,B>, division of the term of type A by a scalar of type B.

• OP<'\^{ ',A,B>}, power of the term of type A by a scalar of type B.

Such arithmetic operations will return an unevaluated arithmetic tree and the computation will be performed only when the assignment operator will be used.