Compiling large switch statements

[Paul Govereau]

This issue is now being tacked here:

  https://bugs.openjdk.java.net/browse/JDK-8058243

Paul

On 09/10/2014 05:10 PM, Paul Govereau wrote:
> Hello,
>
> I have been looking at the javac code generator, and I think we may be
> doing a poor job of compiling large switch statements because of an
> overly conservative estimate of the cost of the lookupswitch
> instruction. Because we over estimate the cost of a lookupswitch, we
> can generate very large tableswitch instructions: twice the size or
> larger than necessary.
>
> Briefly, javac estimates the total cost of a switch instruction to be:
>
>    space + 3 * time,
>
> and generates the lowest cost instruction. However, javac assumes the
> time cost of a lookupswitch is linear, so we greatly favor the
> tableswitch. (For reference, the relevant code is in the visitSwitch
> method in jvm.Gen).
>
> As an example, consider a large switch containing 50 cases. For the
> tableswitch, the important factor is the range of the matched values,
> because this determines the size of the array needed for the table of
> addresses. Let's call this size S, then the cost of a tableswitch is
> estimated as:
>
>    size (words): 4 + S + 1
>    computation:  3 steps (2 comparisons, 1 load)
>
> For the same code the cost for a lookupswitch is estimated as:
>
>    size(words): 3 + 2 * 50
>    computation: 50 steps (presumably 50 comparisons?)
>
> Note that the lookupswitch match-offset pairs must be sorted. So, it
> stands to reason that to implementation is using (at least) a binary
> search on the sorted list of keys. Therefore, the computation cost
> must be closer to 2*log(50), no?
>
> With the current metrics, we allow a tableswitch instruction with 50
> items to be as large as 976 bytes before we change to the much smaller
> 412 byte lookupswitch. It seems to me the log-estimate is more
> accurate and we should change to the lookupswitch when the tableswitch
> reaches 468 bytes. However, I am only guessing as to how these
> bytecodes are implemented. Does anyone on the list know the details?
>
> Paul