State of the Values

April 2014: Infant Edition

John Rose, Brian Goetz, and Guy Steele

“Codes like a class, works like an int!”

This is a sketch of proposed enhancements to the Java Virtual Machine instruction set, and secondarily to the Java Language, to support small immutable, identityless value types. (They may also be considered as identityless aggregates, user-defined primitives, immutable records, or restricted classes.) This is an early draft, intended to describe the overall approach. Readers are expected to be familiar with the JVM bytecode instruction set.

Background

The Java VM type system offers two ways to create aggregate data types: heterogeneous aggregates with identity (classes), and homogeneous aggregates with identity (arrays). The only types that do not have identity are the eight hardwired primitive types: byte, short, int, long, float, double, char, and boolean. Object identity has footprint and performance costs, which is a major reason Java, unlike other many object oriented languages, has primitives. These costs are most burdensome for small objects, which do not have many fields to amortize the extra costs.

More detail: In terms of footprint, objects with identity are heap-allocated, have object headers of one or two words, and (unless dead) have one or more pointers pointing at them. In terms of performance, each distinct aggregate value must be allocated on the heap and each access requires a dependent load (pointer traversal) to get to the “payload”, even if it is just a single field (as with java.lang.Integer). Also, the object header supports numerous operations including Object.getClass, Object.wait, and System.identityHashCode; these require elaborate support.

Object identity serves only to support mutability, where an object’s state can be mutated but remains the same intrinsic object. But many programming idioms do not require identity, and would benefit from not paying the memory footprint, locality, and optimization penalties of identity. Despite significant attempts, JVMs are still poor at figuring out whether an object’s identity is significant to the program, and so must pessimistically support identity for many objects that don’t need it.

More detail: Even a nominally stateless object (with all final fields) must have its identity tracked at all times, even in highly optimized code, lest someone suddenly use it as a means of synchronization. This inherent “statefulness” impedes many optimizations. Escape analysis techniques can sometimes mitigate some of these costs, but they are fragile in the face of code complexity, and break down almost completely with separate compilation. The root problem is identity.

Running example: Point

Consider a Point class:

final class Point {
    public final int x;
    public final int y;

    public Point(int x, int y) { 
        this.x = x;
        this.y = y;
    }
}

Even though Point is immutable, the JVM doesn’t usually know that you have no intention of using its identity (for example, casting one to Object and using it as an intrinsic lock), and hence represents Point as a “box” object for x and y. An array of Point objects requires an extra object header (8 to 16 bytes) and a reference (4 to 8 bytes), meaning those 8 bytes of data take up 20 to 32 bytes of heap space, and iterating this array means a pointer dereference for every Point visited, destroying the inherent locality of arrays and limiting program performance. (Plus, allocation entails work for the garbage collector.) Programmers often resort to tricks like representing an array of points as two arrays of ints to avoid these costs, but this sacrifices encapsulation (and maintainability) just to reclaim the performance lost to identity. If, on the other hand, we could represent a Point in the same manner we do an int, we could store them in registers, push them on the stack, iterate through an array with locality, and use far less memory, with no loss of encapsulation.

Thesis

The goal of this effort is to explore how small immutable user-defined aggregate types without identity can be surfaced in the language and the JVM instruction set to support memory- and locality-efficient programming idioms without sacrificing encapsulation.

We believe that the design of the Java VM and language can be gently extended with a new kind of type, a value type, which usefully combines the properties of Java’s current classes and primitive types.

We expect to borrow most of the definition and encapsulation machinery from classes, allowing users to easily and safely build new value-based data structures. In particular, we believe that it is useful, both at the JVM and language levels, to regard value type definitions as specially marked, specially restricted class definitions.

At the same time, users of value types will be free to treat them as if they were simply a new kind of primitive type.

If we succeed, the user experince with value types can be summed up as, “Codes like a class, works like an int!”

As will be seen below, we also believe that, while the value types are usefully similar to classes, it is useful (as with primitives) to make clear and systematic distinctions between a value type and a reference type, at the operational level of bytecodes.

