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

419
Maljam 2016-02-21 15:51.

私は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ます。

理由を知りたいのですが。誰かが光を当てることができますか?それはコンパイラですか、それともハードウェアレベルですか?

編集: 好奇心から...今私は、分岐予測について学んだことを、私はアナログ比較はために表示されるでしょうかと思ったOR Bは、非ゼロであります:

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

更新

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

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

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

4 -一部の人々が含まれるように示唆されたa != 0 & b != 0とは対照的に、a != 0 && b != 0それがより密接に振る舞うだろうと予測して、a*b != 0我々は分岐予測の効果を除去するであろうからです。これが&ブール変数で使用できることを知りませんでした。整数を使用した二項演算にのみ使用されると思いました。

注:私がこれらすべてを検討していたコンテキストでは、intオーバーフローは問題ではありませんが、一般的なコンテキストでは間違いなく重要な考慮事項です。

CPU:Intel 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、混合モード)

5 answers

245
Stephen C 2016-02-21 16:09.

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

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

後者、私は思う:

  if (a != 0 && b != 0)

2つのメモリロードと2つの条件付き分岐にコンパイルされます

  if (a * b != 0)

2つのメモリロード、乗算と1つの条件分岐にコンパイルされます。

ハードウェアレベルの分岐予測が効果的でない場合、乗算は2番目の条件付き分岐よりも高速になる可能性があります。比率を上げると、分岐予測の効果が低下します。

条件分岐が遅い理由は、条件分岐によって命令実行パイプラインが停止するためです。分岐予測とは、分岐がどちらの方向に進むかを予測し、それに基づいて投機的に次の命令を選択することにより、ストールを回避することです。予測が失敗した場合、他の方向の命令がロードされるまでに遅延が発生します。

(注:上記の説明は単純化されすぎています。より正確な説明を得るには、CPUメーカーが提供するアセンブリ言語コーダーおよびコンパイラー作成者向けの資料を参照する必要があります。分岐予測に関するWikipediaページは優れた背景です。)


ただし、この最適化で注意する必要があることが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ます。

70
Boann 2016-02-22 05:50.

あなたのベンチマークにはいくつかの欠陥があり、実際のプログラムについて推測するのに役立たないかもしれないと思います。これが私の考えです:

  • (a|b)!=0どちらかの値がゼロ以外(a+b)!=0どうa != 0 && b != 0(a*b)!=0テストし、両方がゼロ以外どうをテストします。したがって、算術演算のタイミングだけを比較しているわけではありません。条件がより頻繁に真になると、if本体の実行が増え、時間もかかります。

  • (a+b)!=0 合計がゼロになる正と負の値に対して間違った処理を行うため、ここで機能する場合でも、一般的なケースでは使用できません。

  • 同様に、(a*b)!=0オーバーフローした値に対して間違った処理を行います。(ランダムな例:196608 * 327680は0です。これは、実際の結果がたまたま2 32で割り切れるためです。したがって、下位32ビットは0であり、int操作の場合はこれらのビットだけが取得されます。)

  • VMは、外側(fraction)ループの最初の数回の実行中に式を最適化します。これは、fractionが0の場合、分岐がほとんど行われない場合です。fraction0.5から開始すると、オプティマイザは異なることを行う可能性があります。

  • VMがここで配列境界チェックの一部を排除できない限り、境界チェックのために式には他に4つのブランチがあります。これは、低レベルで何が起こっているのかを理解しようとするときの複雑な要因です。2次元配列を2つのフラット配列に分割し、nums[0][i]nums[1][i]を変更すると、異なる結果が得られる可能性がnums0[i]ありnums1[i]ます。

  • CPU分岐予測子は、データ内の短いパターン、または実行されている、または実行されていないすべての分岐の実行を検出します。ランダムに生成されたベンチマークデータは、ソートされた配列の処理が、ソートされていない配列の処理よりも速いのはなぜですか?。実世界のデータに予測可能なパターンがある場合、またはすべてゼロとすべて非ゼロの値が長時間実行される場合、ブランチのコストははるかに低くなる可能性があります。

  • 条件が満たされた後に実行される特定のコードは、ループを展開できるかどうか、使用可能なCPUレジスタ、フェッチされたnums値のいずれかが必要かどうかなどに影響するため、条件自体の評価のパフォーマンスに影響を与える可能性があります。状態を評価した後に再利用されます。ベンチマークでカウンターをインクリメントするだけでは、実際のコードが実行することの完全なプレースホルダーではありません。

  • System.currentTimeMillis()ほとんどのシステムでは、+ /-10ミリ秒より正確ではありません。System.nanoTime()通常はより正確です。

