C++ Template Meta Programming – Part 1

You may have heard of template meta programming before. It is a technique that uses the features of C++ templates to shift program execution from runtime to compile time. Basically, we are going to trick the compiler into running our code at compile time and then putting the output into our executable.

Let’s look at an example:

#include <iostream>

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

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

int main() {
    std::cout << Factorial<5>::value << std::endl;
    return 0;
}

What does this code do? Well, first we define a templated struct that takes an integer as a parameter.

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

Notice, that inside this struct, we define a field named value. This field is defined to be n times the value field of Factorial<n-1>. We are also using total template specialisation:

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

This means that if we ever specialise the Factorial template with the parameter 0 it will use this version of Factorial that defines the value field to be 1.

So, when we specialise the Factorial template with the parameter 5, the compiler creates the classes Factorial<5>, Factorial<4>, Factorial<3>, Factorial<2>, Factorial<1> and Factorial<0>. Then it computes the value field for each of these classes. The value field for Factorial<0> is 1. The compiler calculates the value field for each successive Factorial<n> by multiply n times the value field of the previous Factorial specialisation. So we have defined a recursion that calculates the factorial of an integer. What is weird is that this calculation happens entirely at compile time. When we run this code, the first six values of the factorial series have already been calculated, and we will just be reading the last value from the code the compiler has created.

We can do exactly the same thing with the Fibonacci numbers:

#include <iostream>

template<int n>
struct Fibonnaci
{
    enum { value =  Fibonnaci<n - 1>::value + Fibonnaci<n - 2>::value };
};

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

template<>
struct Fibonnaci<1>
{
    enum {value = 1};
};

int main() {
    std::cout << Fibonnaci<5>::value << std::endl;
    return 0;
}

So we have seen how to do recursions via template meta programming. Next we will see how to write conditional statements that are evaluated at compile time.

Generic Programming, C++ vs C#

At first glance, C++ and C# are two very similar languages. However the more you look, the more you realise that they are two very different beasts. Today we are going to talk about how these two languages handle generic programming.

The Implementation

First lets look at how the two languages implement generic programming. In C++ we can define a template for a class like this:

template<typename T>
class Holder
{
public:
   T value;
};

We can then use that template in our code like so:

Holder<int> intHolder;

When the compiler sees this usage, it goes back to the definition of the Holder class and generates a new class. In this new class it replaces the type variable T with the type int. This new class generated by the compiler is what the name Holder<int> refers to. This class gets compiled as normal. It would be completely equivalent if we had instead defined a Holder class specialised to ints ourselves:

class Holder_int
{
public:
   int value;
};

If we also specialise our Holder class with the type double, the compiler will generate another version of Holder, this time with type variable T replaced by the type double.

Now, in C# the equivalent to the above example is:

class Holder<T>
{
    public T value;
}

This looks very similar, however the underlying implementation is very different. In C# generics are resolved at runtime not at compile time. The Holder class we defined will remain generic when it is complied to intermediate language. When we run code that uses the Holder class, the just in time compiler generates the different machine code implementations for whatever specialisation of Holder we have used. The JIT compiler will generate separate versions of the Holder class for each value type used. However, it generates a single implementation that is shared for all reference types. This works because reference types are implemented as pointers, which are always the same size, regardless of the type they are pointing to.

Constraints

Usually we need more than just a typename in our generic code. We want to do things with the values of that type. So, suppose we wanted to add a method to our generic Holder class that calls a length method on our inner object of type T. In C# we do it like this:

public interface IHasLength
{
   int length();
};

public class Holder<T> where T : IHasLength
{
   public T value;
   int GetLength()
   {
      return T.length();
   }
}

The syntax, class Holder where T : IHasLength specifies that whatever type this generic is specialised with must implement the interface IHasLength. With that constraint, the compiler knows that whatever type we specialise this class with will have a Length method, so we can call it freely in our generic code. There are five different kinds of constraint we can impose. We have just seen the interface constraint. We can also constrain a type parameter to be a subclass of a given class, to have a default constructor, to be a value type or to be a reference type.

