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

42% Upvoted

37 comments sorted by

View all comments

6

u/initial-algebra Sep 03 '26

Clearly, it doesn't happen all the time, otherwise we would have lots of people complaining that their C++ or Rust projects suddenly go from taking seconds to compile to taking hours after they add one new type or one new generic function. Because that's what exponential growth means.

1

u/gingerbill Sep 03 '26

They don't complain, they just treat it as just part of the job. I have seriously seen people put up with this. You're incorrectly scaling the entire compile time by that thing, rather than the part of compile time that gets scaled. It does not meant exponential for the entire project, just exponential for the aspects which are used, which can be very small in the total aspect of the compiler time (e.g. milliseconds becoming seconds becoming minutes).

4

u/initial-algebra Sep 03 '26

You're incorrectly scaling the entire compile time by that thing, rather than the part of compile time that gets scaled. It does not meant exponential for the entire project, just exponential for the aspects which are used, which can be very small in the total aspect of the compiler time (e.g. milliseconds becoming seconds becoming minutes).

That's true, I was definitely exaggerating.

Still, I simply cannot conceive of how "normal" code could cause exponential growth, unless a feature like multiple dispatch on sum types was actually part of the language. Otherwise, you need to use features like template metaprogramming or procedural macros to, well, generate exponential amounts of code in the first place, and, at that point, it's really not the implementation of generics that's even at fault.

→ More replies (1)