March 6th, 2015

by Ivan St. Ivanov

In the Bulgarian JUG we had an event dedicated to trying out the OpenJDK Valhalla project’s achievements in the area of using primitive parameters of generics. Our colleague and blogger Mihail Stoynov already wrote about our workshop. I decided, though, to go in a little bit more details and explain the various aspects of the feature.

In the first part of this three-part series of posts you could read about the reasoning behind not supporting generic classes with primitive parameters. In the second part we went through the proposed syntax, the implementation approaches and the compromises that led to them. In this last installment I will turn your attention to something that is very important when such big language and platform changes happen: the possible migration of the existing APIs and namely – the Collections library.

Again, before I start, I would like to make the same disclaimer again. I am not an expert in this matter. I just try to follow the project Valhalla mailing list as well as I read Brian Goetz’s State of Specialization document. So look at this series more as explaining the generics proposals in layman’s terms.

The usual suspect

There is one common thing about Java 5 and Java 8. They were both revolutionary releases with respect to the language, the platform and the APIs. And in both cases most of the discussions were how the big features coming with these new versions will affect and will be affected by the java.util libraries.

For example, let’s take the introduction of generics. The container nature of the collection API made it one of the most obvious candidates for generifying. That is why most of the compromises that were made (type erasure for example) were because of it and its ubiquitous usage.

Same in Java 8. The collections were again the usual suspect for benefiting from the newly introduced functional concepts made possible by the lambda expressions. Thus the Stream API was born, which allowed for more functional approach in working with containers, rather than following the imperative style of programming with iterators and loops. But in order to retrofit that new API into the existing java.util interfaces, they needed to be evolved in a backward compatible manner. Thus the needs of the collections (for the most part) brought us the concept of default methods.

So based on the history that we have, there’s no doubt that the introduction of the primitives in generics feature researched in project Valhalla will lead to some more migration challenges, mainly caused by the praised collection API.

Migration challenges

Let’s go through some of these challenges.

The java.util.ArrayList class is backed by Object array assuming that the type parameter extends Object. This doesn’t hold any more if you want to make the ArrayList parameterized with any T. And this and all other locations, where we have the following code:

T[] array = (T[]) new Object[n];

have to be adapted to support the specialization. Like this:

T[] array = new T[];

It is internal representation, you say, and its change is slightly easier, because of not breaking compatibility. And you will be right. But let’s check the other challenge. Let’s look at the List interface and its most commonly used implementation: ArrayList. What do you think about this method in the interface:

boolean remove(Object o);

It works fine with erasure, but will not work in the specialization case as primitive types cannot be cast to Object.

Similar is the situation with another, this time generified method in the List interface:

boolean removeAll(Collection<?> c);

As we saw in the previous installment of this series, Collection<?> cannot be cast to Collection<any T>. So this will not work with specialized List either.

Going even further, let’s consider the hypothetic situation, where the remove method is generified and takes T instead of Object. Then we will get the following overloaded methods in the List interface with rather different meaning:

remove(T element);
remove(int position);

This is not a simple overload: the above methods have completely different semantics. The first one is used to remove a concrete element, while the second one is used to remove the element with the specified index (presumably in a random access collection). If the class that defines these methods is made generic over any T and if T is int, then the virtual machine will have hard time to pick which of the two remove methods to call.

The final challenge that we’ll look here comes with the so called sentinel value of the get(key) method of java.util.Map. At the moment, if there is no value for the specified key in the map, this method will return null. However, this cannot be the case any more if the map can take non-reference types as they are not assignable to null. Finding proper sentinel value for primitive types is not an easy job (think about boolean :)).

The peeling technique

After going through the challenges, let’s take a look at how they can be resolved.

One of the solutions that was proposed in Brian Goetz’s paper is the so called peeling technique. According to it, an interface is broken down into layers. One generic layer that is common to all types of parameters and then optionally separate layers for the different kinds of type parameters: one for reference types, another one for primitive types, etc. In order to illustrate this, let’s take our hypothetical fully generified List with overloaded remove method:

public class List<E> {
    public boolean remove(E element);
    public boolean remove(int index);

It is already clear that its any-fying is not straightforward because of the option to specialize E to int. So, if we want to have a list over any E, we’ll have to somehow avoid method overloading. This can be done with the following possible steps:

  1. Define methods removeByValue(E) and removeByIndex(int) that are available to all the possible types E (primitive and reference). These methods will belong to the generic layer.
  2. To keep the backward compatibility, keep the overloaded remove methods, but define them only in the reference layer.
  3. In the same reference layer provide default implementations of the newly added generic methods that simply delegate to the respective remove method.

Here is one possible syntax for those three steps:

interface List<any E> {
    // 1) New methods added to the generic layer
    void removeByValue(E element);
    void removeByIndex(int pos);