In C++ we don’t need explicit type constraints. Instead there are implicit type constraints. For example, suppose we have the following code:

template<typename T>
class Holder
{
public:
   T value;
   int GetLength()
   {
      return value.length();
   }

}

Here, we have just written our code assuming that an object of type T has a Length method that returns a value that can be cast to an integer. We do not need to specify this constraint ourselves. We can instantiate this class and specify a specific type, for example via:

Holder<string> stringHolder();

The compiler then generates the version of Holder specialised to the type string. This new class is then compiled as normal. As the string class has a length method, this will compile successfully. However, suppose we instantiated our class like so:

Holder<int> intHolder();

The int type does not have a length method, so the class generated by this code will not compile.

Whereas the constraints on C# generic types are quite limited, in C++ we can use any constraint at all. For example, it is impossible to impose a constraint on a generic type parameter in C# that it must have an addition operator. This is because there is no interface that all types that have an addition operator implement. However, in C++, we just use the addition operator in our template code and the compiler will make sure that the specific types we use have an addition operator. This all works in C++ because the types are resolved at compile time, so the compiler can check that types satisfy the implicit interface then. In C# the type substitution does not actually happen until runtime, so it would be impossible for the C# compiler to do a check like this.

Beyond Type Parameters

Another cool feature of C++ templates is that we can pass values to our templates as well as type parameters. For example, in C++ the following code is valid:

tempate<int n>
bool LessThan(int x)
{
   return x < n;
}

This defines a template function with a parameter of type int. We can use this template like so:

bool result = LessThan<10>(5);

The code LessThan<10> causes the compiler to generate a version of the LessThan method with 10 substituted for the parameter n. You can’t do anything like this in C#.

Overall, C++ templates are a lot more powerful and flexible than C# generics. Of course this means that it is a lot easier to trip yourself up with C++ templates. And when things do go wrong the compiler output is probably going to be completely incomprehensible. As C++ generates separate code for every different version of a template that gets used this has the potential to create very large binaries. However, on a modern system this probably won’t really be a problem.

Book Review – The Pragmatic Programmer

This book is a classic. It doesn’t cover any particular language or technology, instead it provides general advice to the aspiring software developer. This advice is organised as seventy separate aphorism. Each of these numbered tips gives a general recommendation to improve your work. There is a lot of good advice in this book, and I can’t really cover it all in a single post. So I’m just going to try and cover some of the main themes and the parts that I did not agree with.

Modularity is a theme that comes up again and again. The authors advocate for code that is cleanly divided into orthogonal modules with clear APIs. This is, of course, very good advice. Another mantra they return to repeatedly is “DRY – Don’t repeat yourself”. Again, this is broadly good advice, you should definitely avoid unnecessary duplication. But in reality you are going to have to repeat yourself. In fact repeating yourself is often the best option. Another major theme is to avoid programming by coincidence. Again this is broadly good advice. You should not just randomly permute things until they work. However, sometimes this is the only way to find out how things do in fact work.

The authors also advocate for fixing issues whenever you see them. Sure this is a good idea. But the reality of a large complex system is that it just isn’t really possible. In a large evolving legacy code base, you will see a lot of awful code. If you fixed every issue you came across you would never get any work done. Also this kind of tinkering can be pretty dangerous.

The authors strongly recommend making your code highly configurable. They advocate for a model of software where you can completely change the behaviour of your binary with a change to a config file. In my opinion this is an anti-pattern. It makes code execution unpredictable. It makes reading and reasoning about code hard. Having to carefully trace how config values percolate through the code base can be a nightmare. Also, it leads to a lot of dead code, if no one is sure what code is actually used, old code will just be left to rot.

