This doc covers some groundwork on rationalizing existing translation of
switch as we move towards pattern-enabled switches.
# Switch Translation, Part 1
#### Maurizio Cimadamore and Brian Goetz
#### December 2017
This document examines the current translation of `switch` constructs by
`javac`, and proposes a more general translation for switching on
primitives, boxes, strings, and enums, with the goals of:
- Unify the treatment of `switch` variants, simplifying the compiler
implementation and reducing the static footprint of generated code;
- Move responsibility for target classification from compile time to
run time, allowing us to more freely update the logic without updating
the compiler;
- Lay the groundwork for patterns in `switch`.
Part 2 of this document will focus on the challenges of translating
pattern `switch`.
## Current translation
Switches on `int` (and the smaller integer primitives) are translated in
one of two ways. If the labels are relatively dense, we translate an
`int` switch to a `tableswitch`; if they are sparse, we translate to a
`lookupswitch`. The current heuristic appears to be that we use a
`tableswitch` if it results in a smaller bytecode than a `lookupswitch`
(which uses twice as many bytes per entry), which is a reasonable
heuristic.
#### Switches on boxes
Switches on primitive boxes are currently implemented as if they were
primitive switches, unconditionally unboxing the target before entry
(possibly throwing NPE).
#### Switches on strings
Switches on strings are implemented as a two-step process, exploiting
the fact that strings cache their `hashCode()` and that hash codes are
reasonably spread out. Given a switch on strings like the one below:
switch (s) {
case "Hello": ...
case "World": ...
default: ...
}
The compiler desugar this into two separate switches, where the first
switch maps the input strings into a range of numbers [0..1], as shown
below, which can then be used in a subsequent plain switch on ints. The
generated code unconditionally calls `hashCode()`, again possibly
throwing NPE.
int index=-1;
switch (s.hashCode()) {
case 12345: if (!s.equals("Hello")) break; index = 1; break;
case 6789: if (!s.equals("World")) break; index = 0; break;
default: index = -1;
}
switch (index) {
case 0: ...
case 1: ...
default: ...
}
If there are hash collisions between the strings, the first switch must
try all possible matching strings.
#### Switches on enums
Switches on `enum` constants exploit the fact that enums have (usually
dense) integral ordinal values. Unfortunately, because an ordinal value
can change between compilation time and runtime, we cannot rely on this
mapping directly, but instead need to do an extra layer of mapping.
Given a switch like:
switch(color) {
case RED: ...
case GREEN: ...
}
The compiler numbers the cases starting a 1 (as with string switch), and
creates a synthetic class that maps the runtime values of the enum
ordinals to the statically numbered cases:
class Outer$0 {
synthetic final int[] $EnumMap$Color = new
int[Color.values().length];
static {
try { $EnumMap$Color[RED.ordinal()] = 1; } catch
(NoSuchFieldError ex) {}
try { $EnumMap$Color[GREEN.ordinal()] = 2; } catch
(NoSuchFieldError ex) {}
}
}
Then, the switch is translated as follows:
switch(Outer$0.$EnumMap$Color[color.ordinal()]) {
case 1: stmt1;
case 2: stmt2
}
In other words, we construct an array whose size is the cardinality of
the enum, and then the element at position *i* of such array will
contain the case index corresponding to the enum constant with whose
ordinal is *i*.
## A more general scheme
The handling of strings and enums give us a hint of how to create a more
regular scheme; for `switch` targets more complex than `int`, we lower
the `switch` to an `int` switch with consecutive `case` labels, and use
a separate process to map the target into the range of synthetic case
labels.
Now that we have `invokedynamic` in our toolbox, we can reduce all of
the non-`int` cases to a single form, where we number the cases with
consecutive integers, and perform case selection via an
`invokedynamic`-based classifier function, whose static argument list
receives a description of the actual targets, and which returns an `int`
identifying what `case` to select.
This approach has several advantages:
- Reduced compiler complexity -- all switches follow a common pattern;
- Reduced static code size;
- The classification function can select from a wide range of
strategies (linear search, binary search, building a `HashMap`,
constructing a perfect hash function, etc), which can vary over time or
from situation to situation;
- We are free to improve the strategy or select an alternate strategy
(say, to optimize for startup time) without having to recompile the code;
- Hopefully at least, if not more, JIT-friendly than the existing
translation.
We can also use this approach in preference to `lookupswitch` for
non-dense `int` switches, as well as use it to extend `switch` to handle
`long`, `float`, and `double` targets (which were surely excluded in
part because the JVM didn't provide a convenient translation target for
these types.)
#### Bootstrap design
When designing the `invokedynamic` bootstraps to support this
translation, we face the classic lumping-vs-splitting decision. For now,
we'll bias towards splitting. In the following example,
`BOOTSTRAP_PREAMBLE` indicates the usual leading arguments for an indy
bootstrap. We assume the compiler has numbered the case values densely
from 0..N, and the bootstrap will return [0,n) for success, or N for "no
match".
A strawman design might be:
// Numeric switches for P, accepts invocation as P -> I or Box(P) -> I
CallSite intSwitch(BOOTSTRAP_PREAMBLE, int... caseValues)
// Switch for String, invocation descriptor is String -> I
CallSite stringSwitch(BOOTSTRAP_PREAMBLE, String... caseValues)
// Switch for Enum, invocation descriptor is E -> I
CallSite enumSwitch(BOOTSTRAP_PREAMBLE, Class<Enum<E extends
Enum<E>>> clazz,
String... caseNames)
It might be possible to encode all of these into a single bootstrap, but
given that the compiler already treats each type slightly differently,
it seems there is little value in this sort of lumping for non-pattern
switches.
The `enumSwitch` bootstrap as proposed uses `String` values to describe
the enum constants, rather than encoding the enum constants directly via
condy. This allows us to be more robust to enums disappearing after
compilation.
This strategy is also dependent on having broken the limitation on 253
bootstrap arguments in indy/condy.
#### Extending to other primitive types
This approach extends naturally to other primitive types (long, double,
float), by the addition of some more bootstraps (which need to deal with
the additional complexities of infinity, NaN, etc):
CallSite longSwitch(BOOTSTRAP_PREAMBLE, long... caseValues)
CallSite floatSwitch(BOOTSTRAP_PREAMBLE, float... caseValues)
CallSite doubleSwitch(BOOTSTRAP_PREAMBLE, double... caseValues)
#### Extending to null
The scheme as proposed above does not explicitly handle nulls, which is
a feature we'd like to have in `switch`. There are a few ways we could
add null handling into the API:
- Split entry points into null-friendly or null-hostile switches;
- Find a way to encode nulls in the array of case values (which can be
done with condy);
- Always treat null as a possible input and a distinguished output,
and have the compiler ensure the switch can handle this distinguished
output.
The last strategy is appealing and straightforward; assign a sentinel
value (-1) to `null`, and always return this sentinel when the input is
null. The compiler ensures that some case handles `null`, and if no
case handles `null` then it inserts an implicit
case -1: throw new NullPointerException();
into the generated code.
#### General example
If we have a string switch:
switch (x) {
case "Foo": m(); break;
case "Bar": n(); // fall through
case "Baz": r(); break;
default: p();
}
we translate into:
int t = indy[bsm=stringSwitch["Foo", "Bar", "Baz"]](x)
switch (t) {
case -1: throw new NullPointerException(); // implicit null case
case 0: m(); break;
case 1: n(); // fall through
case 2: r(); break;
case 3: p(); // default case
}
All switches, with the exception of `int` switches (and maybe not even
non-dense `int` switches), follow this exact pattern. If the target
type is not a reference type, the `null` case is not needed.
## Patterns in narrow-target switches
When we add patterns to the language, we may encounter switches whose
targets are tightly typed (e.g., `String` or `int`) but still use some
patterns in their expression. For switches whose target type is a
primitive, primitive box, `String`, or `enum`, we'd like to use the
optimized translation strategy outlined here, but the following kinds of
patterns might still show up in a switch on, say, `Integer`:
case var x:
case _:
case Integer x:
case Integer(var x):
The first three (if supported at all) can be translated away by the
source compiler, as they are semantically equivalent to `default`. If
any nontrivial patterns are present (including deconstruction patterns),
we will need to translate as a pattern switch scheme -- details coming
in Part 2. (While the language may not distinguish between "legacy" and
"pattern" switches -- in that all switches are pattern switches -- we'd
like to avoid giving up obvious optimizations if we can.)
## Looking ahead -- patterns
A key motivation for reexamining switch translation is the impending
arrival of patterns in switch. We expect switch translation for the
pattern case to follow a similar structure -- lower to an `int` switch
and use an indy-based classifier to select an index. However, there are
a few additional complexities. One is that pattern cases may have
guards, which means we need to be able to re-enter the bootstrap with an
indication to "continue matching from case N", in the event of a failed
guard.
Translating pattern switches is more complicated because there are more
options for how to divide the work between the statically generated code
and the switch classifier, and different choices have different
performance side-effects (are binding variables "boxed" into a tuple to
be returned, or do they need to be redundantly calculated). These will
be explored in Part 2.
