JDK-8143859 : branch nests testing for intervals should be converted to internal switch ranges and rebalanced
  • Type: Enhancement
  • Component: hotspot
  • Sub-Component: compiler
  • Affected Version: 9,10
  • Priority: P4
  • Status: Open
  • Resolution: Unresolved
  • Submitted: 2015-11-24
  • Updated: 2021-04-27
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 :  
Description
Sometimes users need to classify an integral value into a series of ranges, much as a switch statement classifies an integer according to a series of points.

The server JIT has internal logic to transform such a computation into a search of a balanced binary tree, but it only uses it for switch bytecodes.  It should also perform this transformation for general nests of ifs and switches, where those nests are all testing the same integral value.

This would allow them to write integer classification code more idiomatically and naturally; without hand optimizing control flow into search trees.  There are two more advantages beyond avoiding hand optimization:  First, the translation could be tuned using on-line profile data (branch and/or value profiling), to avoid testing for values that do not occur frequently in practice.  Second, if the if/switch transformation is performed after loop transformations, then a textually simple loop (in source code) over the classification critical points can be transformed into a finely tuned binary search (in object code).

Internally, the server JIT transforms switch statements into a series of ranges and then (unless the points are compact enough to merit a jump table) emits IR to perform a binary search, classifying the input.  Note that case labels for adjacent values are merged, if they label the same statement.  This means that even today some switches are transformed into interval tests.

Here is an example of a conversation where users are hand optimizing code that should be optimized automatically:

http://mail.openjdk.java.net/pipermail/core-libs-dev/2015-November/036766.html

The critical points of that classification are powers of ten, through the dynamic range of an int or long.  They are most naturally produced by a short "for" loop, which should be unrolled to a series of ifs and then rebalanced.
Comments
Will do.
22-02-2017

Thank you, Doug [~dnsimon]. Could you please notify me once GRAAL has been closed?
22-02-2017

Yes, the GRAAL OpenJDK project should be closed. All active upstream development now happens at https://github.com/graalvm/graal-core. I'll look into what it takes for GRAAL to be closed.
22-02-2017

Thank you, for the clarification, John. Let's consider this issue for Graal then. Regarding the administrative side of proceeding with this issue: I'm not sure if moving this issue over to the "GRAAL" OpenJDK project would keep the issue on the radar. I checked, and as of today the last "actions" for GRAAL were recorded in September 2016 (i.e., more than five months back from now). Instead, I'll keep this issue in OpenJDK, remove the 'c2' label, and add the 'graal' label. I hope that makes sense.
22-02-2017

This RFE should be transferred over to Graal, in which case it could be closed as WNF for C2. The essence of it is that user-specified testing order in a decision tree of repeated comparisons against a single key should be overridden if profiling or other analysis determines that a rebalanced decision tree is likely to reduce the average number of comparisons. Put another way, if the user breaks a switch down into a decision tree, the JIT should build it back up into a switch, if there is a benefit. Users get stuff like this wrong all the time, or they fail to take account of the actual dynamics of the program. Hand-tuned decision trees are about as robust as hand-tuned register allocation.
21-02-2017

Graal also attempts to emit code for switches that aims for the smallest average number of comparisons until a decision is reached (taking profiles into account): http://hg.openjdk.java.net/graal/graal-compiler/file/deb6336662b6/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/SwitchStrategy.java#l506 Like C2, it does not take it does not apply this more generally.
24-11-2015

[~dnsimon], what is Graal doing in this case?
24-11-2015