abandon all U-types, welcome to L-world (or, what I learned in Burlington)

abandon all U-types, welcome to L-world (or, what I learned in Burlington)

John Rose john.r.rose at oracle.com
Sun Nov 19 21:40:33 UTC 2017

We just had a 50-hour week of face-to-face meetings by the
Valhalla VM team.  We learned a lot and surprised ourselves
by coming to a consensus that a promising design for value
types uses mainly the same legacy L-type descriptors, makes
relatively little use of Q-type descriptors, and does not appear
to need a third descriptor "kind" or "mode", such as U for
universal, or R for reference-only.

First a few highlights out of many.  Fred Parain explained to us how
he has prototyped a thread-local analog of Java heaps to store value
structs in a form convenient to the interpreter.  Tobias Hartmann
and Roland Westrelin (of Red Hat) explained what the compiler
prefers to see, which is (obviously) the scalarized components
of each value.  The three of them have worked out detailed
rules for calling between interpreted and compiled code.

It seems to me that other implementations of the JVM (looking
at you, IBM) will tend in similar directions, so although our
results are strongly informed by our own prototyping, we think
it is likely that they will apply to other, independent JVM
implementations.  (Or are there platforms where the interpreter
will scalarize aggressively and the optimizer will prefer to
keep everything in structs?  Not.)

Karen Kinnear and the Oracle Valhalla lead, David Simms, were
there to make sure we solved the important problems and asked
the hard questions.  As a special appearance, one of our spec.
gurus, Dan Smith, was there to help us make rigorous sense out
of our intuitions and hacks.

Since we were short on language experts, we just worked in
the mode (my personal favorite) of pretending that the JVM
is the most important thing, and the Java language designers
will just have to figure out how to use it.  Of course, that's an
oversimplification; the JLS and JVMS inform each other very
strongly, but it was freeing to temporarily take current thoughts
about JLS extensions as a given and vary the JVM to find
the sweet spot that would be simple to implement and supportive
to what we think we know about the Valhalla Java of the future.

We had some long conversations about carrier types: L, Q, U,
and more, and that's what I want to write about here.  We also
make significant progress in the design of crackable lambdas,
template classes, and current and future versions of condy.
We talked to Ron Pressler about kick starting Loom fibers.
But it is L-types I want to talk about here; the above is just a
sketch of the past week's environment.

Logically speaking, we have two things we want to do, and
that unfolds to a choice between three "worlds" of up to four
distinct kinds: L/Q/U/R.  L is always present because it is
a legacy model for reference types.  Q is always present
because we know we need (at least sometimes) to make
a syntactic distinction between flattened values and legacy
objects.

(Why not just always look inside the classfile? Because
the verifier cannot be expected to load a class for every
type it sees, so needs a descriptor kind character from
time to time.)

The U kind came a year or two ago when we realized
that any-generics (and/or templates) and interfaces both
require a disjoint-union type that is neither Q nor L, but
can keep track of Q payloads (value instances) and L
payloads (nullable references to object instances),
without mixing them up.  In other words, neither Q-types
nor legacy L-types are parallel class-based constructs,
and neither conveniently "sits on top" of the other; they
need a common supertype to carry them without confusion.

Before I describe the three logically possible "worlds",
I'll add one more letter, R.  An R-type is exactly a legacy
L-type, a nullable reference.  Why use a separate letter?
Answer:  For the same reason we introduced the other
kind letters, to preserve all the necessary distinctions
among different kinds of payloads and carrier types,
and also to talk about the explicit encoding of descriptors.