I think that the biggest overall issue with this book is that it is old: it was published in 1999. So a lot of the advice is out of date. I don’t mean that it has since proven to be wrong, but that it is now so widely accepted that you won’t need to read the pragmatic programmer to find it, it will just be part of any normal software development job. For example there is an entire section about how you should use source control. They also recommend using nightly tagged builds as well as integrating testing into your build process. There is even advice on how to use email!

Another problem with this book is that there are very few concrete examples given. This does help to keep the book relatively light and readable. But it makes it hard to relate the general tips to real world programming.

On the whole, this is a good book. It can be quite vague and dated, but there is definitely useful advice in there. I should say that a new edition of this book was published while I was reading it. I assume that it has been updated appropriately, however I didn’t read it so I really can’t say.

Finally, the rule of five in C++

Ok, we’ve talked in detail about the special copy and move methods. It’s time to put them together in a reasonable example. Suppose we have the Bond class as defined in our previous examples. We are going to define a Portfolio class that represents a collection of Bonds. The rule of five refers to the four methods we have discussed so far, along with the destructor. The destructor is just a method that frees up whatever resources your class has a reference to. The rule of five states that if you define any of these five special methods, you ought to define them all.

Let’s look at the code.

#include <string>
#include <algorithm>

class Portfolio
{
private:
	std::string Name;
	Bond* Bonds;
	int Size;
public:
	Portfolio(std::string name, Bond* bonds, int size) : Name(name), Bonds(bonds), Size(size)
	{
	}

	Portfolio(const Portfolio& lhs) : Name(lhs.Name)
	{
		std::copy(lhs.Bonds, lhs.Bonds + lhs.Size, Bonds);
	}

	Portfolio& operator=(const Portfolio& lhs)
	{
		if(&lhs != this)
		{
			delete[] Bonds;
		        std::copy(lhs.Bonds, lhs.Bonds + lhs.Size, Bonds);	
			Name = lhs.Name;
			Size = lhs.Size;
		}
		return *this;
	}
		
	Portfolio(Portfolio&& lhs) : Name(lhs.Name), Bonds(lhs.Bonds)
	{
		lhs.Bonds = nullptr;
		lhs.Size = 0;
	}

	Portfolio& operator=(Portfolio&& lhs)
	{
		if(&lhs != this)
		{
			delete[] Bonds;
			Bonds = lhs.Bonds;	
			Name = lhs.Name;
			Size = lhs.Size;
			lhs.Size = 0;
			lhs.Bonds = nullptr;
		}
		return *this;
	}

	~Portfolio()
	{
		delete[] Bonds;
	}
};

Now this code isn’t perfect, in fact we’ll be refining it in future posts. But I think it is a good demonstration of the various special methods in action.

Our Portfolio class manages a resource, a block of memory containing Bond objects. Let’s look at the copy methods first. Whenever we copy a portfolio we want to make a copy of it’s set of bonds. So our copy construction uses the std::copy function to make a deep copy of this resource. When we copy assign, we first free whatever memory we currently have a pointer to. Then we do a deep copy of the array of Bonds. Also, when assigning we check to make sure that we aren’t self assigning.

When we move, we don’t need to copy the entire portfolio of bonds. So, in the move constructor we just copy the pointer to the array, rather than copying its contents. Now that we have moved our array into a new object we don’t want to leave another Portfolio with a pointer to it, so we set the array pointer in the source object to nullptr. Just like with copy assignment, when move assigning, first we check for self assignment. Then we delete the memory we currently have a pointer to, and copy the pointer from the source object. Finally, as before, we set the source object’s pointer to nullptr.

Moving in C++

So, in a previous post we covered the copy constructor and copy assignment operator. We also had a look at copy elision. Now it’s time to talk about the move constructor and move assignment operator. To explain what these special move methods are and why we need them, we are going to have another quick look at our Bond example. As before we are including a subclass to prevent elision.

#include <iostream>

class Bond
{
private:
	double Rate;
public:
	Bond(double rate) : Rate(rate)
	{
               std::cout << "Constructing" << std::endl;
	}

