Project Valhalla, Simple as it can be, but not simpler

John Rose, 2023-0814
(“what about”s and other adjustments are solicited)

Introduction: Q-descriptors and v-bytecodes

Since the inception of Valhalla JVM prototyping around 2015, many versions of the Valhalla VM prototype feature a new sort of VM type called Q-types, expressed by new descriptors for those types (QC; for some classes C where LC; is already a descriptor). Many also feature special bytecodes, beginning with the letter v, for operating on Q-type values.

The reasoning for these features is simple: Valhalla introduces a new kind of class, a value class, to the Java language. (A Java value class is a bit like a C struct, while a normal Java class, an identity class, is a bit like a C pointer to a struct. One is passed around by value, the other by reference.) Given this, surely fundamentally new types in the managed runtime must be given new names and operations, so descriptors and bytecodes are a way to describe such type names and operations, in the Valhalla VM support for these new Java value classes.

With the benefit of abundant hindsight, all this seems to be changing, for the better. New optimization techniques allow us to express struct-like values and their operations as normal Java classes with the pre-existing operations on their managed references. What has been suprising to us is not that Java classes are adequate to model struct-like flat values. The surprise is that we can do this without sacrificing our performance goals. This note describes the removal of Q-types and v-bytecodes, and the resulting adjusted VM design. The intricate optimizations that justify will be discussed elsewhere.

First, let’s look at an example of Q-types and v-bytecodes in action, in a version of the Valhalla VM protoype which leans heavily into these features. Suppose a caller needs to invoke the method Integer::valueOf to unbox an integer. The bytecode evaluation would work like this:

# in caller…
vload 99                # load a local Integer value V onto the stack
vinvoke Integer::valueOf()int

# in Integer::valueOf…
vload 0                 # get the Integer value V passed passed from caller
vgetfield Fieldref(Integer.value:int)
ireturn                 # return the stacked int value

# back in caller…
istore 88               # store returned value into an int local

In a design like this, Q-types and L-types (the existing class and interface reference types) have their own separate operations. The verifier requires that an invokevirtual instruction consume only L-types, while the vinvoke instruction consumes only Q-types. A more recent prototype allows the two kinds of types to mix, allowing v-bytecodes to be replaced by overloaded legacy bytecodes, like this:

# in caller…
aload 99                # load a local Integer V, as an L-type or Q-type
invokevirtual Integer::valueOf()int

# in Integer::valueOf…
aload 0                 # get the Integer V passed passed from the caller
getfield Fieldref(Integer.value:int)
ireturn                 # return the stacked int value

# back in caller…
istore 88               # store returned value into an int local

Since bytecodes work equally well on value classes and plain identity classes, there is little or no need for the verifier to track Q-types. This is a simpler design, which allows clients of Integer to operate as if the class had not be changed. As we will now see, that turns out to be a big deal.

Migration and binary compatibility

Beyond simplifying the Java VM specification, the great benefit of removing Q-types and v-bytecodes is migration compatibility. We expect to migrate the existing class Integer (and Optional, and many other so-called value-based classes) to a value class. Doing this will require recompiling the source code that defines the changed classes, but will it necessarily require clients of Integer (and Optional, etc.) to be recompiled as well? Yes, if clients need to use those classes with Q-types and/or v-bytecodes. But no, if the existing bytecodes and constant pool formats still apply to Integer even after they are migrated to be value classes. When determining whether migration is practical or not, the determining issue is binary compatility, as documented in Chapter 13 of the Java Language Specification (in all versions of Java). Here is how the JLS defines it:

A change to a type is binary compatible with (equivalently, does not break binary compatibility with) pre-existing binaries if pre-existing binaries that previously linked without error will continue to link without error.

Binaries are compiled to rely on the accessible members and constructors of other classes and interfaces. To preserve binary compatibility, a class or interface should treat its accessible members and constructors, their existence and behavior, as a contract with its users.

The more we use existing classfile encodings for a value-migrated Integer, the less we will ask users to recompile their classfiles. If Integer is converted to a value class at its definition site, then as an ideal goal, existing class files would not need to be recompiled; their code would “just work” on the Integer references now treated (by the VM) as pure values. Doing this without client recompilations has seemed an impossible goal, but it now seems within reach, as we reduce the changes to the classfile format to the bare minimum.

Here are some details. In places where QC; seemed necessary, plain old LC; works fine, sometimes accompanied by a side channel that says, “nulls not welcome here”. Such a side channels is now called a “type restriction”. In historical discussions we have characterized this approach as using “L-star” descriptors, envisioned as a descriptor L*C; (instead of QC;) where the asterisk is somehow encoded somewhere else; such an asterisk “rubs off easily”, so it doesn’t get in the way of dynamically linking.

