if-statement - 「IF」は高いですか？

Question

私は一生、先生がその日に言ったことを正確に思い出すことはできません。おそらくあなたが知っていることを願っています.

モジュールは「Data Structures and Algorithms」で、彼は次のような内容を教えてくれました。

ステートメントは最もif高価な [何か] です。[何か] が [何か] を登録します。

はい、私には恐ろしい記憶があり、本当に申し訳ありませんが、何時間もグーグルで検索しましたが、何も出てきませんでした. 何か案は？

score 211 · Accepted Answer

非常に低いレベル (ハードウェア内) では、はい、s が高価な場合。その理由を理解するには、パイプラインがどのように機能するかを理解する必要があります。

実行される現在の命令は、通常、命令ポインタ(IP) またはプログラムカウンタ(PC) と呼ばれるものに格納されます。これらの用語は同義ですが、異なるアーキテクチャでは異なる用語が使用されます。ほとんどの命令では、次の命令の PC は、現在の PC に現在の命令の長さを加えたものになります。ほとんどの RISC アーキテクチャでは、命令はすべて一定の長さであるため、PC は一定量だけインクリメントできます。x86 などの CISC アーキテクチャの場合、命令は可変長になる可能性があるため、命令をデコードするロジックは、現在の命令が次の命令の場所を見つけるまでの長さを把握する必要があります。

ただし、分岐命令の場合、次に実行される命令は、現在の命令の次の場所ではありません。分岐は goto です。次の命令がどこにあるかをプロセッサに伝えます。分岐は条件付きまたは無条件のいずれかであり、ターゲットの場所は固定または計算のいずれかです。

条件分岐と無条件分岐は簡単に理解できます。条件分岐は、特定の条件 (ある数値が別の数値と等しいかどうかなど) が成立する場合にのみ実行されます。分岐が発生しない場合、制御は通常のように分岐後の次の命令に進みます。無条件分岐の場合、分岐は常に実行されます。条件付き分岐は、ステートメントとおよびループifの制御テストに現れます。無条件分岐は、無限ループ、関数呼び出し、関数の戻り、ステートメント、悪名高いステートメントなどに現れます (これらのリストはすべてを網羅しているわけではありません)。forwhilebreakcontinuegoto

分岐先も重要な問題です。ほとんどのブランチには、固定されたブランチターゲットがあります。それらは、コンパイル時に固定されるコード内の特定の場所に移動します。これには、ifステートメント、あらゆる種類のループ、通常の関数呼び出しなどが含まれます。 計算済みブランチは、実行時にブランチのターゲットを計算します。これには、switchステートメント (場合によっては)、関数からの戻り、仮想関数呼び出し、および関数ポインター呼び出しが含まれます。

では、これはパフォーマンスにとって何を意味するのでしょうか? プロセッサは、分岐命令がパイプラインに現れるのを確認すると、パイプラインをいっぱいにし続ける方法を理解する必要があります。プログラムストリームで分岐の後に来る命令を把握するには、(1) 分岐が行われるかどうか、および (2) 分岐のターゲットの 2 つを知る必要があります。これを理解することは分岐予測と呼ばれ、難しい問題です。プロセッサが正しく推測した場合、プログラムは全速力で続行します。代わりに、プロセッサが間違って推測した場合は、間違った計算に時間を費やしただけです。パイプラインをフラッシュし、正しい実行パスからの命令で再ロードする必要があります。結論: パフォーマンスが大幅に向上します。

したがって、 if ステートメントが高価である理由は、分岐の予測ミスによるものです。これは最低レベルのみです。高度なコードを書いている場合は、これらの詳細についてまったく心配する必要はありません。これは、パフォーマンスが非常に重要なコードを C またはアセンブリで記述している場合にのみ気にする必要があります。その場合、さらにいくつかの命令が必要な場合でも、分岐のないコードを記述することは、分岐するコードよりも優れていることがよくあります。abs()、min()、などmax()を分岐せずに計算するために実行できる、クールなビット操作のトリックがいくつかあります。

score 22 · Accepted Answer

「高価」は非常に相対的な用語であり、特に「」ステートメントとの関係ifでは、状態のコストも考慮に入れる必要があるためです。これは、いくつかの短い CPU 命令から、リモートデータベースを呼び出す関数の結果のテストまで、さまざまです。

私はそれについて心配しません。組み込みプログラミングを行っていない限り、" " のコストについてまったく気にする必要はないでしょうif。ほとんどのプログラマーにとって、これがアプリのパフォーマンスを左右する要因になることはありません。

score 15 · Accepted Answer

