読者です 読者をやめる 読者になる 読者になる

Java7のswitch文から得られるバイトコードの考察

仕事ではJava6しか使ってないが(ごめんなさい)、Java7に関する以下の文章を読んでいたらswitch文というものがよく分からなくなった。

Java SE 7 で導入された言語機能の 1 つは、switch 文の判断基準の対象としてプリミティブ型や列挙型と同様に文字列型の変数を使えるようになったことです。

(中略)

一見、switch 文はネストされた if ... else 文に対する構文糖にすぎないように思えます。実際、開発者は、switch 文とネストされた if ... else 文のうち、どちらがコード内での見栄えが良いかを大方の基準として、いずれかを選ぶことが頻繁にあります。しかし、switch 文とネストされた if ... else 文は同じではありません。switch 文にはパフォーマンスと安全性の両方の理由から、switch 文に特有の制約があります。その制約とは、case ラベルは定数値でなければならず、switch のオペランドは定数のように振る舞う型に制限される、というものです。ラベルを定数に制限することで、分岐計算は O(n) ではなく O(1) の演算になります。

言語設計者のノート: 何よりもまず害をなさないことより


えっと...何を言っているのかわからない。実際にコードを書いて確認しよう。


switchの仕組み

以下の簡単なswitch文のソースコードをコンパイルして得られるバイトコードについて考える。

public class Testing {

	public static void main(String[] args) {
		String num = "one";
		int result;

		switch (num) {
		case "zero":
			result = 0;
			break;
		case "one":
			result = 1;
			break;
		case "two":
			result = 2;
			break;
		default:
			result = -1;
			break;
		}

		System.out.println(result);
	}
}


Java7でコンパイルして得られるのは以下のバイトコード。javap -cコマンドで出力する。

Compiled from "Testing.java"
public class Testing extends java.lang.Object{
public Testing();
  Code:
   0:	aload_0
   1:	invokespecial	#8; //Method java/lang/Object."<init>":()V
   4:	return

public static void main(java.lang.String[]);
  Code:
   0:	ldc	#16; //String one
   2:	astore_1
   3:	aload_1
   4:	dup
   5:	astore_3
   6:	invokevirtual	#18; //Method java/lang/String.hashCode:()I
   9:	lookupswitch{ //3
		110182: 44;
		115276: 56;
		3735208: 68;
		default: 95 }
   44:	aload_3
   45:	ldc	#16; //String one
   47:	invokevirtual	#24; //Method java/lang/String.equals:(Ljava/lang/Object;)Z
   50:	ifne	85
   53:	goto	95
   56:	aload_3
   57:	ldc	#28; //String two
   59:	invokevirtual	#24; //Method java/lang/String.equals:(Ljava/lang/Object;)Z
   62:	ifne	90
   65:	goto	95
   68:	aload_3
   69:	ldc	#30; //String zero
   71:	invokevirtual	#24; //Method java/lang/String.equals:(Ljava/lang/Object;)Z
   74:	ifne	80
   77:	goto	95
   80:	iconst_0
   81:	istore_2
   82:	goto	97
   85:	iconst_1
   86:	istore_2
   87:	goto	97
   90:	iconst_2
   91:	istore_2
   92:	goto	97
   95:	iconst_m1
   96:	istore_2
   97:	getstatic	#32; //Field java/lang/System.out:Ljava/io/PrintStream;
   100:	iload_2
   101:	invokevirtual	#38; //Method java/io/PrintStream.println:(I)V
   104:	return

上記のバイトコードを要点だけまとめると

  • 6:でStringのgetHash()を呼び出して文字列のハッシュ値を取り出す
  • 9:でlookupswitch命令を使ってハッシュ値に対応するcase処理を呼び出す
  • caseの飛び先(oneなら45:)で、equalsメソッドを呼び出して一致すれば値を格納、そうでなければデフォルトの処理(95:)へ飛ぶ


「パフォーマンスの面によりcaseが定数値でなければならない」という制約は、Stringに限って言えばequalsメソッドを呼ぶ回数が1回で済むように、予め文字列のハッシュを計算おく為にあるのだと考えられる。

疑問

ここで疑問が出てくる。getHash()が一致するにも関わらずequalsがfalseになるような値があった場合どうなるのか?例えば以下のようなコード。

public class Switch {

