Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8198477

Arrays.binarySearch on constant array should be optimized by the JIT



    • Type: Enhancement
    • Status: Open
    • Priority: P4
    • Resolution: Unresolved
    • Affects Version/s: 10
    • Fix Version/s: tbd
    • Component/s: hotspot
    • Labels:


      The various kinds of switch statements (strings, enums, non-dense ints, and more) are being code-generated (by javac) through a unified framework that uses Arrays.binarySwitch over constant arrays in order to classify data in log time. (See JDK-8161250.) Even non-dense integer case sequences, formerly handled by lookupswitch, may be translated into a binary search over a sorted array of ints or longs, and mapped to a dense index to a tableswitch.

      See calls to binarySearch in this file:

      This means that new code shapes will hit the JIT which perform binary searching over short int (and also long) arrays. The JIT will lose its ability to prune dead code, if it cannot predict the result of executing the binary search that computes the mapping to the tableswitch index.

      It will sometimes be the case that the JIT will be able to predict the value (or reduced range of values) of a switch value. (This happens if the method containing the switch is inlined into a method which supplies a constant operand to the switch.) If that happens, the JIT should "manually" perform the binarySwitch over the constant index array. (The array can be trusted, as it will probably be defined as @Stable or perhaps frozen.) If the JIT can predict the result of the binarySearch, or if it can predict a reduced range of possible results, it can also predict a subset of live tableswitch control points. This will allow it to fold up dead code, with the usual benefits.


          Issue Links



              Unassigned Unassigned
              jrose John Rose
              0 Vote for this issue
              3 Start watching this issue