ITコンサルの日常

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

if-elseの最適化(フラットなif-else if-elseを、二分木に展開)

Java

テキスト

ハイパフォーマンスJavaScript

ハイパフォーマンスJavaScript

お題

4.2.2 if-elseの最適化に載ってるのですが、

		if(value == 0) {
			return hoge + "a";
		} else if(value == 1) {
			return hoge + "b";
		} else if(value == 2) {
			return hoge + "c";
		} else if(value == 3) {
			return hoge + "d";
		} else if(value == 4) {
			return hoge + "e";
		} else if(value == 5) {
			return hoge + "f";
		} else if(value == 6) {
			return hoge + "g";
		} else if(value == 7) {
			return hoge + "h";
		} else if(value == 8) {
			return hoge + "i";
		} else if(value == 9) {
			return hoge + "j";
		} else {
			return hoge + "k";
		}

というif文を書くよりも、

		if(value < 6) {
			if(value < 3) {
				if(value == 0) {
					return hoge + "a";
				} else if(value == 1) {
					return hoge + "b";
				} else {
					return hoge + "c";
				}
			} else {
				if(value == 3) {
					return hoge + "d";
				} else if(value == 4) {
					return hoge + "e";
				} else {
					return hoge + "f";
				}	
			}
		} else {
			if(value < 8) {
				if(value == 6) {
					return hoge + "g";
				} else {
					return hoge + "h";
				}
			} else {
				if(value == 8) {
					return hoge + "i";
				} else if(value == 9) {
					return hoge + "j";
				} else {
					return hoge + "k";
				}
			}
		}

というif文を書いた方が、条件分岐の判断回数が少ないので速いよ。という話。

計ってみた

Javaでもそうなるのかどうなのか、試しに計ってみた on Macbook Air。

$ java -version
java version "1.6.0_24"
Java(TM) SE Runtime Environment (build 1.6.0_24-b07-334-10M3326)
Java HotSpot(TM) 64-Bit Server VM (build 19.1-b02-334, mixed mode)

- hoge(フラット版) hoge2(二分木版) hoge3(switch版)
1回目 854 658 427
2回目 718 724 423
3回目 849 681 426
4回目 824 720 427
5回目 785 626 429
平均 806[ms] 681.8[ms] 426.4[ms]

というわけで、二分木版の方が約18%速いという結果になりました。
いやこれはマジで感動したよ！
でも、SIer的には、可読性が落ちるのでNGっぽい気がしますけどね。
まあ、その前にswitch使えっていう。。


(追記)
switchも計ってみました。
ていうかswitchの圧勝ｗ
そもそもif-else if-elseを10個も並べるケースってあるんだろうか。
あんまり実用的じゃない気がしてきた。。

完全なソース

なんか文字列連結しているのは、そのままvalueと同じ値をリテラルで返す実装だと、
最適化が効いているのか、速攻でプログラムが終了してしまったため。

public class test
{
	public static void main(String[] args) throws Exception {
		long startTime = System.currentTimeMillis();
		
		for(int i=0; i<1000000; i++) {
			hoge(i % 11);
		}
		
		long endTime = System.currentTimeMillis();
		System.out.println(endTime - startTime);


		long startTime2 = System.currentTimeMillis();
		
		for(int i=0; i<1000000; i++) {
			hoge2(i % 11);
		}
		
		long endTime2 = System.currentTimeMillis();
		System.out.println(endTime2 - startTime2);

		long startTime3 = System.currentTimeMillis();
		
		for(int i=0; i<1000000; i++) {
			hoge3(i % 11);
		}
		
		long endTime3 = System.currentTimeMillis();
		System.out.println(endTime3 - startTime3);
	}

	private static String hoge(int value) {
		String hoge = value + "";
		if(value == 0) {
			return hoge + "a";
		} else if(value == 1) {
			return hoge + "b";
		} else if(value == 2) {
			return hoge + "c";
		} else if(value == 3) {
			return hoge + "d";
		} else if(value == 4) {
			return hoge + "e";
		} else if(value == 5) {
			return hoge + "f";
		} else if(value == 6) {
			return hoge + "g";
		} else if(value == 7) {
			return hoge + "h";
		} else if(value == 8) {
			return hoge + "i";
		} else if(value == 9) {
			return hoge + "j";
		} else {
			return hoge + "k";
		}
	}

	private static String hoge2(int value) {
		String hoge = value + "";
		
		if(value < 6) {
			if(value < 3) {
				if(value == 0) {
					return hoge + "a";
				} else if(value == 1) {
					return hoge + "b";
				} else {
					return hoge + "c";
				}
			} else {
				if(value == 3) {
					return hoge + "d";
				} else if(value == 4) {
					return hoge + "e";
				} else {
					return hoge + "f";
				}	
			}
		} else {
			if(value < 8) {
				if(value == 6) {
					return hoge + "g";
				} else {
					return hoge + "h";
				}
			} else {
				if(value == 8) {
					return hoge + "i";
				} else if(value == 9) {
					return hoge + "j";
				} else {
					return hoge + "k";
				}
			}
		}
	}

	private static String hoge3(int value) {
		String hoge = value + "";
		
		switch(value) {
			case 0:
				return hoge + "a";
			case 1:
				return hoge + "b";
			case 2:
				return hoge + "c";
			case 3:
				return hoge + "d";
			case 4:
				return hoge + "e";
			case 5:
				return hoge + "f";
			case 6:
				return hoge + "g";
			case 7:
				return hoge + "h";
			case 8:
				return hoge + "i";
			case 9:
				return hoge + "j";
			default:
				return hoge + "k";
		}
	}
}