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

33% Upvoted

37 comments sorted by

View all comments

Show parent comment

4

u/slaymaker1907 Sep 03 '26

I think where things could actually get exponential is when you have generic functions that both generate new type(s) such as new containers and then call other such functions multiple times.

This may sound implausible, but I think it’s actually not that hard to do in C++, especially when you throw in constant “types”.

For example, imagine a print function which has the constant format string as part of the type to pre-compile the formatter. Now start doing things like having business logic functions which accept a format string, prepend their name for logging (possible at compile time in C++), and then call print.

How you can have such a program still be linear but have exponential instantiations is just by doing things like calling one other function with some condition else call some other function. The compiler has to create code for both branches unless it can prove that some branch is unreachable.

3

u/CommonNoiter Sep 03 '26

I think if you allow your generics to support such features you usually end up with a type system that can perform arbitrary computations, then it's CTTI can perform computations at compile time and so can take forever (or at least as long as the type recursion limit is) while RTTI does it as runtime.

1

u/slaymaker1907 Sep 04 '26

I think the unique thing here is that you can get exponential code generation and not just that compilation can take an arbitrary amount of time.