We will touch on how these features might be surfaced in the Java Language, but this is a secondary concern for the time being. (The interplay of value types and generics is an area of great interest, but will be treated as a separate exploration.) Earlier explorations of the ideas contained herein include Value Types in the VM and Tuples in the VM. This has been a long-running design problem for Java, as may be seen in James Gosling’s call for “efficient classes”.

Use cases

Thorough integration of values into the JVM can support a number of language features which may be desirable additions to the Java language, or features already implemented suboptimally by other JVM languages. Some examples include:

Requirements

An efficient value-type facility at the JVM level should offer the following beneficial characteristics:

Since values do not have identity, there are certain operations that are identity-specific and either need to be disallowed on values or assigned a new meaning for use in the context of values.

Many of the above restrictions correspond to the restrictions on so-called value-based classes. In fact, it seems likely that the boxed form of every value type will be a value-based class.

A “soft” restriction on values is that they are “not too large”. Values with tens of components, though legal, are not the design center of this proposal. Since values are passed, well, by value, the overhead of copying many components is increasingly likely to overwhelm any savings obtained by removing the overhead of a pointer and an object header, as the number of components grows. Large groups of component values should usually be modeled as plain classes, since they can be passed around under single pointers.

Put positively, a well-conceived use of a value type gets a performance and complexity win by omitting the object pointer and header, and routinely passing the components by value. A value type with a small number of components will neatly match the capabilities of present CPUs, which have relatively small limits on the size of their register file. When those limits are passed, the JVM will also have flexibility to spill values onto stack stack and/or managed heap memory.

Life without pointers

Also a value does not have its own pointer, or a least such a pointer is a secret inside the VM’s implementation. Therefore there are certain additional operations that also either need to be disallowed or assigned a new meaning.

General approach: definition

We’ve already identified several requirements of value types that are common with classes: a collection of named, type components (fields), behavior (methods), privacy (access control), programmatic initialization (constructors), etc. It makes sense, therefore, to use existing elements of classfiles to the extent possible to describe value types, with additional metadata as needed. Similarly, it makes sense to re-use syntactic elements from classes in the source language.

We have good precedent for taking this approach, since interfaces are closely similar to classes. Apart from some mode bits and minor syntax, the binary of an interface is identical to that of a proper class, except that interfaces have additional syntactic and semantic restrictions. The same point applies to the source language.

Using a strawman syntax (please, no comments on syntax!), we could express our Point example as a value as follows:

final __ByValue class Point {
    public final int x;
    public final int y;

    public Point(int x, int y) { 
        this.x = x;
        this.y = y;
    }

    public boolean equals(Point that) {
        return this.x == that.x && this.y == that.y;
    }
}

The syntactic difference between this and its reference equivalent start with the keyword __ByValue marking the class. (This syntax is a placeholder only; the key point being illustrated here is that we intend to reuse many coding idioms from classes, where appropriate, to describe values, such as fields, constructors, and methods.) Both the whole class and the individual fields x and y are required to be final. Other relevant restrictions are enforced as well (e.g., no use of value-sensitive operations). We presume the compiler or VM would fill in an appropriately specified componentwise hashCode, equals, and toString method, if the user does not provide one (and the language allows this omission).

If another class declared a field of type Point, the VM would allocate storage for the x and y components in the hosting class, rather than a reference to a Point box. (This can be viewed as object inlining or flattening.) Similarly, an array of Points would be laid out as a packed array of alternating x and y values, rather than a series of references.

As you can see, this clearly “codes like a class”. In fact, except for the funny annotation-like keyword, the meaning of this definition is immediately clear to any Java coder.

What are the pitfalls for the coder of this class? It appears that they are mainly due to the restrictions the user agrees to in exchange for getting “by value” semantics. For example, it is unlikely that the keywords “extends” or “protected” will be accepted in a value type definition.

The language already has sufficient power to express some of the necessary restrictions, such as the immutability of subfields after construction or the inability. If the user leaves off a “final” keyword, the compiler will explain that it is necessary.

