Fine Tuning Java Code - Inside the Switch Statement
Summary
The switch statement is a potential candidate for optimisation. When using a switch at the source level, maximise the probability of having a tableswitch bytecode (rather than lookupswitch bytecode) by populating as many of the case values as possible.
The switch statement
Tip 1 (switch)
The switch statement is a potential candidate for optimisation. When using a switch at the source level, maximise the probability of having a tableswitch bytecode (rather than lookupswitch bytecode) by populating as many of the case values as possible.
When all case values within the interval [minCaseValue...maxCaseValue] are specified, a tableswitch bytecode is guaranteed, providing optimal performance of the switch statement. When there are missing case values the choice is left to the specific Java compiler in use.
Although there is only one switch statement at the source level, there are two possible switch bytecodes available;
- tableswitch bytecode
- lookupswitch bytecode
Although both bytecodes perform the same function, their implementation is different and this will affect runtime performance. The decision of selecting the appropriate bytecode is taken by the Java compiler.
The tableswitch bytecode works on consecutive values, while the lookupswitch bytecode searches arbitrary values. In terms of runtime implementation, a tableswitch performs an indirect jump using a pre-computed offset, while the lookupswitch searches a set of case values for the correct jump.
As an illustration of the difference at runtime, consider the following code samples;
int i = ...;
switch(i){
case 2 : System.out.println("2");break;
case 0 : System.out.println("0");break;
case 3 : System.out.println("3");break;
case 1 : System.out.println("1");break;
default: System.out.println("i not in [0..3]");
}
The given values are in the range of [0..3] and all the values are given, therefore the Java compiler can use a tableswitch.
.....
1B // 3 : iload_1
AA // 4 : tableswitch
00 00 00 /*padding*/
0000004C /*default goto 50 */
00000000 /*low*/
00000003 /*high*/
0000002B /*case 0 goto 2F */
00000041 /*case 1 goto 45 */
00000020 /*case 2 goto 24 */
00000036 /*case 3 goto 3A */
B2 000F // 24 : getstatic Ljava/io/PrintStream; java/lang/System.out
12 11 // 27 : ldc "2"
B6 0017 // 29 : invokevirtual java/io/PrintStream.println
(Ljava/lang/String;)V
A7 002C // 2C : goto 58
B2 000F // 2F : ....
12 19 // 32 : ....
B6 0017 // 34 : ....
A7 0021 // 37 : ....
......
B2 000F // 3A : ....
......
B2 000F // 45 : ....
......
03 // 58 : ....
......
Notice that the compiler has rearranged the case values in order 0,1,2,3 associating to a jump offset to each value.
Now modify the code slightly by adding another case value with a value radically different from the others - 50.
int i = ...;
switch(i){
case 50:
case 2 : System.out.println("2 or 50");break;
case 0 : System.out.println("0");break;
case 3 : System.out.println("3");break;
case 1 : System.out.println("1");break;
default: System.out.println("i not in [0..3] and i!=50");
}
The case values are now in [0..50], but are not consecutive.
(note that the compiler arranges the case values in order, allowing faster searches than sequential ones. Some non-optimised JVMs will implement lookupswitch as a sequential search).
....
1B // 3 : iload_1
AB // 4 : lookupswitch
00 00 00 /*padding*/
00000060 /*default goto 64 */
00000005 /*npairs*/
00000000 0000003F /*case 0 goto 43 */
00000001 00000055 /*case 1 goto 59 */
00000002 00000034 /*case 2 goto 38 */
00000003 0000004A /*case 3 goto 4E */
00000032 00000034 /*case 50 goto 38 */
B2 000F // 38 : getstatic Ljava/io/PrintStream; java/lang/System.out
12 11 // 3B : ldc 2 or 50
B6 0017 // 3D : invokevirtual java/io/PrintStream.println
(Ljava/lang/String;)V
A7 002C // 40 : goto 6C (offset-10-base = 44)
....
Not only is the lookupswitch slower at runtime (a search is needed), it also takes more room in the classfile! Indeed, each case value is stored in the bytecode, so each entry of a lookupswitch is twice the size of a tableswitch entry. (Smart compilers can take advantage of this, in order to maximise the use of tableswitch, without any bytecode size penalties)
If the number of missing case values is less than the half of the switch value range (max - min case values), a smart JAVA compiler may generate a tableswitch instead of a lookupswitch. An example is as follows;
int i = ...;
switch(i){
case 7 :
case 2 : System.out.println("2 or 7");break;
case 0 : System.out.println("0");break;
case 3 : System.out.println("3");break;
case 1 : System.out.println("1");break;
default: System.out.println("i not in [0..3] and i!=7");
}
Here the case values are in the range [0..7], which is 8 values wide. The switch statement provides the compiler with 5 different case values : 3 are missing (4,5,6) in order to get a tableswitch. However, they are added by the compiler (4,5,6 all branch to the default case), allowing the use of a tableswitch.
....
1B // 3 : iload_1
AA // 4 : tableswitch
00 00 00 /*padding*/
0000005C /*default goto 60 */
00000000 /*low*/
00000007 /*high*/
0000003B /*case 0 goto 3F */
00000051 /*case 1 goto 55 */
00000030 /*case 2 goto 34 */
00000046 /*case 3 goto 4A */
0000005C /*case 4 goto 60 */
0000005C /*case 5 goto 60 */
0000005C /*case 6 goto 60 */
00000030 /*case 7 goto 34 */
B2 000F // 34 : getstatic Ljava/io/PrintStream; java/lang/System.out
12 11 // 37 : ldc 2 or 7
B6 0017 // 39 : invokevirtual java/io/PrintStream.println
(Ljava/lang/String;)V
A7 002C // 3C : goto 68 (offset-10-base = 44)
....
