1. ホーム

[解決済み】Javaで(a != 0 && b != 0)よりも(a*b != 0)の方が速いのはなぜか?

2022-03-24 04:53:02

疑問点

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 != 0a | b != 0 の場合です。 そこで あり得る ブランチ・プレディクターのロジックに何か巧妙なものがあるのでしょう。 あるいは、他の何かを示している可能性もあります。

(このようなことは、特定のチップのモデル番号やバージョンに特有のものであることに注意してください。 ベンチマークの結果は他のシステムで異なる可能性があります)。

しかし、両者とも、すべての負でない値の ab .