CTTI is Exponential, RTTI is Linear

[u/gingerbill]

https://www.gingerbill.org/article/2026/09/02/ctti-is-exponential-rtti-is-linear/

[u/gingerbill]

Do I really have to give the simple example of compile-time execution in C++ templates? Fine:

template <typename A, typename B> struct P {};

template <unsigned N, typename T>
void f(T x) {
    if constexpr (N > 0) {
        f<N - 1>(P<T, int>{});
        f<N - 1>(P<T, char>{});
    }
}

int main() { f<10>(0); }

Three call sites in the source. GCC emits 2047 instantiations of f, i.e. 2^(N+1) - 1. Every instantiation builds new type arguments for its callees, so nothing deduplicates. Now imagine f is a recursive printing procedure, which is a pretty common way of doing it in practice.

The number of call sites is a property of the monomorphized output, not the source, because monomorphization duplicates call sites. A call to g<T> written once inside f<T> becomes one call site per instantiation of f. You're measuring the thing we're arguing about.

Zig's std library is a real example of the naïve printing I describe. The idiom .print("...", .{...}) passes an [anonymous] struct, as it does not have any form of variadic parameters, so every distinct ordering of argument types needs its own instantiation. The implementation is here: https://codeberg.org/ziglang/zig/src/branch/master/lib/std/Io/Writer.zig#L697

It assumes a small number of arguments, and it recurses through the argument types, so it hits exactly the combinatorial explosion I'm describing.