Compile time shenanigans with C++

Templates in C++ are what I like to refer to as the ‘Dark side’ of C++, as I always considered them the pathway to many abilities I consider unnatural, since they allow one to compute complex results at compile time. Yeah, not at runtime, but at compile time! This means that by the time the compiler spits out a binary, the only thing that’s in it (apart from things you want to run at runtime, obviously) is the result of said template magic. Having messed around with them for a few days, I’m starting to get the basics.

Templates are widely used with containers (like std::vector) so that you don’t have to write different classes for each type of vector-of-class you’d like to have (vector of cats, vector of dogs …). Instead, given a template instantiation (std::vector<T>), the compiler generates the code for you using this template as a blueprint (hence the name).

Since this is all done at compile-time, you can force the compiler to compute stuff on the fly for you. Let’s look at a simple example of computing the nth term of the Fibonacci series.

Let’s start with the following base code.

template <unsigned long long X>
struct fibo {
    unsigned long long value = X;
};

int main() {
    std::cout << fibo<10>().value << '\n';
}
// Output: 10

Adding the base recursion cases, we have the following.

template <unsigned long long X>
struct fibo {
    unsigned long long value = fibo<X - 1>().value + fibo<X - 2>().value;
};

// Template specialization for base cases
template <>
struct fibo<0> {
    unsigned long long value = 0;
};

template <>
struct fibo<1> {
    unsigned long long value = 1;
};

If you compile this code and look at the generated assembly (line 38, for example) you’ll notice that all recursive template instantiations are generated, which is not what we want.

To overcome this, all the values must ‘belong’ to the types, so that we don’t have to instantiate them. Doing just that, by making the value static constexpr, we have a working example.

template <unsigned long long X>
struct fibo {
    static constexpr unsigned long long value = fibo<X - 1>::value + fibo<X - 2>::value;
};

template <>
struct fibo<0> {
    static constexpr unsigned long long value = 0;
};

template <>
struct fibo<1> {
    static constexpr unsigned long long value = 1;
};

It’s important to note that memoization is automatically done for us, as the compiler (probably) caches the result of all the recursive template instantiations, so the fan-out of the recursive call tree isn’t large. The compiler computes fibo(93) in under 3 seconds, whereas a naïve python implementation takes ages. This allows you to safely compute values till the 93^rd Fibonacci number, after which there seem to be computation errors (using ull - unsigned long long doesn’t fix it either).

fibo<93>::value // gives 12200160415121876738, correct ✔
fibo<94>::value // gives 01293530146158671551, wrong ❌
// ------ supposed to be 19740274219868223167

Using our new-found skills, let’s try to solve this problem. With a few modifications, it’s possible to calculate the sum of all even Fibonacci numbers. The first step is to add a helper function that checks if a number is even.

template <unsigned long long v>
struct is_even {
    static constexpr bool value = v % 2 == 0;
};

Applying standard recursion techniques, computing the running sum is fairly straightforward (accumulate the sum from the leaves to the top. Don’t forget the base case!).

template <unsigned long long X>
struct fibo {
    static constexpr unsigned long long value =
            fibo<X - 1>::value + fibo<X - 2>::value;

    // capturing the sum from the left sub-tree is enough.
    static constexpr unsigned long long sum =
            fibo<X - 1>::sum + is_even<value>::value * value;
};
// Don't forget to add in the base cases

int main() {
    constexpr auto fib = fibo<34ull>();
    std::cout << fib.value << "\n";
    std::cout << fib.sum << "\n";
    return 0;
}
// Output
// 5702887
// 4613732

Given this can be computed at compile-time, one might ask, “Is this Turing complete”? Turns out, yes! Templates are Turing complete! Heck, there’s even ray-tracers built with templates! With enough effort, one can compute basically anything during compilation and store just the end result, but to do that, you probably need a lot of time, patience, and a forgiving compiler.