Compiling large switch statements

[Paul Govereau]

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