        // copy assignment
       	Bond& operator=(const Bond& other)
	{
		std::cout << "Copy assigning" << std::endl;
		Rate = other.Rate;
		return *this;
	}

        // copy constructor
       	Bond(const Bond& other) : Rate(other.Rate)
	{
		std::cout << "Copy constructing" << std::endl;
	}
};

class NamedBond : public Bond
{
private:
       string Name;
public:
       NamedBond(string name, double rate) : Bond(bond), Name(name)
       {
             std::cout << "Sub class constructing" << std::endl;
       }
}

When we run the following code:

Bond b(new NamedBond(1.2, "Name"));

we will see something like:

Constructing
Sub class construction
Copy constructing

What happens is, we build an object of type NamedBond and then copy it into a Bond object. But we don’t actually use the NamedBond object we constructed. It just exists as a temporary object without a name. We don’t actually have to copy it into the Bond object b. We can move it.

So, we are going to add two more special methods, the move constructor and the move assignment operator. This is how we define them:

        // move constructor
       	Bond(Bond&& other) : Rate(other.Rate)
	{
		std::cout << "Move constructing" << std::endl;
	}
 
        // move assignment
       	Bond& operator=(Bond&& other)
	{
		std::cout << "Move assigning" << std::endl;
		Rate = other.Rate;
		return *this;
	}

Now when we run:

Bond b(new NamedBond(1.2, "Name"));

we will see:

Constructing
Sub class constructing
Move constructing

So, the move constructor was used here. Why did the compiler decide to do that? Well, the compiler knows we are just using a temporary value to create b. Also the && modifier on the move constructor’s parameter, indicates it accepts a temporary value. This means that the move constructor will always get called when initialising with a temporary object. For example, suppose we have a function such as:

static NamedBond NamedBondFactory(double rate, string name)
{
      return new NamedBond(rate, name);
}

The following code:

Bond b(NamedBondFactory(1.2, "Name"));

will also go through the move constructor rather than the copy constructor. Similarly, if we have defined an addition operator on NamedBonds, then

NamedBond a(1.2, "Name1");
NamedBond b(2.4, "Name2");
NamedBond c(a + b);

will use the move constructor rather than the copy constructor.

We see the same thing with move assignment. However, just as with copy assignment, the compiler is much stricter and will not elide move assignments. So we can see the effect without using the NamedBond subclass.

So, suppose we run the following code:

Bond b(1.2);
b = Bond(2.3);

We will see:

Constructing
Construction
Move Assigning

We did not pass through the copy constructor. This is because the object created by Bond(2.3) is only a temporary object. Similarly, suppose we have a function which returns a Bond object, let’s call it BondFactory. The following code:

Bond b(1.2, "Name");
b = BondFactory();

Will print:

Constructing
Constructing
Move assigning

Why would we bother with these two extra methods? Why not just use the copy constructor and copy assignment? Well, the secret is in the signature. Firstly, we know that the move methods only take arguments that are temporary values. Secondly, the parameters to the move constructor and move assignment are not const. Taken together this means that, rather than copy data/resources the source object, we can just move data/resources out of it.

We can say that the move methods allow us to transfer ownership of resources from one object to another. For a class like Bond this distinction is a little pointless. But for more complex objects it can be crucial. For example, suppose we have an object that contained an array, our copy constructor and copy assignment would copy all the values in the array, whereas the move constructor and move assignment would just copy the pointer and set the pointer in the source to null. This pattern, a deep copy in the copy methods and a shallow copy in the move methods, is fairly typical. Also, when we move, we we always make sure to not leave any reference in the source object to whatever resources we are moving.

We can also invoke the move methods explicitly. We do this by using the std::move() function. So, as we know, the following code,

DerivedBond b(1.2, "Name");
Bond c(b);

will use the copy constructor to initialise c. However, if we use std::move like so:

DerivedBond b(1.2, "Name");
Bond(std::move(b));

