Template Metaprogramming - i still don't get it :(

Question

Hi folks ...

i have a problem .. i don't understand Template Metaprogramming.

The Problem is : i read a lot . But it does not make much sense to me :/

Fact nr.1 : Template Metaprogramming is faster

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

// Factorial<4>::value == 24
// Factorial<0>::value == 1
void foo()
{
    int x = Factorial<4>::value; // == 24
    int y = Factorial<0>::value; // == 1
}

so this Metaprogram is faster ... beacause of the Constant Literal.
BUT : Where in the real World do we have constant Literals ?
Most programms i use react on user input.

FACT nr. 2 : Template Metaprogramming can acomplish better maintainability.

Yeah.The Factorial Example May Be maintainable ... but when it comes to complex functions, i and most of other C++ programmers can't read the functions. And the Debugging options are poor.(or at least i don't know how to debug )

Where does Template Metaprogramming make sense ?

Answer 1

I suggest you read Modern C++ Design by Andrei Alexandrescu - this is probably one of the best books on real-world uses of C++ template metaprogramming; and describes many problems which C++ templates are an excellent solution.

Answer 2

Just as factorial is not a realistic example of recursion in non-functional languages, neither is it a realistic example of template metaprogramming. It's just the standard example people reach for when they want to show you recursion.

In writing templates for realistic purposes, such as in everyday libraries, often the template has to adapt what it does depending on the type parameters it is instantiated with. This can get quite complex, as the template effectively chooses what code to generate, conditionally. This is what template metaprogramming is; if the template has to loop (via recursion) and choose between alternatives, it is effectively like a small program that executes during compilation to generate the right code.

Here's a really nice tutorial from the boost documentation pages (actually excerpted from a brilliant book, well worth reading).

http://www.boost.org/doc/libs/1_39_0/libs/mpl/doc/tutorial/representing-dimensions.html

Answer 3

TMP can be used from anything like ensuring dimensional correctness (Ensuring that mass cannot be divided by time, but distance can be divided by time and assigned to a velocity variable) to optimizing matrix operations by removing temporary objects and merging loops when many matrices are involved.

Answer 4

Scott Meyers has been working on enforcing code constraints using TMP.

Its quite a good read:
http://www.artima.com/cppsource/codefeatures.html

In this article he introduces the concepts of Sets of Types (not a new concept but his work is based ontop of this concept). Then uses TMP to make sure that no matter what order you specify the members of the set that if two sets are made of the same members then they are equavalent. This requires that he be able to sort and re-order a list of types and compare them dynamically thus generating compile time errors when they do not match.

Answer 5

so this Metaprogram is faster ... beacause of the Constant Literal. BUT : Where in the real World do we have constant Literals ? Most programms i use react on user input.

That's why it's hardly ever used for values. Usually, it is used on types. using types to compute and generate new types.

There are many real-world uses, some of which you're already familiar with even if you don't realize it.

One of my favorite examples is that of iterators. They're mostly designed just with generic programming, yes, but template metaprogramming is useful in one place in particular:

To patch up pointers so they can be used as iterators. An iterator must expose a handful of typedef's, such as value_type. Pointers don't do that.

So code such as the following (basically identical to what you find in Boost.Iterator)

template <typename T>
struct value_type {
  typedef typename T::value_type type;
};

template <typename T>
struct value_type<T*> {
  typedef T type;
};

is a very simple template metaprogram, but which is very useful. It lets you get the value type of any iterator type T, whether it is a pointer or a class, simply by value_type<T>::type.

And I think the above has some very clear benefits when it comes to maintainability. Your algorithm operating on iterators only has to be implemented once. Without this trick, you'd have to make one implementation for pointers, and another for "proper" class-based iterators.

Tricks like boost::enable_if can be very valuable too. You have an overload of a function which should be enabled for a specific set of types only. Rather than defining an overload for each type, you can use metaprogramming to specify the condition and pass it to enable_if.

Earwicker already mentioned another good example, a framework for expressing physical units and dimensions. It allows you to express computations like with physical units attached, and enforces the result type. Multiplying meters by meters yields a number of square meters. Template metaprogramming can be used to automatically produce the right type.

But most of the time, template metaprogramming is used (and useful) in small, isolated cases, basically to smooth out bumps and exceptional cases, to make a set of types look and behave uniformly, allowing you to use generic programming more efficiently

Answer 6

Seconding the recommendation for Alexandrescu's Modern C++ Design.

Templates really shine when you're writing a library that has pieces which can be assembled combinatorically in a "choose a Foo, a Bar and a Baz" approach, and you expect users to make use of these pieces in some form that is fixed at compile time. For example, I coauthored a data mining library that uses template metaprogramming to let the programmer decide what DecisionType to use (classification, ranking or regression), what InputType to expect (floats, ints, enumerated values, whatever), and what KernelMethod to use (it's a data mining thing). We then implemented several different classes for each category, such that there were several dozen possible combinations.

Implementing 60 separate classes to do this would have involved a lot of annoying, hard-to-maintain code duplication. Template metaprogramming meant that we could implement each concept as a code unit, and give the programmer a simple interface for instantiating combinations of these concepts at compile-time.

Dimensional analysis is also an excellent example, but other people have covered that.

I also once wrote some simple compile-time pseudo-random number generators just to mess with people's heads, but that doesn't really count IMO.

Answer 7

I use template mete-programming for SSE swizzling operators to optimize shuffles during compile time.

SSE swizzles ('shuffles') can only be masked as a byte literal (immediate value), so we created a 'mask merger' template class that merges masks during compile time for when multiple shuffle occur:

