6 ms·

> Java is the only one on this list that has a different approach. Instead of using generics at compile time, it is actually doing a dispatch of the code to opt

> Java is the only one on this list that has a different approach. Instead of using generics at compile time, it is actually doing a dispatch of the code to optimized routines based on runtime types. That does mean that they had to write the same sort code multiple times, of course. > Using Java: public static void sort(int [] a); public static void sort(long[] a); public static void sort(Object[] a); Perhaps they meant it another way, but this makes it sound like there is runtime dispatch between these different signatures - there isn't. int, long etc. are unboxed types in Java, which are not Objects, and cannot be used for Object-based generic type-erasure. So the decision which of these sorts is going to be used is made by the compiler. All Objects are sorted using the third signature.

zwieback 4y ago
Yes, seems like Java generics are an argument against the "generics allow optimization" argument. Maybe I misunderstood what he was trying to say.
- lifthrasiir 4y ago
  Generics allow optimization, but that optimization has to be implemented in the first place. Java generics is an afterthought so you can expect such a suboptimal design.
  - malfist 4y ago
    Features added after launch doesn't make something an afterthought. Java generics are a key part of the language.
    - switchbak 4y ago
      Generics were only added in Java 1.5, they were absolutely not part of the original design, and type erasure is very much a considerable restriction in some cases. I would wager that a greenfield design would look quite different. Whether you call that an afterthought? I'm sure the designers had this in mind, but at the same time they painted themselves into a corner somewhat with earlier decisions and a huge dedication to backward compatibility. Their work on threads on the other hand shows some real forethought and they were able to avoid most of the pitfalls that a few other language impl's fell into.
    - wvenable 4y ago
      Generics in C# were also added after launch but have a significantly better implementation. While they are a key part of the language they aren't a key part of the platform.
  - cogman10 4y ago
    Java optimizes at the method level and the majority of methods when writing an app will have constant types used against them. Your method signature may look like void foo(Iterable<Bar> b) which would make you think of vtables and casting performance losses. However, Java's JIT is fairly cleaver. It can tell that you always call `foo` with an `ArrayList` and it can tell that `ArrayList`'s iterator always emits a `Bar` Object. From there it can elate a lot of the type tables and virtual dispatch to just be direct dispatch. It does that at the cost of a couple of added runtime checks to make sure those assumption's aren't violated. The impact of generics on performance has, for me, generally been pretty low. I've seen a much higher impact due to java's memory model (which is getting fixed with Valhalla). This, btw, is how JavaScript's and indeed most high speed JITs function.
    - lifthrasiir 4y ago
      Yeah, JIT does subsume naive AOT + generics for many cases, but it is a bit unfair comparison because there is no reason for other languages to implement such optimizations (PGO is one of them). And such an inference is not free and causes usual JIT pain points.
  - kaba0 4y ago
    I don’t think it is fair to call it an afterthought. I would even say that it was extremely well thought out, managing to move a whole ecosystem with millions of lines of code from unsafe raw usage to type-safe generics without much hiccup, at a time when this feature wasn’t all that well known by the average developer.
    - titzer 4y ago
      Erasure was a bad design choice. C# did the exact same upgrade (add generics to the language), but they chose to reify them and add them to the binary format, with a better overall result (IMHO). C# does not have platform reach that Java has, but there are a lot of factors at play there that go beyond language design choices.
      - kaba0 4y ago
        As I learned from another commenter here, C# 1.0 didn’t actually have generics at a language level, but was already designed that way on a vm level. So C# 2.0 could take advantage of that, making it much more of a planned feature from the start. Also, I don’t see erased generics all that big of a deal — if there was no reflection (which is not that common feature in languages) one could not even differentiate between the two models. Haskell also does complete type erasure for example. As for another view point, it is often brought up on HN that what made the JVM language ecosystem so thriving is exactly the type erasure model. C# effectively forces their idea of generics onto the whole platform, while JVM languages are free to choose their own model. I don’t know how true is that, but empirically it does seem to sound true (F# does share its generics model with C#, and the CLR has a history of getting some attempts at being a target which is later dropped. Though I assume it is more often due to it simply being a smaller target)
        titzer 4y ago
        > if there was no reflection (which is not that common feature in languages) one could not even differentiate between the two models. Haskell also does complete type erasure for example. You can, even without reflection, because the Java generic type system doesn't have the parametricity property; you can detect runtime types with cast/instanceof. Haskell doesn't have non-parametric operations, so erasure is not observable.
