Template Metaprogramming: Compile time loops over class methods

Don’t be scared by the title!

Template Metaprogramming: Getting your code to write code (credit)

This post was inspired by this blog post. In the post, Stefan mentions that he is leaving the full blown implementation as an “exercise for the reader”. After a while learning about template metaprogramming I came up with an implementation that I thought I’d share in this post. Yes, you can use boost but where’s the fun in that?

Ultimately, the util method we end up creating here will be used for my game engine implementation, so if you can’t see a real use case quite yet, just wait ;).

Problem

We want to execute a for loop that calls a class method that relies on the iterator value parameter. This is is an extraordinarily easy problem, here’s the solution:

(Once again, if viewing on iOS make sure to open in Safari to see the gists inline)

Wow, what an easy blog post, we can all go home now!

Just kidding. The actual challenge is to perform the above operation, but executed at compile time instead of runtime. This is known as loop unrolling, because instead of the loop shown above, the compiled version will look something like:

someClassMethod(0);
someClassMethod(1);
someClassMethod(2);
someClassMethod(3);

When you look up “loop unrolling”, usually it’s explained as a tiny space-time trade off optimization. Our use case, however, is that we want access to our iterator i at compile time instead of runtime. This means instead of passing i as an argument, we need to pass it as a template argument:

template<int N>
someClassMethod(/* Possible other arguments here */) {
  /* Some code that uses N, needs it to be a template */
}

If you don’t have a lot of experience with templates, you might expect to be able to write some code like this:

for(int i=0; i < 4; i++){
  someClassMethod<i>();
}

Unfortunately, this isn’t possible because i is only available at runtime, while templates are compiled at compile time. This is a very important concept to understand when dealing with templates in C++: templates don’t exist at runtime. All templates are compiled to real types at compile time.

So, if we call a templated method with two different template arguments, they will actually be compiled into two totally different calls:

It follows that trying to call a method with a value that only exists at runtime like i isn’t possible — templates don’t even exist at runtime!

Solution

Well this is it. This is what we call template metaprogramming. We’re trying to write code that will run at compile time, and first we need to figure out how to write a loop. A lot of template metaprogramming relies on recursion, because we don’t have “variables” — templates are just a big state machine.

Here’s some non-templated pseudo code explaining what we’re going to do:

Before we start, there’s a great wikibooks article on the building blocks of template metaprogramming, which explains how we can implement variables (cannot be altered), functions, and branching. Might be worth giving it a quick look over before moving on here.

Here’s our templated for loop:

Here’s what happens if we run forLoop< 3 >():

321done

Why does this work?

The keyword template<> indicates that we are “specializing” our template method. In this case, we’re performing a partial specialization. For a quick introduction to partial specialization of templates, check out this example.

So far pretty easy. Let’s toss our code into an example:

Cleaning House

Our robot cleaning business (credit)

We run a cleaning business that has to clean a bunch of houses but with a different tool each day. Here’s our HouseCleaner class:

This seems fine until we want to come up with something more generic, something we can reuse. What if we have 3 different member classes that we want to call? Well, we’d better be ready to write 6 template loopers! (also note that this won’t actually compile)

So how can we generalize this to work for any class and any member method? Our first issue is to be able to pass in generic arguments (and any number of them!). To do this, we will have to modify our looper a little bit:

If the “…” syntax doesn’t make sense, check out this post on variadic templates. They’re not a super difficult concept but are important for the functionality of this method.

Edit note: Previously I was using rvalue references (&&), but after further consideration they are not necessary and might actually cause some runtime issues. Instead, we use regular references (&). If you’re curious about rvalue references, you can read more about them here.

Further Generalizing forLoop

Now we’ve generalized our arguments but unfortunately we’re still making the cleanHouse() call. There are a couple roads that *look* like good solutions but unfortunately don’t fit our requirements.

1. Pass a pointer-to-member into our loop
   This doesn’t work because you can’t get a generic pointer to templated member: &HouseCleaner::cleanHouse<0> is a valid pointer-to-member, but there’s no way of passing the generic &HouseCleaner::cleanHouse (don’t worry if this sounds confusing, trust me it won’t work).
2. Change cleanHouse to a struct with operator() and pass it in.
   This is pretty close to what we will end up doing, so let’s try implementing it.

Great! We’ve done it! Except that this won’t actually compile. This is because on line 4 we instantiate a static struct that has no reference to its original parent. Therefore, we can’t access our “message” value.

Adding the Wrapper

Not this kind of wrapper (credit)

To solve this issue, we will need to add one layer of abstraction. Instead of passing a CleanHouse struct to forLoop, we’re going to pass in a different struct, CleanHouseWrapper, that will then call our cleanHouse() method for us.

Let’s run down what we’ve got here:

forLoop

Util method that will recursively loop and call operator() on Wrapper.
N: How many times to run the loop (N = 4 means 4 runs with N=1,2,3,4).
Wrapper: This is a struct that should implement operator(), to which we will forward all given arguments.
Args: List of arguments to pass on to Wrapper.operator().

CleanHouseWrapper

Wrapper that allows us to call a member method (cleanHouse).
N: This is the current iteration of the loop that needs to be passed on to the member method.
parent: This is a pointer to the instance of the parent type which we will be calling the member method of.
tool: Gets passed on to cleanHouse()

cleanHouse

Clean a house. From this method, we can use N but also access any private values of our instance of HouseCleaner.
N: Which house to clean (template parameter — available at compile time)
tool: Tool to use to clean the house (real parameter — available at run time)

And we’ve done it! Let’s try running our code:

HouseCleaner * cleaner = new HouseCleaner();
cleaner->cleanAllHouses("broom");

Output:
Cleaning house #4 with broom
Cleaning house #3 with broom
Cleaning house #2 with broom
Cleaning house #1 with broom

I lied to you.

If you’ve been trying to follow along and compile the code above, you’ll likely be getting an error about partial specialization of function templates. In C++, functions cannot be partially specialized, but classes can. So we wrap our functions in partially specialized classes and call it a day:

Our final compiler-ready HouseCleaner code looks like this:

Kabam! You’re now a template metaprogramming pro. If you think that the house cleaning example is a bit contrived and can’t figure out why you’d ever want to do something like this, wait for the next couple posts on Nomad, then you will understand.