☰

Java では (a*b != 0) が (a != 0 && b != 0) よりも速いのはなぜですか? 質問する

tag-icon • tag-icon java performance processing-efficiency microbenchmark branch-prediction
Java では (a*b != 0) が (a != 0 && b != 0) よりも速いのはなぜですか? 質問する

私は Java でコードを書いていますが、ある時点で、プログラムの流れは、2 つの int 変数「a」と「b」がゼロ以外であるかどうかによって決まります (注: 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% を超える場合、a*b != 0以下よりも高速であることを示していますa!=0 && b!=0。

a AND b がゼロ以外の場合の結果のグラフ

理由を知りたいです。誰か教えていただけますか? コンパイラの問題ですか、それともハードウェア レベルの問題ですか?

編集: 好奇心から...分岐予測について学んだので、aまたはb がゼロ以外の場合のアナログ比較で何が表示されるのか疑問に思いました。

a または b がゼロでないグラフ

予想どおり分岐予測の効果は同じですが、興味深いことにグラフは X 軸に沿って多少反転しています。

アップデート

1-!(a==0 || b==0)何が起こるかを確認するために分析を追加しました。

2-分岐予測について学んだ後、好奇心から、a != 0 || b != 0と(a+b) != 0も含めました。しかし、これらは他の式と論理的に同等ではありません。なぜなら、 true を返すには、 a OR b のみがゼロ以外である必要があるため、処理効率を比較することを意図していないからです。(a|b) != 0

3- 分析に使用した実際のベンチマークも追加しました。これは、任意の int 変数を反復するだけです。

a != 0 & b != 04-ではなくを含めることを提案する人もいました。これは、分岐予測の効果がなくなるため、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、混合モード)

ベストアンサー1

私は、ベンチマークに欠陥があるかもしれないという問題を無視し、結果を額面通りに受け止めています。

それはコンパイラですか、それともハードウェア レベルですか?

後者については、私はこう思います。

  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。

おすすめ記事