There are three worlds we could design to hold both legacy
R-types (today's L-types) and Q-types:  U-world, L-world,
and R-world.  They might be notated respectively as U/QL,
L/Q, and U/QR.

The "U-world" is what I have been mentally preparing for
for many months.  It is the design where L-types, marked
as such in bytecode type descriptors, are always legacy
object references or null, and Q-types, also marked as
such in bytecodes, are always new value types.  To
carry runtime payloads which may dynamically vary
between the two modes, we need a third mode, U-types,
which carry the two kinds of payloads (I hesitate to say
"values" because I want to include reference values also).

A U-type is a disjoint union between corresponding,
similarly named Q-types and L-types.

(Mathematically, a _disjoint union_ of C = A |_| B is no more
and no less than the sum of all elements or points comprised
by the two constituent sets A and B.  The disjoint union has
nothing more: no points not in A or B.  It has nothing less:
every point of C is from either A and B, but never both.
If A and B somehow look like they have a non-empty
intersection, then C is adjusted so as to keep straight
which elements are from A and which are from B.)

The "R-world" is a copy of the "U-world", except that the
new world has no L-types at all, or rather they are renamed
as R-types.  In this world, bridges would be required
between legacy bytecodes (which use L's) and Valhalla
bytecodes (which use R's for the same concept).

We are pretty sure we don't want to live in R-world, but
it helps to think about it, since it makes the maximum
distinctions between legacy APIs and upgraded Valhalla
APIs.  Any bridge from R-world to legacy code will
presumably come after a clear decision has been made
to allow the legacy code to see, under the name of L-types,
the R's from the new world, plus whatever Q's are also
allowed over the bridge to interoperate wit the old code.

The U-world has similar need for bridges, but less extreme.
We know we will need some bridges to upgrade legacy
classes like List to use U-types (List<int>, List<ComplexDouble).
The L-types of U-world just mix without effort into the legacy
L-types of legacy classes, since the same letter is used.

The third logical choice, and the one we are now looking
at very seriously, is "L-world".  (Break out the "abandon
all hope" and "Niflheim" jokes!)  In L-world, we identify
(some would say conflate or confuse) the necessary
U-type which unites R-types and Q-types with the legacy
syntax "L".  The Q-type syntax is *maybe* needed, but
in any case does not appear in a parallel position of
importance with the dominant L-type syntax.  The R-type
syntax seems even less important; we haven't thought
of a use for it.  But it is in reserve, in case we need
R-type descriptors for some corner case.

The distinction between value types and object types
is still fundamental, as is the distinction between flat
and non-flat data.  The classfile which defines any
given type unambiguously declares whether it is an
object or value type.  But in L-world, the L-type
descriptors can carry both payloads.  That's the
key decision before us.

(For brevity I'll say R-type/R-value when I mean a
legacy nullable reference type/value, and Q-type/Q-value
for value type/instance.  This doesn't mean that we
will need Q's and R's in the final bytecode syntax.
But they are useful concepts.)

There are many implications from the decision to
put L-types at the top:

* The type L-Object ("Ljava/lang/Object;") carries both
.  Thus, we don't need a
new top-type.  (There are objectionable properties of
L-Object which need remediation, but this was always
true, and is not a showstopper for L-world.)

* Likewise, legacy interface types like L-Comparable
are immediately useful (without bridges) for carrying
value instances as well as object instances (and null).

* It is possible, in some cases, that standard and user-written
collection classes will work correctly, without recompilation,
with value types.  (This is a big claim, and valuable if true.
Read on.)

* All basic operations that the JVM applies to R-types must
extend immediately and pervasively to Q-types, since it
applies them to L-type values (which may be either,
dynamically).

* Today, simple movement of R-types is really cheap, just
a machine pointer move.  That needs to be true for L-types
in L-world, or else we will get systematic performance hits
for legacy code, and new code will go slow too.

* There are a number of object-specific operations which
the JVM applies to L-types.  The most common is "acmp"
(the "==" operator for references).  Those operations must
be enhanced to do something useful with values, with a
possible runtime cost to detect the distinction between
an L-type carrying a Q-value and an L-type carrying a
legacy R-value.  The performance and usable semantics
of these object operations will make L-world either
a programmer's paradise or a…  well you know.

* There is no need for boxes, and they turn out to be
undesirable.  Legacy types like java.lang.Integer must
be given a golden watch and a pension, somehow.
That's easy for the JVM but hard for the language,
which mandates that "(Object)(int)x" produces an
Integer rather than an "int".  It seemed a good idea
at the time.

* There is no need for a new "universal" carrier type,
since L-types do the whole job.  Before the L-world
discussion, my thought has been that we want a 128-bit
U-type and a 64-bit legacy L/R-type.  Somebody burst
my bubble this week, by saying that if we do that,
we may find that interpreter speeds for U-type generics
will risk a built-in performance barrier just from the
larger standard carrier type.  If we JVM folks can agree
that U-types should be 64-bits (by all available means)
then it is just a simple step to rename U to L.  This is
the rabbit hole that took our conversation down to L-world.

* In L-world, the "acmp" instruction needs a very fast way
to detect Q-values.  This *may* require a tag bit on the 64-bit
root value.  That in turn will affect GC dynamics.  There is
a delicate balance here—but we think there is a way through.

* We probably need extra interpreter profiling to track whether
a given L-value has ever been a Q-value or an R-value,
dynamically.  Today we do null tracking on some instructions.
This probably needs to be upgraded to null/Q/R tracking,
and perhaps on additional instructions such as "acmp".

* There are a number of ways to assign semantics to
an object-like L operation when it encounters a Q-value.
This will require additional mails, but I think we have
identified about a half dozen models, of which one or two
seem to be very promising:  Providing both useful semantics
and amenable to optimization.

* One residual use for Q-types is in the declaration of
instance fields.  In order to avoid loading *all* classfiles
of types mentioned in field declarations, a classfile which
declares a flattened field will need to include enough
information to allow the classfile loader to load *only*
those fields marked as requiring flattening.  There are
at least two ways to do this:  Use a Q-type descriptor
syntax *only* for field declarations, as today.  Or,
require the ACC_VALUE bit on field declarations which
are supposed to be flattened.

* As we were able to dispense with boxes, we may also
dispense with non-flattened value types.  In that case,
the translation strategy might emit an ACC_VALUE bit
or Q-type on a field if and only if the classfile for the
field's type defines it with ACC_VALUE.  The JVM will
have to support non-flattened values in L-Object fields,
of course.

* If the system uses a thread-local store for value structures
(to avoid heap traffic), a store barrier will have to quickly
detect Q-types that are inside the thread and reallocate
them to the heap, when they are first stored to the heap
(e.g., as an element of an L-Object array).

* The Q-type modifier *might* be useful in some settings
to guarantee, in a verifiable way, that a given value is
*not* an R-type, *not* null, and *not* modifiable; TBD.

* The R-type modifier *might* be useful in some settings
to guarantee, in a verifiable way, that a given value is
*not* a Q-type, and *does* have an object identity or
is null.  This is also TBD.

* For best compatibility with legacy code, combined with
diagnosability of anti-value algorithms like IdentityHashMap,
the "acmp" instruction should return false unconditionally
if either operand is a Q-value (punting to the following
Object.equals call), and other object-like operations
such as identityHashCode and monitorenter must throw
errors in the JVM.  (In the language errors and warnings
will be appropriate.)

* New operations are needed for substitutability checks
which generalize reference equality and hashcode.
These can be system methods, and do not need to be
loaded onto either new or old bytecodes.

* We will almost certainly need to make primitives
retroactively values.  This means "int" all along has
really been Q-int (in the JVM) and is a real subtype
of L-Object.

* Covariant array subtyping only works for R-types.
So both int[] and DoubleComplex[] are *not* subtypes
of Object[], even though int and DoubleComplex *are*
subtypes of Object.

* From some points of view (legacy code), Q-values
are masked invaders coming into the home of code
which expected to work only on R-values.  Changing
L-descriptors to encompass Q-values opens such
code to potentially risky new behaviors.  Is it safe?
Shouldn't we just have boxes to mediate values
in such settings?  It depends on the code, really.

There's more, but this is enough for one message.

The L-world is very attractive:  No bridges or boxes,
legacy code is value-enabled, and we get all the
flattening we need.

We need to do some experiments:  Can we afford
the extra Q-checks on acmp and storage to the heap?
Will legacy algorithms really work on masked but not
boxed values?  Do other JVM implementations experience
similar trade-offs, or is this only a HotSpot-centric set
of compromises?  Can we really avoid all those new
descriptors and bridges!!??

Let's talk!

— John

P.S. Dan, you should send out your notes on U-types.

More information about the valhalla-spec-observers mailing list