4 ms·

A generics List<T> isn't much slower than the non-generic List if T is some class. This is only true generics using erasure, such as in Java. Since Java will s

A generics List<T> isn't much slower than the non-generic List if T is some class. This is only true generics using erasure, such as in Java. Since Java will store Objects (pointers to objects) in both cases. But in languages that use e.g. monomorphization a List<T> stores the Ts adjacent in memory, since the size of each element is known, whereas a non-generic list has to store pointers to objects, since the object sizes are not known and may vary per element. A generic List<T> that is monomorphized has two large benefits: fewer cache misses due to locality and more opportunities to inline T method implementations.

magicalhippo 8y ago
I was assuming the parent post was referencing the Java implementation as described in the article.
Someone 8y ago
You can only do that if you can prove that T will never have subclasses that are larger. To check that, the compiler either has to see all code that will run in the process, which means whole program compilation and no plugins, or the language needs a way to make classes that cannot be subclassed, preventing code that the compiler didn’t see from subclassing T (https://en.wikipedia.org/wiki/Class_(computer_programming)#Non-subclassable https://en.wikipedia.org/wiki/Class_(computer_programming)#N...)
- danieldk 8y ago
  You can only do that if you can prove that T will never have subclasses that are larger. Only if generic type parameters are covariant, if type parameters are invariant, this is not a problem. I guess that most languages with subtypes use invariance by default. Also, many languages that do generics through monomorphization do not support subclassing (Rust, Haskell, etc.). no plugins, Well, there is always the option of boxing collection elements. (E.g. by using Box in Rust.)
  - catnaroek 8y ago
    In general, Haskell does not do parametric polymorphism through monomorphization. In particular, higher-rank polymorphism becomes unusable if polymorphism is implemented through monomorphization. On the other hand, if I recall correctly, Rust only supports higher-rank polymorphism for lifetimes, which neither have nor need a runtime representation. This is why monomorphization is a viable implementation strategy for Rust generics. (Aside: Type checkers essentially see recursive function definitions as applications of a fixed point operator to non-recursive functions. If your function has a rank-1 type but uses polymorphic recursion, the type checker sees it as the application of a rank-2 fixed point operator to a non-recursive function. This is why I see polymorphic recursion as “morally higher-rank polymorphism”, even when the type signatures in your code are ostensibly rank-1 ones. Polymorphic recursion is widely used in Haskell.) However, IMO, you only need rank-1 polymorphism 95% of the time anyway, so optimizing for the common use case is a good strategy. By far, the main use case for generics is implementing efficient and reasonably reusable data structures and algorithms in a reasonably type-safe way. For this use case, monomorphization and aggressive inlining of small functions are evidently the right things to do. Other uses of generics (say, streaming I/O frameworks) strike me as a lot more questionable.

magicalhippo 8y ago

I was assuming the parent post was referencing the Java implementation as described in the article.

Someone 8y ago

You can only do that if you can prove that T will never have subclasses that are larger. To check that, the compiler either has to see all code that will run in the process, which means whole program compilation and no plugins, or the language needs a way to make classes that cannot be subclassed, preventing code that the compiler didn’t see from subclassing T (https://en.wikipedia.org/wiki/Class_(computer_programming)#Non-subclassable https://en.wikipedia.org/wiki/Class_(computer_programming)#N...)

danieldk 8y ago
You can only do that if you can prove that T will never have subclasses that are larger. Only if generic type parameters are covariant, if type parameters are invariant, this is not a problem. I guess that most languages with subtypes use invariance by default. Also, many languages that do generics through monomorphization do not support subclassing (Rust, Haskell, etc.). no plugins, Well, there is always the option of boxing collection elements. (E.g. by using Box in Rust.)
- catnaroek 8y ago
  In general, Haskell does not do parametric polymorphism through monomorphization. In particular, higher-rank polymorphism becomes unusable if polymorphism is implemented through monomorphization. On the other hand, if I recall correctly, Rust only supports higher-rank polymorphism for lifetimes, which neither have nor need a runtime representation. This is why monomorphization is a viable implementation strategy for Rust generics. (Aside: Type checkers essentially see recursive function definitions as applications of a fixed point operator to non-recursive functions. If your function has a rank-1 type but uses polymorphic recursion, the type checker sees it as the application of a rank-2 fixed point operator to a non-recursive function. This is why I see polymorphic recursion as “morally higher-rank polymorphism”, even when the type signatures in your code are ostensibly rank-1 ones. Polymorphic recursion is widely used in Haskell.) However, IMO, you only need rank-1 polymorphism 95% of the time anyway, so optimizing for the common use case is a good strategy. By far, the main use case for generics is implementing efficient and reasonably reusable data structures and algorithms in a reasonably type-safe way. For this use case, monomorphization and aggressive inlining of small functions are evidently the right things to do. Other uses of generics (say, streaming I/O frameworks) strike me as a lot more questionable.