6 ms·

Out of curiosity, what do you think is wrong with monomorphization-based polymorphism? The other alternatives I'm aware of are 1. type-erasure via v-table based

by nicoty 4mo ago

Out of curiosity, what do you think is wrong with monomorphization-based polymorphism? The other alternatives I'm aware of are 1. type-erasure via v-table based dynamic dispatch (which Rust also has in the form of the `dyn` keyword), which has performance and memory-allocation overhead and 2. macros, which Rust also has and, if used for polymorphism, would essentially be like compile-time monomorphization, but clunkier. Maybe I'm missing something though and there are other alternatives done differently in other languages?

uecker 4mo ago
The correct choice IMHO is type-erasure. It does not necessarily have overhead, because optimizers can specialize or devirtualize. Of course, this my depend on how you implement your language, but in C this works nicely. The problem with monomorphization is that it leads to exponential expansion, which later passes of the compiler can not unify again (at least this is much harder than not expanding in the first place). It should also fundamentally limit what you can do, because expansion has to stop at some point, but I haven't thought about this too much. I also think that where you want monomophization, macro seem fine. I do not think this necessarily has to be clunky, but this is just a guess.
- tialaramex 4mo ago
  I don't think the numbers bear out that "this works nicely" in C, it seems like you have worse perf numbers for some common cases like sorting ?
  - uecker 4mo ago
    Not sure what numbers you are talking about. If you use qsort from the C library the comparison function will not be inlined, but if you provide your own, this is no problem.
    - tialaramex 4mo ago
      > if you provide your own, this is no problem. If just "providing my own" would help why wouldn't the stdlib benefit too? You're going to have to spell out what you think can actually work here if you want me to believe there's "no problem".
      - uecker 4mo ago
        It would also, but nobody cares enough because qsort is already fast enough for most things, and if you cared it is simply enough to do yourself. Are you doubting that C compilers can devirtualize function calls? Here is a small example that illustrates this. The compiler dervirtualizes all calls than folds the result: https://godbolt.org/z/E6cMMr8vx https://godbolt.org/z/E6cMMr8vx
        tialaramex 4mo ago
        [dead]
- fluffybucktsnek 4mo ago
  Type-erasure does have an inherent overhead. Sure, optimizations can be made, but they can be fickle and specialization is basically implicit monomorphization. Using C macros to replicate Rust's monomorphism has several drawbacks: they are inherently unhygienic, even in comparison to Rust's own; you can't set type-bounds; they aren't even a part of C proper, etc. I prefer Rust's approach with the choice between generics, macros, dyn and Any.
  - uecker 4mo ago
    What inherent overhead does type-erasure have? The optimizer can always specialize just like for monomorphization. The difference is that it does not have to do this. Monomorphization specializes everything before the optimizer even has a chance to look the the code. So it fundamentally can not have advantages, only restrictions. C macros are certainly a proper part of C and one can also certainly add type-bounds. But yes, they are not ideal. Still, if one wanted to do this, one could certainly improve them a lot for type-generic programming. I would prefer this to having macros, generics, a const expression sublanguage, and vtables.
    - fluffybucktsnek 4mo ago
      The inherent overhead of type-erasure is the vtable. Which is funny, because you said you prefer one over the other at the end, when they are basically synonymous. The compiler may choose to devirtualize and specialize, but that isn't guaranteed. If you want this behavior, &dyn does the exact same thing. Specialization provides more opportunities for optimizations, whereas proper type-erasure (which bars specialization optimizations) doesn't due to lack of type information. "C macros" are a part of the preprocessor, which runs before the actual C compiler. As such, it lacks all semantical information the C compiler would have at that point, such as function implementions. In practice, macros in C serve two purposes: manipulating C source code (which Rust macros can also do, but with more hygiene); specialization polymorphism, but worse (in which both Rust's generics and C++ templates do better).
      - uecker 4mo ago

by nicoty 4mo ago

uecker 4mo ago

The correct choice IMHO is type-erasure. It does not necessarily have overhead, because optimizers can specialize or devirtualize. Of course, this my depend on how you implement your language, but in C this works nicely. The problem with monomorphization is that it leads to exponential expansion, which later passes of the compiler can not unify again (at least this is much harder than not expanding in the first place). It should also fundamentally limit what you can do, because expansion has to stop at some point, but I haven't thought about this too much. I also think that where you want monomophization, macro seem fine. I do not think this necessarily has to be clunky, but this is just a guess.

tialaramex 4mo ago
I don't think the numbers bear out that "this works nicely" in C, it seems like you have worse perf numbers for some common cases like sorting ?
- uecker 4mo ago
  Not sure what numbers you are talking about. If you use qsort from the C library the comparison function will not be inlined, but if you provide your own, this is no problem.
  - tialaramex 4mo ago
    > if you provide your own, this is no problem. If just "providing my own" would help why wouldn't the stdlib benefit too? You're going to have to spell out what you think can actually work here if you want me to believe there's "no problem".
    - uecker 4mo ago
      It would also, but nobody cares enough because qsort is already fast enough for most things, and if you cared it is simply enough to do yourself. Are you doubting that C compilers can devirtualize function calls? Here is a small example that illustrates this. The compiler dervirtualizes all calls than folds the result: https://godbolt.org/z/E6cMMr8vx https://godbolt.org/z/E6cMMr8vx
      - tialaramex 4mo ago
        [dead]
fluffybucktsnek 4mo ago
Type-erasure does have an inherent overhead. Sure, optimizations can be made, but they can be fickle and specialization is basically implicit monomorphization. Using C macros to replicate Rust's monomorphism has several drawbacks: they are inherently unhygienic, even in comparison to Rust's own; you can't set type-bounds; they aren't even a part of C proper, etc. I prefer Rust's approach with the choice between generics, macros, dyn and Any.
- uecker 4mo ago
  What inherent overhead does type-erasure have? The optimizer can always specialize just like for monomorphization. The difference is that it does not have to do this. Monomorphization specializes everything before the optimizer even has a chance to look the the code. So it fundamentally can not have advantages, only restrictions. C macros are certainly a proper part of C and one can also certainly add type-bounds. But yes, they are not ideal. Still, if one wanted to do this, one could certainly improve them a lot for type-generic programming. I would prefer this to having macros, generics, a const expression sublanguage, and vtables.
  - fluffybucktsnek 4mo ago
    The inherent overhead of type-erasure is the vtable. Which is funny, because you said you prefer one over the other at the end, when they are basically synonymous. The compiler may choose to devirtualize and specialize, but that isn't guaranteed. If you want this behavior, &dyn does the exact same thing. Specialization provides more opportunities for optimizations, whereas proper type-erasure (which bars specialization optimizations) doesn't due to lack of type information. "C macros" are a part of the preprocessor, which runs before the actual C compiler. As such, it lacks all semantical information the C compiler would have at that point, such as function implementions. In practice, macros in C serve two purposes: manipulating C source code (which Rust macros can also do, but with more hygiene); specialization polymorphism, but worse (in which both Rust's generics and C++ templates do better).
    - uecker 4mo ago