Project Valhalla – Generic Specialization
Last week I wrote about value types, which are one of the new language features that are being investigated for a future version of Java. This time I’ll explain another possible new language feature being investigated in Project Valhalla: generic specialization.
In Java, you can only use reference types as generic type arguments. For example, you can’t have a List<int>. The purpose of generic specialization is to make it possible to use primitive types (and value types, when they are added to Java) as type arguments.
At first sight you might think: that’s simple, it’s just an extension of auto-boxing, just make List<int> an alias for List<Integer> (and vice versa for the other primitive types), but that would not be very satisfactory. A List<Integer> is a very inefficient way to store a list of integers, for the reasons that I mentioned in last week’s post about value types.
What you’d really want, is for example have an ArrayList<int> which is backed by an int instead of an Object containing Integer objects, avoiding the overhead of objects and auto-(un)boxing.
The people at Oracle have already been busy experimenting with generic specialization, and details about what it would mean and how it would are described in State of the Specialization – Proto Edition.
It will not be easy to add this to Java, mainly because of the strict requirements to maintain backward compatibility.
A lot of existing Java code assumes that a type parameter T is a reference type, for example by assigning null to variables of type T, or by calling methods defined in class Object on them such as hashCode() and toString(). This will not work anymore if T can be something else than a reference type. That’s already a big backward compatibility problem – however this new feature will be added to Java, existing generic classes won’t be able to automatically make use of it. Existing classes such as ArrayList will have to be modified in some way.
The assumption that type parameters are reference types has more consequences. For example, subtyping relations are not straightforward.
A List<Integer> is a subtype of List<?>, which is a subtype of the raw type List. Because of that we can write code like this:
List<?> list1 = new ArrayList<Integer>();
List list2 = new ArrayList<Integer>();
Object element = list2.get(0);
But the same relations will not be true for a List<int>.
// Error! An ArrayList<int> is not a List<?> nor a raw List
List<?> list1 = new ArrayList<int>();
List list2 = new ArrayList<int>();
// This should not be possible, list2 does not contain objects
Object element = list2.get(0);
Trouble with collections
There are also issues with the API of the collections interfaces and classes. For backward compatibility with pre-generics Java, there are some methods in the collections API that take an Object instead of a value of the type parameter E, for example in interface List the methods contains(Object o), indexOf(Object o), remove(Object o) and in interface Map the method get(Object key). In interface List it’s even worse, because remove is overloaded, there’s also a method remove(int index). Suppose that remove(Object o) would be replaced by remove(E element) (which would already be a change that breaks backward compatibility), then if E would be allowed to be int, it would be impossible for the compiler to choose between remove(int index) and remove(E element).
State of the Specialization goes into detail about how generic specialization might be implemented in Java at the byte code level and describes ideas for how it might be developed further. One interesting part is that it might give us a few bonus features:
- Instantiating arrays of a generic type: new T[size]. When T would be a primitive type, you’d get an array of the primitive type.
- Use of generic types in for example casts without getting an “unchecked cast” warning.
- Class literals of generic types, for example ArrayList<int>.class.
This would be an interesting feature to have in Java, and especially if value types will be added then this is the next logical feature to have (it would not be nice if you couldn’t easily make a List where the elements are of a value type).
As you can see it’s far from easy to add major new language features to Java, especially when it has to be done in a way that maintains backward compatibility.
 The Trove library provides specialized collection classes such as TIntArrayList, which is exactly like a regular ArrayList backed by an int.