For example, a classfile method reference to the factory method Integer::valueOf has three componebts, java/lang/Integer, valueOf, and (I)Ljava/lang/Integer;. Such a triplet of strings is called a symbolic reference, and is embodied in a Methodref constant pool entry. If the VM required values to have a Q-type descriptor, the third component would instead need to look like (I)Qjava/lang/Integer;. Since the VM’s dynamic linking mechanism requires exact string matches of all symbolic reference components, even that one-character change (from L to Q) would break migration compatibility for Integer::valueOf, requiring all its clients to be recompiled.

But recent versions of the Valhalla VM do not require this particular change, even if they do support Q-types. This requires powerful optimizations under the hood, to treat the calling sequence for LInteger; as by value, even if it seems to be by reference (since all L-types denote managed managed references). In fact, removing Q-descriptors altogether (in favor of type restrictions, as noted above) removes a large class of migration hazards. If there is no need ever for a client of a migrated value class to mention its Q-type, let’s just take such types away altogether, and then there’s no chance of Q-types messing up binary compatibility, or complicating the JVMS.

What about v-bytecodes? It turns out (surprisingly to exactly everybody) that there is no real need for v-bytecodes either. Removing them improves the migration story as well. Most versions of the Valhalla VM prototype define v-bytecode replacements for putfield and new; most recently there are just two, aconst_init (for creating a blank new value) and withfield (for changing one field). Earlier versions had vnew, vwithfield, and vgetfield as well, even vinvoke was proposed; if there is a parallel universe of Q-types, then clearly it is reasonable to posit a parallel universe of bytecodes to work on them. Equally reasonably, removing Q-types questions the existence of the v-bytecodes.

The dance at the dawn of creation

The most difficult challenge to migration compatibility, for Valhalla objects, is not method invocation or field access, but object creation. The reasons for this are complex.

In the Java VM, every new object is created by a complicated interaction of many bytecodes, a choreography that might be called “the new/dup/init dance”. The steps of this dance are as follows:

• Using the new bytecode, make R, a blank new object of some class C.
• Use dup to save an extra copy of R; keep it handy in a local or on stack.
• Push more values on the stack – these are the constructor arguments.
• Call the constructor, named C::<init>, on R using invokespecial.
• At this point, R will be useless in the caller until C::<init> returns.
• Inside C::<init>, call putfield on R as needed to set up the object.
• Also inside C::<init>, invoke the superclass constructor S::<init> on R.
• Before this point, R is useless, except for putfield in C::<init>.
• After the S::<init> call, R is now a complete, usable C instance.

The interactions of these bytecodes, new, dup (or astore and aload), invokespecial, and putfield, are orchestrated in detail by the Java VM specification, with their correct relations enforced by the bytecode verifier. In particular, before R is a completed object, the verifier represents its type using the special category uninitializedThis, not just the class C. This special type of reference is sometimes referred to a larval object, appealing to the hidden life of some immature insects and fish. When the <init> call returns, matching occurrences of uninitializedThis are transparently converted (in the verifier’s view of types) into C, allowing subsequent code to treat them as fully-fledged “adult” objects.

The effect of the special verifier type for larval objects is to suppress all uses of the reference R (except calling <init> and doing putfield) until the right moment, when R becomes a real C object. (You might say, when it “molts from larva to adult.”) This is all in the verifier’s view of types; the interpreter does not need to change the R values on stack or in locals; they just mature in place into C references.

As a specific example, here is the sequence for executing the expression new Integer(42):

# in caller…
new Integer             # C = Integer, R = new (larval) object
dup                     # save a copy of R
bipush 42               # constructor argument = 42
invokespecial Methodref(Integer::<init>(int)void)

# in Integer::<init>…
aload 0                 # R = new (larval) object passed from caller
invokespecial Number::<init>()void  # S = Number
# R is, at this point, a complete, usable (adult) Integer instance

aload 0                 # R again, for putfield
iload 1                 # constructor argument = 42
putfield Fieldref(Integer.value:int)
# R’s field is now initialized

return                  # do not return a value; caller must have copy of R

# back in caller…
areturn                 # return copy of R, which was on stack, from dup

(Note: We have edited the symbolic references, removing excess punctuation and package prefixes, to make them easier to read.)

There is no required relative order of field initialization and superclass invocation, so the sequence of operations could also have been coded like this:

# in Integer::<init>…
aload 0                 # R = new (larval) object passed from caller
iload 1                 # constructor argument = 42
putfield Fieldref(Integer.value:int)
# R’s field is now initialized (it is OK that R is still larval)

