Re: Switch translation
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.
I see why you use this structure, because it fits a general paradigm
of first mapping to an integer.
Or, "used", since this is the historical strategy which we're tossing
over for the indy-based one.
I now suggest that a post-optimization might then turn this into:
SUCCESS: {
DEFAULT: {
switch (s.hashCode()) {
case 12345: if (s.equals("Hello")) { stmts1; break SUCCESS; }
else if (s.equals(“Goodbye")) { stmts3; break SUCCESS; } else break
DEFAULT;
Yes; the thing that pushed us to this translation was fallthrough and
other weird control flow; by lowering the string-switch to an
int-switch, the control structure is preserved, so any complex control
flow comes along "for free" by existing int-switch translation. Of
course, it's not free; we pay with a pre-switch. (When we added strings
in switch, it was part of "Project Coin", whose mandate was "small
features", so it was preferable at the time to choose a simpler but less
efficient desugaring.)
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:
Inconsistency: in the string example above, you actually numbered the
cases 0 and 1, not 1 and 2.
The old way, where the compiler generated the transform table (Java 5
and later) used 1-origin, for the reason you surmise. The new,
indy-based translation uses 0, like the String example.
Presumably for this example the chosen integers start with 1 rather
than 0, so that if any element of the array is not explicitly
initialized by Outer$0, its default 0 value will not be confused with
an actual enum value. This subtle point should be mentioned explicitly.
Yes, that's exactly why the historical approach did it this way. The new
way (which is uniform with other indy-based switch types) takes care of
this with pre-filling the array with the index that indicates "default"
at linkage time. From SwitchBootstraps::enumSwitch:
ordinalMap = new int[enumClass.getEnumConstants().length];
Arrays.fill(ordinalMap, enumNames.length);
for (int i=0; i<enumNames.length; i++) {
try {
ordinalMap[E.valueOf(enumClass,
enumNames[i]).ordinal()] = i;
}
catch (Exception e) {
// allow non-existent labels, but never match them
continue;
}
}
}
The catch-and-continue is so that if an enum disappears, we don't fail
linkage of the classifier site, its arm just becomes dead code (which is
fine, since the enum constant no longer exists.)
Explicit continue
An alternative to exposing guards is to expose an explicit `continue`
statement in switch, which would have the effect of "keep matching at
the next case." Then guards could be expressed imperatively as:
case P:
if (!guard)
continue;
...
break;
case Q: …
A nice idea, but careful: it is already meaningful to write:
while (…) { switch (…) { case 1: … case 2: if (foo) continue; … } }
and expect the `continue` to start a new iteration of the `while`
loop. Indeed, this fact was already exploited above under “### Guards”.
Yes. One of the downsides of exposing `continue` is that currently the
(switch, continue) entry in my table from "Disallowing break label and
continue label inside expression switch" has a P instead of an X,
meaning that continue is currently allowed in a switch if there's an
enclosing continue-able context. So this could be disambiguated as you
say with "continue switch", or with requiring a label in some or all
circumstances.
Re: Switch translation
Very comprehensive. Four groups of comments below (one at the very bottom).
> On Apr 6, 2018, at 11:51 AM, Brian Goetz <brian.go...@oracle.com> wrote:
>
> The following outlines our story for translating improved switches, including
> both the switch improvements coming as part of JEP 325, and follow-on work to
> add pattern matching to switches. Much of this has been discussed already
> over the last year, but here it is in one place.
>
> # Switch Translation
> Maurizio Cimadamore and Brian Goetz
> April 2018
>
> ## Part 1 -- constant switches
>
> This part 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.
>
> ## 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.
Minor point: unclear why the default case has to assign -1 to index, when it it
already initialized to -1.
I see why you use this structure, because it fits a general paradigm of first
mapping to an integer.
However, a post-optimization might be able to turn such a structure, where the
assignments to “index” are all constants rather than the results of calling
some opaque classifier method, into a control structure with a single switch
statement and no use of the intermediate integer encoding. I’ll show a more
general example to give you the idea:
switch (s) {
case "Hello": stmts1;
case "World": stmts2;
case “Goodbye": stmts3;
default: stmtsD;
}
and suppose that “Hello” and “Goodbye” happen to have the same hashcode. It
might be transformed into:
int index=-1;
switch (s.hashCode()) {
case 12345: if (s.equals("Hello")) index = 0; else if
(s.equals(“Goodbye")) index = 2; break;
case 6789: if (s.equals("World")) index = 1; break;
default: break;
}
switch (index) {
case 0: stmts1;
case 1: stmts2;
case 2: stmts3;
default: stmtsD;
}
I now suggest that a post-optimization might then turn this into:
SUCCESS: {
DEFAULT: {
switch (s.hashCode()) {
case 12345: if (s.equals("Hello")) { stmts1; break SUCCESS; } else if
(s.equals(“Goodbye")) { stmts3; break SUCCESS; } else break DEFAULT;
case 6789: if (s.equals("World")) { stmts2; break SUCCESS; } else break
DEFAULT;
default: break DEFAULT;
}
break SUCCESS;
}
do { stmtsD; } while(0);
}
where `SUCCESS` and `DEFAULT` are suitably generated fresh statement labels.
(You might think that simp
Switch translation
The following outlines our story for translating improved switches,
including both the switch improvements coming as part of JEP 325, and
follow-on work to add pattern matching to switches. Much of this has
been discussed already over the last year, but here it is in one place.
# Switch Translation
Maurizio Cimadamore and Brian Goetz
April 2018
## Part 1 -- constant switches
This part 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.
## 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
Re: Switch translation, part 2
Hi all,
while the proposed translation is a good translation by default, when you can
have fallthroughs or guards, if you have none of them, it's not the best
translation.
[CC John Rose because i may say something stupid]
The problem is that the VM doesn't not prune never called cases in a switch
while it does that for the branch of a if, so an if ... else can be faster than
a switch in the case only some cases are exercise at runtime.
Also note that a lot of tableswitch end up to be generated by the VM as if ..
else if you take a look to the generated assembly code because jumping to a
computed address is not free.
So it seems a good idea in the case of an expression switch with no guard to
not generate an indy + a tableswitch but just an indy.
So instead of lowering:
switch (x) {
case T t: A
case U u: B
case V v: C
}
to
int y = indy[bootstrap=typeSwitch(T.class, U.class, V.class)](x)
switch (y) {
case 0: A
case 1: B
case 2: C
}
I propose to lowering it to something similar to the lambda translation:
var expr = indy[bootstrap=exprTypeSwich(1, T.class, U.class, V.class)(x);
and let the bootstrap to do all the lifting.
The first bootstrap argument is the number of the switch in the code, here 1.
With A, B and C being desugared as static methods respectively to
switch$1case$0, switch$1case$1 and switch$1case$2 (i.e. "switch$" +
switchNumber + "case$" + caseNumber.
The bootstrap method exprTypeSwich can work like an inlining cache if the
number of branches actually visited is small, this is interesting because the
performance of an expression switch will be in the same ball park as the
performance of the corresponding virtual call, and if there is too many
branches used, revert to use a new method handle combinator that does a
tableswitch*.
cheers,
Rémi
* the JSR 292 has talked several times to introduce such method handle
combinator.
> De: "Brian Goetz" <brian.go...@oracle.com>
> À: "amber-spec-experts" <amber-spec-experts@openjdk.java.net>
> Envoyé: Lundi 11 Décembre 2017 22:37:57
> Objet: Switch translation, part 2
> # Switch Translation, Part 2 -- type test patterns and guards
> Maurizio Cimadamore and Brian Goetz
> December 2017
> This document examines possible translation of `switch` constructs involving
> `case` labels that include type-test patterns, potentially with guards. Part 3
> will address translation of destructuring patterns, nested patterns, and OR
> patterns.
> ## Type-test patterns
> Type-test patterns are notable because their applicability predicate is purely
> based on the type system, meaning that the compiler can directly reason about
> it both statically (using flow analysis, optimizing away dynamic type tests)
> and dynamically (with `instanceof`.) A switch involving type-tests:
> switch (x) {
> case String s: ...
> case Integer i: ...
> case Long l: ...
> }
> can (among other strategies) be translated into a chain of `if-else` using
> `instanceof` and casts:
> if (x instanceof String) { String s = (String) x; ... }
> else if (x instanceof Integer) { Integer i = (Integer) x; ... }
> else if (x instanceof Long) { Long l = (Long) x; ... }
> Guards
> The `if-else` desugaring can also naturally handle guards:
> switch (x) {
> case String s
> where (s.length() > 0): ...
> case Integer i
> where (i > 0): ...
> case Long l
> where (l > 0L): ...
> }
> can be translated to:
> if (x instanceof String
> && ((String) x).length() > 0) { String s = (String) x; ... }
> else if (x instanceof Integer
> && ((Integer) x) > 0) { Integer i = (Integer) x; ... }
> else if (x instanceof Long
> && ((Long) x) > 0L) { Long l = (Long) x; ... }
> Performance concerns
> The translation to `if-else` chains is simple (for switches without
> fallthrough), but is harder for the VM to optimize, because we've used a more
> general control flow mechanism. If the target is an empty `String`, which
> means
> we'd pass the first `instanceof` but fail the guard, class-hierarchy analysis
> could tell us that it can't possibly be an `Integer` or a `Long`, and so
> there's no need to perform those tests. But generating code that takes
> advantage of this information is more complex.
> In the extreme case, where a switch consists entirely of type test patterns
> for
> final classes, this could be performed as an O(1) operation by hashing. And
> this is a common case involving switches over alternatives in a sum (sealed)
> type. (We probably shouldn't rely on finality at compile time, as this can
> change between compile and run time, but we would like to take advantage of
> this at run time if we can.)
> Finally, the straightforward static translation may miss o
Switch translation, part 2
# Switch Translation, Part 2 -- type test patterns and guards
Maurizio Cimadamore and Brian Goetz
December 2017
This document examines possible translation of `switch` constructs
involving `case` labels that include type-test patterns, potentially
with guards. Part 3 will address translation of destructuring patterns,
nested patterns, and OR patterns.
## Type-test patterns
Type-test patterns are notable because their applicability predicate is
purely based on the type system, meaning that the compiler can directly
reason about it both statically (using flow analysis, optimizing away
dynamic type tests) and dynamically (with `instanceof`.) A switch
involving type-tests:
switch (x) {
case String s: ...
case Integer i: ...
case Long l: ...
}
can (among other strategies) be translated into a chain of `if-else`
using `instanceof` and casts:
if (x instanceof String) { String s = (String) x; ... }
else if (x instanceof Integer) { Integer i = (Integer) x; ... }
else if (x instanceof Long) { Long l = (Long) x; ... }
Guards
The `if-else` desugaring can also naturally handle guards:
switch (x) {
case String s
where (s.length() > 0): ...
case Integer i
where (i > 0): ...
case Long l
where (l > 0L): ...
}
can be translated to:
if (x instanceof String
&& ((String) x).length() > 0) { String s = (String) x; ... }
else if (x instanceof Integer
&& ((Integer) x) > 0) { Integer i = (Integer) x; ... }
else if (x instanceof Long
&& ((Long) x) > 0L) { Long l = (Long) x; ... }
Performance concerns
The translation to `if-else` chains is simple (for switches without
fallthrough), but is harder for the VM to optimize, because we've used a
more general control flow mechanism. If the target is an empty
`String`, which means we'd pass the first `instanceof` but fail the
guard, class-hierarchy analysis could tell us that it can't possibly be
an `Integer` or a `Long`, and so there's no need to perform those tests.
But generating code that takes advantage of this information is more
complex.
In the extreme case, where a switch consists entirely of type test
patterns for final classes, this could be performed as an O(1) operation
by hashing. And this is a common case involving switches over
alternatives in a sum (sealed) type. (We probably shouldn't rely on
finality at compile time, as this can change between compile and run
time, but we would like to take advantage of this at run time if we can.)
Finally, the straightforward static translation may miss opportunities
for optimization. For example:
switch (x) {
case Point p
where p.x > 0 && p.y > 0: A
case Point p
where p.x > 0 && p.y == 0: B
}
Here, not only would we potentially test the target twice to see if it
is a `Point`, but we then further extract the `x` component twice and
perform the `p.x > 0` test twice.
Optimization opportunities
The compiler can eliminate some redundant calculations through
straightforward techniques. The previous switch can be transformed to:
switch (x) {
case Point p:
if (((Point) p).x > 0 && ((Point) p).y > 0) { A }
else if (((Point) p).x > 0 && ((Point) p).y > 0) { B }
to eliminate the redundant `instanceof` (and could be further
transformed to eliminate the downstream redundant computations.)
Clause reordering
The above example was easy to transform because the two `case Point`
clauses were adjacent. But what if they are not? In some cases, it is
safe to reorder them. For types `T` and `U`, it is safe to reorder
`case T` and `case U` if the two types have no intersection; that there
can be no types that are subtypes of them both. This is true when `T`
and `U` are classes and neither extends the other, or when one is a
final class and the other is an interface that the class does not
implement.
The compiler could then reorder case clauses so that all the ones whose
first test is `case Point` are adjacent, and then coalesce them all into
a single arm of the `if-else` chain.
A possible spoiler here is fallthrough; if case A falls into case B,
then cases A and B have to be moved as a group. (This is another reason
to consider limiting fallthrough.)
Summary of if-else translation
While the if-else translation at first looks pretty bad, we are able to
extract a fair amount of redundancy through well-understood compiler
transformations. If an N-way switch has only M distinct types in it, in
most cases we can reduce the cost from _O(N)_ to _O(M)_. Sometimes _M
== N_, so this doesn't help, but sometimes _M << N_ (and sometimes `N`
is small, in which case _O(N)_ is fine.)
Reordering clau
Switch translation, part 1
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
