lookupswitchとtableswitchの違い
昨日に引き続きJavaのswitchをコンパイルしたときに使われるtableswitch命令とlookupswitch命令をそれぞれ見ていく。switch難しいです><
tableswitch命令
tableswitch命令は、switchにおける各ケースをターゲット・オフセットのテーブルに対するインデックスとして効率的に表現出来る場合に用いられる。
(中略)
switchにおけるケースがまばらになっている場合、tableswitch命令におけるテーブル表現では、スペース効率が悪いものとなる。
効率的とはいったい何なのか...。とりあえず以下のコードを書いてコンパイルしてみる。
public class Switch { public static void main(String[] args) { int a = 10; String b; switch(a) { case 0: b = "zero"; break; case 1: b = "one"; break; case 2: b = "two"; break; case 4: b = "four"; break; default: b = "default"; } System.out.println(b); } }
case節に0, 1, 2と連続して並んでいるところに3を飛ばして4を入れた。これをコンパイルすると以下のバイトコードが得られる。
public class Switch extends java.lang.Object{ public Switch(); Code: 0: aload_0 1: invokespecial #8; //Method java/lang/Object."<init>":()V 4: return public static void main(java.lang.String[]); Code: 0: bipush 10 2: istore_1 3: iload_1 4: tableswitch{ //0 to 4 0: 40; 1: 46; 2: 52; 3: 64; 4: 58; default: 64 } 40: ldc #16; //String zero 42: astore_2 43: goto 67 46: ldc #18; //String one 48: astore_2 49: goto 67 52: ldc #20; //String two 54: astore_2 55: goto 67 58: ldc #22; //String four 60: astore_2 61: goto 67 64: ldc #24; //String default 66: astore_2 67: getstatic #26; //Field java/lang/System.out:Ljava/io/PrintStream; 70: aload_2 71: invokevirtual #32; //Method java/io/PrintStream.println:(Ljava/lang/String;)V 74: return }
なるほど。4:のtableswitch命令を見るとソースコードには書かれていない、3の場合のジャンプ先が書かれている(ジャンプ先はdefaultと同様)。tableswitchは開始インデックスと終了インデックスの値を持ち、その後にジャンプ先のアドレスが連続して並んでいるようだ。
87654321 0011 2233 4455 6677 8899 aabb ccdd eeff 0123456789abcdef ------------------------------------------------------------------- 00000230: f700 0200 0300 0000 4b10 0a3c 1baa 0000 ........K..<.... 00000240: 0000 0000 3c00 0000 0000 0000 0400 0000 ....<........... 00000250: 2400 0000 2a00 0000 3000 0000 3c00 0000 $...*...0...<... 00000260: 3612 104d a700 1812 124d a700 1212 144d 6..M.....M.....M
バイナリエディタで見てみよう。0x23dからがtableswitch(0xaa)の命令。0x241-0x244がデフォルトの飛び先(0x0000003c)、0x245-0x248が開始インデックス(0x00000000)、0x249-24cが終了インデックス(0x00000004)。その後は4バイト毎にジャンプ先が並んでいる。
tableswitchの中の実装は見ていないが、実行時はswitchの対象の値から開始インデックスを引いた値*4に対して、オフセット(開始インデックスのジャンプ先が書かれている位置)を足すだけでジャンプ先のアドレスを特定できそうな気がする。tableswitchは二分探索っていう記事を見たが本当か...?
lookupswitch
tableswitchでは連続している値を利用する場合は効率良くジャンプ出来るが、そうでない場合にtableswitchを使うと無駄なジャンプ先のアドレスを定義する必要が出てきて無駄が多くなる。そういう場合に使われるのがlookupswitchだ。
以下のようにcase節が連続でないコードを書いてみる。
public class Switch { public static void main(String[] args) { int a = 10; String b; switch(a) { case 0: b = "zero"; break; case 1000: b = "one"; break; case 50: b = "two"; break; case 800: b = "four"; break; default: b = "default"; } System.out.println(b); } }
これをコンパイルすると以下のバイトコードが得られる。
public class Switch extends java.lang.Object{ public Switch(); Code: 0: aload_0 1: invokespecial #8; //Method java/lang/Object."<init>":()V 4: return public static void main(java.lang.String[]); Code: 0: bipush 10 2: istore_1 3: iload_1 4: lookupswitch{ //4 0: 48; 50: 60; 800: 66; 1000: 54; default: 72 } 48: ldc #16; //String zero 50: astore_2 51: goto 75 54: ldc #18; //String one 56: astore_2 57: goto 75 60: ldc #20; //String two 62: astore_2 63: goto 75 66: ldc #22; //String four 68: astore_2 69: goto 75 72: ldc #24; //String default 74: astore_2 75: getstatic #26; //Field java/lang/System.out:Ljava/io/PrintStream; 78: aload_2 79: invokevirtual #32; //Method java/io/PrintStream.println:(Ljava/lang/String;)V 82: return }
lookupswitch命令には開始/終了インデックスという概念は無く、単純にジャンプ先の数を持ち、その数の分だけキーとジャンプ先のペアを持つ。キーはコンパイル時に昇順にソートして配置される。昇順に配置することで二分探索することが可能になるのでおそらく実行時は二分探索をしている。ただJVMの仕様上は昇順に並べるとしか定義されていない為、どう探索するかは実装によるのだと思う。
87654321 0011 2233 4455 6677 8899 aabb ccdd eeff 0123456789abcdef ------------------------------------------------------------------- 00000230: ff00 0200 0300 0000 5310 0a3c 1bab 0000 ........S..<.... 00000240: 0000 0000 4400 0000 0400 0000 0000 0000 ....D........... 00000250: 2c00 0000 3200 0000 3800 0003 2000 0000 ,...2...8... ... 00000260: 3e00 0003 e800 0000 3212 104d a700 1812 >.......2..M....
バイナリを見てみよう。0x23dがlookupswitch(0xab)だ。0x240-0x243がデフォルトのジャンプ先(0x00000044)、0x245-0x249がジャンプ先の数(0x00000004)、それ以降が4バイトのキーと、4バイトのジャンプ先アドレスのペアが4つ並ぶ。実行時はキーを探索し、マッチしたキーに対応するジャンプ先に飛ぶ。
少しだけswitchについて理解できたかも。