CTTI is Exponential, RTTI is Linear

[u/gingerbill]

https://www.gingerbill.org/article/2026/09/02/ctti-is-exponential-rtti-is-linear/

[u/initial-algebra]

The math makes no sense. Yeah, technically the worst case (more like pathological) scenario for monomorphization is exponential, but where does "best case N×K" come from? How can you even multiply the two quantities meaningfully?

Monomorphizing compilers only generate code for instances that you actually use. The only way I can think of to get exponential code size out of this is by putting all your N types in a big sum type and using that with K-ary dispatch (so you have a match expression with N branches, and each of those branches has a match expression with N branches, and so on, so you have a tree with Nᴷ leaves, each calling a different instance of the generic code). But, is that really common, or even possible to do accidentally in any existing language?

Also, you can have types for "type-erased blobs with RTTI" e.g. Rust's dyn types. So, monomorphization can be strictly more flexible, allowing the programmer to decide when to take the size/speed tradeoff.

[u/todo_code → u/initial-algebra]

I have also had this thought. It's why a lot of optimizations that end up being some sort of exponential for implementation ends up being fine. The input is still something that has to be typed out and have purpose. Even LLM's would have a hard time hitting numbers to cause issues.

[u/Nuoji → u/initial-algebra]

It’s easy to make it slow, because the up front cost is not visible. For example, consider creating a serializer with RTTI vs CTTI. In the CTTI case you can easily go a naive route where you loop through every field and generate code inline for every type. You get code which looks like the serialization of every supported type… once. But because we generate it at runtime, we never see the actual resulting size of the function when serializing large structs then multiply that by every struct you serialize.

With RTTI what you see is what you get: typically a loop over fields at runtime and then runtime switching over the types. All this through a single function rather than ”one function per type”

Where the RTTI solution and the CTTI solution looks almost like the same thing, say we have 20 structs to serialize? We’ll get around 20 times the size of the RTTI.

This is not theoretical: with CTTI the ”easy” solution, people will gravitate towards such solutions in the name of ”top performance” even at the cost of binary bloat, just because the binary size is hard to quantify.

This is not to say that CTTI MUST imply bloated solutions, but this is what it pushes people towards.

In C3 both variants are available and I had to add features to show binary sizes to help people track down binary size issues. We’re talking about people submitting some innocent looking code to the stdlib and suddenly compile times were 20 times slower, because they casually generated code on the order of ten times the entire stdlib with their submission of a few hundred lines pf code.

[u/matthieum → u/initial-algebra]

The math makes no sense.

While I do agree that the math is exaggerated, I do want to note that monomorphization bloat is real.

You can find countless examples in C++ and Rust good practices:

1. In C++, I remember the technique of "shim", where a thin typed layer -- expected to be inlined -- is used to delegate to a type-erased layer so that the bulk of the code is only generated once.
2. In Rust, inner items of a generic functions do not "inherit" the generic parameters of their scope, leading to a common technique of having an inner function that is less generic that its caller, to minimize monomorphization bloat.

[u/gingerbill → u/initial-algebra]

I have just added another nota bene paragraph to show you an example of what I mean with the combinatorial explosure:

n.b. I'll give a simple example of the problem with a naïve approach to parametric polymorphic printing. Consider a language with only 4 types (e.g. int, float, string, bool) and a variadic, parametrically polymorphic printing procedure. Each distinct sequence of argument types needs its own instantiation, so for K arguments there are on the order of Nᵏ = 4ᵏ combinations; adding a fifth type makes that ~5ᵏ. To see the (usually hidden) combinatorial explosion, suppose you never print more than 5 arguments, that allows up to 1365 instantiations. Add another type and it becomes 3906. Raise the maximum to 6 arguments and it becomes 19531. You might say that this is at least bounded, and it "is", for a single printing procedure. However, printing procedure easily interact with every other use of parametric polymorphism in the program, and the total quickly stops being something you can trivially predict by just reading the code.

[u/QuaternionsRoll → u/gingerbill]

The math wasn’t confusing anyone. You’d be hard pressed to find a software engineer that can’t explain permutations without replacement.

The point is that the number of unique instantiations of the print function is bounded by the number of potentially unique instantiations, which is in turn bounded by the number of unique ways to reach a print call in the code. While you can intentionally blow this up by e.g. fucking around with std::visit, in practice the number of instantiations will grow roughly linearly with the size of the project.

[u/gingerbill → u/initial-algebra]

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

[u/initial-algebra → u/gingerbill]

Like I said,

Monomorphizing compilers only generate code for instances that you actually use.

Or, at least, that's standard practice. Because eagerly generating code for every possible instance, even if they're not used, is painfully, obviously bad. And there's no good reason I can see to do so despite the cost (it doesn't even make sense for libraries, because you still want to allow instantiation with downstream-defined types).

