[解決済み】Javaで(a != 0 && b != 0)よりも(a*b != 0)の方が速いのはなぜか?
疑問点
Javaでコードを書いているのですが、ある時点で、2つのint変数、"a"と"b"が0以外かどうかで、プログラムの流れが決まります(注:aとbは決して負ではなく、整数のオーバーフロー範囲内でもありません)。
で評価できる。
if (a != 0 && b != 0) { /* Some code */ }
または、その代わりに
if (a*b != 0) { /* Some code */ }
そのコード片は1回の実行で何百万回も実行されることが予想されるので、どちらが速いのか気になったのです。また、配列のスパース性(データの割合=0)が結果にどのような影響を与えるかも気になりました。
long time;
final int len = 50000000;
int arbitrary = 0;
int[][] nums = new int[2][len];
for (double fraction = 0 ; fraction <= 0.9 ; fraction += 0.0078125) {
for(int i = 0 ; i < 2 ; i++) {
for(int j = 0 ; j < len ; j++) {
double random = Math.random();
if(random < fraction) nums[i][j] = 0;
else nums[i][j] = (int) (random*15 + 1);
}
}
time = System.currentTimeMillis();
for(int i = 0 ; i < len ; i++) {
if( /*insert nums[0][i]*nums[1][i]!=0 or nums[0][i]!=0 && nums[1][i]!=0*/ ) arbitrary++;
}
System.out.println(System.currentTimeMillis() - time);
}
そして結果は、"a" や "b" が 0 になることを期待すると、~3%以上の確率で 0 になることがわかりました。
a*b != 0
よりも高速です。
a!=0 && b!=0
:
その理由が気になる。どなたか教えていただけませんか?コンパイラに原因があるのでしょうか、それともハードウェアレベルに原因があるのでしょうか?
編集する 興味本位で言うと... 分岐予測について知った今、アナログ比較で何を示すのかというと OR bが0でない場合。
分岐予測の効果は予想通りですが、面白いことに、グラフがX軸に沿って多少反転しています。
更新情報
を追加しました。
!(a==0 || b==0)
を解析に追加して、何が起こるか見てみましょう。
2- また、私は
a != 0 || b != 0
,
(a+b) != 0
と
(a|b) != 0
は、分岐予測について学んだ後、興味本位で使ってみました。しかし、これらは他の表現と論理的に等価ではありません。
または
bは0以外でないと真を返さないので、処理効率で比較するものではありません。
3- 実際に解析に使用したベンチマークも追加しました。これは、任意のint型変数を反復しているだけです。
4- 何人かの人は
a != 0 & b != 0
とは対照的に
a != 0 && b != 0
に近い挙動を示すだろうという予測で
a*b != 0
というのも、分岐予測効果を取り除くことができるからです。私は知らなかったのですが
&
はブーリアン変数にも使えるんですね!整数の二項演算にしか使えないと思っていました。
注:私が考えていた文脈では、intのオーバーフローは問題ではありませんが、一般的な文脈では間違いなく重要な検討事項です。
CPU インテル Core i7-3610QM @ 2.3GHz
Javaバージョン:1.8.0_45
Java(TM) SE ランタイム環境 (ビルド 1.8.0_45-b14)
Java HotSpot(TM) 64ビットサーバーVM(ビルド25.45-b02、ミックスモード)。
解決するには?
あなたのベンチマークが問題を無視している かもしれない には欠陥があり、その結果を額面通りに受け取っています。
コンパイラのせいなのか、ハードウェアレベルのせいなのか。
その後者だと思います。
if (a != 0 && b != 0)
は、2つのメモリロードと2つの条件分岐にコンパイルされます。
if (a * b != 0)
は、2つのメモリロード、乗算、1つの条件分岐にコンパイルされます。
ハードウェアレベルの分岐予測が有効でない場合、2つ目の条件分岐よりも乗算の方が高速になる可能性が高いです。 比率を上げると......分岐予測が効かなくなる。
条件分岐が遅くなるのは、命令実行パイプラインがストールしてしまうからです。 分岐予測は、分岐の方向を予測し、それに基づいて次の命令を推測的に選択することで、ストールを回避するものである。 予測に失敗した場合は、反対方向の命令がロードされるまでの間、遅延が発生する。
(注:上記の説明は簡略化しすぎています。 より正確な説明は、CPUメーカーがアセンブリ言語のコーダーやコンパイラー向けに提供している文献を参照する必要があります。 ウィキペディアの ブランチプレディクター は良い背景です)。
ただし、この最適化で気をつけなければならないことが1つあります。 の値がありませんか?
a * b != 0
は間違った答えを与えるでしょうか? 積を計算すると整数のオーバーフローが発生するような場合を考えてみましょう。
アップデイト
グラフは、私が言ったことを裏付ける傾向にあります。
-
また、条件分岐には、"分岐予測"効果もあります。
a * b != 0
の場合、それがグラフに表れています。 -
X軸0.9を超えて投影すると、1)約1.0で合流し、2)合流点はX=0.0のときとほぼ同じY値になりそうです。
アップデイト2
のカーブが違う理由がわからない。
a + b != 0
と
a | b != 0
の場合です。 そこで
あり得る
ブランチ・プレディクターのロジックに何か巧妙なものがあるのでしょう。 あるいは、他の何かを示している可能性もあります。
(このようなことは、特定のチップのモデル番号やバージョンに特有のものであることに注意してください。 ベンチマークの結果は他のシステムで異なる可能性があります)。
しかし、両者とも、すべての負でない値の
a
と
b
.
関連
-
[解決済み] Eclipse デフォルトのフォント名
-
[解決済み] JOGLまたはLWJGLの既成のプロジェクト
-
[解決済み] 文字列の巻き方
-
[解決済み] この2回(1927年)を引き算すると、なぜおかしな結果になるのでしょうか?
-
[解決済み] JavaでInputStreamを読み込んでStringに変換するにはどうすればよいですか?
-
[解決済み] JavaでNullPointerExceptionを回避する方法
-
[解決済み] JavaにおけるHashMapとHashtableの違いは何ですか?
-
[解決済み] B "の印刷が "#"の印刷より劇的に遅いのはなぜですか?
-
[解決済み] 要素ごとの加算は、結合ループよりも分離ループの方がはるかに高速なのはなぜですか?
-
[解決済み] <は<=より速いのか?
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン
おすすめ
-
[解決済み] パラメータ[変数]の不正な修飾子;finalのみが許可される[closed]。
-
[解決済み] Oracle DB : java.sql.SQLException: 閉じた接続
-
[解決済み] Java UnknownFormatConversionException
-
[解決済み] Java Swingで複数のボタンに対して複数のActionListenersを追加する方法
-
[解決済み] javac ソースファイルが見つかりません
-
[解決済み] javax.mail.MessagingException: SMTPホストに接続できませんでしたか?
-
[解決済み] Javaにおけるシンボリック参照
-
[解決済み] java.sql.SQLRecoverableException: IO エラーです。NL Exceptionが発生しました
-
[解決済み] Javaコンパイラーエラー:ステートメントではありません
-
[解決済み] GCC 5.4.0での高価なジャンプ