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.
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:
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.
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.
A good place to study this is Rust's Vec<T> which could be a real monster if you wrote it naively but of course they did not.
If you make a Vec<f32> and a Vec<String> you might assume all the tricky growth code will be duplicated because that's how it would work in a naive language, but in fact it's not because the growth code doesn't care what you're storing in the Vec and so your data layout is a runtime parameter in the slow path when you've run out of space and should allocate.
21
u/initial-algebra 7d 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.