	public static void main(String[] args) {
		String hoge = "FB";

		switch (hoge) {
		case "Ea":
			System.out.println("Ea");
			break;
		case "FB":
			System.out.println("FB");
			break;
		case "Hoge":
			System.out.println("Hoge");
			break;
		default:
			System.out.println("DEFAULT");
			break;
		}
	}
}


上記のコードは一見何の変哲も無いコードに見えるが、"Ea"と"FB"のgetHash()の値が衝突(2236)する。先程と同じようなバイトコードが出力されていればハッシュが同じなので"FB"の番地に飛び、switch対象の"FB"と"Ea"とのequalsメソッドが呼ばれてfalseとなり、defaultの番地に飛ばされるはずである。


Compiled from "Switch.java"
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:	getstatic	#16; //Field java/lang/System.out:Ljava/io/PrintStream;
   3:	ldc	#22; //String FB
   5:	invokevirtual	#24; //Method java/lang/String.hashCode:()I
   8:	invokevirtual	#30; //Method java/io/PrintStream.println:(I)V
   11:	getstatic	#16; //Field java/lang/System.out:Ljava/io/PrintStream;
   14:	ldc	#36; //String Ea
   16:	invokevirtual	#24; //Method java/lang/String.hashCode:()I
   19:	invokevirtual	#30; //Method java/io/PrintStream.println:(I)V
   22:	ldc	#22; //String FB
   24:	astore_1
   25:	aload_1
   26:	dup
   27:	astore_2
   28:	invokevirtual	#24; //Method java/lang/String.hashCode:()I
   31:	lookupswitch{ //2
		2236: 56;
		2254917: 77;
		default: 122 }
   56:	aload_2
   57:	ldc	#36; //String Ea
   59:	invokevirtual	#38; //Method java/lang/String.equals:(Ljava/lang/Object;)Z
   62:	ifne	89
   65:	aload_2
   66:	ldc	#22; //String FB
   68:	invokevirtual	#38; //Method java/lang/String.equals:(Ljava/lang/Object;)Z
   71:	ifne	100
   74:	goto	122
   77:	aload_2
   78:	ldc	#42; //String Hoge
   80:	invokevirtual	#38; //Method java/lang/String.equals:(Ljava/lang/Object;)Z
   83:	ifne	111
   86:	goto	122
   89:	getstatic	#16; //Field java/lang/System.out:Ljava/io/PrintStream;
   92:	ldc	#36; //String Ea
   94:	invokevirtual	#44; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   97:	goto	130
   100:	getstatic	#16; //Field java/lang/System.out:Ljava/io/PrintStream;
   103:	ldc	#22; //String FB
   105:	invokevirtual	#44; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   108:	goto	130
   111:	getstatic	#16; //Field java/lang/System.out:Ljava/io/PrintStream;
   114:	ldc	#42; //String Hoge
   116:	invokevirtual	#44; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   119:	goto	130
   122:	getstatic	#16; //Field java/lang/System.out:Ljava/io/PrintStream;
   125:	ldc	#47; //String DEFAULT
   127:	invokevirtual	#44; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   130:	return

}


実際にコンパイルしてみたところ、ハッシュで特定の番地(56:)に飛ぶところまでは同じだが、飛んだ先でequalsとifne命令ででそれぞれ文字列をチェックしている。まあこのくらい当然か。
パフォーマンスだけを考慮するとハッシュだけを利用するのが良さそうに見えるが、安全性を確保(衝突を回避)する為にequalsも並行して使用しているようだ。

後半に書かれているオーダーについては以下のブログが参考になる。自分でもそのうち記事にするかもしれない。
http://d.hatena.ne.jp/taka_2/20110922/p1