lookupswitchとtableswitchの違い

昨日に引き続きJavaのswitchをコンパイルしたときに使われるtableswitch命令とlookupswitch命令をそれぞれ見ていく。switch難しいです><

tableswitch命令

tableswitch命令は、switchにおける各ケースをターゲット・オフセットのテーブルに対するインデックスとして効率的に表現出来る場合に用いられる。
(中略)
switchにおけるケースがまばらになっている場合、tableswitch命令におけるテーブル表現では、スペース効率が悪いものとなる。

Java仮想マシン仕様 第2版 p.347


効率的とはいったい何なのか...。とりあえず以下のコードを書いてコンパイルしてみる。

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について理解できたかも。