Alternate route: We could also, as with interfaces and closures, switch the defaults and silently add the “final” keywords where required. This seems like an easy win for brevity, but since clarity is more important than brevity, and since all asymmetries between normal classes and value types will create surprises, we wish to be cautiously sparing with symmetry-breaking. Also, switching the defaults would make it hard to loosen restrictions later on, if that should prove desirable. Eliding the Object methods is not so surprising, and is likely to be permitted, since system-supplied defaults are expected here.

General approach: usage

The next question is, how does it “work like an int”? Here are some simple uses of our Point class:

static Point origin = __MakeValue(0, 0);
static String stringValueOf(Point p) {
    return "Point("+p.x+","+p.y+")";
}
static Point displace(Point p, int dx, int dy) {
    if (dx == 0 && dy == 0)
      return p;
    Point p2 = __MakeValue(p.x + dx, p.y + dy);
    assert(!p.equals(p2));
    return p2;
}

Either of these methods would work well as members of Point itself. In these examples, a point can be a field, argument, local variable, or return value. In all those cases, the JVM is likely to place the components of the point into independently managed locations, such as machine registers. Note that displace returns a new point value, which the JVM is likely to return by value and not by (invisible) reference.

Like primitives, value type can guide overloading. Here are some more overloads for stringValueOf which are compatible with the above:

static String stringValueOf(int i) {
    return Integer.valueOf(i);
}
static String stringValueOf(Object x) {
    return x.toString();
}

How do these usages differ from a plain int? First of all, the dot syntax for member selection applies to value types, as with p.x or p.equals. Primitives do not support the dot syntax at all. (It is possible that the value/box duality gives us a foot in the door for applying methods on primitives, by defining methods on pseudo-types int, float, etc. Many of the methods of wrappers like Integer would be candidates for such treatment.)

Second, there are no literals for Point. Instead, the constructor of the definition must be invoked. Encapsulation demands that component-wise value creation must not be possible unless provided for by a suitable constructor. We use a place-holder keyword __MakeValue to mark the two places above where new point values are created. (Some possible spellings for the keyword are “new Point”, “Point”, and the null string. Some ongoing design efforts for quasi-literal expressions apply here also, but are beyond the scope of this proposal. It seems plausible that omitting “new” would be a tasteful way to express the presence of a non-heap value.)

Just as there are no literals, there is no concept of compile-time constant for values. This might not seem urgent for Point, but will likely be felt as a burden when programmers use value types for unsigned numbers or other very simple quantities.

Alternate route: In principle, Java could adapt some features from other languages to support user definition of literals and constant expressions. Difficulties would include adapting the design to “feel like Java” (in simplicity, class orientation, and separate compilation), and clearly defining how to run user code at compile time (to execute constant-creating constructors and methods).

Third, Java’s built-in operators, which are the main way of working with primitives, do not apply to Points. Plausible exceptions might be those operators which work on every kind of value, namely the relationals (== and !=) and string concatenation (+).

String concatenation is dangerous ground, since it is subtly overloaded precisely at the distinction between classes and primitives, which is where value types live. (As most every Java programmer has found by trial and error, the expressions ("a"+1)+2 and "a"+(1+2) differ in a tricky way.)

Alternate route: It is wise to leave space here for true numeric addition, depending on where the story with numerics and operators goes in the future. Likewise, cursor types might work better with for-loops if operators like j < k and j++ were supported, but this again depends on both the future story with operators and with possible enhancements to for-loops themselves. A final observation: user-defined operators also seem to require compile-time code execution to build constant expressions. But we do not propose to solve all this in one step.

The simple relationals probably pass muster as aliases for the equals method, by analogy with other primitives. (Low-level bitwise equality seems to be another candidate, departing from the operator’s behavior of float and double, but that would break abstraction.) The major objection to these operators is that they can potentially lead to behavior divergences between the boxed and unboxed form of a value, as follows:

