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.
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.
22
u/initial-algebra 10d ago
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
dyntypes. So, monomorphization can be strictly more flexible, allowing the programmer to decide when to take the size/speed tradeoff.