aload 0                 # R again, for superclass constructor
invokespecial Number::<init>()void  # S = Number
# R is, at this point, a complete, usable (adult) Integer instance

Note that the reference R, while it is in the uninitialized state, is a “blank slate” on which the field values are written (using putfield). Although it is not a fully complete object, it would seem to be (at least) an identity object, because the putfield operations that store initial field values must have an identity (a location in the heap) to write those values into.

In recent prototypes of the Valhalla VM, value instance creation uses a different code shape, making use not of the method <init> but a new value factory method <vnew>. If Integer were migrated to a value class, the recompiled code for new Integer(42) would look like this:

# in caller…
bipush 42               # constructor argument = 42
invokestatic Methodref(Integer::<vnew>(int)Integer)

# in Integer::<vnew>…
aconst_init Integer     # in the factory, start with a blank Integer
iload 1                 # constructor argument = 42
withfield Fieldref(Integer.value:int)
areturn                 # return the constructed value to caller

# back in caller…
areturn                 # return the constructed value

The code shape is completely different. Any client that says new Integer(42) needs to be recompiled if Integer is migrated. Luckily, Integer::valueOf (like Optional::of) hides the details of object construction, so that relatively few clients need recompilation. (And for Optional the constructor is private, providing additional protection.) But recompilation hazards, in general, add risks to migration.

Although they don’t literally begin with “v”, the two new bytecodes aconst_init and withfield are (in their hearts) v-bytecodes. Can we get rid of them? It turns out the answer is “yes”. Here is the beginning of an amended construction sequence for newInteger(42), as a value class:

# in caller…
new Integer             # C = Integer, R = new (larval) object
dup                     # save a copy of R
bipush 42               # constructor argument = 42
invokespecial Methodref(Integer::<init>(int)void)

What is happening here? Well, we allow the new bytecode to be overloaded to support value classes like Integer. (This is much like we have already overloaded getfield, instead of having a separate vgetfield.) Obviously that means “make a blank value”, but immediately alarm bells should be going off: Does this mean that any client is allowed to make blank values and play around with them? Supposedly access to blank values is controllable by the Java language (by making the appropriate constructor private).

The problem goes away, so far, when you realize that the verifier will allow an untrusted client to call new, but will not allow that client to immediately access the resulting value. After all, it is of type uninitializedThis, a larval object reference.

The next step should be alarming as well. As with regular identity classes, we pass the larval reference R to its constructor:

# in Integer::<init>…
aload 0                 # R = new (larval) object passed from caller
iload 1                 # constructor argument = 42
putfield Fieldref(Integer.value:int)
# R’s field is now initialized

OK, now we are overloading putfield. How can that possibly work? We have defined value classes (like the older value-based classes) to be fully immutable. Clearly calling putfield is a foul play. Before sending the player off the field, however, remember that the classic (pre-Valhalla) VM allows putfield to a final field in exactly one place, a constructor method such as Integer::<init> here. So we can prolong the play here, as long as the putfield has a place to put its value (42).

This is where the new insight comes in, as a surprise to everyone: If the larval reference created by new is allowed to be a mutable value buffer, instead of a regular (adult) value which is immutable, then putfield (inside the constructor) can be given a meaning: It can be given the same meaning as for a classic identity class, which is to initialize a final field which is temporarily mutable (just for the constructor).

The new code sequence finishes like this:

# still in Integer::<init>, just finishing up…
return                  # do not return a value; caller must have copy of R

# back in caller…
areturn                 # return copy of (adult) R, which was on stack, from dup

There are two things to notice here. First, we completely skipped the invocation of the constructor of the superclass, Number::<init>()void. How did we avoid calling that? Second, as if by magic, the last use of R, which was created (by dup) as a copy of a larval object, has suddenly been promoted to its adult phase. When did that happen?

The answers to those questions are connected. As a new rule in the Valhalla VM, when a value class constructor exits, all references to the newly constructed object transition from larval to adult. They are no longer of a verifier type of kind uninitializedThis, but rather of type Integer (which is an L-type, not a Q-type). This seems impossible magic, until you realize two things: First, the verifier is already in the business of making a hard and fast distinction between larval and adult references, just for identity classes. We are simply extending this distinction to value classes as well. Second, the Java Memory Model already dictates (for identity classes) that all final fields of a class C change from mutable to immutable on (normal) exit from the constructor of C. This is called a freeze operation. We are simply extending the application of the JMM freeze operation to value classes as well.

The alert reader will note that when a value object is frozen, it loses its identity, as well as makes its fields immutable. The VM must correctly track the freezing event, so that it applies certain optimizations (value cloning and deduplication) only to value objects in the adult state (otherwise the effects of putfield would become unpredictable).

