Expression Templates

[madhu.srikkanth]

Hi,

I came across a paper by Angelika Langer in C++ Users Journal on
Expression Templates.

In the article she had mentioned that the code snippet below used to
calculate a dot product is an expression template.

template <size_t N, class T>
class DotProduct {
public:
static T eval(T* a, T* b)
{ return DotProduct<1,T>::eval(a,b)
+ DotProduct<N-1,T>::eval(a+1,b+1);
}
};

//specialization
template <class T>
class DotProduct<1,T> {
public:
static T eval(T* a, T* b)
{ return (*a)*(*b); }
};

template <size_t N, class T>
inline T dot(T* a, T* b)
{ return DotProduct<N,T>::eval(a,b); }
int a[4] = {1,100,0,-1};
int b[4] = {2,2,2,2};
cout << dot<4>(a,b);

Is this actually an expression template or this just a case of
template meta programming since this doesn't overload the function
operator. My understanding of expression templates may be a bit hazy
as I don't have access to books on the topic as of now. Would be glad
if someone here can throw more light on this.

Cheers
Madhusudhan

 

[Michael DOUBEZ]

(e-mail address removed) a écrit :

Hi,

I came across a paper by Angelika Langer in C++ Users Journal on
Expression Templates.

In the article she had mentioned that the code snippet below used to
calculate a dot product is an expression template.

template <size_t N, class T>
class DotProduct {
public:
static T eval(T* a, T* b)
{ return DotProduct<1,T>::eval(a,b)
+ DotProduct<N-1,T>::eval(a+1,b+1);
}
};

//specialization
template <class T>
class DotProduct<1,T> {
public:
static T eval(T* a, T* b)
{ return (*a)*(*b); }
};

template <size_t N, class T>
inline T dot(T* a, T* b)
{ return DotProduct<N,T>::eval(a,b); }
int a[4] = {1,100,0,-1};
int b[4] = {2,2,2,2};
cout << dot<4>(a,b);

Is this actually an expression template or this just a case of
template meta programming since this doesn't overload the function
operator.

IMO template meta programming deals broadly with operations on type
while expression template focuses on template to provide faster and more
expressive code.

Code above would have been also written:
template <class T>
inline dot(int site,T* a, T* b)
{
T ret=T();
for(int i=0;i<size;++i)
{
ret+=a*b;
}
}

cout << dot(4,a,b);

Unless you have some aggressive optimization (inlining, loop unrolling
....), the code is more likely to create temporaries and other
sub-optimal constructs.

And the alternative:
cout<< (a[0]*b[0]+...+a[3]*b[3])<<endl;
is cumbersome and doesn't give the meaning of what you do.

My understanding of expression templates may be a bit hazy
as I don't have access to books on the topic as of now. Would be glad
if someone here can throw more light on this.

http://en.wikibooks.org/wiki/More_C++_Idioms/Expression-template

 

[James Kanze]

(e-mail address removed) a écrit :

[...]

IMO template meta programming deals broadly with operations on
type while expression template focuses on template to provide
faster and more expressive code.

I'm not sure, but I'd generally consider expression templates as
a subset of template metaprogramming. Generally, I'd consider
anything which involves "writing code for the compiler" in
templates as template meta-programming.

But it really is a question of vocabulary, and I don't think
that there's any one correct answer.

(Note too that much of what is now known under the name of
expression templates was being done before templates existed,
with inheritance. Since all of the derived types ended up being
used as temporary objects, on the stack, the compiler always
knew the exact type, and could inline the functions anyway, even
though they were virtual.)

Code above would have been also written:
template <class T>
inline dot(int site,T* a, T* b)
{
T ret=T();
for(int i=0;i<size;++i)
{
ret+=a*b;
}
}

cout << dot(4,a,b);

Unless you have some aggressive optimization (inlining, loop
unrolling ...), the code is more likely to create temporaries
and other sub-optimal constructs.

Well... maybe not for this simple example. But as soon as
you start doing more complex things, yes. You save a lot of
intermediate temporaries, and it's very, very difficult for the
compiler to eliminate them itself.

And the alternative:
cout<< (a[0]*b[0]+...+a[3]*b[3])<<endl;
is cumbersome and doesn't give the meaning of what you do.

And becomes impossible as soon as the dimension ceases to be a
compile time constant.

Using dot<4>(a,b) expand nicely to a[0]*b[0]+...+a[3]*b[3] while
retaining the meaning.

My understanding of expression templates may be a bit hazy
as I don't have access to books on the topic as of now.
Would be glad if someone here can throw more light on this.

http://en.wikibooks.org/wiki/More_C++_Idioms/Expression-template

Wouldn't it be better to refer him to some original sources,
like Todd Veldhuizen's original article
(http://ubiety.uwaterloo.ca/~tveldhui/papers/Expression-Templates/
exprtmpl.html).
There's also considerable treatment in the Vandevoorde and
Josuttis.

 

[kwikius]

Using dot<4>(a,b) expand nicely to a[0]*b[0]+...+a[3]*b[3] while
retaining the meaning.

See my dot alg for better solution.

http://groups.google.com.tj/group/comp.lang.c++/msg/f1f1c607fec4c10b

see asm at end of thread

regards
Andy Little

 

[kwikius]

And the alternative:
cout<< (a[0]*b[0]+...+a[3]*b[3])<<endl;
is cumbersome and doesn't give the meaning of what you do.

And becomes impossible as soon as the dimension ceases to be a
compile time constant.

I use compile time constants (in template parameters), wherever possible
for mathematical constructs such as size of vectors and matrices for
graphics. I have found that there is never a need to make things such as
size of a vector a runtime value in the algebra domain even for
complicated expressions. The pay offs in speed and code size are very
large. The disadvantage is that compile times increase as expressions
get more complex, but this is a problem of the unsuitability of TMP for
type computations. For example I always use my own pow<N>(v) functon to
the extent now I forget the argument order of the std:ow(v,n) or
pow(n,v) function.

Apart from anything else it is very satisfying to explicitly state the
structure of expressions in terms of types rather than runtime values.

regards
Andy Little

 

[kwikius]

And the alternative:
cout<< (a[0]*b[0]+...+a[3]*b[3])<<endl;
is cumbersome and doesn't give the meaning of what you do.

And becomes impossible as soon as the dimension ceases to be a
compile time constant.

I use compile time constants (in template parameters), wherever possible
for mathematical constructs such as size of vectors and matrices for
graphics. I have found that there is never a need to make things such as
size of a vector a runtime value in the algebra domain even for
complicated expressions. The pay offs in speed and code size are very
large. The disadvantage is that compile times increase as expressions
get more complex, but this is a problem of the unsuitability of TMP for
type computations. For example I always use my own pow<N>(v) functon to
the extent now I forget the argument order of the std:ow(v,n) or
pow(n,v) function.

Apart from anything else it is very satisfying to explicitly state the
structure of expressions in terms of types rather than runtime values.

regards
Andy Little