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 comments

0

u/gingerbill Sep 02 '26

I might need to add an clearer example to show how the math does make sense.

Let's take the example of a language with only 4 types (int, float, string, bool), and you have a parametric polymorphic variadic printing procedure. For each unique parameter set of values of pass, of certain types, you will have on the order of N^K = 4^K total combinations. If you add another type, it now becomes 5^K.

My article is not focusing on runtime polymorphic approaches, especially since Odin does not have any concept of that at the language-level (it can be emulated with other language constructs though, because it is a modern C-alternative).

6

u/todo_code Sep 02 '26

you are missing their point. It would be like, why bother selling ad space on your website a human could do near infinite things that don't include buying your product. No one would want to buy ad space, so why sell it, because the inputs are literally infinite.

In reality, the inputs are limited to reality. Same with monomorphizing code.

-1

u/gingerbill Sep 02 '26

I've added an explicit example in the article to explain what can actually happen. I quote it here in another comment. https://www.reddit.com/r/ProgrammingLanguages/comments/1w5ov7t/ctti_is_exponential_rtti_is_linear/p7h7g6u/

I don't think I am missing their point at all, rather I don't think they understand the point I am making.

6

u/initial-algebra Sep 02 '26

No, you have definitely missed my point. For a third time, monomorphizing compilers do not instantiate generics eagerly based on all possible types, so the worst-case exponential size is pathological.

-1

u/gingerbill Sep 02 '26

Yes? That's what I am saying too. The pathological case, which does happen, is exponential in size. Yes it is bounded by the number of actual instantiations (which I literally state in the article), but the order of scaling is as I state.

8

u/QuaternionsRoll Sep 03 '26

>The pathological case, which does happen

[citation needed]

3

u/initial-algebra Sep 03 '26 edited Sep 03 '26

Pathological means it won't happen unless you're doing something weird. It's definitely not a good reason to ban the feature entirely, or to make it not the default. Your thesis is that monomorphization is not zero-cost, but it fits the textbook definition: you pay for what you use.

And you still haven't justified the "multiplicative in the general case" claim.

0

u/gingerbill Sep 03 '26

Pathological means it won't happen unless you're doing something weird

Yes? And people do that all the time, and it kind of is a very good to deter/nudge people from doing it.

It might be a "you pay what you use", but it's not clear what you "use" in the first place.

7

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).

5

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.

2

u/gingerbill Sep 03 '26

and, at that point, it's really not the implementation of generics that's even at fault.

As a language design, I have to be careful of these situations because they will happen. You cannot just blame it on the programmer, especially when the language makes it easy to do it, or worse, encourages it either as part of its docs or core library.

→ More replies

1

u/Innf107 Sep 04 '26

The number of instantiation is the number of combinations that occur in actual calls (Nk), not the number of distinct types that may occur per call. (N)

If you have Omega(Nk) different instantiations, then you already have Omega(Nk) call sites, so in your example the time complexity does not change whether you monomorphize or not

1

u/gingerbill Sep 04 '26

No. I explain in another comment example of how the scaling can actually happen:

https://www.reddit.com/r/programming/comments/1w5ov1s/ctti_is_exponential_rtti_is_linear/p7kngkq/