- marginalia_nu 4y ago
  The path Java chooses for optimization is through JIT, but that's entirely orthogonal to generics. Java generics are a syntactic construction, there really is no JVM support for them what so ever.
  - cogman10 4y ago
    It's complicated. There actually IS JVM support for generics in surprising locations. Just not at method dispatch... sort of. For example void <T extends Foo> bar(T f); will, under the covers, create a function that looks like void bar(Foo f); If you create a class class Foo implements Supplier<Bar> { Bar get() { return new Bar(); } } The method signature for `Foo` does in fact return a `Bar` type and not some `Object` type even though `Supplier<Bar>` would imply that is erased. The same applies to if that generic was used within the method parameters. That generic type information is, in fact, stored off at the class level and can be extracted through Java's reflection API. This is how magic like json.parse("[1,2,3]", new TypeReference<List<Integer>>{}); is getting it's stuff done. It's creating a new anonymous class of "TypeReference<List<Integer>>" which the json library can then use to introspect and pull the generic information out and know that it should create a `List` of `Integer` rather than of `Long` or `Double` or a `Set`. This makes generics more than just a syntactic construction in Java.
    - marginalia_nu 4y ago
      class Foo implements Supplier<Bar> { Bar get() { return new Bar(); } } Bar isn't a generic in Foo though (if we remove the implements-clause, that is very clear). It's only a generic in Supplier, so I don't see where the implied erasure quite comes from.
      - cogman10 4y ago
        I didn't add it, but the `get` method comes is an override from the `Supplier`. For example, if we did something like class Foo extends HashMap<Foo, Bar> { @Override Bar put(Foo f, Bar b) { super.put(f, b); } } The `Map` signature for `put` is `Object put(Object, Object)` due to erasures. However, because you are extending and specifying the generics, the overriden method ends up reifying the type. All this is to say that generics end up being a little more than just syntactic sugar.
- mumblemumble 4y ago
  I think the author got it slightly wrong here because he's conflating the programming language feature and its semantics with the run-time implications of the technique(s) you use to implement that feature. For what it's worth, this seems to be a common misunderstanding where generics are concerned.
- kaba0 4y ago
  That is also not true — Java’s generics don’t add any overhead. If you would have written an ArrayList implementation before generics you would have had the exact same compiled method signature like put(Object o) and Object get() - the only difference is that it would not have been type safe, that is you could have inserted a String into it while you might have expected to get an Integer on the other side. So generics are completely a language semantic concept in case of Java, with no performance detriment/benefit. Of course more information can be used up for better optimizations as well, see Rust’s or C++’s generics/templates.
  - titzer 4y ago
    The javac source compiler erases source-level types and inserts casts into the bytecode (at usage sites, not within the generic class). So if you have ArrayList<T>, it will generate one version of ArrayList. But usage sites will have casts inserted where necessary. In particular, in a use of put() on the outside doesn't need a cast (because the single implementation of ArrayList uses Object underneath), but get() will have a cast from Object to String at the call site.
dcminter 4y ago
Plus I don't know about you, but I don't sort (or really use) arrays in Java very much. I see a lot more of the Collections.sort() methods, particularly the comparator based one.
- marginalia_nu 4y ago
  Sorting arrays of primitives ought to be nearly as frequent as the need for sorted arrays of primitives due to the downright comical overhead of List<Integer>, but sorting arrays of objects has be rare in Java code written this millennium.
  - dcminter 4y ago
    I mean I don't sort List<Integer> more than once in a blue moon either. I'm much more likely to either be sorting a list of model objects with a comparator, or manipulating a collection of objects that's already been sorted by some external source. In the unlikely event that I'm modeling something that can be represented as a list of integers AND it's a significant performance bottleneck then, sure, I'll consider the array methods. But I don't recall the need arising in the last year or two. Enterprise Java stuff just isn't often bottlenecked on that sort of thing. Network latency fills far more of my dreams ;)
    - marginalia_nu 4y ago
      Maybe we're seeing different sides of the language then. I'm doing a lot of integer-list sorting, building a search engine in java. I'm evenly split between Arrays.sort or GNU Trove's specialized primitive collections. The overhead of List<Integer> really can not be overstated, it can approach order 1000% memory consumption, speed is prima facie about half for dealing with collections, but in practice it can be much lower from the GC churn. Even for lists as small as a million entries this can be quite untenable.
      - Scarbutt 4y ago
        Maybe we're seeing different sides of the language then. You are not seeing different sides of the language but participating in different domains, application/business logic programming vs more system level stuff.
