New Age C++

C++ Generics: Meta-Programming and Variadic Templates

A meta-program is "executed" as the result of template instantiation (therefore, before compiled code is produced). Meta-program results are then compiled and merged into object code, including any back-end optimization.

• By Diego Dagum
• 01/25/2013

I discussed C++ templates last month, and how they differ from the .NET and Java generic programming you're used to. This month I'll discuss some more C++ generics features unavailable in managed code.

I compared C++ templates to stencils, saved until they're instantiated. Then the compiler uses the stencil to generate a concrete class or function. Note, however, that the conversion from source code to object code happens after templates are instantiated. This enables developers to add so-called "meta-programs" in code; programs beyond the program being compiled.

Heavy Meta
A meta-program is "executed" as the result of template instantiation (therefore, before compiled code is produced). Meta-program results are then compiled and merged into object code, including any back-end optimization.

Here's an example: a few months ago I was talking about circular references. I presented an example about a series of people with their best friends. In my main program, I chained them manually:

best_friend["John"] = "Charles";
best_friend["Charles"] = "Emma";
best_friend["Emma"] = "Cindy";
best_friend["Cindy"] = "Arthur";
best_friend["Arthur"] = "Laurie")
best_friend["Laurie"] = "John";

I could avoid this manual typing (which would likely be error-prone, since it would probably be from a copy/paste operation) if I had some high-order function:

generate_circular_friendship("John", "Charles", "Emma", "Cindy", "Arthur", "Laurie");

I'll define this function as a template. Thus, the compiler will apply this "stencil" to produce a code similar to the first snippet:

// You'll probably wonder about the ellipsis (...) in this snippet,
// I'll talk about it next
template <typename F, typename... Fs>
inline void generate_circular_friendship(F friend1, F friend2, Fs... friends) {
    // friend1's best friend is friend2
    add_best_friend(friend1, friend2);
    // then, process sequentially the rest of the people and return
    // the last one. That one's best friend is friend1.
    add_best_friend(generate_sequential_friendship(friend2, friends...), friend1);
}

Notice the ellipsis in the definition above. This is a new C++11 feature known as "variadic templates". My function gets at least two parameters -- friend1 and friend2 -- both of a same generic type, "F". The third argument represents a possibly null series, and is sent "as is" to generate_circular_friendship, as defined here:

template <typename F> // base case
inline F generate_sequential_friendship(F friend1, F friend2) {
    add_best_friend(friend1, friend2);
    return friend2; // the last guy in the duo is returned
}

template <typename F, typename... Fs> // general case
inline F generate_sequential_friendship(F friend1, F friend2, Fs... friends) {
    add_best_friend(friend1, friend2);
    // keep generating the sequence, return the last guy
    return generate_sequential_friendship(friend2, friends...);
}

The first template is the two-argument base case. The second argument becomes the first one's best friend, and is also returned.

The second template is a general case of the function template. Once again I use the variadic notation, as the number of arguments won't be known until instantiation. I can anticipate that this general case will be used when there are three or more arguments. If there are only two, the compiler chooses the first template definition that matches the number of arguments: the base case.

Notice the recursive instantiation of the function template in the general case. It seems recursive, but it's actually another instantiation: the argument "friend1" is missing, so there's one less argument. Thus, it's not the same function.

The definition is completed with the code here:

#include <iostream>
#include <map>

using namespace std;

map<string, string> best_friend;

void add_best_friend(string friend1, string friend2) {
    best_friend[friend1] = friend2;
    cout << friend1 << "'s best friend is " << friend2 << endl;
}

Notice that the function add_best_friend is a regular function, not a template. Running the program produces the following output:

John's best friend is Charles
Charles's best friend is Emma
Emma's best friend is Cindy
Cindy's best friend is Arthur
Arthur's best friend is Laurie
Laurie's best friend is John

This template meta-program produces a complete loop rollout with the list of arguments, generating the proper set of invocations to add_best_friend, depending on the number of arguments.

Computing Values During Compilation
Another use of template meta-programming is the one that computes values during compilation. The produced code contains calculation results, rather than the algorithms used to compute them.

For example, I'll modify generate_circular_friendship to print a legend showing the total number of pairs (person, best friend) that could exist for a given set of people. In other words, the total number of ways to permute n people in ordered pairs. In our example, this is six candidates to fill the first member of the pair, multiplied by five remaining candidates to be their best friend. The template notation is shown here:

template <typename F, typename... Fs>
inline void generate_circular_friendship(F friend1, F friend2, Fs... friends) {
  add_best_friend(friend1, friend2);
  add_best_friend(generate_sequential_friendship(friend2, fs...), friend1);
  // Get ready for a new variadic meta-program  
  cout << endl << "There are " << permutations<2, 2+sizeof...(friends)>::result << " posible pairs (person, best friend)" << endl;
}

See the use of the new C++11 keyword "sizeof...". It returns, during the template instantiation, the number of arguments that a variadic parameter is representing. The template function "permutations" is defined as shown here:

// non-type template parameters
template <unsigned GroupSize, unsigned TotalElements>
struct permutations {
  static const unsigned result = TotalElements*permutations<GroupSize-1, TotalElements-1>::result;
};
// base case as a partial implementation 
template <unsigned TotalElements>
struct permutations<1, TotalElements> {
  static const unsigned result = TotalElements;
};

It may seem strange that the template parameters are declared "unsigned" instead of "typename". These are known as non-type template parameters. These can be all integer types, bool, char, pointer and references. The template parameter GroupSize indicates the number of elements per group (two in my case), while TotalElements speaks for itself (six). The template declares a static constant, result, as the result of a product between the number of elements and the result of recursively permuting one level under.

The final snippet above is completed with a redefinition, known as partial instantiation, saved for the base case when GroupSize is one.

In my example, the instantiation of this template produces the product "6x5 = 30". This 30 literal, rather than the product from which it came, is later included in the object code. The struct permutations, instead, won't get the object code at all.

Study the Black Arts
Template meta-programming is one of the black arts of C++ development. It takes some time to master, but could help you get a few things resolved at compile time instead of runtime. Thus, your executable code should get an extra performance gain on top of the built-in advantage of running on the metal.

Template meta-programming has drawbacks as well. A template meta-program doesn't look much like its equivalent, non-template version. This can challenge your ability to comprehend existing meta-programs from the code itself, if they're not well commented or documented. And since they run at compile time, they slow the compiling process.

Use your judgment with these techniques. They'll help optimize code that needs optimization. If your code doesn't need optimization, then heed that old advice that warns "premature optimization is the root of all evil."

• Get Code Download