the move constructor will be used. This is especially useful when we want to transfer ownership of a resource that is held by an object that is not temporary. We can also use std::move to invoke the move assignment operator. Whereas

Bond a(1.3);
DerivedBond b(1.2, "Name");
a = b;

will invoke the copy assignment method, this code:

Bond a(1.3);
DerivedBond b(1.2, "Name");
a = std::move(b);

will invoke move assignment.

The examples we have covered are a little bit complicated. Usually, when they are explained the effect of copy elision is ignored, which I think it quite confusing. If you try to run some examples you see on the internet they will not work at all the way they should, because the moves/copies are elided by the constructor. Our next post will bring everything we have covered together in a single example.

Not Copying in C++

So, in our last post we had a look at copy construction and copy assignment. Let’s use the code from that post and look at a quick example. Suppose we have simple function that returns a Bond. Something like:

static Bond BondFactory(double rate)
{
        return Bond(rate);
}

Of course this example is very silly, but let’s just go with it. So, suppose we run the following code in a Main method:

Bond b(BondFactory(1.2));

What do we see? Well, the output should look like this:

Constructing

This seems kind of strange. We constructed a Bond object inside the method BondFactory, and we see in the output that we visited the Bond constructor. However, we also copied the return value of BondFactory into a new Bond object b. So why did execution not pass through the copy constructor?

The answer is copy elision. The constructor sees that we are directly copying the result of the BondFactory method into another Bond object. So, rather than constructing and copying, it just constructs the Bond object once, creating the object b directly. What’s surprising here is that our copy constructor has a side effect, it prints to the console, yet the compiler stills skips it.

Now, suppose we defined a subclass of Bond:

class NamedBond : public Bond
{
private:
       string Name;
public:
       NamedBond(string name, double rate) : Bond(bond), Name(name)
       {
             std::cout << "Sub class constructing" << std::endl;
       }
}

And we had a factory method like:

static Bond BondFactory(double rate)
{
      return new NamedBond(rate, "none");
}

Now, if we run the following code in our main method,

Bond b(BondFactory(1.2));

We will see:

Constructing
Sub class constructing
Copy constructing

This time we do pass through the copy constructor. That is because copy elision only happens when the return type is the same as the value it is being copied into. In this case, the return type is a subclass of the value it is being coped into. So the compiler will not elide the copy step.

We will see the same effect when we copy from temporary objects that never get assigned a name. If we run the following code:

Bond b(Bond(1.2));

Our output will be:

Constructing

Whereas, if we run:

Bond b(NamedBond(1.2, "Name"));

we will get:

Constructing
Sub class constructing
Copy constructing

Similarly if we define an addition operator on Bond objects. If we run the following code:

Bond a(1.6);
Bond b(2.3);
Bond c(a + b);

The output will be:

Constructing
Constructing
Constructing

However, if we use the subtype, as so:

NamedBond a(1.6, "Name1");
NamedBond b(2.3, "Name2");
Bond c(a + b);

We will see the copy construction taking place.

Constructing
sub class Constructing
Constructing
sub class Constructing
Constructing
sub class Constructing
Copy constructing

With copy assignment the constructor is a lot stricter. With our example code, the following:

Bond b(1.2);
Bond c(2.3);
b = c;

will result in:

Constructing
Constructing
Copy assigning

So, the copy assignment method gets called here. This is because the compiler only elides the copy assignment when doing so has no consequence. In our case, if it was elided, we would miss the cout statement so it does not. It makes sense to be stricter with elision for the assignment operator, as we may have logic in that method that frees up resources that have already been initialised, this would not be the case with the copy constructor.

The C++ standard allows copy elision to take place, it does not mandate it. This means that elision behaviour depends entirely on what C++ compiler you use, what version of the language you are using and what compiler settings you have enabled. What I have described above is what you should normally expect to see.

Copy elision can also happen when throwing exceptions. However I will not get into the details here, as it is really not as interesting. If your exceptions are defined in such away that copy elision is important, you are defining them wrong.