From Template Metaprogramming to constexpr (C++)

Template Metaprogramming#

#include <cstdint>

template <uint64_t N> struct Fact {
    enum { Value = N * Fact<N - 1>::Value };
};

template <> struct Fact<1> {
    enum { Value = 1 };
};

template <uint64_t N> struct Fib {
    enum { Value = Fib<N - 1>::Value + Fib<N - 2>::Value };
};

template <> struct Fib<1> {
    enum { Value = 1 };
};

template <> struct Fib<2> {
    enum { Value = 2 };
};

template <uint64_t base, uint64_t exp> struct Pow {
    enum { Value = base * Pow<base, exp - 1>::Value };
};

template <uint64_t base> struct Pow<base, 1> {
    enum { Value = base };
};

int main() {
    auto val1 = Fact<10>::Value;
    auto val2 = Fib<20>::Value;
    auto val3 = Pow<2, 10>::Value;
    return 0;
}

In the above code snippet, we have implemented compile-time calculations using templates (supported since C++11).

constexpr#

Starting from C++14, it is possible to use constexpr to modify functions. If a constant is passed to this function, it will be evaluated by the compiler; if a variable is passed, it can only be evaluated at runtime. This can be seen from the generated assembly code.

#include <cstdint>

constexpr auto fact(uint64_t n) {
    if (n == 1) {
        return n;
    }
    return fact(n-1) * n;
}

int main() {
    constexpr auto val = fact(10);
    return 0;
}

fact(int):
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     DWORD PTR [rbp-4], edi
        cmp     DWORD PTR [rbp-4], 1
        jne     .L2
        mov     eax, DWORD PTR [rbp-4]
        jmp     .L3
.L2:
        mov     eax, DWORD PTR [rbp-4]
        sub     eax, 1
        mov     edi, eax
        call    fact(int)
        imul    eax, DWORD PTR [rbp-4]
.L3:
        leave
        ret
main:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 32
        mov     DWORD PTR [rbp-20], edi
        mov     QWORD PTR [rbp-32], rsi
        mov     DWORD PTR [rbp-4], 3628800
        mov     eax, DWORD PTR [rbp-20]
        mov     edi, eax
        call    fact(int)
        mov     DWORD PTR [rbp-8], eax
        mov     eax, 0
        leave
        ret

Comparison between constexpr and Template Metaprogramming#

#include <cstdint>

constexpr auto fib(uint64_t n) {
    if (n <= 1) {
        return 1;
    }
    return fib(n-1) + fib(n-2);
}

int main(int argc, char *argv[]) {
    constexpr auto val = fib(40);
    return 0;
}

If we use the constexpr approach, the compiler will throw an error because this function involves a lot of repetitive calculations.

However, if we use the template metaprogramming approach shown below, it will work because the compiler will memoize the calculations, eliminating the need for repetitive calculations.

In the future, compilers may support memoization for constexpr functions.

template<uint64_t N> struct Fib {
    enum { Value = Fib<N-1>::Value + Fib<N-2>::Value };
};

template<> struct Fib<1> {
    enum { Value = 1 };
};

template<> struct Fib<0> {
    enum { Value = 1};
};

int main(int argc, char *argv[]) {
    auto val = Fib<40>::Value;
    return 0;
}

constexpr if#

Starting from C++17, constexpr if is supported, which allows us to simplify the syntax of template metaprogramming by eliminating the need for instantiating initial values. This means that even complex calculations can be supported because template metaprogramming involves memoization.

#include <cstdint>

template<uint64_t N> struct Fib {
    static constexpr uint64_t Value = []{
        if constexpr (N <= 1) {
            return 1;
        } else {
            return Fib<N-1>::Value + Fib<N-2>::Value;
        }
    }();
};

int main(int argc, char *argv[]) {
    constexpr auto val = Fib<40>::Value;
    return 0;
}