State of the Specialization

July 2014: Infant Edition

Brian Goetz

This is an informal sketch of proposed enhancements to the Java Language (and secondarily, to the Java Virtual Machine) to support generics over primitives (and eventually value types). This is a very early draft, intended only to describe the overall goals and approach.

It has always been an irritant that one cannot generify over primitive types without boxing; with the addition of value types, as is proposed under a separate project, this restriction starts to become untenable.

Parametric polymorphism always entails a tradeoff between code footprint and specificity, and different languages have chosen different tradeoffs. At one end of the spectrum, C++ creates a specialized class for each instantiation of a template, and different specializations have no type system relationship with each other. At the other end, we have Java's current erased implementation which produces one class for all reference instantiations and no support for primitive instantiations. C# supports generics over both reference and struct types; it takes the approach of unifying the two in the bytecode, and generating one set of native code for all reference types, and a specialized representation for each instantiated struct type.

A separate tradeoff is the timing of specialization, which includes both the choice of ahead-of-time (as Scala does) or on-demand (as C# does), and for delayed specialization, whether the shared artifact produced by the compiler is generic (and therefore requires specialization for all cases, as C# does) or whether it is biased towards a specific instantiation pattern.

In these examples, we will illustrate speicialization of generics over primitives; these examples extend naturally to value types.

Example: a simple Box class

Suppose we have the following class:

class Box<T> {
    private final T t;

    public Box(T t) { this.t = t; }

    public T get() { return t; }
}

Compiling this class today yields the following bytecode:

class Box extends java.lang.Object{
private final java.lang.Object t;

public Box(java.lang.Object);
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   aload_0
   5:   aload_1
   6:   putfield    #2; //Field t:Ljava/lang/Object;
   9:   return

public java.lang.Object get();
  Code:
   0:   aload_0
   1:   getfield    #2; //Field t:Ljava/lang/Object;
   4:   areturn
}

A possible encoding

In this bytecode, some occurrences of Object really mean Object, and some are derived from the erasure of the type variable T. If we were to specialize this class for T=int, we would expect the signature of get() to return int. The following listing shows the same bytecode marked up to preserve erasure information, where a *T next to a type name or bytecode means that the type in the classfile is derived from the erasure of T, and therefore would need to be adjusted during specialization.

class Box extends java.lang.Object{
private final java.lang.Object*T t;

public Box(java.lang.Object*T);
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   aload_0
   5:   aload_1*T
   6:   putfield    #2; //Field t:Ljava/lang/Object*T;
   9:   return

public java.lang.Object* get();
  Code:
   0:   aload_0
   1:   getfield    #2; //Field t:Ljava/lang/Object*T;
   4:   areturn*T
}

When specializing for T=int, we would replace instances of Object*T with int, and replace a bytecodes with corresponding i ones. We could encode this in the bytecode with attributes that carry the "stars" in the previous example, mapping uses of type names or typed bytecodes to the type variable whose erasure they correspond to. Then, when specializing, replace the "starred" type names and bytecodes with the appropriate ones for the specialization, as follows:

class Box${T=int} extends java.lang.Object{
private final int t;

public Box${T=int}(int);
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   aload_0
   5:   iload_1
   6:   putfield    #2; //Field t:int;
   9:   return

public int get();
  Code:
   0:   aload_0
   1:   getfield    #2; //Field t:int;
   4:   ireturn
}

In order for on-demand specialization at runtime to be practical, specialization should ideally be entirely mechanical; we would prefer to not do any additional dataflow analysis or typechecking at runtime beyond existing verification. Accordingly, conversion metadata needs to be present in the classfile so that the specializer can be as simple as possible, and the resulting bytecode can then be verified as normal.

The approach illustrated here is biased towards the existing erased generics; the bytecode for Box.class is already erased and suitable for direct use with reference instantiations, and we add metadata that enable it to also be used as a template for runtime specialization of primitive instantiations. The approach suggested is one of many possible choices, where we mark bytecodes that need to be adapted from a* to i* (or other primitive or value type) and similarly mark components of field or method signatures that need to be adapted. These would likely take the form of attributes that point into the code attribute to identify which bytecodes need to be adjusted for each specializable type variable, and similarly attributes that annotate which components of field or method signatures in the constant pool need to be adjusted. This may ultimately take the form of new classfile attributes and/or new constant pool types.

Subtyping

For generics as they exist today, there is a subtyping relationship for instantiated generics:

ArrayList<Integer>  <:  ArrayList<?>
ArrayList<?>  <: ArrayList

(The latter occurrence of ArrayList is a raw type.) Since subtyping is transitive, we also have:

ArrayList<Integer> <: ArrayList

Initially, it might also seem sensible that ArrayList<int> could be a subtype of raw ArrayList. But this is not possible, because int is unrelated to any reference type. For example, consider the problem posed by fields. If Box<T> has a field t of type T, then the raw type has a field t of type Object. By the Liskov Substitution Principle, if Box<int> were a subtype of raw Box, then Box<int> would have to have a field t of type Object. But Box<int> has a field t of type int instead (and definitely doesn't want both). So Box<int> cannot be a subtype of raw Box. For the same reason, Box<int> cannot be a subtype of Box<Integer>.

Similarly, Box<int> cannot be a subtype of Box<Integer> or Box<?>, because if it were, transitivity would take us back to Box<int> <: Box. Without introducing a fictitious Any type that would pretend to be a supertype of both primitive and reference types (though could have no physical representation), we don't get a relationship between primitive-instantated generic types and wildcard (or raw) generic types. We do have:

ArrayList<int>  <:  List<int>

but not

ArrayList<int>  <:  ArrayList<Integer>
ArrayList<int>  <:  ArrayList<?>
ArrayList<int>  <:  ArrayList
List<int>  <:  List<Integer>
List<int>  <:  List<?>
List<int>  <:  List

Since generics are invariant, it is not surprising that List<int> is not a subtype of List<Integer>. The slightly surprising thing here is that a specialized type cannot interoperate with its raw counterpart. However, this is not a serious restriction; not only are raw types discouraged (having been introduced solely for the purpose of supporting a gradual migration from non-generic code to generic code), but it is still possible to write fully generic code using generic methods -- see "Generic Methods".

The example above depends on fields, suggesting that since interfaces have no fields, it might be possible for List<int> to still be a subtype of List<Integer>, by adding bridge methods to List<int> that bridged to the List<Integer> methods. However, this would require the addition of additional complexity in overload selection, since this would routinely generate methods which overloaded on return type (int get(K) vs Integer get(K).)

A more complicated example

For each specialization of a generic type (e.g., Box<int>), we need a means to name that specialized type in the classfile. For purposes of the next few sections of this document, assume that we will use a static naming convention like Box${T=int} (though we have no intention of expecting the VM to understand that a class named Box${T=int} has anything to do with specializing Box; from the VM's perspective, Box${T=int} is just a class.) Which means that the subtyping relationships like

ArrayList<int>  <:  List<int>

must turn into subclassing relationships of the form

ArrayList${T=int}  <:  List${T=int}

Getting this right can be tricky when a class extends another partially specialized class and then is further specialized. Consider:

class Pair<T,U> { 
    final T t;
    final U u;

    Pair(T t, U u) { this.t = t; this.u = u; }
}

class IntPair<U> extends Pair<int, U> { 
    IntPair(int t, U u) { super(t, u); }
}

class IntLongPair extends IntPair<long> { 
    IntLongPair(int t, long u) { super(t, u); }
}

In this example, we partially specialize Pair to IntPair, and then further specialize IntPair to IntLongPair, which indirectly extends Pair<int,long>. We need to ensure that the following subtyping relationships still hold:

IntLongPair <: IntPair<long>
IntLongPair <: Pair<int, long>

Classloading may be triggered by executing a new bytecode or by LDCing of a class literal. These may, in turn, trigger the loading of superclasses. To load IntLongPair, we first have to specialize IntPair, with U=long which in turn requires we specialize Pair with T=int. So first we get:

class Pair${T=int}<U> { 
    final int t;
    final U u;

    Pair(int t, U u) { this.t = t; this.u = u; }
}

Note that we must propagate any specialization metadata for the remaining unspecialized type variables (here, U) into the partially specialized class, since it may be further specialized. We can then load IntPair, which requires no adaptation other than rewriting its supertype:

class IntPair<U> extends Pair${T=int}<U> { 
    IntPair(int t, U u) { super(t, u); }
}

For the final step, we have to further specialize Pair${T=int} with U=long. However, we must do so carefully; as we respecialize the already specialized type IntPair, we have to rewrite its supertype as Pair${T=int,U=long}, otherwise we will not achieve the desired subtyping relationship at runtime. This yields:

class Pair${T=int,U=long} { 
    final int t;
    final long u;

    Pair(int t, long u) { this.t = t; this.u = u; }
}

class IntPair${U=long} extends Pair${T=int,U=long} { 
    IntPair(int t, long u) { super(t, u); }
}

class IntLongPair extends IntPair${U=long} { 
    IntLongPair(int t, long u) { super(t, u); }
}

and we obtain the desired subtypings

IntLongPair <: IntPair<long>
IntLongPair <: Pair<int,long>

While the examples here used a naming convention such as Pair${T=int} to represent a specialized type, nominal classes are somewhat unsatifying as a solution for specialization. An alternate, and far more flexible mechanism is outlined here, which uses a structured metadescription of the specialization desired. In any case, instantiating an object of specialized type would need to trigger the specialization of that class and any necessary superclasses.

Generic methods

Even though specialized generics cannot interoperate with raw types, it is still possible to write code that is fully generic across all possible instantiations of T with generic methods:

<T> void good(List<T> list) { ... }
void bad(List list) { .... }
...
List<int> list = new ArrayList<>();
good(list);  // good
bad(list);   // bad

When we invoke a generic method inferring a primitive or value type for a type parameter, we need to specialize a version of that method. Specializing generic methods is harder than specializing classes, because VM implementations are often organized around the assumption that the set of methods in a class is fixed.

There are several approaches we might take for implementing and invoking specialized generic methods. One approach would be to sidestep the problem using invokedynamic; another would be via a "method missing" approach.

For simplicity of exposition, we assume that injecting a new method into a class can be made a suitably cheap and safe operation, subject to suitable restrictions (i.e., static methods or private instance methods, so as not to perturb the layout of the vtable.)

To translate with invokedynamic, we could inject each specialization into the containing class as a static method, and invoke it using invokedynamic using a bootstrap that ensures that the target method is present, and if not, injects it, thereafter linking the call site to the appropriate invokestatic target. There are a few holes with this approach, the most significant being that some method bodies rely on instance context, such as for super calls. These can be handled as they currently are in lambda expressions, where a bridge method is created to perform instance-sensitive operations.

Alternately, the VM could provide a "method missing" handler, one which would allow the method to be invoked with invokevirtual but introduce an additional stage that allowed for programmatic linkage after the ordinary nominal linkage failed.

Key to either strategy is the observation that, for specialized invocations of generic methods, the specialized parameters will always be known at bytecode-generation time (which may be at compile time, as in the above example, or may be at specialization time for the case where one generic method calls another) and therefore the linkage can always be static. This is because none of the manipulations on types (e.g., T => ? extends T) can take as input a reference type and produce as output a value type, so the "value-reference footprint" (which type params are values and which are references) of the type parameters will always be statically known, as will the identities of any value-typed parameters.

The same observation is true for class type parameters that influence generic method parameters; at specialization time, their values will be statically known.

User control over specialization

The mechanical translation of a generic class into a specialized one is straightforward, but may be too limiting. We may wish to support a higher degree of user control. We see two possibilities of how this might be surfaced; wholesale replacement, and extension.

Wholesale replacement

One form of control might be to allow a completely hand-coded version for a particular specialization. For example:

class Generator<any T> { 
    T generate() { 
        // generic implementation
    }
}

class Generator<int> { 
    int generate() {
        // int-specific implementation
    }
}

In this way, the hand-written Generator<int> would "override" the auto-specialization for T=int. (For a concrete example, one might want to specialize ArrayList<boolean> using a BitSet as the backing store rather than a boolean[].)

Specializing the specializations

An alternate form of control would be to use the automated specialization, but to add (or override) specialization-specific method implementations. For example:

class List<T> { 
    void add(T t) { ... }
    T get(int index) { ... }

    // pay no attention to syntax
    <where T=int> int sum() { ... }
}

Here, while List<sum> has an auto-specialized implementation of add and get, it additionally has a method sum that is not a member of all lists.

Specializing generic methods

The "wholesale replacement" issue arises with generic methods as well as generic classes. For example, supposing you have a generic method:

<any T> void accept(T t) { ... }

It may be that for specific primitive or value types, you want to provide a different implementation:

void accept(T t) { /* int-specific implementation */ }

A syntactic indication may or may not be needed to identify that this is in fact a specialization of an existing generic method.

Specialization challenges

Certain patterns of usage are incompatible with specialization because they are tied to implicit assumptions about reference-ness of type variables.

Nonspecializable types

In order for a class to be specializable, the specialization metadata described above must be present (and verifiable) in the bytecode. Accordingly, legacy classfiles may not be specializable.

For compatibility purposes, it is unlikely that we would make specializability the default; instead, we'd likely require some sort of opt-in. This could be per-class or per-type-variable; we'll use the syntax any T as a place-holder for a specializable type variable.

Assumptions of reference-ness

The following idiom in classes like ArrayList would fail under specialization because it embodies the incorrect assumption that T[] and Object[] are related by subtyping:

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

These would have to be updated to use:

T[] array = new T[n];

and this construct would need to be given reasonable meaning (including adjustment of warning messages to preserve the guarantee of no-heap-pollution.)

Reference-primitive overloadings

Some overloadings that are valid today would become problematic under specialization. For example, these methods would have a problem if specialized with T=int:

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

These need to be resolved both on the specialization side (what methods to generate) and on the overload selection (which method to invoke.)

Incomplete generification

Classes like Collection also have methods that were incompletely generified. For example, the remove(T) method is really declared as remove(Object), but when the class is specialized, these methods should be specialized too. There would need to be a way to indicate "specialize me as if this type parameter were declared as T", likely with an annotation (e.g., @ICouldaBeenAGeneric).

Null

Another challenge with specialization is the use of null. Null is a valid value of every reference type, and is often used to represent "nothing is there." Primitive and value types, however, have no analogue of null. This is a challenge for methods like Map.get, which are defined to return null if the specified key cannot be found in the map.

When specializing a class, we need to either assign semantics to assignment to and comparison with null, or outlaw these usages (which may negatively impact specializability of some important classes, like HashMap.)

An unsatisfying option would be to treat assignment to null as an assignment to the zero value, which is the value that uninitialized fields and array elements are set to (zero for numeric types, false for boolean, etc), and comparison to null as comparing to the zero value. This treatment introduces ambiguities where one cannot distinguish between "no value" and "value equal to zero" (which has a perverse symmetry with the behavior of Map.get today, where a return value of null could mean "no mapping" or could mean "mapped to null".)

The "Peeling" Technique

The specialization challenges listed above are not theoretical; they show up in the core Collection classes. A possible way out is via peeling a generic class into a generic layer and a "specialized to erased reference type" layer, which builds on the "specialize the specializations" feature.

Invalid overloads

Consider the overload pair in a List-like class:

interface ListLike<T> {
    public void remove(int position);
    public void remove(T element);
}

Existing uses of ListLike will all involve reference instantiations, since those are the only instantiations currently allowed in a pre-specialized world. Note that while compatibility requires that reference instantiations have both of these methods, it requires nothing of non-reference instantiations (since none currently exist.)

The intuition behind peeling is to observe that, while we're used to thinking of the existing ListLike as the generic type, that it might really be the union of a type that is generic across all instantiations, and a type that is generic across only reference instantations.

If we were writing this class from scratch in a post-specialization world, we might have written it as:

interface ListLike<T> {
    void removeByIndex(int position);
    void removeByValue(T element);
}

But, such a change now would not be either source-compatible or binary-compatible. However, peeling allows us to add these methods to the generic layer, and implement them in a reference-specific layer, without requiring them in the specializations, restoring compatibility:

interface ListLike<T> {
    // New methods added to the generic layer
    void removeByValue(T element);
    void removeByIndex(int pos);

    // Abstract methods that exist only in the reference layer
    <where reference T>
    void remove(int pos);

    <where reference T>
    void remove(T element);

    // Default implementations of the new generic methods
    <where reference T>
    default void removeByIndex(int pos) { remove(pos); }

    <where reference T>
    default void removeByValue(T t) { remove(t); }
}

Now, reference instantiations have remove(T), and remove(int) (as well as the new methods removeByIndex and removeByValue), ensuring compatibility, and specializations have the nonproblematic overloads of removeByValue(T) and removeByIndex(int). Existing implementations of ListLike would continue to compile since the new methods have a default implementation for reference specializations (which simply bridges to the existing remove methods). For primitive specializations, removeByIndex and removeByValue are seen as abstract and must be provided, but remove does not exist at all.

Use of null

This same approach works for the problematic method Map.get, eliminating the problem with nullable results in the API for primitive-specialized types: we simply move the existing Map.get into the reference specialization, and steer primitive users towards the (added in Java 8) getOrDefault method:

interface Map<K,V> { 
    // Generic
    V getOrDefault(K key, V defaultValue);

    // Abstract method for reference specializations
    <where reference V>
    V get(K key);

    // Default for reference specializations
    <where reference V>
    default V getOrDefault(K key, V defaultValue) {
        return containsKey(key) ? get(key) : defaultValue;
    }
}