ITコンサルの日常

ITコンサル会社に勤務する普通のITエンジニアの日常です。

switch文は、case式の書き方によって、lookupswitch命令か、tableswitch命令のいずれかにコンパイルされる模様。

Java

のツイートで、Java7では、switchのcase式に文字列が使えることを知りました。
全くJava7押さえてないわ。。現場は未だJava5だし。。。


んで、こないだswitch文はtableswitchにコンパイルされるんだぜってのを確認したし、
switchのcase式に文字列を使った場合、どういうバイトコード吐くのよってのが気になったので、
ググって見つけたページがこちら。
Java SE 7 (1) - 文字列switchのからくり - argius note


中身は良くわかったのですが、lookupswitchなる見慣れない命令が。。
あれ、tableswitchじゃないの？
で、またググってWikipediaにたどり着きました。
Java仮想マシン - Wikipedia

lookupswitch - switch文のcase式の値が不連続である場合に、値を探しながら飛び越し先を探し、飛び越しを行う。
tableswitch - switch文のcase式の値が連続である場合に、（キーがインデクス値、値が飛び越し先番地の）表を使って飛び越しを行う。（高速である）

という記述から察するに、

  • lookupswitch: 線形検索 O(n)

-tableswitch: ハッシュ検索 O(1)

  • tableswitch: 二分検索 O(log2n)

って感じなんじゃないかと思います。
（コメントでツッコミいただきましたので、訂正しました。）


ところで、どういう場合にlookupswitchにコンパイルして、
どういう場合にtableswitchにコンパイルするのだろう？
という疑問が沸いたので、手元の、

>javac -version
javac 1.6.0_26

な環境で試してみました。

case式が2つの場合

ソース
public class test
{
	public static void main(String[] args) {
		switch(0) {
		case 0:
			System.out.println("0");
			break;
		case 1:
			System.out.println("1");
			break;
		}
	}
}
javap -c testの結果
Compiled from "test.java"
public class test extends java.lang.Object{
public test();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return

public static void main(java.lang.String[]);
  Code:
   0:   iconst_0
   1:   lookupswitch{ //2
                0: 28;
                1: 39;
                default: 47 }
   28:  getstatic       #2; //Field java/lang/System.out:Ljava/io/PrintStream;
   31:  ldc     #3; //String 0
   33:  invokevirtual   #4; //Method java/io/PrintStream.println:(Ljava/lang/Str
ing;)V
   36:  goto    47
   39:  getstatic       #2; //Field java/lang/System.out:Ljava/io/PrintStream;
   42:  ldc     #5; //String 1
   44:  invokevirtual   #4; //Method java/io/PrintStream.println:(Ljava/lang/Str
ing;)V
   47:  return
}

switch文は、lookupswitch命令にコンパイルされた。

case式が3つの場合

ソース
public class test
{
	public static void main(String[] args) {
		switch(0) {
		case 0:
			System.out.println("0");
			break;
		case 1:
			System.out.println("1");
			break;
		case 2:
			System.out.println("2");
			break;
		}
	}
}
javap -c testの結果
Compiled from "test.java"
public class test extends java.lang.Object{
public test();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return

public static void main(java.lang.String[]);
  Code:
   0:   iconst_0
   1:   tableswitch{ //0 to 2
                0: 28;
                1: 39;
                2: 50;
                default: 58 }
   28:  getstatic       #2; //Field java/lang/System.out:Ljava/io/PrintStream;
   31:  ldc     #3; //String 0
   33:  invokevirtual   #4; //Method java/io/PrintStream.println:(Ljava/lang/Str
ing;)V
   36:  goto    58
   39:  getstatic       #2; //Field java/lang/System.out:Ljava/io/PrintStream;
   42:  ldc     #5; //String 1
   44:  invokevirtual   #4; //Method java/io/PrintStream.println:(Ljava/lang/Str
ing;)V
   47:  goto    58
   50:  getstatic       #2; //Field java/lang/System.out:Ljava/io/PrintStream;
   53:  ldc     #6; //String 2
   55:  invokevirtual   #4; //Method java/io/PrintStream.println:(Ljava/lang/Str
ing;)V
   58:  return
}

switch文は、tableswitch命令にコンパイルされた。

というわけで

case式が3つになると、より高速なtableswitchに最適化するということらしいです。

ちなみに

		switch(0) {
		case 0:
			System.out.println("0");
			break;
		case 1:
			System.out.println("1");
			break;
		case 4:
			System.out.println("2");
			break;
		}

だと、

   1:   tableswitch{ //0 to 4
                0: 36;
                1: 47;
                2: 66;
                3: 66;
                4: 58;
                default: 66 }

になるんですが、

		case 0:
			System.out.println("0");
			break;
		case 1:
			System.out.println("1");
			break;
		case 5:
			System.out.println("2");
			break;

だと、

   1:   lookupswitch{ //3
                0: 36;
                1: 47;
                5: 58;
                default: 66 }

になったりして、面白いですね！
これも、空き番が3つ以上になったら、連番とみなさないみたいなルールがあるんでしょうか。
javacのソース読まないと分かりませんなあ。。