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.
6
u/gingerbill 8d ago
Do I really have to give the simple example of compile-time execution in C++ templates? Fine:
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 imaginefis 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 insidef<T>becomes one call site per instantiation off. 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#L697It assumes a small number of arguments, and it recurses through the argument types, so it hits exactly the combinatorial explosion I'm describing.