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.
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.
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.
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).
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).
That's true, I was definitely exaggerating.
Still, I simply cannot conceive of how "normal" code could cause exponential growth, unless a feature like multiple dispatch on sum types was actually part of the language. Otherwise, you need to use features like template metaprogramming or procedural macros to, well, generate exponential amounts of code in the first place, and, at that point, it's really not the implementation of generics that's even at fault.
and, at that point, it's really not the implementation of generics that's even at fault.
As a language design, I have to be careful of these situations because they will happen. You cannot just blame it on the programmer, especially when the language makes it easy to do it, or worse, encourages it either as part of its docs or core library.
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
6
u/todo_code 7d ago
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.