Point p1 = __MakeValue(0, 1);
Point p2 = __MakeValue(1, 0);
Point p3 = __MakeValue(1, 0);
assert(!p1.equals(p2));  // value equality
assert(p1 != p2);  // value equality, again
assert(p2.equals(p3) && p2 == p3);
Object box1 = p1, box2 = p2, box3 = p3;  // box 'em
assert(box1 == box1);  // x==x always (except NaNs)
assert(!box1.equals(box2)); // Object.equals calls Point.equals
assert(box1 != box2);  // must also be
assert(box2.equals(box3));
if (box2 == box3)  println("the cat died");  // indeterminate
assert((Point)box2 == (Point)box3);  // back to Point.equals
if (box2 == (Object)p2)  println("the cat died");  // indeterminate

With minor adjustments, all the above tests can be reproduced with int and Integer. (For some small integer values, the cat never survives, but this is a peculiarity of the Integer.valueOf factory method, rather than an inherent feature of primitives, values, or boxes.)

A fourth aspect of primitives is that, although they do not have values that correspond to the null reference, they do have default values, generally some sort of zero. This default value shows up in the initial contents of uninitialized fields and array elements. It is therefore necessary to specify a default value for each value type. The simplest default composite value is the one which which is recursively default in all of its subfields. Given that predefined default values are a fixture in Java, this convention does not appear harmful, so we will adopt it.

As a result, the author of methods in a value type definition will need provide behavior to default (all-zero-bits) values, even if the constructors never create them, since they can be observed in some uninitialized variables. It is likely that we will either forbid no-argument constructors or require them to produce default values, to avoid “duelling defaults”.

Alternate route: We could force the explicit construction of default values by mandating the inclusion of a public null constructor, like this: public Point() { x = 0; y = 0; } All sub-fields would be initialized to default values, or the compiler and verifier would report an error. This amount of required boilerplate feels like overkill, even though it is logically similar to requiring the final keyword in various places. It would also prevent null constructors from being used for other purposes. It it more likely that we will disallow null constructors, and reserve their meaning for default values.

Alternate route: A more elaborate default could be specified through some pattern or syntax imposed on standard class definitions, but there are three objections to this: It requires an special extension rather than a simple restriction. It also requires special rules to cope with side effects from the null constructor. Finally, applying user-specified defaults at runtime is much more costly than a convention of all-zero-bits; it would not be a shallow change to the JVM.

Details, details

Our mantra is “codes like a class, works like an int.” Of course, the devil is in the details; there are going to be features of classes that do not make sense for value types. Some questions we might want to ask about value classes are as follows, with tentative answers where appropriate. Where a comparison with primitives would make sense, the answers for these questions for values are the same as they would be for primitives.

The decision to limit or prohibit subclassing and subtyping of value types is necessary to avoid pointer polymorphism. Abstract super types (like the interface Comparable) are only considered because they cannot be instantiated.

We can therefore ensure that all methods are resolved unambiguously in the exact type of the method receiver. Invoking a value method is always like invokestatic or invokespecial and never like invokevirtual or invokeinterface.

This decision also sidesteps a problem with arrays of values, which would seem to require variable-sized elements if an array could contain (say) both 2-field Point and 3-field ColoredPoint values. For arrays, it is convenient to lean on “works like an int”, since primitive arrays already have completely homogeneous elements. This is not a perfect story. For example, if we have a value type Bignum that implements Comparable (see example below) we will allow an array of boxes Bignum.__BoxedValue[] to be a subtype of the interface array Comparable[], but the flat array type Bignum[] cannot also be a subtype of Comparable[].

New bytecodes and type descriptors

In determining how to surface value types in the bytecode instruction set, there are two extremes: add all-new bytecodes for values, treating values as an entirely new thing, or overload existing bytecodes to accept either values or references. While the final answer will almost certainly be somewhere in the middle, for purposes of exposition and analysis we will initially err on the side of the first choice, for explicitness and simplicity. At worst, we anticipate fewer than a dozen new bytecodes will be needed, and one new form of type descriptor.