taeric 4y ago
Yeah, this really needs to point out that the elements in Arrays.sort have to be Comparable. More, they have to be Comparable with each other. Should probably show the Collections.sort that takes a Comparator to really make the point that that is dispatched at runtime. But then you would probably need to cover just how aggressive the JIT is in the JVM and how the costs may not be what you would think they are.
- GordonS 4y ago
  You're not wrong, but I feel like this doesn't need explicitly spelled out, as it would be obvious to any Java dev (or C#, or indeed probably any language with generics).
  - taeric 4y ago
    I think my problem is that there is no runtime dispatch between the methods that were listed. Such that that was a bit of a non-sequitur for the point at hand.
Koshkin 4y ago
This has little (nothing?) to do with generics, though. This is an example of function (name) overloading.
- tialaramex 4y ago
  The technical term for this feature in this context is "ad hoc polymorphism". It's polymorphic because it only allows you to specify different types, you can't just go around making six different foo() methods that all take a string - that doesn't work because the compiler can't tell which one you wanted, and it's ad hoc because you can just fill out whatever you want in each version. The negative consequence of being ad hoc is that there's not even a very strong implication beyond the name that these different functions all do the same thing, and sure enough they often don't. So now either your users must read your documentation very carefully, or sometimes they will have unhappy accidents. This is made worse in many modern languages with type inference where your users may be mistaken about which of the functions they're actually calling since they don't always know the type of anything anyway... Ad hoc polymorphism is over-used because it is relatively cheap to implement, and it's cheap to add more of these overrides later.
  - Koshkin 4y ago
    Well, having methods in different classes that happen to share the same name is also an example of that, and so it cannot be avoided (not in practice, anyway).
charcircuit 4y ago
>All Objects are sorted using the third signature. Just to be pedantic int[] and long[] are both objects, but will be sorted using the first two signatures because the JVM uses different instructions for loading and storing elements from an array. Technically you could make a single function to return an array's length since it uses the same instruction.
- anonymoushn 4y ago
  This surely meant "All arrays of Objects"
mrighele 4y ago
Java generics works only on reference types (i.e. anything that derives from Object), and not on primitive types like int and long. For this reason, if you want a method that work on both primitives and reference types, you have to provide distinct implementations. This is true even if you provide a generic version like public static <A> void sort(A[] e); You will not be able to use the above method with an int[]. Whenever possible the compiler will try to be helpful, and automatically box/unbox primitives for you, so for example the following will work public <A> A max(A a1, A a2); /* ... */ void foo() { int x = max(1,2); } this comes at the cost of boxing ints inside Integer, though. So, if you ignore for a moment primitives types, whenever you have generics, everything boils down to a single method accepting Objects and returning Objects. What the JVM does is to do runtime profiling of what actually you are passing to the generic method, and generate optimized routines for the "best case". In theory this is the best of the two worlds, because (unlike, let's say, C++) you will have a single implementation of the method, avoiding code explosion, but if you use it in an hot spot you get the optimized code. In a way, it is quite wasteful, because you throw away a lot of information at compile time, just to get it back (and maybe not all of it) at runtime through profiling, but in practice it works quite well. A side effect of this is this makes the JVM a wonderful VM for running dynamic languages like Ruby and Python, because that information is _not_ there at compile time. In particular GraalVM/Truffle and exposes this functionality to dynamic language implementations, allowing very good performance (according to their website [1][2], Ruby and Python on Truffle are about 8x faster than the official implementation, and JS in line with V8) [1] https://www.graalvm.org/ruby/ https://www.graalvm.org/ruby/ [2] https://www.graalvm.org/python/ https://www.graalvm.org/python/
- amenghra 4y ago
  The state of Java’s type erasure makes me quite sad when I need the type information via introspection. I’d say the best situation would be keep the type information at compile time but let the VM decide if multiple implementations are needed or not at runtime.
  - admax88qqq 4y ago
    What information do you need that's gone? Type erasure happens but the objects still carry their true dynamic type with them, isn't that sufficient?

zwieback 4y ago

Yes, seems like Java generics are an argument against the "generics allow optimization" argument. Maybe I misunderstood what he was trying to say.

lifthrasiir 4y ago
Generics allow optimization, but that optimization has to be implemented in the first place. Java generics is an afterthought so you can expect such a suboptimal design.
- malfist 4y ago
  Features added after launch doesn't make something an afterthought. Java generics are a key part of the language.
  - switchbak 4y ago
    Generics were only added in Java 1.5, they were absolutely not part of the original design, and type erasure is very much a considerable restriction in some cases. I would wager that a greenfield design would look quite different. Whether you call that an afterthought? I'm sure the designers had this in mind, but at the same time they painted themselves into a corner somewhat with earlier decisions and a huge dedication to backward compatibility. Their work on threads on the other hand shows some real forethought and they were able to avoid most of the pitfalls that a few other language impl's fell into.
  - wvenable 4y ago
    Generics in C# were also added after launch but have a significantly better implementation. While they are a key part of the language they aren't a key part of the platform.
- cogman10 4y ago
  Java optimizes at the method level and the majority of methods when writing an app will have constant types used against them. Your method signature may look like void foo(Iterable<Bar> b) which would make you think of vtables and casting performance losses. However, Java's JIT is fairly cleaver. It can tell that you always call `foo` with an `ArrayList` and it can tell that `ArrayList`'s iterator always emits a `Bar` Object. From there it can elate a lot of the type tables and virtual dispatch to just be direct dispatch. It does that at the cost of a couple of added runtime checks to make sure those assumption's aren't violated. The impact of generics on performance has, for me, generally been pretty low. I've seen a much higher impact due to java's memory model (which is getting fixed with Valhalla). This, btw, is how JavaScript's and indeed most high speed JITs function.
  - lifthrasiir 4y ago
    Yeah, JIT does subsume naive AOT + generics for many cases, but it is a bit unfair comparison because there is no reason for other languages to implement such optimizations (PGO is one of them). And such an inference is not free and causes usual JIT pain points.
- kaba0 4y ago
  I don’t think it is fair to call it an afterthought. I would even say that it was extremely well thought out, managing to move a whole ecosystem with millions of lines of code from unsafe raw usage to type-safe generics without much hiccup, at a time when this feature wasn’t all that well known by the average developer.
  - titzer 4y ago
    Erasure was a bad design choice. C# did the exact same upgrade (add generics to the language), but they chose to reify them and add them to the binary format, with a better overall result (IMHO). C# does not have platform reach that Java has, but there are a lot of factors at play there that go beyond language design choices.
    - kaba0 4y ago
      As I learned from another commenter here, C# 1.0 didn’t actually have generics at a language level, but was already designed that way on a vm level. So C# 2.0 could take advantage of that, making it much more of a planned feature from the start. Also, I don’t see erased generics all that big of a deal — if there was no reflection (which is not that common feature in languages) one could not even differentiate between the two models. Haskell also does complete type erasure for example. As for another view point, it is often brought up on HN that what made the JVM language ecosystem so thriving is exactly the type erasure model. C# effectively forces their idea of generics onto the whole platform, while JVM languages are free to choose their own model. I don’t know how true is that, but empirically it does seem to sound true (F# does share its generics model with C#, and the CLR has a history of getting some attempts at being a target which is later dropped. Though I assume it is more often due to it simply being a smaller target)
      - titzer 4y ago
        > if there was no reflection (which is not that common feature in languages) one could not even differentiate between the two models. Haskell also does complete type erasure for example. You can, even without reflection, because the Java generic type system doesn't have the parametricity property; you can detect runtime types with cast/instanceof. Haskell doesn't have non-parametric operations, so erasure is not observable.
marginalia_nu 4y ago
The path Java chooses for optimization is through JIT, but that's entirely orthogonal to generics. Java generics are a syntactic construction, there really is no JVM support for them what so ever.
- cogman10 4y ago
  It's complicated. There actually IS JVM support for generics in surprising locations. Just not at method dispatch... sort of. For example void <T extends Foo> bar(T f); will, under the covers, create a function that looks like void bar(Foo f); If you create a class class Foo implements Supplier<Bar> { Bar get() { return new Bar(); } } The method signature for `Foo` does in fact return a `Bar` type and not some `Object` type even though `Supplier<Bar>` would imply that is erased. The same applies to if that generic was used within the method parameters. That generic type information is, in fact, stored off at the class level and can be extracted through Java's reflection API. This is how magic like json.parse("[1,2,3]", new TypeReference<List<Integer>>{}); is getting it's stuff done. It's creating a new anonymous class of "TypeReference<List<Integer>>" which the json library can then use to introspect and pull the generic information out and know that it should create a `List` of `Integer` rather than of `Long` or `Double` or a `Set`. This makes generics more than just a syntactic construction in Java.
  - marginalia_nu 4y ago
    class Foo implements Supplier<Bar> { Bar get() { return new Bar(); } } Bar isn't a generic in Foo though (if we remove the implements-clause, that is very clear). It's only a generic in Supplier, so I don't see where the implied erasure quite comes from.
    - cogman10 4y ago
      I didn't add it, but the `get` method comes is an override from the `Supplier`. For example, if we did something like class Foo extends HashMap<Foo, Bar> { @Override Bar put(Foo f, Bar b) { super.put(f, b); } } The `Map` signature for `put` is `Object put(Object, Object)` due to erasures. However, because you are extending and specifying the generics, the overriden method ends up reifying the type. All this is to say that generics end up being a little more than just syntactic sugar.
mumblemumble 4y ago
I think the author got it slightly wrong here because he's conflating the programming language feature and its semantics with the run-time implications of the technique(s) you use to implement that feature. For what it's worth, this seems to be a common misunderstanding where generics are concerned.
kaba0 4y ago
That is also not true — Java’s generics don’t add any overhead. If you would have written an ArrayList implementation before generics you would have had the exact same compiled method signature like put(Object o) and Object get() - the only difference is that it would not have been type safe, that is you could have inserted a String into it while you might have expected to get an Integer on the other side. So generics are completely a language semantic concept in case of Java, with no performance detriment/benefit. Of course more information can be used up for better optimizations as well, see Rust’s or C++’s generics/templates.
- titzer 4y ago
  The javac source compiler erases source-level types and inserts casts into the bytecode (at usage sites, not within the generic class). So if you have ArrayList<T>, it will generate one version of ArrayList. But usage sites will have casts inserted where necessary. In particular, in a use of put() on the outside doesn't need a cast (because the single implementation of ArrayList uses Object underneath), but get() will have a cast from Object to String at the call site.

dcminter 4y ago

Plus I don't know about you, but I don't sort (or really use) arrays in Java very much. I see a lot more of the Collections.sort() methods, particularly the comparator based one.

marginalia_nu 4y ago
Sorting arrays of primitives ought to be nearly as frequent as the need for sorted arrays of primitives due to the downright comical overhead of List<Integer>, but sorting arrays of objects has be rare in Java code written this millennium.
- dcminter 4y ago
  I mean I don't sort List<Integer> more than once in a blue moon either. I'm much more likely to either be sorting a list of model objects with a comparator, or manipulating a collection of objects that's already been sorted by some external source. In the unlikely event that I'm modeling something that can be represented as a list of integers AND it's a significant performance bottleneck then, sure, I'll consider the array methods. But I don't recall the need arising in the last year or two. Enterprise Java stuff just isn't often bottlenecked on that sort of thing. Network latency fills far more of my dreams ;)
  - marginalia_nu 4y ago
    Maybe we're seeing different sides of the language then. I'm doing a lot of integer-list sorting, building a search engine in java. I'm evenly split between Arrays.sort or GNU Trove's specialized primitive collections. The overhead of List<Integer> really can not be overstated, it can approach order 1000% memory consumption, speed is prima facie about half for dealing with collections, but in practice it can be much lower from the GC churn. Even for lists as small as a million entries this can be quite untenable.
    - Scarbutt 4y ago
      Maybe we're seeing different sides of the language then. You are not seeing different sides of the language but participating in different domains, application/business logic programming vs more system level stuff.

taeric 4y ago

Yeah, this really needs to point out that the elements in Arrays.sort have to be Comparable. More, they have to be Comparable with each other. Should probably show the Collections.sort that takes a Comparator to really make the point that that is dispatched at runtime. But then you would probably need to cover just how aggressive the JIT is in the JVM and how the costs may not be what you would think they are.

GordonS 4y ago
You're not wrong, but I feel like this doesn't need explicitly spelled out, as it would be obvious to any Java dev (or C#, or indeed probably any language with generics).
- taeric 4y ago
  I think my problem is that there is no runtime dispatch between the methods that were listed. Such that that was a bit of a non-sequitur for the point at hand.

Koshkin 4y ago

This has little (nothing?) to do with generics, though. This is an example of function (name) overloading.

tialaramex 4y ago
The technical term for this feature in this context is "ad hoc polymorphism". It's polymorphic because it only allows you to specify different types, you can't just go around making six different foo() methods that all take a string - that doesn't work because the compiler can't tell which one you wanted, and it's ad hoc because you can just fill out whatever you want in each version. The negative consequence of being ad hoc is that there's not even a very strong implication beyond the name that these different functions all do the same thing, and sure enough they often don't. So now either your users must read your documentation very carefully, or sometimes they will have unhappy accidents. This is made worse in many modern languages with type inference where your users may be mistaken about which of the functions they're actually calling since they don't always know the type of anything anyway... Ad hoc polymorphism is over-used because it is relatively cheap to implement, and it's cheap to add more of these overrides later.
- Koshkin 4y ago
  Well, having methods in different classes that happen to share the same name is also an example of that, and so it cannot be avoided (not in practice, anyway).

charcircuit 4y ago

>All Objects are sorted using the third signature. Just to be pedantic int[] and long[] are both objects, but will be sorted using the first two signatures because the JVM uses different instructions for loading and storing elements from an array. Technically you could make a single function to return an array's length since it uses the same instruction.

anonymoushn 4y ago
This surely meant "All arrays of Objects"

mrighele 4y ago

Java generics works only on reference types (i.e. anything that derives from Object), and not on primitive types like int and long. For this reason, if you want a method that work on both primitives and reference types, you have to provide distinct implementations. This is true even if you provide a generic version like public static <A> void sort(A[] e); You will not be able to use the above method with an int[]. Whenever possible the compiler will try to be helpful, and automatically box/unbox primitives for you, so for example the following will work public <A> A max(A a1, A a2); /* ... */ void foo() { int x = max(1,2); } this comes at the cost of boxing ints inside Integer, though. So, if you ignore for a moment primitives types, whenever you have generics, everything boils down to a single method accepting Objects and returning Objects. What the JVM does is to do runtime profiling of what actually you are passing to the generic method, and generate optimized routines for the "best case". In theory this is the best of the two worlds, because (unlike, let's say, C++) you will have a single implementation of the method, avoiding code explosion, but if you use it in an hot spot you get the optimized code. In a way, it is quite wasteful, because you throw away a lot of information at compile time, just to get it back (and maybe not all of it) at runtime through profiling, but in practice it works quite well. A side effect of this is this makes the JVM a wonderful VM for running dynamic languages like Ruby and Python, because that information is _not_ there at compile time. In particular GraalVM/Truffle and exposes this functionality to dynamic language implementations, allowing very good performance (according to their website [1][2], Ruby and Python on Truffle are about 8x faster than the official implementation, and JS in line with V8) [1] https://www.graalvm.org/ruby/ https://www.graalvm.org/ruby/ [2] https://www.graalvm.org/python/ https://www.graalvm.org/python/

amenghra 4y ago
The state of Java’s type erasure makes me quite sad when I need the type information via introspection. I’d say the best situation would be keep the type information at compile time but let the VM decide if multiple implementations are needed or not at runtime.
- admax88qqq 4y ago
  What information do you need that's gone? Type erasure happens but the objects still carry their true dynamic type with them, isn't that sufficient?