Template Meta Programming

[Jon Rea]

http://osl.iu.edu/~tveldhui/papers/Template-Metaprograms/meta-art.html

Can anyone shed some light on the need for stuff like this when using
any of the most modern compilers?

If i have a function :

double Square( double d )
{
return d * d;
}

and use it like this:

int main()
{
double answer = Square( 4.0 );
}

I always assumed that the compiler is cleaver enough to decide that the
function call is not needed and just set 'answer' to 16 in the compiled
machine code. If that is the case, is the use of simple meta templates
irrelevent with modern compilers (esp. see 'Temporary variables' in the
example posted URL above).

I assume that more complex meta programs are still useful today when the
compiler cannot make informed choices about complex code.

Many thanks for your replies,
Jon

 

[Victor Bazarov]

http://osl.iu.edu/~tveldhui/papers/Template-Metaprograms/meta-art.html

Can anyone shed some light on the need for stuff like this when using
any of the most modern compilers?

If i have a function :

double Square( double d )
{
return d * d;
}

and use it like this:

int main()
{
double answer = Square( 4.0 );
}

I always assumed that the compiler is cleaver enough to decide that
the function call is not needed and just set 'answer' to 16 in the
compiled machine code. If that is the case, is the use of simple meta
templates irrelevent with modern compilers (esp. see 'Temporary
variables' in the example posted URL above).

How do templates play into this non-template code? Here your 'Square'
always takes a double and returns a double. If you would like to use
any type that defines the "squaring" semantics, you _should_ declare
(and define) 'Square' as a template.

I assume that more complex meta programs are still useful today when
the compiler cannot make informed choices about complex code.

I am not sure what exactly your question/statement means. You seem
to want to simplify template metaprogramming by reducing it to making
compile-time calculations and using the results instead of computing
those values during run-time. But you're discounting the whole other
side of templates: compile-time polymorphism. How come?

V

 

[=?ISO-8859-1?Q?Szabolcs_Horv=E1t?=]

double Square( double d )
{
return d * d;
}

and use it like this:

int main()
{
double answer = Square( 4.0 );
}

I always assumed that the compiler is cleaver enough to decide that the
function call is not needed and just set 'answer' to 16 in the compiled
machine code. If that is the case, is the use of simple meta templates
irrelevent with modern compilers (esp. see 'Temporary variables' in the
example posted URL above).

The compiler will optimize away the call to Square() if Square() is an
inline function. Some optimizing compilers (such as g++ with the -O3
option) can inline functions automatically.

Template metaprogramming is another thing: it allows to automatically
generate specialized (and thus efficient) code. E.g., if you want to
create a function that computes integer powers, you could use a for loop:

double power(int i, double x) {
double res = 1.0
for (; i > 0; i--)
res *= x;
return res;
}

The compiler cannot optimize a call to power(3,x) to x*x*x. But you can
achieve this using the following function:

template<int N>
inline double power(double x) { return x*power<N-1>(x); }

template<>
inline double power<1>(double x) { return x; }

Now power<3>(x) is exactly equivalent to x*x*x;

You can further improve this function to compute x^4 as t=x*x;
result=t*t; i.e. with 2 multiplications instead of 3. If you want this
to work for any integer power (e.g x^6 = (x^2)^3) you must use recursive
function calls. But functions that call themselves cannot be inlined
unless the argument that changes during subsequent calls is a template
parameter.

I hope this example sheds some light on the usefulness of template
metaprogramming.

-- Szabolcs

 

[ristretto4u]

I wrote a simple example of how to do a dot product using template
expressions. The following is optimised to a single assignment
expression.

template<typename _Value>
struct Vector
{
_Value _value;
};

template<typename _Vector> struct VectorDotProd {};

template<typename _Type, int _Length>
struct VectorDotProd<Vector<_Type[_Length]> >
{
typedef Vector<_Type[_Length]> _Vector;

__inline static float Apply(_Vector const & vector0,
_Vector const & vector1)
{
return Impl<_Type, _Length-1>::Apply(vector0, vector1);
}

template<typename _Type, int _Index>
struct Impl
{
__inline static float Apply(_Vector const & vector0,
_Vector const & vector1)
{
return vector0._value[_Index] * vector1._value[_Index]
+ Impl<_Type, _Index-1>::Apply(vector0, vector1);
}
};

template<typename _Type>
struct Impl<_Type, 0>
{
__inline static float Apply(_Vector const & vector0,
_Vector const & vector1)
{
return vector0._value[0] * vector1._value[0];
}
};

};

int main()
{
typedef Vector<float[3]> Vector3f;
Vector3f v0 = {1.0f, 2.0f, 3.0f};
Vector3f v1 = {1.0f, 2.0f, 3.0f};

float result = VectorDotProd<Vector3f>::Apply(v0, v1);
_RPTF1(_CRT_WARN, "v0.v1 = %f\n", result);

printf("%f\n", result);

return 0;
}

 

[Azumanga]

The compiler will optimize away the call to Square() if Square() is an
inline function. Some optimizing compilers (such as g++ with the -O3
option) can inline functions automatically.

Template metaprogramming is another thing: it allows to automatically
generate specialized (and thus efficient) code. E.g., if you want to
create a function that computes integer powers, you could use a for loop:

double power(int i, double x) {
double res = 1.0
for (; i > 0; i--)
res *= x;
return res;
}

The compiler cannot optimize a call to power(3,x) to x*x*x. But you can
achieve this using the following function:

Do not underestimate modern compilers. g++ on -O3 is quite capable of
turning "power(3,d)" into "d*d*d". (I saw this by running
-fdump-tree-all, a command which shows the internal structure of the
code as the compiler compiles it). Of course templates are still
useful, but I consider them more useful for writing different functions
for different types and avoiding virtual functions, not for forcing
optimisers to do things they can often do by themselves.

 

[Rolf Magnus]

The compiler will optimize away the call to Square() if Square() is an
inline function. Some optimizing compilers (such as g++ with the -O3
option) can inline functions automatically.

However, the function's code must be known in the translation unit that it
is used in, which usually means that you have to define it in the header
instead of doing the usual separation interface/implementation.

Template metaprogramming is another thing: it allows to automatically
generate specialized (and thus efficient) code. E.g., if you want to
create a function that computes integer powers, you could use a for loop:

double power(int i, double x) {
double res = 1.0
for (; i > 0; i--)
res *= x;
return res;
}

The compiler cannot optimize a call to power(3,x) to x*x*x.

Well, you'd be surprised what kinds of optimzations compilers are capable
of.

 

[red floyd]

I wrote a simple example of how to do a dot product using template
expressions. The following is optimised to a single assignment
expression.

template<typename _Value>
struct Vector
{
_Value _value;
};

The identifier _Value is reserved to the implementation per 17.4.3.1.2,
and therefore your program will exhibit undefined behavior. It can do
anything.

[remainder of code redacted]

 

[Nate Barney]

template<int N>
inline double power(double x) { return x*power<N-1>(x); }

template<>
inline double power<1>(double x) { return x; }

As a side note, n to the 0 power is 1, so it would seem to be more
correct to specialize for N=0:

template<>
inline double power<0>(double) { return 1.0; }

Given this, The specialization for N=1 might still be useful, or might
not be.


Nate

 

[=?ISO-8859-1?Q?Szabolcs_Horv=E1t?=]

Do not underestimate modern compilers. g++ on -O3 is quite capable of
turning "power(3,d)" into "d*d*d". (I saw this by running
-fdump-tree-all, a command which shows the internal structure of the
code as the compiler compiles it). Of course templates are still
useful, but I consider them more useful for writing different functions
for different types and avoiding virtual functions, not for forcing
optimisers to do things they can often do by themselves.

Wow, I am really amazed! I checked the assembly output and it really
does compute it at compile time.

However, the optimizer is still not smart enough to turn x*x*x*x into
(x^2)^2, nor can it optimize away a function that implements this using
recursion. But you can do it with templates (see attached code). This
way C++'s integer power calculation can be just as efficient as FORTRAN's.

According to http://osl.iu.edu/~tveldhui/papers/techniques/ , section
1.9, these techniques can also be used to eliminate temporaries when
e.g. adding to vectors 'a' and 'b' and make 'c=a+b;' store the result
directly into 'c', without the + operator creating and intermediate
object which in turn would be copied into 'c'.
See http://www.oonumerics.org/blitz/

Performance if often important when you are doing physics, like Jon.

I admit that these techniques can be really ugly and confusing, at least
I got really confused when trying to implement similar things (and gave
up). But they are also fascinating.

---

template<int N>
inline double power(double x) {
if (N%2 == 0)
return power<2>(power<N/2>(x));
if (N%3 == 0)
return power<3>(power<N/3>(x));
return x*power<N-1>(x);
}

template<>
inline double power<1>(double x) { return x; }

template<>
inline double power<2>(double x) { return x*x; }

template<>
inline double power<3>(double x) { return x*x*x; }