分岐は、特に RISC アーキテクチャのマイクロプロセッサでは、最もコストのかかる命令の 1 つです。これは、多くのアーキテクチャでは、コンパイラがどの実行パスが最も可能性が高いかを予測し、それらの命令を実行可能ファイルの次に配置するため、分岐が発生したときに既に CPU キャッシュにあるためです。分岐が別の方向に進んだ場合、メインメモリに戻って新しい命令をフェッチする必要があります。これにはかなりのコストがかかります。多くの RISC アーキテクチャでは、分岐 (多くの場合 2 サイクル) を除いて、すべての命令が 1 サイクルです。ここでは大きなコストについて話しているわけではないので、心配する必要はありません。また、コンパイラは、99% の確率で、ユーザーが行うよりも優れた最適化を行います。) EPIC アーキテクチャ (Itanium がその例です) の本当に素晴らしい点の 1 つは、分岐の両側からの命令をキャッシュ (および処理を開始) し、分岐の結果が得られると不要なセットを破棄することです。知られています。これにより、予期しないパスに沿って分岐する場合に、典型的なアーキテクチャの余分なメモリアクセスが節約されます。

score 13 · Accepted Answer

セルのパフォーマンスに関するブランチの削除によるパフォーマンスの向上に関する記事を確認してください。もう1つの楽しいものは、リアルタイム衝突検出ブログのブランチレスセレクションに関するこの投稿です。

この質問への回答としてすでに投稿されている優れた回答に加えて、「if」ステートメントは高価な低レベルの操作と見なされますが、高レベルの環境でブランチフリーのプログラミング手法を利用しようとしていることを思い出してください。スクリプト言語やビジネスロジック層（言語に関係なく）などは、途方もなく不適切な場合があります。

ほとんどの場合、プログラムは最初に明確にするために作成し、次にパフォーマンスのために最適化する必要があります。パフォーマンスが最優先される問題領域は数多くありますが、単純な事実として、ほとんどの開発者は、レンダリングエンジンのコアの奥深くで使用するモジュールや、数週間にわたって実行される高性能の流体力学シミュレーションを作成していません。ソリューションが「正しく機能する」ことが最優先事項である場合、最後に頭に浮かぶのは、コード内の条件ステートメントのオーバーヘッドを節約できるかどうかです。

score 10 · Accepted Answer

ifそれ自体は遅くありません。遅さは常に相対的なものです。私の人生では、if ステートメントの「オーバーヘッド」を感じたことはないと思います。パフォーマンスの高いコードを作成する場合は、とにかく分岐を避けたいと思うかもしれません。if遅くするのは、プロセッサがヒューリスティックifなどに基づいてコードをプリロードしていることです。また、パイプラインがマシンコードの分岐命令の直後にコードを実行するのを停止しifます。これは、プロセッサがどのパスが使用されるかをまだ認識していないためです (パイプライン化されたプロセッサでは、複数の命令がインターリーブされて実行されます)。実行されたコードは、逆に実行する必要がある可能性があります (他の分岐が行われた場合は、と呼ばれますbranch misprediction)。またはnoop、これが起こらないように、それらの場所に入力する必要があります。

ifが悪ならswitch悪も、そして&&も||。ご心配なく。

score 7 · Accepted Answer

最新のプロセッサには長い実行パイプラインがあります。つまり、複数の命令がさまざまな段階で同時に実行されます。次の命令が実行を開始したときに、ある命令の結果を常に知っているとは限りません。条件付きジャンプ (if) に遭遇すると、パイプラインが空になるまで待たなければならないことがあり、その後、命令ポインタが進むべき方向を知ることができます。

長い貨物列車だと思います。大量の貨物を直線で速く運ぶことができますが、コーナリングが苦手です。

Pentium 4 (Prescott) には、有名な 31 ステージの長いパイプラインがありました。

ウィキペディアの詳細

score 7 · Accepted Answer

可能な限り低いレベルでif構成されます (特定のアプリ固有のすべての前提条件を計算した後if):

いくつかのテスト命令
テストが成功した場合はコード内のどこかにジャンプし、それ以外の場合は先に進みます。

それに関連する費用:

低レベルの比較 -- 通常は 1 CPU で動作、超安価
潜在的な飛躍 -- 費用がかかる可能性があります

ジャンプが高価な理由:

CPUによってキャッシュされていないことが判明した場合、メモリ内のどこにでもある任意のコードにジャンプできます-メインメモリにアクセスする必要があるため、低速です。
最新の CPU は分岐予測を行います。if が成功するかどうかを推測し、パイプラインで先にコードを実行するため、速度が上がります。予測が失敗した場合、パイプラインによって先に行われたすべての計算を無効にする必要があります。それも高価な操作です