In order to retain the bright line between larval and adult states, for value classes, we add a new rule which forbids value class constructor to call its superclass constructor. After all, if Number::<init> were invoked, bad things might happen, since the Integer::<init> constructor would view the constructed object (after the superclass constructor call) as a completed adult value, but putfield would also be allowed to modify that value in place, leading to ambiguities and even races (if the completed object were shared with another thread).

To avoid such ambiguities, we forbid calling the superclass <init> method. In any case, value classes (as currently designed) are forbidden to have non-trivial superclass constructors. There is a special marking, for abstract classes like Number, that says “the no-argument constructor takes no action”. Therefore, not calling it is a semantically neutral decision, and it avoids prematurely molting the constructing object from larval to adult; this happens at the JMM freeze at the end of the value class constructor call, such as Integer::<init>.

The net result is that no new bytecodes are needed; the pre-existing rules that govern the pre-existing bytecodes for object creation (the new/dup/init dance) can be adjusted incrementally to cover value object creation, and in such a way that existing clients do not need to be recompiled. Only the value class itself, with its superclasses, needs recompilation.

There is a permanent oddity here, the shift (of a value object being created) from larval to adult phases, as tracked by the verifier and the VM. Wouldn’t adding real purpose-built v-bytecodes (aconst_init and withfield, aka vnew and vputfield) allow cleaner VM design, than building in the larval/adult state change? Maybe, but notice one more thing: We need the larval/adult state change anyway, even with the v-bytecodes, in order to cover the needs for deserialization of objects. The prototype Valhalla VM already has the methods Unsafe::makePrivateBuffer (for vnew) and Unsafe::finishPrivateBuffer (for freeze), as well as plain old mutating Unsafe::putInt (for mutating the larval buffer). The VM already needs to optimize the particular unsafe version the dance, which might be called new/putfield/freeze. (In this version, putfield and freeze operations are considered separately from any <init> call.) Taking away the v-bytecodes simply asks the VM to use similar “dances” for deserialization and regular object creation.

We think overall this makes for a simpler VM design for Valhalla, as well as one with fewer migration hazards.

Simple as it can be, but not simpler

Regarding the modeling of physical reality, Einstein said this in 1933:

It can scarcely be denied that the supreme goal of all theory is to make the irreducible basic elements as simple and as few as possible without having to surrender the adequate representation of a single datum of experience.

This has been paraphrased (by non-scientists) as “Everything should be as simple as it can be, but not simpler”. We find this to esthetic principle be true in the design of the Java virtual machine, where a simple model of computation is as powerful (in its own sphere) as a simple theory for physics.

For physicists, simple theory retains power for modeling known phenomena, and predicting new discoveries. It makes easy calculations easier, and allows hard calculations to encompass more detail. Likewise, for VM designers, a clean design models all necessary calculations with understandable simplicity, and lays the groundwork for unknown use cases, not yet discovered. A clean design makes simple implementations simpler, and increases the reach of aggressive optimizations.

Relying on Q-types and v-bytecodes, like reckoning with the Ptolemaic epicycles of pre-modern astronomy, would make for an “adequate representation” of computing with values, at the cost of a user model complicated by extra differences between value classes and identity classes. Removing the extra differences makes the model simpler for end users, friendlier to migration, and easier to implement and analyze.

The punchline of Einstein’s aphorism was “…without having to surrender the adequate representation of a single datum of experience”. Well, he blew that line, so some artists fixed it for him: “…as simple as possible, but not simpler”. For the Valhalla VM, our version of “…but not simpler” is the deft addition of one extra epicycle (or one short-range quantum field, if you like). This is the concept of type restrictions, which modify specific fields and arrays, in a way that allows the Valhalla VM to exclude nulls and use flattened (null-free) representations for values stored in those places. These type restrictions are added as side channel to the L-descriptors for the values; this replaces the complexity of Q-descriptors, which would apply to every part of the VM design, not just fields and arrays.

To choose a slightly less lofty comparison, Michaelangelo is wrongly quoted as saying this about sculpting his masterpiece, the David:

It is easy. You just chip away the stone that doesn’t look like David.

In the case of the Valhalla VM, it appears we may chip away almost everything, Q-types and v-bytecodes together, and the result will still look like a value-processing virtual machine, as long as we leave behind a few extra chunks. Those are a value bit in the class file header, a tweak to superclass constructor definition and invocation for value classes, and a type restriction mechanism for fields and arrays. These chunks are (to us) surprisingly small, with the resulting VM design surprisingly similar to to the pre-Valhalla VM. Let’s hope that this design will look obvious in hindsight.

from Hacker News https://ift.tt/IY0URrd