はじめに
どうしてもfor文の中でif文の分岐を入れなければならない場合
多く入るであろう分岐先処理をif文直下のtrueの方に書くか
それとも、else文のfalseの方に書くか
どっちの方が早いのか疑問に思ったので検証してみます。
先に結論
先に結論から。
どっちに書いても速度は変わらない。
目次
背景
来年から社会人になるので、会社の研修で使うと言われたJavaを最近勉強しています。
そしたら演習問題で、for文の中にif文を使って毎回2択の分岐判定をしなければならない問題が出てきました。
それを見て、以前スーパースカラプロセッサについて大学で授業を受けていた時のことを思い出しました。
分岐予測をして高速化を図る
これはプロセッサの中の話だったので、単純にプログラミンゲで出てくる分岐（ifやswitch文）だけではなく
ジャンプ命令を使うfor文やwhile文もここで言う分岐予測にあたると思います。
なので、この分岐予測による高速化というのは
forとかのループが出てきたときに「次はきっとtrueだろう」と予測して
判定結果が出る前に先にそっちを実行しておく。
そうすれば判定結果が出てから実行するより早いよね（予測が当たれば）ということなのですが
じゃあ、if文の時も分岐予測でどっちかを先に実行していれば
予測している分岐先に、たくさん入る分岐先の処理を書いた方が実行速度早いんじゃね
と思ったわけです。
環境
- Windows 10
- Java
> java -version
openjdk 17.0.1 2021-10-19
OpenJDK Runtime Environment Temurin-17.0.1+12 (build 17.0.1+12)
OpenJDK 64-Bit Server VM Temurin-17.0.1+12 (build 17.0.1+12, mixed mode, sharing)
実験コード
先にプログラムの全体を出します。
前半と後半でそれぞれ「1. 検証」と「2. 分析」の2つに大きく分かれています。
public class test1 {
static double sqr( double x ){
return x * x;
}
public static void main(String[] args) {
int N = Integer.parseInt(args[0]); // 試行回数
int[] data = new int[N]; // N 回試行したときの平均時間
int count_true = 0; // true に入った回数
int count_false = 0; // false に入った回数
long start_time;
long time;
// 1. 検証
for (int n=0; n<N; n++){
count_true = 0;
count_false = 0;
start_time = System.currentTimeMillis(); // 時間計測:開始
//////// ↓ 検証処理 ↓ ////////
for (int i=0; i<Integer.MAX_VALUE/10; i++){
if (i == Integer.MAX_VALUE/10-1) count_true += 1; // 分岐（True）
else count_false += 1; // 分岐（False）
}
//////// ↑ ここまで ↑ /////////
time = System.currentTimeMillis() - start_time; // 時間計測:終了
data[n] = (int)time;
}
System.out.println("Trueに入った回数: " + count_true);
System.out.println("Falseに入った回数: " + count_false);
// 2. 分析（ここからは平均, 分散, 標準偏差を求める）
double sum = 0.0;
for (int i = 1; i < N; i++){
sum += data[i]; // データの和
// System.out.println("data[" + i + "] = " + data[i] + " [ms]");
}
N -= 1; // 最初だけめちゃくちゃ早く終わるから計算から除外
double mean = sum / N; // 平均
double ssum = 0.0;
for (int i = 0; i < N; i++){
ssum += sqr(data[i] - mean); // 2乗和
}
double variance = ssum / N; // 分散
double sd = Math.sqrt(variance); // 標準偏差
System.out.printf("平均: %.3f [ms]\n", mean);
System.out.printf("標準偏差: %.3f [ms]", sd);
}
}
コードの説明
前半の
// 1. 検証
. . .
. . .
という部分に検証用の処理が書かれています。
//////// ↓ 検証処理 ↓ ////////
for (int i=0; i<Integer.MAX_VALUE/10; i++){
if (i == Integer.MAX_VALUE/10-1) count_true += 1; // 分岐（True）
else count_false += 1; // 分岐（False）
}
//////// ↑ ここまで ↑ /////////
っていう部分が検証処理の核になる部分です。
forループの中で毎回if文を使って条件分岐の判定をさせています。（Integer.MAX_VALUE/10回：MAX_VALEまでやってると長いため/10してる）
見たらわかりますが, 最後の1回だけTrueに入って他は全部Falseに入るようになっています。
一応それぞれに入った回数のカウントも行っています。
この条件判定の == を != と書き変えることでTrueに多く入るかFalseに多く入るかを切り替えます
そして、その外側にあるforループで同じ検証を何回も試行しています。
試行回数$N$はユーザーの入力で決定します。
後半にある
// 2. 分析（ここからは平均, 分散, 標準偏差を求める）
. . .
. . .
という部分以降はただの分析用の計算です。
$N$回試行の平均と標準偏差を求めています。
最初の１試行目だけなぜか実行時間が圧倒的に短かったのでそこは計算から除外しています。
なぜかわかる方がいたらご教授ください。
検証
Falseに多く入るとき
1000回試行で実行
> java test1 1000
Trueに入った回数: 1
Falseに入った回数: 214748363
平均: 140.875 [ms]
標準偏差: 11.516 [ms]
Trueに多く入るとき
if (i == Integer.MAX_VALUE/10-1) count_true += 1; // 分岐（True）
↓↓変更↓↓
if (i != Integer.MAX_VALUE/10-1) count_true += 1; // 分岐（True）
1000回試行で実行
> java test1 1000
Trueに入った回数: 214748363
Falseに入った回数: 1
平均: 139.842 [ms]
標準偏差: 11.237 [ms]
結果まとめ
| 平均 [ms] | ±標準偏差 [ms] | |
|---|---|---|
| True | 139.842 | ±11.237 |
| False | 140.875 | ±11.516 |
変わらないですね。
この1000回試行自体を何回かやったりしてみたのですが
意外とばらつきがあって、試行回数を増やすだけ平均が収束するということはなさそうでした。
それでも大体2[ms]前後のずれだったので, まぁ標準偏差以内には全然収まっていて誤差なのかなぁ、といった印象です。
結論
何回もif文を通るときに
多く通る処理をTrueに書くかFalseに書くか。
どちらに書いても変わらないから、可読性重視で決めればいい。
おわりに
分岐予測の話に戻りますが
CPUに実行してもらう命令列を作っているのはコンパイラであって
多分この結果ってコンパイラの性能が優秀だからどっちでも変わらないんじゃないかなと
何となく思います。（確信は全くない）
なので逐次実行しているPythonとかだと違いが出るかもしれません。
今回は記事書くのが不慣れすぎて時間かかって疲れたので、この先はまた気が向いたら検証してみます。