要約すると：

高価になる可能性がある場合は、本当に、本当に、信頼してパフォーマンスを気にする必要があります。
リアルタイムレイトレーサーや生物学的シミュレーションなどを作成している場合にのみ、これを気にする必要があります。現実世界のほとんどでそれを気にする理由はありません。

score 6 · Accepted Answer

6

分岐によって CPU 命令のプリフェッチが停止する可能性がありますか?

于 2008-11-24T20:22:51.707 に答える

score 5 · Accepted Answer

多くの人が指摘しているように、最新のコンピューターでは条件分岐が非常に遅くなる可能性があります。

そうは言っても、if ステートメントには存在しない条件分岐がたくさんあります。コンパイラーが何を考え出すかを常に知ることはできません。また、基本的なステートメントにかかる時間を心配することは、実質的に常に間違っています。する。(コンパイラが確実に生成するものがわかれば、適切な最適化コンパイラを持っていない可能性があります。)

score 4 · Accepted Answer

これが言及している可能性があると私が想像できる唯一のことは、ifステートメントが通常分岐につながる可能性があるという事実です。プロセッサアーキテクチャの仕様によっては、分岐によってパイプラインストールやその他の最適ではない状況が発生する可能性があります。

ただし、これは非常に状況によって異なります。最近のほとんどのプロセッサには、分岐の悪影響を最小限に抑える分岐予測機能があります。もう 1 つの例は、ARM アーキテクチャ (およびおそらく他のアーキテクチャ) が条件付きロジックを処理する方法です。ARM には命令レベルの条件付き実行があるため、単純な条件付きロジックでは分岐が発生しません。条件が満たされない場合、命令は単純に NOP として実行されます。

とはいえ、このようなことを心配する前に、ロジックを正しく理解してください。間違ったコードは、可能な限り最適化されていません。

score 3 · Accepted Answer

CPU は深くパイプライン化されています。分岐命令 (if/for/while/switch/etc) は、CPU が次にロードして実行する命令を実際には認識していないことを意味します。

CPU は何をすべきかを知るのを待っている間に停止するか、または CPU が推測を行います。古い CPU の場合、または推測が間違っている場合は、正しい命令をロードしてロードする間にパイプラインストールが発生する必要があります。CPU によっては、これは 10 ～ 20 命令分のストールに相当する場合があります。

最新の CPU は、適切な分岐予測を行い、複数のパスを同時に実行し、実際のパスのみを保持することで、これを回避しようとします。これは非常に役立ちますが、これまでのところしかできません。

クラスで頑張ってください。

また、実際にこれについて心配する必要がある場合は、おそらく OS 設計、リアルタイムグラフィックス、科学計算、または同様に CPU バウンドの何かを行っているでしょう。悩む前にプロフィール。

score 2 · Accepted Answer

明らかに非効率的ではない、最も明確で、最も単純で、最もクリーンな方法でプログラムを作成してください。これにより、最も高価なリソースであるあなたを最大限に活用できます。プログラムを書いたり、後でデバッグしたり（理解が必要）します。パフォーマンスが十分でない場合は、測定しますボトルネックがどこにあるかを確認し、それらを軽減する方法を確認してください。その際、個々の (ソース) 命令について心配する必要があるのは、ごくまれな場合だけです。パフォーマンスとは、最初の行で適切なアルゴリズムとデータ構造を選択し、慎重にプログラミングし、十分に高速なマシンを取得することです。優れたコンパイラを使用してください。最新のコンパイラが行うコードの再構築の種類を見て驚くでしょう。パフォーマンスのためにコードを再構築することは、一種の最後の手段です。コードはより複雑になり (したがってバグが増え)、変更が難しくなり、全体的により高価になります。

score 0 · Accepted Answer

ALUの使用に関して最も高価ですか？比較する値を格納するためにCPUレジスタを使い果たし、ifステートメントが実行されるたびに値をフェッチして比較するのに時間がかかります。

したがって、その最適化は、ループが実行される前に1つの比較を実行し、結果を変数として格納することです。

足りない単語を解釈しようとしているだけです。

score 0 · Accepted Answer

私はかつて私の友人とこの議論をしました。彼は非常に素朴な円のアルゴリズムを使用していましたが、私の場合は使用したので、私のもの（円の1/8しか計算しない種類）よりも速いと主張しました。結局、ifステートメントはsqrtに置き換えられ、どういうわけかそれはより高速でした。おそらくFPUにsqrtが組み込まれているためですか？

if-statement - 「IF」は高いですか？

18 に答える 18

Related

Reference