template <unsigned target, unsigned mask>
struct _mask_merger
{
 enum
 {
  ROW0 = ((target >> (((mask >> 0) & 3) << 1)) & 3) << 0,
  ROW1 = ((target >> (((mask >> 2) & 3) << 1)) & 3) << 2,
  ROW2 = ((target >> (((mask >> 4) & 3) << 1)) & 3) << 4,
  ROW3 = ((target >> (((mask >> 6) & 3) << 1)) & 3) << 6,

  MASK = ROW0 | ROW1 | ROW2 | ROW3,
 };
};

This works and produces remarkable code without generated code overhead and little extra compile time.

Answer 8

Here's one trivial example, a binary constant converter, from a previous question here on StackOverflow:

http://stackoverflow.com/questions/699781/c-binary-constant-literal

template< unsigned long long N >
struct binary
{
  enum { value = (N % 10) + 2 * binary< N / 10 > :: value } ;
};
template<>
struct binary< 0 >
{
  enum { value = 0 } ;
};

Answer 9

The factorial example is about as useful for real-world TMP as "Hello, world!" is for common programming: It's there to show you a few useful techniques (recursion instead of iteration, "else-if-then" etc.) in a very simple, relatively easy to understand example that doesn't have much relevance for your every-day coding. (When was the last time you needed to write a program that emitted "Hello, world"?)

TMP is about executing algorithms at compile-time and this implies a few obvious advantages:

• Since these algorithms failing means your code doesn't compile, failing algorithms never make it to your customer and thus can't fail at the customer's. For me, during the last decade this was the single-most important advantage that led me to introduce TMP into the code of the companies I worked for.
• Since the result of executing template-meta programs is ordinary code that's then compiled by the compiler, all advantages of code generating algorithms (reduced redundancy etc.) apply.
• Of course, since they are executed at compile-time, these algorithms won't need any run-time and will thus run faster. TMP is mostly about compile-time computing with a few, mostly small, inlined functions sprinkled in between, so compilers have ample opportunities to optimize the resulting code.

Of course, there's disadvantages, too:

• The error messages can be horrible.
• There's no debugging.
• The code is often hard to read.

As always, you'll just have to weight the advantages against the disadvantages in every case.

As for a more useful example: Once you have grasped type lists and basic compile-time algorithms operating on them, you might understand the following:

typedef 
    type_list_generator< signed char
                       , signed short
                       , signed int
                       , signed long
                       >::result_type
    signed_int_type_list;

typedef 
    type_list_find_if< signed_int_type_list
                     , exact_size_predicate<8>
                     >::result_type
    int8_t;

typedef 
    type_list_find_if< signed_int_type_list
                     , exact_size_predicate<16>
                     >::result_type
    int16_t;

typedef 
    type_list_find_if< signed_int_type_list
                     , exact_size_predicate<32>
                     >::result_type
    int32_t;

This is (slightly simplified) actual code I wrote a few weeks ago. It will pick the appropriate types from a type list, replacing the #ifdef orgies common in portable code. It doesn't need maintenance, works without adaption on every platform your code might need to get ported to, and emits a compile error if the current platform doesn't have the right type.

Another example is this:

template< typename TFunc, typename TFwdIter >
typename func_traits<TFunc>::result_t callFunc(TFunc f, TFwdIter begin, TFwdIter end);

Given a function f and a sequence of strings, this will dissect the function's signature, convert the strings from the sequence into the right types, and call the function with these objects. And it's mostly TMP inside.

Answer 10

TMP does not necessarily mean faster or more maintainable code. I used the boost spirit library to implement a simple SQL expression parser that builds an evaluation tree structure. While the development time was reduced since I had some familiarity with TMP and lambda, the learning curve is a brick wall for "C with classes" developers, and the performance is not as good as a traditional LEX/YACC.

I see Template Meta Programming as just another tool in my tool-belt. When it works for you use it, if it doesn't, use another tool.

Answer 11

'static const' values work as well. And pointers-to-member. And don't forget the world of types (explicit and deduced) as compile-time arguments!

BUT : Where in the real World do we have constant Literals ?

Suppose you have some code that has to run as fast as possible. It contains the critical inner loop of your CPU-bound computation in fact. You'd be willing to increase the size of your executable a bit to make it faster. It looks like:

double innerLoop(const bool b, const vector<double> & v)
{
    // some logic involving b

    for (vector::const_iterator it = v.begin; it != v.end(); ++it)
    {
        // significant logic involving b
    }

    // more logic involving b
    return ....
}

The details aren't important, but the use of 'b' is pervasive in the implementation.

Now, with templates, you can refactor it a bit:

template <bool b> double innerLoop_B(vector<double> v) { ... same as before ... }
double innerLoop(const bool b, const vector<double> & v)
{ return b ? innerLoop_templ_B<true>(v) : innerLoop_templ_B<false>(v) ); }

Any time you have a relatively small, discrete, set of values for a parameter you can automatically instantiate separate versions for them.

Consider the possiblities when 'b' is based on the CPU detection. You can run a differently-optimized set of code depending on run-time detection. All from the same source code, or you can specialize some functions for some sets of values.

As a concrete example, I once saw some code that needed to merge some integer coordinates. Coordinate system 'a' was one of two resolutions (known at compile time), and coordinate system 'b' was one of two different resolutions (also known at compile time). The target coordinate system needed to be the least common multiple of the two source coordinate systems. A library was used to compute the LCM at compile time and instantiate code for the different possibilities.