Compile-time vs. runtime with C++ templates
Posted on 2025-05-31
I’ve been brushing up on C++ via the excellent Learn C++ online resource, and found templates to be one of the most interesting aspects of the language1.
Templates are C++’s implementation of generic programming, but rather than rely on dynamic dispatch like Java, C++ uses compile-time code generation. This means that C++ generics don’t incur runtime overhead, at the cost of larger program size–a tradeoff that the performance-conscious C++ community is usually willing to make.
One difficulty with templates is having to think about what happens at compile time vs. runtime. Consider the following:
#include <iostream>
template<unsigned int N>
unsigned int sum() {
if (N == 1) {
return 1;
}
return N + sum<N-1>();
};
int main() {
std::cout << sum<10>() << std::endl;
return 0;
}
This seems like it should work, but it actually fails to compile:
fatal error: recursive template instantiation exceeded maximum depth of 1024
The problem is that if (N == 1)
is evaluated at runtime, not compile time. Therefore, template instantiation sees sum<10>
, sum<9>
, etc., until it gets to sum<0>
, after which it wraps around to the largest value of unsigned int
.
To properly terminate the recursion at compile time we can either define the base case as a separate function using template specialization:
template<unsigned int N>
unsigned int sum() {
return N + sum<N-1>();
};
template<>
unsigned int sum<1>() {
return 1;
};
Or, in C++17 and above, use if constexpr
:
template<unsigned int N>
unsigned int sum() {
if constexpr (N == 1) {
return 1;
} else {
return N + sum<N-1>();
}
};
The magic of if constexpr
is that it discards the other branch at compile time:
If condition yields
true
, then statement-false is discarded (if present), otherwise, statement-true is discarded.
So template instantiation never sees the else
branch when N == 1
, which means there’s no infinite recursion.
Note that if constexpr
only works when there are two branches. The following does not work:
template<unsigned int N>
unsigned int sum() {
if constexpr (N == 1) {
return 1;
}
return N + sum<N-1>();
};
The return N + sum<N-1>();
is not in the else
branch, so it’s not discarded.
-
The C++ community certainly agrees, as evidenced by the enduring popularity of Modern C++ Design, a book that puts templates at the heart of C++ design patterns. ↩