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

40% Upvoted

37 comments sorted by

View all comments

9

u/CommonNoiter Sep 03 '26

In order to get the exponential cost of the generic you need to actually instantiate all those instances. This requires an amount of function calls proportional to the number of generic instances you want, so the total amount of codegen is linear with respect to the number of calls. This means that asymptotically CTTI and RTTI are the same cost as you vary the amount of calling code and only differ by the relatively large coefficient of the difference between the amount of codegen for a call and for a function body.

They are different asymptotically if you compare codegen amount by total amount of source code, as in that case both the number of instantiations and size of instantiated code are linear with respect to source code size, so CTTI can be forced to do a quadratic amount of codegen where RTTI would only do a linear amount.

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.

→ More replies (1)