Item — HN Reader

The point is much easier to propagate information (and not accidentally lose it) than to deduplicate after specialiation, so I do not agree that this is only of theoretical relevance.

I agree that monomorphization has explicit rules that force specialization, I do not think this is an advantage at all because it is too rigid and one can introduce explicitness at the language level also for devirtualization where this is needed. In this sense, monomorphization is premature optimization which limits what can be expressed at the language level and makes the job of the optimizer much harder (and practically impossible to undo the damage completely).

1 comments

You seem to be underestimating how easy it is to lose type information. Creating a array of type-erased is already enough to cause confusion, even if the surrounding code is enough to prove the array only has one type. If we are to assume perfect deductive ability for type-erasure, why not for monomorphism as well?

Monomorphization isn't premature optimizations either. It and type-erasure are semantically different. For instance, only monorphization can enable inlining of data structures (as devirtualizating an array of fat pointers involves dealing with ownership concerns, among other things). You either have to type-erase the array itself or box all the items, none of which are very ergonomic for a system-level programming. Also, in terms of performance, monomorphization generally makes the compiler's job easier overall in comparison to type-erasure (specially in Rust where types also encode lifetime), so I don't see the damage unless you are dealing with an extremely size-constrained environment or dealing with instruction cache misses (which is an indication of poor abstractions).

Finally, as stated elsewhere, it's trivial to implement any type-erasure polymorphism in a monomorphic system (save for very specific exceptions, related to hardware), but the reverse is not true. To do so reliably will require assistance of an external codegen tool, like the C macros, generally recreating monomorphism, but worse, as the compiler doesn't actually know the polymorphic code is related, making deduplication even harder.

I don't see why it would easy to lose type information in circumstances where you can do monomorphization. Note that I do not assume "perfect deductive ability". The practical observation is simply that it is far more effort to deduplicate than to clone.

I am not sure why either (I believe it is aliasing), here's an example: https://godbolt.org/z/9szhxoxrf

From the code, we can already tell all elements have the same type, but the compiler is already adding checks. One of the options would be to convert the array of fat pointers into a fat slice. But now you have to enlarge the slice's vtable with all possible item operations, even if we don't use them often. Alternatively, use monomorphism. Or use both.

I see, this is what you meant. GCC can not currently do this. But this also not something that would correspond to a monomorphic version. A polymorphic function over a generic array would be specialized to one member type via monomorphization. This would correspond to this: https://godbolt.org/z/nd333xeTP

A bit of a nitpick, but I think this would be closer to a generic array: https://godbolt.org/z/cfdPWb6zz

Still, adding a different typed array already breaks inlining, https://godbolt.org/z/zavojE8xK (type-erasure) vs. https://godbolt.org/z/barroPfsP (monomorphized).

Aside from being heavily optimization-dependant, thinking through this, I've realized that type-erasure is a bit of a premature abstraction. It forces programmers to use indirection and pass-by-reference/pointer. It forces functions to be type size and alignment-agnostic. That's why type-erasure can't express monomorphism proper, whereas the reverse is not true.

It is trivial to see that the compiler could do inlining also in this case. Your modification does not "break" inlining in the sense of making it impossible. In fact, just making the vtables "const" is enough and it does it: https://godbolt.org/z/oYv47xx8G Or adding "inline" would also do it. (But this not why your argument is wrong.)

The compiler chooses to not inline in your example. And this is the point: The compiler makes inlining decisions based on some heuristics exactly because inlining is not always an advantage (even if it is in toy examples), otherwise it would do it far more often. Implementing type-erasure gives it the freedom to do this while monomorphization hardcodes it. It takes away this freedom. You can get the same result as monomorphization by forcing certain inlining or function-cloning decisions, but the reverse is much harder: you can not automatically deduplicate the already expanded function. (in theory yes, in practice no)

The argument that for a language with type-erasure the inlining heuristics of this specific C compiler may not be ideal, is rather irrelevant. (but interprocedural value propagation is rather smart in principle)

My issue isn't that the modification made it impossible to inline, more so how trivial it was: I just added a different type. Generally, optimizations are disabled not because the compiler finds them inneficent, but because it lacks enough contextual information/intelligence to safely add it. So similar to what you said, in theory, the compiler can optimize type-erasure just like monomorphism, but, in practice, it lacks info to do so. Either by programmer accident, language/compiler limitations, or both.

Also, monomorphization doesn't actually take the compiler freedom away (on its own) to optimize. Similar to how type-erasure can be optimized to behave like monomorphization through devirtualization, monomorphized calls can be virtualized (which Swift shows). The problem is that it takes away transparency from the programmer. It also changes the semantics of the call behind the scene (type-erasure is strictly pass-by-pointers, monomorphism is not). That wouldn't work well for a low-level language.