多くの不確実性があり、あるVMまたはCPUで高速なトリックは別のVMまたはCPUで低速になる可能性があるため、この種のマイクロ最適化で明確なことを言うのは常に困難です。64ビットバージョンではなく32ビットHotSpotJVMを実行している場合は、2つの種類があることに注意してください。「クライアント」VMは「サーバー」VMとは異なる(弱い)最適化を持っています。

VMによって生成されたマシンコード逆アセンブルできる場合は、それが何をするのかを推測するのではなく、それを実行してください。

24
Pagefault 2016-02-22 16:43.

私は物事を改善するかもしれないという考えを持っていましたが、ここでの答えは良いです。

2つの分岐と関連する分岐予測が原因である可能性が高いため、ロジックをまったく変更せずに、分岐を1つの分岐に減らすことができる場合があります。

bool aNotZero = (nums[0][i] != 0);
bool bNotZero = (nums[1][i] != 0);
if (aNotZero && bNotZero) { /* Some code */ }

それはまたするために働くかもしれません

int a = nums[0][i];
int b = nums[1][i];
if (a != 0 && b != 0) { /* Some code */ }

その理由は、短絡の規則により、最初のブール値がfalseの場合、2番目のブール値は評価されるべきではないためです。falseであるnums[1][i]かどうかの評価を回避するために、追加のブランチを実行する必要nums[0][i]があります。さて、それnums[1][i]が評価されることを気にしないかもしれませんが、コンパイラは、評価されるときに範囲外またはnullrefをスローしないことを確信できません。ifブロックを単純なブール値に減らすことにより、コンパイラーは、2番目のブール値を不必要に評価しても悪影響がないことを理解するのに十分賢い場合があります。

11
Sanket Gupte 2016-02-21 16:30.

掛け算をすると、1つの数が0であっても、積は0になります。

    (a*b != 0)

製品の結果を評価することにより、0から始まる反復の最初の数回の発生を排除します。その結果、比較は、条件が次の場合よりも少なくなります。

   (a != 0 && b != 0)

すべての要素が0と比較され、評価されます。したがって、必要な時間は短くなります。しかし、2番目の条件がより正確な解決策を与えるかもしれないと私は信じています。

9
StackedCrooked 2016-02-24 15:55.

ランダム化された入力データを使用しているため、ブランチが予測できなくなります。実際には、ブランチは(〜90%)予測可能であることが多いため、実際のコードでは、ブランチフルコードの方が高速である可能性があります。

そうは言った。どうすれa*b != 0ばより速くなるのかわかりません(a|b) != 0。一般に、整数乗算はビット単位のORよりもコストがかかります。しかし、このようなことは時々奇妙になります。たとえば、Gallery of Processor Cache Effectsの「例7:ハードウェアの複雑さ」の例を参照してください。

Related questions

MORE COOL STUFF

「水曜日」シーズン1の中心には大きなミステリーがあります

「水曜日」シーズン1の中心には大きなミステリーがあります

Netflixの「水曜日」は、典型的な10代のドラマ以上のものであり、実際、シーズン1にはその中心に大きなミステリーがあります.

ボディーランゲージの専門家は、州訪問中にカミラ・パーカー・ボウルズが輝くことを可能にした微妙なケイト・ミドルトンの動きを指摘しています

ボディーランゲージの専門家は、州訪問中にカミラ・パーカー・ボウルズが輝くことを可能にした微妙なケイト・ミドルトンの動きを指摘しています

ケイト・ミドルトンは、州の夕食会と州の訪問中にカミラ・パーカー・ボウルズからスポットライトを奪いたくなかった、と専門家は言う.

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンが、オリビア・ワイルドが彼女とハリー・スタイルズとの間の「難しい」が「非常に友好的」な分割を恒久的にすることを望んでいる理由を見つけてください.

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする 

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする&nbsp;

エリザベス女王の死後、ケイト・ミドルトンが舞台裏で「非常に困難な時期」を過ごしていたと伝えられている理由を調べてください.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

