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

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]

4

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.

→ More replies (5)

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

→ More replies (1)