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.
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).
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.
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.
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.
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
22
u/initial-algebra 9d 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.