Currently, there are single-letter type descriptors for primitives (e.g., I for int), “L” descriptors for classes (e.g., Ljava/lang/Object;), and for any type descriptor, one can derive the type descriptor for an array of that type by prepending a [. We add one more form, for value types; the type descriptor for a value type com.foo.Bar would be Qcom/foo/Bar;, which is just like the “L” descriptor, except with a “Q”. (Perhaps it stands for “quantity”; “V” already means void.) For example, if we had the following method:

public static double getR(Point p) { ... }

its signature would be (QPoint;)D, indicating it took a single argument of value type Point.

New bytecodes are described in the following format:

// Description
opcode [ constant pool operands ] stack operands -> stack result

For all opcodes, a “qdesc” is a Q-descriptor for a value type; for most bytecodes, it seems possible for the verifier to infer the descriptor and hence omit it from the bytecode. Local variable table slots and stack slots can hold values as well as primitives or references.

For simplicity and better binary compatibility, we define (unlike with longs and doubles) that values always consume a single slot in the local variable array. As with classes, we want values to be able to change size and layout without recompiling clients.

We posit the following bytecodes for manipulating values on the stack. Again, while some of the forms here are arguably unnecessary, we err on the side of explicitness and completeness, minimizing the number of new bytecodes can come later.

// Load value from local variable
vload [ qdesc?, index ] -> value

// Store value into local variable
vstore [ qdesc?, index ] value -> 

// Create new array of value types
vnewarray [ qdesc ] size -> arrayref

// Store value into array
vastore [ qdesc? ] arrayref, index, value -> 

// Load value from array
vaload [ qdesc? ] arrayref, index -> value

// Extract a component from a value
vgetfield [ field-desc ] value -> result

// Insert a component into a value (for private use by constructors)
vputfield [ field-desc ] value argument -> value

// Construct a fresh value with all default components (for use by constructors)
vnew [ qdesc ] -> value

// Invoke a method on a value
vinvoke [ method-desc ] value, (argument)* -> (return)?

// Return a value
vreturn [ qdesc? ] value

Additionally, there are a number of “polymorphic” bytecodes, such as dup, that can operate on stack contents of any type; these would be extended to support values as well.

Many of these could be overloaded onto existing bytecodes with little discomfort. For example, the vinvoke functionality could be overloaded onto invokestatic; the vgetfield functionality could be overloaded onto getfield. Again, for clarity of design we refrain from doing such overloadings, at least at this point.

The field and method descriptors referred to above would be constant pool references of type CONSTANT_Methodref and CONSTANT_Fieldref. The CONSTANT_Class components of the descriptors would refer to the value types by their normal names (without any “Q” prefix). The boxed forms of the class would have their own bytecode name, perhaps derived from the descriptor language (e.g., .LFoo;).

Alternate route: We may wish to continue the pattern of opcode cloning by also cloning the constant pool types, as CONSTANT_ValueMethodref, etc. But we do not yet see a reason to force us to do this.

Static methods in values do not need special opcodes; they will continue to be invoked by invokestatic, and similarly for static fields in values.

Constructor invocation will not pass in the value to be constructed by reference (since that is defined to be impossible). Instead, value type constructors will be static factory methods which will be invoked by invokestatic. Individual mutation steps for component initialization are represented, internally to the constructor, by use of the privileged instruction vputfield, which operates equivalently to the special putfield that initializes an normal all-final object. Note that vputfield returns the updated value; there is no side effect.

Alternate route: We could combine the effects of the vnew and vputfield operators, as used by constructors, into a vpack instruction, which would take a series of components on the stack. The order and type of those components would be implicitly defined by the containing value class. Although this would make some simple constructors slightly more compact, it would introduce a new kind of coupling between an instruction and its containing class. It seems simpler to mimic the other instructions which operate on JVM composites as clusters of named fields, rather than on ordered tuples of stacked values. The correspondence between bytecode and source code is also simpler to track, if each field initialization has its own vputfield opcode.

Boxing and object interoperability

Every value type has a corresponding box type, just as Integer is the box type for int. Rather than having a separate source and classfile artifact and tracking their association, the box type for value types is automatically derived from the classfile for the value type. If the value type is described in the bytecode as QFoo;, the corresponding box type is described as LFoo;. For both types, the VM will know to look for a classfile called Foo and generate a value- or reference- view of that class.

Since many common operations, such as construction, will have different mechanics for value or reference classes, either the static compiler will generate multiple versions of class artifacts (e.g., a standard constructor with signature (...)V and a value constructor with signature (...)QFoo;) or the VM will derive one from the bytecode of the other as needed.

For sake of exposition, for a value class Foo, we’ll write Foo to refer to the value form and Foo.__BoxedValue to refer to the boxed form of Foo. (Explicit naming of the box type will rarely be needed, as autoboxing should take care of most value-reference interactions. Note that we are not speculating on syntax here.)

The conversions between the boxed and unboxed representations of value types might be represented by methods following a naming convention, as they are with the current primitive boxes (e.g., valueOf(boxed)) or might be represented by conversion bytecodes like these:

// Box a value
v2a [qdesc] value -> ref

// Unbox a value
a2v [qdesc] ref -> value

Comparisons between values (analogous to acmp and icmp bytecodes) might also be represented by methods following a naming convention, or with special bytecodes like these:

// Compare two values using componentwise, bitwise and reference equality
vcmp [ qdesc? ] value, value -> boolean

(In examples below we will use patterned method names, to show another possibility.)

Although we find it useful for design purposes to contemplate the “cloning” of new value bytecodes like those which manipulate primitives and references, the conversion and comparison bytecodes are likely to work best as simple method calls (using vinvoke).

Box types, like array types, are generated by the system, so they have a “magic” feel to them. Our intention is to make them as un-magic as possible. One way to do this is to factor box code, as much as possible, into a common abstract superclass. This is approximately the approach taken for classic objects, where the default behaviors are found in java.lang.Object.

Now we have enough structure to work some examples.

Example: construction

For objects, objects are initialized by first executing a new bytecode (which creates an uninitialized object), and then invoking the constructor (using dup and invokespecial.) Constructors for values behave more like factory methods. The following shows the bytecode generated for Point’s constructor:

final __ByValue class Point {
    public final int x;
    public final int y;

    public Point(int x1, int y1) { 
            ; public static <new>(II)QPoint;
        //implicit: initialize 'this' to all-zero-bits
            ; vnew           // stack holds [ this ]
        this.x = x1;
            ; iload 0 ('x1') // stack holds [ this x1 ]
            ; vputfield 'x'  // stack holds [ this ]
        this.y = y1;
            ; iload 1 ('y1') // stack holds [ this, y1 ]
            ; vputfield 'y'  // stack holds [ this ]
        //implicit: return 'this'
            ; vreturn
    }
}

To create an instance of a Point in a local variable, the factory method is invoked, and the result stored in the local:

Point p = new Point(1, 2);
    ; iconst_1
    ; iconst_2
    ; invokestatic "Point.<new>(II)QPoint;
    ; vstore 6 (create 'p')

Note that invokespecial is not relevant here, since the factory method does not take a pointer to an uninitialized value as its implicit first argument. To simplify exposition, we have changed the name of the constructor of a value type to <new>, to emphasize that it is a factory method.

Example: nested values

final __ByValue class Path {
    final Point start;
    final Point end;
}

class Foo {        // regular class
    Path path;     // regular field
}

int startX = path.start.x;
    ; aload 0 ('this')       // stack holds [ Foo ]
    ; getfield Foo.path      // stack holds [ path ]
    ; vgetfield Path.start   // stack holds [ start ]
    ; vgetfield Point.x      // stack holds [ x ]
    ; istore 1               // stack holds [ ]

Note that when a nested value is read, its enclosing values are always read first.

Example: arrays

Arrays are created with the vnewarray bytecode, and manipulated much like any other array type.

Point[] points = new Point[100];
    ; bipush 100
    ; vnewarray Point
    ; astore 1 (create 'points')
points[3] = new Point(2, 19);
    ; aload 1 ('points')
    ; iconst_3
    ; iconst_2
    ; bipush 19
    ; invokestatic "Point.<new>(II)QPoint;
    ; vastore

Example: method invocation

All methods on value types are resolved statically. The invokestatic instruction would be sufficient (as a bytecode syntax) for invoking both static and non-static methods of a value type, but for clarity of exposition we will use a new invocation instruction vinvoke for non-static methods of value types.

class Point {
    public final int x;
    public final int y;

    public double getR() { 
        double dx = x, dy = y;
        return sqrt(dx*dx + dy*dy);
    }
}

Point p = ...
    ; vstore 1 
double r = p.getR();
    ; vload 1
    ; vinvoke Point.getR()D
    ; dstore 2

Example: boxing

When a value is assigned a variable of type Object, its box type, or an interface type which it implements, it should be autoboxed by the compiler. For example:

Object[] array = ...
Point p = ...
array[1] = p;
    ; aload 1    // array
    ; iconst_1   // index
    ; vload 2    // p
    ; vinvoke Point.<v2a>()LPoint;  // box p 
    ; aastore
Point p = ...
    ; vstore 1 
Point.__BoxedValue bp = p;  // descriptor LPoint; not QPoint;
    ; vload 1
    ; vinvoke Point.<v2a>()LPoint;  // box p 
    ; astore 99  // continued below...

Example: unboxing

When a value is assigned from a variable of type Object, its box type, or an interface type which it implements, the reference is first checked to see if it is the corresponding box type, and then the value is unboxed:

Object[] array = ...
Point p = (Point) array[1];
    ; aload 1    // array
    ; iconst_1   // index
    ; aaload
    ; checkcast LPoint;
    ; invokevirtual Point.<a2v>()QPoint;  // unbox array[1]
    ; vstore 2   // p
Point p2 = bp;
    ; aload 99   // bp; see above
    ; invokevirtual Point.<a2v>()QPoint;  // unbox bp
    ; astore 5

A boxed reference can have value methods invoked directly on it:

double r = bp.getR();
    ; aload 99   // bp; see above
    ; invokevirtual Point.getR()D
    ; dstore 3

Example: flattened hash table

Because value types are pointer-free, they can be used to flatten some data structures by removing levels of indirection. Flattening not only removes dependent loads from critical paths, but also (typically) moves related data onto the same cache line.

Ideally, a well-tuned resizable hash table should be able to answer a query in not much more than two cache line references, one reference to consult the table header about table size, and one reference to probe an entry in the table. This ideal can be achieved if the table entries are flattened within the data array carrying the table, and this becomes possible with the help of value types.

class ToStringIntHashMap {
  private static final __AlwaysAtomic __ByValue class Entry {
    final int key;
    final String value;
  }
  private Entry[] table;
  private Entry getEntry(int k1) {
    int idx = hash(k1) & (table.length-1);
    Entry e1 = table[idx];
        ; aload_0           // this
        ; getfield table    // this.table
        ; iload_2           // idx
        ; vaload            // table[idx]
        ; vstore_3          // e1
    int k2 = e1.key;
        ; vload_3
        ; vgetfield key     // e1.key
        ; istore_4          // k2
    if (k1 == k2)  return e1;
    {... else slow path ...}
  }
}

The above code actually touches three cache lines, in order to extract an array length from the array header. Fixing that requires hoisting the array length up into hash table header, which is an interesting exercise in array design, but beyond the scope of this proposal.

More detail: The above code sidles around the problem of distinguishing a default-valued entry (zero hash, null string reference) from a failure to find an entry. This is a typical issue in adapting pointer-oriented algorithms (in Java) to values. It could be patched in a number of ways. The simplest is probably to introduce a value which expresses an optional Entry (entry plus boolean), and return that from getEntry. Note that the ability to make an default (null) Entry value might be useful here, at the end of the slow path for getEntry. Default values are part of the Java’s landscape for reasons given above, and we might wish to embrace them to get more use out of them.

The effect of __AlwaysAtomic here is to ensure that array elements values are read consistently, without internal races. Without that modification, on some platforms, struct tearing might lead to states where a value might be associated with the wrong key. This hazard comes from flattening; it is not present in the “pointer rich” version of the data structure.

Happily, most platforms will be able to implement atomicity for this data structure without extra cost, by means of 64-bit memory references. This assumes that the value component can be packed into 32 bits, which is usually the case.

More detail: More generally, even a value of four components is likely to fit into 128 bits, and most hardware platforms can provide atomic 128-bit reads and writes, at a reasonable cost. After those options run out, there are others, but this proposal does not attempt to make a deep review of the implementation options. For larger values, say with five or more components, the costs for atomicity will go up sharply, which is why atomicity is not the default.

Alternate route: General data structure layout control, of the type found in C and C#, does not appear to mesh well with Java’s data model, but does show up when Java code needs to interoperate with native data structures. It is therefore a direct goal for Project Panama, which is seeking to expand Java’s native interconnection capabilities.

Note that this example data structure is “hardwired” to work on ints and Strings. A corresponding generic class would gain some benefits from the flattened array, but could not work directly on unboxed ints. A template-like mechanism to parameterize over non-references would apply nicely to this example, but such a proposal is out of scope here.

Example: comparison

As noted above, it is useful for values to implement interfaces. Here is an example of a value which supports comparison:

final __ByValue class Bignum implements Comparable<Bignum> {
  private final int intValue;
  private final BigInteger bigValue;
  public Bignum(int n) { intValue = n; bigValue = null; }
  public Bignum(BigInteger n) {
    if (fitsIn32(n)) { bigValue = null; intValue = n.intValue(); }
    else             { intValue = 0;    bigValue = n; }
  }
  public int compareTo(Bignum that) {...usual stuff...}
}

The automatically created box class will properly implement the interface, bridging to the given compareTo method. A vinvoke instruction can also directly invoke the compareTo method as written.

Here are some examples of calls to the interface function.

Bignum bn1 = __MakeValue(24), bn2 = __MakeValue(42);
    ; bipush 24
    ; invokestatic Bignum.<new>(I)QBignum;
    ; vstore_1          // bn1
    ; bipush 42
    ; invokestatic Bignum.<new>(I)QBignum;
    ; vstore_2          // bn2
int res = bn1.compareTo(bn2);
    ; vload_1           // bn1
    ; vload_2           // bn2
    ; vinvoke Bignum.compareTo(QBignum;)I
    ; istore_3          // res
Comparable box = bn1;
    ; vload_1           // bn1
    ; vinvoke Bignum.<v2a>()LBignum;
    ; astore_4          // box
res = box.compareTo(bn2);
    ; aload_4           // box
    ; vload_2           // bn2
    ; vinvoke Bignum.<v2a>()LBignum;
    ; invokeinterface Comparable.compareTo(Ljava/lang/Object;)I
    ; istore_3          // res
res = bn1.compareTo((Bignum)box);
    ; vload_1           // bn1
    ; aload_4           // box
    ; checkcast Bignum.__BoxedValue
    ; invokevirtual Bignum.<a2v>()QBignum;  // unbox
    ; vinvoke Bignum.compareTo(QBignum;)I
    ; istore_3          // res

As with classes, there is often an option to make a direct, non-interface call (vinvoke in this case) to the method which implements the interface.

Note that the interface takes an erased Object parameter, as required by the current rules of Java. In the context of the value type, we allow the type parameter (T in Comparable<T>) to bind to the value type Bignum and thus bridge the box method through to the value method compareTo. The language rules which govern this are not yet defined in detail.

We expect every value to implement an ad hoc interface or abstract super type that looks something like this:

interface __Objectable<ThisType> {
  default String toString() {...}
  default int hashCode() {...}
  default boolean equals(ThisType) {...}
}

Open questions

Many questions remain, including the ones raised above in passing.

Here are a few more questions that need answering:

Conclusion

Along with the questions, we believe we have enough answers and insights to begin prototyping value types, and verifying our thesis. That is, we think it quite likely that a restricted class-like type can be made to look enough like a primitive to be worth adding to the language and VM.

Acknowledgements

This draft has deeply benefited from the comments of many people. Outside of Oracle, conversations with Doug Lea, Karl Taylor, Dan Heidinga, and Jeroen Frijters have been especially helpful.