JDK-8161250 : javac should use indy to compute switch indexes for strings and enums
  • Type: Enhancement
  • Component: tools
  • Sub-Component: javac
  • Priority: P3
  • Status: Open
  • Resolution: Unresolved
  • Submitted: 2016-07-13
  • Updated: 2022-05-05
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
Other
tbdUnresolved
Related Reports
Relates :  
Relates :  
Relates :  
Relates :  
Description
In the class com.sun.tools.javac.comp.Lower, the methods visitStringSwitch and visitEnumSwitch produce code which maps a string or enum to a locally determined index set.

The logic for this is complex, voluminous, and difficult to optimize.  In particular, the map array used for enum switches is not constant (we don't have frozen arrays yet), and the decision logic used to index strings likewise uses non-constant values (the String.hashCode).

Shaping the decision logic for both strings and enums is a job for the JVM runtime, not for the static compiler.  An invokedynamic statement should be "planted" at the head of each such switch to map the expected inputs to the compact index set.  As with JDK-8085796, this will allow the runtime to compose code shapes that the JIT is ready to optimize.  In particular, if mapping arrays are to be used, they can be marked @Stable, which is a trick the static compiler cannot use (in general).

The static arguments to the indy bootstrap (a switch indexer metafactory) will be an ordered sequence of expected case values, or (in the case of enums) their name strings.  At link time, the metafactory can choose the best available decision tactic for the particular strings in question, and the particular optimizations known to the JIT.

Since there was a limit (before Java 11) of about 200 arguments to a BSM, the static compiler may be called upon to construct a local method to invoke the metafactory (or create a jumbo array) using local code.  But in most cases, a single indy instruction is all that's needed.  (This would also be an application of a CONSTANT_Group CP type, if that existed.)
Comments
By the way, indy or condy is not the only way to get this effect. To avoid bootstrapping problems caused by an early run through java.lang.invoke, but get an effect similar to condy, we could also translate a switch to refer to a static-final object in a helper class like this: switch (aString) { case "thing1": … case "thing2": … } => switch ($HC.DISCRIMINATOR.discriminate(aString)) { case 1: case 2: } class $HC { private static final StringDiscriminator DISCRIMINATOR = StringDiscriminator.of("thing1", "thing2"); } That might be a useful fallback for compiling JDK code (kind of like we want a fallback for indified string concat). But, apart from bootstrap issues, condy is probably better than this static-final trick, because it avoids the various confusions and overheads of having helper classes.
05-05-2022

Consider factoring the internal constant arrays to allow probes to complete in fewer cache line touches. In the case of switch over strings, pull the String.hashCode out of the switch operand, and then search for it in a dense int[] array, rather than searching for it indirectly in a String[] array. That way you only need to touch one String instead of log N Strings. Also, consider packing the parallel values and label-indexes array (for 32-bit switching) into a long array. Put the value into the arithmetic high part of each long, and the label-index into the low 32 bits. Run binarySearch over the long[] array, using the 32-bit left shift of the switch key, and pull the result out by casting out the low bits with an (int) cast. The benefit of this is you will avoid touching the header and body (two cache lines) of the secondary array. http://cr.openjdk.java.net/~jrose/jdk/8161250/switch-bootstraps.patch
22-02-2018

Note: Add @Stable to internal arrays so that the JIT can fold through them. One goal is for the JIT to be able to turn switch (n) { ... case M: foo } into foo when n is a constant M (which can arise after inlining the switch from a call site). This folding only works if arrays consulted are @Stable and if the logic is not too complex, and non-stable final fields are not consulted. Suggest making Enum.ordinal trusted (JDK-8161245). Suggest maybe telling the JIT to constant-fold binarySearch as an intrinsic (JDK-8198477). A current limitation of @Stable arrays is that zero values are *not* constant folded. (That is, a @Stable array element is treated as if its array were frozen, but only if it is possible to detect that the element has been changed from its initial default zero value.) If the other optimizations are done, and the code still doesn't fold up, it may be necessary to increment some of the stable array values by some offsets, in order to avoid zero elements. (Sorry.) For a set of patches that roughly express these ideas, see: http://cr.openjdk.java.net/~jrose/jdk/8161250/switch-bootstraps.patch
22-02-2018

FWIW, one factor driving the original strings in switch implementation (JDK-6827009) was ease of testing by having a uniform translation scheme. At least a few alternatives were considered at the time (https://blogs.oracle.com/darcy/entry/project_coin_string_switch_break), but not an indy-based one.
13-07-2016