JVM switch文とバイトコード

Java で switch 文を書くと、バイトコードとして tableswitch か lookupswitch が生成される。tableswitch 生成条件と、tableswitch と lookupswitch の挙動について調べた。参考にしたコードは OpenJDK の jdk7u。

tableswitch と lookupswitch

Chapter 3. Compiling for the Java Virtual Machine
Chapter 6. The Java Virtual Machine Instruction Set
Chapter 6. The Java Virtual Machine Instruction Set

tableswitch は、ほぼ連続した case に対して高速にジャンプ先を見つける命令。lookupswitch はとびとびの case に対して空間効率を重視してジャンプ先を見つける命令。

tableswitch / lookupswitch 生成条件

jdk7u/jdk/src/share/classes/sun/tools/asm/Instruction.java より、siwtch文に対して、case句の最大・最小の幅を range, case句の数数を entries とすると、

4 + range <= (3 + 2 * entries) * SWITCHRTIO

が成り立つときに tableswitch が生成され、成り立たないときは lookupswitch が生成される。SWITCHRATIO はデフォルトで 1.5。以下該当部分のコード。

283             // Compute the approximate sizes of a tableswitch and a
284             // lookupswitch.  Decide which one we want to generate.
285 
286             long range = (long)sw.maxValue - (long)sw.minValue + 1;
287             long entries = sw.tab.size();
288 
289             long tableSize = 4 + range;
290             long lookupSize = 3 + 2 * entries;
291 
292             if (tableSize <= lookupSize * SWITCHRATIO) {
293                 opc = opc_tableswitch;
294             } else {
295                 opc = opc_lookupswitch;
296             }

tableswitch / lookupswitch の挙動

repos/jdk7u/hotspot/src/share/vm/interpreter/bytecodeInterpreter.cpp より抜粋。UPDATE_PC_AND_TOS で pc を更新している。その更新量となるskipが tableswitch では分岐一発で、lookupswitch では線形検索をしているように見える(が、bytecode - Difference between JVM'a LookupSwitch and TableSwitch? - Stack Overflowで lookupswitch が O(log n) だったらしい?)。

tableswitch

1442       CASE(_tableswitch): {
1443           jint* lpc  = (jint*)VMalignWordUp(pc+1);
1444           int32_t  key  = STACK_INT(-1);
1445           int32_t  low  = Bytes::get_Java_u4((address)&lpc[1]);
1446           int32_t  high = Bytes::get_Java_u4((address)&lpc[2]);
1447           int32_t  skip;
1448           key -= low;
1449           skip = ((uint32_t) key > (uint32_t)(high - low))
1450                       ? Bytes::get_Java_u4((address)&lpc[0])
1451                       : Bytes::get_Java_u4((address)&lpc[key + 3]);
1452           // Does this really need a full backedge check (osr?)
1453           address branch_pc = pc;
1454           UPDATE_PC_AND_TOS(skip, -1);
1455           DO_BACKEDGE_CHECKS(skip, branch_pc);
1456           CONTINUE;
1457       }

lookupswitch

1461       CASE(_lookupswitch): {
1462           jint* lpc  = (jint*)VMalignWordUp(pc+1);
1463           int32_t  key  = STACK_INT(-1);
1464           int32_t  skip = Bytes::get_Java_u4((address) lpc); /* default amount */
1465           int32_t  npairs = Bytes::get_Java_u4((address) &lpc[1]);
1466           while (--npairs >= 0) {
1467               lpc += 2;
1468               if (key == (int32_t)Bytes::get_Java_u4((address)lpc)) {
1469                   skip = Bytes::get_Java_u4((address)&lpc[1]);
1470                   break;
1471               }
1472           }
1473           address branch_pc = pc;
1474           UPDATE_PC_AND_TOS(skip, -1);
1475           DO_BACKEDGE_CHECKS(skip, branch_pc);
1476           CONTINUE;
1477       }