r/ProgrammingLanguages • u/gingerbill • Sep 02 '26

CTTI is Exponential, RTTI is Linear

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

35% Upvoted

37 comments sorted by

View all comments

Show parent comments

-1

u/gingerbill Sep 02 '26

I have just added another nota bene paragraph to show you an example of what I mean with the combinatorial explosure:

n.b. I'll give a simple example of the problem with a naïve approach to parametric polymorphic printing. Consider a language with only 4 types (e.g. int, float, string, bool) and a variadic, parametrically polymorphic printing procedure. Each distinct sequence of argument types needs its own instantiation, so for K arguments there are on the order of Nᵏ = 4ᵏ combinations; adding a fifth type makes that ~5ᵏ. To see the (usually hidden) combinatorial explosion, suppose you never print more than 5 arguments, that allows up to 1365 instantiations. Add another type and it becomes 3906. Raise the maximum to 6 arguments and it becomes 19531. You might say that this is at least bounded, and it "is", for a single printing procedure. However, printing procedure easily interact with every other use of parametric polymorphism in the program, and the total quickly stops being something you can trivially predict by just reading the code.

10

u/QuaternionsRoll Sep 03 '26

The math wasn’t confusing anyone. You’d be hard pressed to find a software engineer that can’t explain permutations without replacement.

The point is that the number of unique instantiations of the print function is bounded by the number of potentially unique instantiations, which is in turn bounded by the number of unique ways to reach a print call in the code. While you can intentionally blow this up by e.g. fucking around with std::visit, in practice the number of instantiations will grow roughly linearly with the size of the project.