[u/todo_code → u/gingerbill]

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.

[u/gingerbill → u/todo_code]

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.

[u/initial-algebra → u/gingerbill]

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.

[u/gingerbill → u/initial-algebra]

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.

[u/QuaternionsRoll → u/gingerbill]

>The pathological case, which does happen

[citation needed]

[u/initial-algebra → u/gingerbill]

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.

[u/gingerbill → u/initial-algebra]

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.

[u/initial-algebra → u/gingerbill]

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.

[u/gingerbill → u/initial-algebra]

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

[u/CommonNoiter]

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.

[u/slaymaker1907 → u/CommonNoiter]

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.

[u/CommonNoiter → u/slaymaker1907]

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.

[u/slaymaker1907 → u/CommonNoiter]

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.

[u/apajx]

1. Monomorphising is not the only way to specialize, you can internalize type codes and do all the same runtime-type shenanigans you want
2. Generics need not be monomorphized so the title is click bait to begin with

[u/gingerbill → u/apajx]

Monomorphising is not the only way to specialize...

Generics need not be monomorphized

Sure but I was specifically referring to parametric polymorphism, not "generics" in general, which is already too generalized of a term.

[u/ultrasquid9 → u/gingerbill]

Programmers know what you mean when you say "generics". If you still don't like the terminology, you can use "type parameters" as people have been doing for years now.

Frankly, if you want to be semantically correct with naming, a far more productive change would be changing "unsigned integer" to "natural" (an integer is by definition a potentially-negative number).

[u/gingerbill → u/ultrasquid9]

When people commonly say "generics", they are referring to parametric polymorphism. That is actually the common meaning of that term.

[u/yorickpeterse]

CTTI is an exponential cost everywhere in the worst-case: semantic checking, code generation, and binary size. Instantiations go multiplicative in the general-case.

I think it's worth defining what "cost" here means. For example, if you have a generic function foo[T](value: T) that's instantiated for three different types, you don't have to type-check the body of foo three different times; instead you just check if those types are compatible with whatever T requires. There's definitely a cost to that, but depending on the implementation of your compiler it may be small enough that no matter the big-O factor it may not matter.

Unfortunately these are the costs so many programmers are most conditioned/trained to ignore [...]

Here I actually have a useful data point, one that does to some degree highlight that (at least in the case of generics) doing more at compile-time is usually the better option: Inko used to essentially group generics into buckets based on the shape (i.e. the size on the stack) of types, instead of specializing for individual types. This was recently removed because it actually turned out to slow down compile times. While I'm certain some of that could've been improved, the grouping of types essentially meant a lot more dynamic dispatch and thus a lot more methods that had to be compiled because they might be called as we couldn't statically determine that they never would be called (amongst other reasons).

So "specialize over types" isn't necessarily slower (in terms of compile times), it depends on a lot more than just that.

Outside of that I generally agree with preferring runtime type information for the purpose of reflection, as it usually allows for a lot more flexibility (e.g. building a REPL). But for more common patterns such as formatting types so they can be printed, I'm not a fan due to the amount of indirect calls/dynamic dispatch it will add.

[u/gingerbill → u/yorickpeterse]

you don't have to type-check the body of foo three different times; instead you just check if those types are compatible with whatever T requires

That depends on the language. In languages like C++, Odin (my language), Jai, Zig, etc, you actually have to check the bodies BECAUSE they do not work on a type-class system. In this ilk of languages, languages like Go and Rust do not need to type check those bodies again, but then again, they are doing something else. Also if those bodies have any form of condition compilation based on the type of that parameter, then you do have to check.

So if you understand that context, then the rest of the article should make more sense.

[u/matthieum]

RTTI is Linear

Doesn't this widely depend upon what information is included in RTTI?

For example, in C++, RTTI can be used to perform cross-casts via dynamic_cast. This requires that every type encode the full hierarchy of interfaces it implements.

The size of this information is linear in the number of types, and linear in the highest number of interfaces implemented by a type... but it's the product of the two, so feels quadratic-ish no?

CTTI’s worst case is exponential, in three places at once (semantic checking, code generation, and binary size)

You're missing perhaps the most important place of all: i-cache.

Bloating the i-cache with virtually (but not quite) identical copies of the same function has a run-time performance cost, due to the ensuing cache-misses which stall execution.

[u/gingerbill → u/matthieum]

C++ doesn't really have any RTTI, and I would not call dynamic_cast a (good) example of that.

I agree that the code to check that will be a quadratic runtime check, but it's also a check virtually no-one should ever be using since C++ is just badly designed everywhere. When I've had to do that kind of check in a company where dynamic_cast was banned, we just stored an enum and the check was now constant.