The rabbit hole of C++ templates

Here I will document some of my interesting findings on C++ templates.

This started when I tried to make a simple machine learning library in C++. When coding the tensor class, I found out about an optimization done with expression templates that allows the C++ compiler to not generate intermediate object code during runtime operations.

Lets start with the basics, what are templates? Templates are a feature in C++ to create generic classes of functions. Here are some examples.

// Function template for generic add
template <typename T>
T add(T a, T b) {
    return a + b;
}

// Class template for generic datatypes
template <typename T>
class Box {
private:
    T value;
public:
    Box(T val) : value(val) {}
    T getValue() { return value; }
};

Templates are incredibly useful for generic programming, allowing the programmer to write a single class/function that can work with many datatypes. It generates all the code at compile time which reduces runtime overhead and performs error-checking at compile time too. Now, lets jump into the rabbit hole of things you can do with templates!

Template metaprogramming

Before we dive into expression templates, lets first understand its superset, template metaprogramming. Template metaprogramming (TMP) is a technique that leverages the C++ compiler's template system to write code that generate more code during compilation. It can also perform computation during compile-time which enables a lot of optimizations.

Here is the most classic example of TMP in action, computing the fibonacci sequence during compile time.

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

constexpr int result = Factorial<5>::value; // result = 120

If you try and run this code, you will realize that it is actually really fast as the compiler essentially memoized the result into the compiled code.

As opposed to a naive implementation, the complexity is O(N) vs O(2^N).

int fibonacci(int n) {
    if (n <= 1) {
        return n; // Base cases: Fib(0) = 0, Fib(1) = 1
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

constexpr int result = fibonacci(5);

Expression templates

Expression templates is the concept of using template classes to represent operations. It allow you to construct multiple operators in a single step, avoiding the creation of intermediate temporary objects during the evaluation. Instead of performing operations step-by-step and storing intermediate results, expression templates enable the compiler to generate optimized code for the entire expression at once.

(WIP!)

Things still to jot down

• Expression templates
• CRTP (Curiously Recurring Template Pattern)
• SFINAE
• Concepts (C++20)