1. ホーム
  2. if-statement

[解決済み] IF」は高いのか?

2022-05-13 07:32:30

質問

その日、先生が何を言ったかどうしても思い出せませんので、あなたが知っていることを期待しています。

モジュールは "Data Structures and Algorithms" で、彼はそのような内容のことを私たちに話しました。

その if ステートメントは、最も高価な [何か] を登録します。[何とか]登録する [何か]を登録します。

はい、私はひどい記憶力を持っていて、本当に本当に申し訳ないのですが、何時間もググっても何も出てきません。何かアイデアはありますか?

どのように解決するのですか?

最も低いレベル(ハードウェアの中)では、そうです。 もし は高価です。 その理由を理解するためには、がどのようなものかを理解する必要があります。 パイプライン がどのように機能するかを理解する必要があります。

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

については ブランチ 命令では、次に実行される命令は、現在の命令の次の位置ではありません。 分岐はゴトであり、次の命令がどこにあるかをプロセッサに伝えます。 分岐には条件付きと無条件があり、ターゲット位置は固定または計算のいずれかにすることができます。

条件付き分岐と無条件分岐は簡単に理解できます。条件付き分岐は、ある条件(ある数字が別の数字と等しいかどうかなど)が成立した場合にのみ実行され、分岐が実行されない場合は通常どおり分岐の次の命令へと制御が進みます。 無条件分岐の場合、分岐は常に行われます。 条件付き分岐は if 文の制御テストと forwhile のループがあります。 無条件分岐は、無限ループ、関数呼び出し、関数戻りなどで現れます。 breakcontinue ステートメント、悪名高い goto ステートメント、その他多数(これらのリストは完全なものではありません)。

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

では、このことはパフォーマンスにとってどのような意味を持つのでしょうか。 プロセッサは、パイプラインに分岐命令が現れると、そのパイプラインをどのように埋めていくかを考える必要があります。 プログラム ストリームで分岐の後に来る命令を把握するために、プロセッサは 2 つのことを知る必要があります。(1)分岐の有無と、(2)分岐先である。 これを把握することを 分岐予測 と呼ばれ、難しい問題です。 プロセッサが正しく推測した場合、プログラムは全速力で実行されます。 もし、プロセッサが が正しくなければ を推測した場合、それは間違ったものを計算するのに時間を費やしただけです。 この場合、パイプラインをフラッシュし、正しい実行パスの命令で再ロードする必要があります。 結論から言うと、大きなパフォーマンスの低下を招きます。

このように、if文が高価なのは、以下の理由によります。 ブランチの予測ミス . これはあくまで最下層での話です。 もしあなたが高レベルのコードを書いているなら、このような詳細を気にする必要は全くありません。 気にする必要があるのは、C やアセンブリで極めてパフォーマンスが重要なコードを書いている場合だけです。 その場合、分岐のないコードを書くと、たとえ数命令多く必要であっても、分岐するコードより優れていることが多いのです。 次のような計算をするために、ビットを操作するクールなトリックがあります。 abs() , min() そして max() を分岐させることなく使用できます。