    layer<ref T> {
        // 2) Abstract methods that exist only in the ref layer
        void remove(int pos);
        void remove(E element);

        // 3) Default implementations of the new generic methods
        default void removeByIndex(int pos) { remove(pos); }
        default void removeByValue(E e) { remove(e); }

I will leave to your imagination or curiosity to find out how could the Map.get method be implemented to support primitive return values.

First experiments

This proposal sounds a bit theoretical and at the same time bold. I still remember the contradiction that one such thing as default methods in interfaces brought in Java 8. We are most probably going to have private methods in interfaces in Java 9. And nobody paid real attention to static methods in interfaces (again Java 8). Comparing to those changes, the layer stuff looks like a revolution of its own. But let’s leave the theoretical discussions to the theoreticians, the philosophical disputes to the philosophers and let’s take a look at something tangible.

A few weeks ago Peter Levart came up with a first experiment for anyfying part of the collection API. He took the following paths in this first attempt:

  • Methods that were not fully generic (like Collection.remove(Object)) were complemented with an additional default method (Collection.removeElement(E))
  • Code with assumption that the internal representation is an object was changed in a way that it is E (or T). Check for example the sort method here
  • The construct new T[length] was used in the TimSort constructor instead of (T[]) Object[]
  • An interesting idiom (don’t know how to call it otherwise) was used for differentiator between pieces of code specific for reference and primitive (or actually value) types: __WhereVal(E) and __WhereRef(E)


In this third and final part of the blog series about primitive generic parameters we talked about what challenges will be there for the existing APIs (mostly the collections) when this feature is introduced. I briefly showed you the (so far) ultimate proposal for coping with those challenges as well as the initial experiments done in project Valhalla source repositories.

And that was it! In this three part series I tried to share with you in plain English the things that I shared with our Java user group in plain Bulgarian a month ago. I will be extremely happy if you enjoyed it and if you learned something new. Stay tuned for more great content from me and especially from our JUG!

February 20th, 2015

by Ivan St. Ivanov


In the Bulgarian JUG we had an event dedicated to trying out the OpenJDK Valhalla project’s achievements in the area of using primitive parameters of generics. Our colleague and blogger Mihail Stoynov already wrote about our workshop.

In the first part of this three-part series of posts you could read about the reasoning behind not supporting generic classes with primitive parameters. Before I continue with the current proposal for the implementation, I would like to again make a very important disclaimer. I am not an expert in this matter. I just try to follow the project Valhalla mailing list as well as I read Brian Goetz’s State of Specialization document. So look at this series more as explaining the generics proposals in layman’s terms.

Project Valhalla

Whenever the OpenJDK developers want to experiment with a concept they first create a dedicated OpenJDK project for that. This project usually has its own source repository, which is a fork of the OpenJDK sources. It has its page and mailing list and its main purpose is to experiment with ideas for implementing the new concept before creating the Java Enhancement Proposals (JEPs), the Java Specification Requests (JSRs) and committing source code in the real repositories. Features like lambdas, script engine support, method handles and invokedynamic walked this way before entering the official Java release.

One such project is Project Valhalla. Its goal is to research things like value types, enhanced volatiles and primitives (and value types) as parameters of generic types. The last feature of this impressive list is the topic of this blog series. Being part of a research project means that it may or may not exist as such in one of the future releases of Java. As Java 9 will be out quite soon (hopefully in a year or so), it is almost sure that we will not have the opportunity to generify over primitives any time soon. Anyway, it is a good idea to closely follow the development of this and other features that is why I wrote this blog post.

Coming back to the primitives in generics topic. After considering many arguments, the project developers, led by the Java language architect Brian Goetz, decided to make three substantial compromises and came up with a proposal.

Compromise#1: the language syntax

The first syntactic construct that comes into mind when talking about a, let’s say, list of primitive integers is List<int>. However, in the previous installment we saw why this is not possible. Or better said, it wouldn’t be possible without making big changes in the platform and possibly breaking backward compatibility. That is, the existing rules are rigorous about the fact that the generic parameter of a type can always be converted to Object, it should be assignable to null, etc. As big incompatible changes are not permitted, we come to compromise number one: if a class wants to allow enhanced generic support, i.e. support of primitives as generic parameter types, it has to explicitly state it in its definition, rather than relying that the rules for generics will be changed. This means that a new special syntax will be introduced on language level that will distinguish these enhanced generics from the existing ones. Here is the current proposal:

public class Box<any T> {

    private T value;

    public Box(T value) {
        this.value = value;

    T value() {
        return value;

You can probably notice the any modifier on the type variable. As per the current proposal it will be used to denote that the Box class can be parameterized with both reference as well as primitive types. Now, you can do things like this with the Box:

Box<int> intBox = new Box<>(42);


Compromise#2: the runtime representation

Another concern that has to be taken into account is about the runtime representation of an enhanced generic type. Before we go into further details here, let me explain the term specialization.

The process of creating different implementation of a certain type based on its generic characteristics is called specialization. Let’s take C++. There you have templates. C++ will generate a different class for each different template type. This is called heterogeneous translation. In Java and C# the situation is the opposite. These languages create one and the same runtime class for any type parameter. This is called homogeneous translation. With heterogeneous translation you are flexible in terms of combining parameter types: you can do things like <String+Integer> for example. But you are not allowed to do things like <? extends Number>, which as we know is perfectly fine in Java.

So, coming back to the proposed implementation topic. The homogeneous translation of generic types was possible in Java because of the erasure. However, primitive types cannot be erased. And this brings compromise number two: there will be a hybrid homogeneous-heterogeneous translation. This means that the reference types will continue to be erased and they will be translated as they used to be. While the primitive type parameters will be specialized: there will be a separate runtime class for every primitive generic type.

To illustrate this, let’s go back to the code from above:

Box<int> intBox = new Box<>(42);


Let’s take a look at the byte code that is emitted (java -p), or at least at the relevant parts of it:

0: new           #3                  // class "Box${0=I}"
6: invokespecial #4                  // Method "Box${0=I}"."<init>":(I)V
14: invokevirtual #6                  // Method "Box${0=I}".value:()I


You can easily notice that whenever the Box is parameterized with a primitive int, at runtime the class that is generated is not called just Box (as it would be called in case of erased Box), but Box${0=I}, where I stands for Integer. So the class name is augmented with specialization info to help the virtual machine generate the right runtime class.

Compromise#3: subtyping

In the generics as they exist today the following subtyping rules are valid: Box<Integer> extends Box<?>, which in turns extends the raw type Box. This does not apply for Box<int>, though. The reason is hiding again in the fact that there is no common type of reference and primitive types. So if we were to allow Box<int> to extend raw Box, then the former should have its value field of type Object. At the same time this field should be of type int, because that is how it was declared. As int and object don’t share common super type, this is not possible.

So the only subtyping relationship with primitive generics would be of the kind ArrayList<int> extends List<int>. And most unfortunate: List<int> cannot extend List<Integer> because of the transitive inheritance leading to the raw type.

Restrictions and special features

Let’s take again our Box<any T> class. Because the T type can be both primitive as well as reference, there are some restrictions for the things that you can do with it:

  • You cannot assign or even compare the value field of the Box class with null
  • It cannot be converted to Object or Object[]
  • You cannot synchronize or lock a block of code with it
  • It is not possible to convert Box<any T> to Box<?> or Box

At the same time, there are some features that are only available to the enhanced generics:

  • You can do things like new T[<size>] (it is not possible to do that with erased T). This will instantiate Object[] when T is reference type and the correct array in case of primitive type.
  • You can do comparisons with the instanceof operator
  • You can call Box<any T>.class

Generic methods

So far we’ve only discussed the implementation proposal for enhanced generic types. But what about enhanced generic methods? They are supported, so you can do things like:

<any T> void printValue(Box<T> box)

While it preserves the language syntax of the generic types, the internal representation is different. With enhance generic types it is possible to have specialization – different runtime type for the different generic parameter types. But this is not possible with methods (i.e. separate runtime method for the different method calls). This is because in that way the interface of the class will change – it would gain some more methods than declared. This is not so easy to achieve as most VM implementations are organized on the assumption that the number of methods for a given class is fixed.

That is why the enhanced generic methods take the same approach as the lambda expressions: invokedynamic. There will be a special bootstrap class (GenericMethodSpecializer), which will receive as arguments all the needed information in order to make the proper decision which special method to call.


In this second installment of the Primitives in Generics series we went quickly through the proposal coming from project Valhalla on how this feature will be implemented in Java. We saw what the proposed syntax will be and how will it be represented in the virtual machine. Then we discussed some of the restrictions introduced in subtyping and in the operations allowed with generic parameters. We also touched the topic of generic methods and how they differ in terms of internal representation.

In the final part of the series we’ll walk the migration path of existing JDK APIs and namely the most important of them all: the collections library.

February 5th, 2015

by Ivan St. Ivanov


Last week in the Bulgarian JUG we had an event dedicated on trying out the OpenJDK Valhalla project’s achievements in the area of using primitives parameters of generics. Our colleague and dedicated blogger Mihail Stoynov already wrote about our workshop. You can find very useful links in his post about the slides that I showed, the VM that he prepared (which you can use to try Valhalla yourself) and even the recording of the meeting (which unfortunately for some of you is in Bulgarian).

In this three-part series of blogs I would like to go in some more details about the current implementation proposal and the reasoning behind the decisions. No, I am not an expert in this matter. I just try to follow the project Valhalla mailing list as well as I read Brian Goetz’s State of Specialization document. So look at this series more as explaining the generics proposals in layman’s terms.


Java generics is one of its most widely commented topics. While the discussion whether they should be reified, i.e. the generic parameter information is not erased by javac, is arguably the hottest topic for years now, the lack of support for primitives as parameter types is something that at least causes some confusion. It leads to applying unnecessary boxing when for example you want to put an int into a List (read on to find out about the performance penalty). It also leads to adding “companion” classes in most of the generic APIs, like IntStream and LongStream for example.

One of the goals of OpenJDK’s project Valhalla is among others to research the possibility to generify over primitives in the language, the Virtual Machine and the standard libraries. Yes, it’s just research. Which means that the current proposal may or may not appear in the future versions of Java. What I am pretty sure is that it won’t make it to Java 9, which is about to be shipped next year.

The State of Generics

As already mentioned, it is not possible at the moment to define generic type or method parameterized with a primitive type. So if you want to create, let’s say,  a List of integers, you will have to consider using the wrapper class:

List<Integer> intList = new ArrayList<>();

Besides looking kind of artificial, this brings also huge performance penalty. It comes from the way reference types are layed out in memory. If we take the array list above, internally it is represented as an array (of Integer’s). Which means that we will get an array with references to Integer objects scattered in the heap. Looking at a single Integer object we need memory not only for the int itself but for all other things needed by the virtual machine: pointer to the class object, some space for the garbage collector flags, others for the object monitor used by the Java synchronization infrastructure, etc. So instead of beautifully ordered ints, we potentially get something like this:



The memory overhead is not the only issue here. The modern processor architectures rely on several layers of cache. This makes going to the main memory for fetching the value of a certain variable a very expensive operation in terms of CPU cycles. That is why most of the optimizations done by the JVM tend to put as much data in the registers as possible. But the problem is that when talking about arrays (remember, ArrayList is represented as an array), the CPU instructions can only cache contiguous memory addresses. Thus if our Integers are scattered around the heap, most probably our VM will not be able to put them in the registers and we’ll have to pay the performance penalty of the cache misses.

Why not generics over primitives?

Normal question here would be why doesn’t Java support generifying over primitive types. The short answer is: because of generic type erasure by javac. Slightly longer answer follows in the next few paragraphs.

Let’s suppose that we have the following class definition:

public class Box<T> {
    private T value;
    public Box(T value) {
        this.value = value;

    public T get() {
        return value;


The generic type T is only used by javac to ensure that correct types are boxed and then retrieved. If you decompile the product of the above class’s compilation, you will notice that the type of the value variable, the constructor parameter and the return type of the get() method are all java.lang.Object. Simply the compiler “erases” the information that you coded above and replaces it with the type that is the parent of all reference types. In Java there is no such thing as a common type of all types (both reference and primitive). Something like Any in Scala for example. That is why you cannot apply erasure to all types: with the current implementation javac doesn’t know to what they should be converted.

Why erasure at all?

Astute readers will ask the question: “But why we need this erasure anyway?” Before trying to answer it, let me first elaborate a bit on the compatibility topic.

Suppose that we have type A. And then we have a class C that uses or extends A. And class A is changed in some manner. We say that this change is source incompatible if the class C does not compile any more after this change (this is rather simplistic explanation, there are also a couple of other subtle causes of source incompatibilities, but let’s keep it simple). Some of you might remember when the enum keyword was added to the language in Java 5 – all the code that used that as identifier did not compile anymore. The same will be the fortune of all of you that use sun.misc.Unsafe BTW ;).

Next, suppose that we change somehow A and let’s say that both classes live in different jars. Class C may still compile after A’s change, however if you drop the hypothetical A.jar in the class path of our program, class C may refuse to link. This is considered as binary incompatibility. You may refer to the Java Language Specification for more information on that matter.

Going back to the generics story. If it was decided upon their introduction in Java 5 that the generic type is not going to be erased, then most likely it would break at least the binary compatibility of your classes. As generics were applied to the most widely used part of the API: the collection library, it would mean that virtually any meaningful Java program in this world would have to be at least recompiled on the day its users decided to upgrade to Java 5. The situation becomes even more complicated, because most of the libraries that we use in our program are developed and maintained by someone else. Which means that if one wanted to upgrade to Java 5, they would need to wait for all the external libraries to be recompiled with Java 5.

The bottom line is that non-erased generic type parameters would have brought a “flag day” when everybody should have recompiled and delivered a new version of their libraries. Which might be fine for smaller or more obedient language communities, but is not the case for Java.


So there are really compelling reasons why we are not able to generify our types and methods over primitive types. In the next installment of this series we’ll look at the current proposal in OpenJDK’s project Valhalla on how it can be implemented without breaking compatibility with older releases of Java.