パンデミックは終わったかもしれないが、Covid-19 は終わっていない

パンデミックは終わったかもしれないが、Covid-19 は終わっていない

2021 年 6 月 8 日にニューヨーク市で開催された covid-19 パンデミックで亡くなった人々の命を偲び、祝うために、ネーミング ザ ロスト メモリアルズが主催するイベントと行進の最中に、グリーンウッド墓地の正門から記念碑がぶら下がっています。週末、ジョー・バイデン大統領は、covid-19 パンデミックの終息を宣言しました。これは、過去 2 年以上にわたり、公の場でそうするための長い列の中で最新のものです。

デビル・イン・オハイオの予告編は、エミリー・デシャネルもオハイオにいることを明らかにしています

デビル・イン・オハイオの予告編は、エミリー・デシャネルもオハイオにいることを明らかにしています

オハイオ州のエミリー・デシャネル みんな早く来て、ボーンズが帰ってきた!まあ、ショーボーンズではなく、彼女を演じた俳優. エミリー・デシャネルに最後に会ってからしばらく経ちました.Emily Deschanel は、長期にわたるプロシージャルな Bones の Temperance “Bones” Brennan としてよく知られています。

ドナルド・トランプはFBIのマー・ア・ラーゴ襲撃映像をリリースする予定ですか?

ドナルド・トランプはFBIのマー・ア・ラーゴ襲撃映像をリリースする予定ですか?

どうやら、ドナルド・トランプに近い人々は、今月初めにFBIによって家宅捜索された彼のMar-a-Lago財産からの映像を公開するよう彼に勧めています. 前大統領はテープを公開するかどうかを確認していませんが、息子はフォックス・ニュースにそうなるだろうと語った.

Andor は、他の Star Wars ショーから大きな距離を置きます。

Andor は、他の Star Wars ショーから大きな距離を置きます。

アンドールの一場面。数十年前、ジョージ・ルーカスがスター・ウォーズのテレビ番組を制作するのを妨げた主な理由は、お金でした。

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、子供向けのパズルの本の序文を書き、ジョージ王子、シャーロット王女、ルイ王子と一緒にテキストを読むと述べた.

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

Yak's Produce は、数十個のつぶれたメロンを野生動物のリハビリ専門家であるレスリー グリーンと彼女のルイジアナ州の救助施設で暮らす 42 匹の動物に寄付しました。

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

8 枚目のスタジオ アルバムのリリースに向けて準備を進めているデミ ロヴァートは、「スーパー グレート ガイ」と付き合っている、と情報筋は PEOPLE に確認しています。

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

イーサン プラスの誕生日のお祝いは、TLC のウェルカム トゥ プラスビルのシーズン 4 のフィナーレで、戦争中の母親のキム プラスと妻のオリビア プラスを結びつけました。

仕事の生産性を高める 8 つのシンプルなホーム オフィスのセットアップのアイデア

仕事の生産性を高める 8 つのシンプルなホーム オフィスのセットアップのアイデア

ホームオフィスのセットアップ術を極めよう!AppExert の開発者は、家族全員が一緒にいる場合でも、在宅勤務の技術を習得しています。祖父や曽祖父が共同家族で暮らしていた頃の記憶がよみがえりました。

2022 年、私たちのデジタル ライフはどこで終わり、「リアル ライフ」はどこから始まるのでしょうか?

20 年前のタイムトラベラーでさえ、日常生活におけるデジタルおよびインターネットベースのサービスの重要性に驚くことでしょう。MySpace、eBay、Napster などのプラットフォームは、高速化に焦点を合わせた世界がどのようなものになるかを示してくれました。

ニューロマーケティングの秘密科学

ニューロマーケティングの秘密科学

マーケティング担当者が人間の欲望を操作するために使用する、最先端の (気味が悪いと言う人もいます) メソッドを探ります。カートをいっぱいにして 3 桁の領収書を持って店を出る前に、ほんの数点の商品を買いに行ったことはありませんか? あなたは一人じゃない。

地理情報システムの日: GIS 開発者として学ぶべき最高の技術スタック

地理情報システムの日: GIS 開発者として学ぶべき最高の技術スタック

私たちが住んでいる世界を確実に理解するには、データが必要です。ただし、空間参照がない場合、このデータは地理的コンテキストがないと役に立たなくなる可能性があります。

Language