c# - case ラベルの順序は、switch ステートメントの効率にどの程度影響しますか?

Question

検討：

if (condition1)
{
    // Code block 1
}
else
{
    // Code block 2
}

condition1それが大部分の時間になることがわかっている場合はtrue、次の代わりに、書かれたとおりにロジックをコーディングする必要があります。

if (!condition1)
{
    // Code block 2
}
else
{
    // Code block 1
}

2番目のコードブロックへのペナルティを回避するためjumpです（注：アセンブリ言語の知識は限られています）。このアイデアはswitchステートメントやcaseラベルに引き継がれますか?

switch (myCaseValue)
{
    case Case1:
        // Code block 1
        break;

    case Case2:
        // Code block 2
        break;

    // etc.
}

caseいずれかのケースがより頻繁に発生することがわかっている場合、より効率的になるようにラベルの順序を並べ替えることができますか? するべきか？私のコードでは、コードを読みやすくするために、特に考えずに大文字と小文字のラベルをアルファベット順に並べています。これはマイクロ最適化ですか？

score 33 · Accepted Answer

x86やx86_64などの最新のハードウェアに関するいくつかの事実：

無条件に取得されたブランチには、デコード以外の追加コストはほとんどありません。数値が必要な場合は、約1/4クロックサイクルです。
正しく予測された条件付きブランチには、追加コストはほとんどありません。
正しく予測されなかった条件付き分岐には、プロセッサパイプラインの長さに等しいペナルティがあります。これは、ハードウェアにもよりますが、約12〜20クロックです。
予測メカニズムは非常に洗練されています。反復回数が少ないループ（たとえば、コア2では最大64）を完全に予測できます。「taken-taken-nottaken-taken」のような小さな繰り返しパターンは、長すぎなければ予測できます（Core2のIIRC 6）。

Agner Fogsの優れたマニュアルで、分岐予測の詳細を読むことができます。

Switchステートメントは通常、コンパイラによってジャンプテーブルに置き換えられます。ほとんどの場合、ケースの順序はまったく違いはありません。間接ジャンプの予測メカニズムもあります。

したがって、問題は、ジャンプが行われる可能性が高いかどうかではなく、少なくともコードを実行する予定のハードウェアについては、ジャンプが十分に予測可能かどうかです。これは簡単な質問ではありません。ただし、ランダム（または疑似ランダム）条件に依存する分岐がある場合は、可能であれば、分岐のないステートメントとして再定式化することを試みることができます。

score 7 · Accepted Answer

if ステートメントに関するあなたの結論は、私がよく知っているほとんどのハードウェアには当てはまりません。問題は、ジャンプしていることではなく、分岐していることです。比較の結果に応じて、コードは 2 つの異なる方向に進む可能性があります。これにより、最新のほとんどの CPU でパイプラインが停止する可能性があります。分岐予測は一般的であり、ほとんどの場合問題を解決しますが、あなたの例とは何の関係もありません。予測子は、比較が真になることを予測できるのと同様に、比較が偽になることを予測することもできます。

いつものように、ウィキペディアを参照してください: Branch Predictor

score 6 · Accepted Answer

場合によります。コンパイラーはswitch、一連のif-likeテストとして実装するか、ジャンプテーブルとして実装するかを決定するために、一連の内部実装依存基準を使用します。これは、たとえば、caseラベルのセットがどれだけ「コンパクト」であるかに依存する場合があります。caseラベル値が「密な」セットを形成する場合、コンパイラはおそらくジャンプテーブルを使用する可能性が高くなります。その場合、ラベルの順序は重要でcaseはありません。一連のif-elseテストに似たものを使用することにした場合は、順序が重要になる可能性があります。

ただし、の本文switchは1つの大きなステートメントであり、caseラベルはそのステートメントへの複数のエントリポイントを提供することに注意してください。caseそのため、そのステートメント内の「サブブロック」を再配置するコンパイラーの機能（およびユーザーの機能）が制限される場合があります。

score 3 · Accepted Answer

ケースラベルは、読みやすくするために最も効率的な方法で注文する必要があります。

プロファイラーが特にこれが問題であるとあなたに言わない限り、効率のためにケースラベルを並べ替えることは時期尚早の最適化のケースです。

score 3 · Accepted Answer

条件を再配置することでステートメントを最適化できるという最初の前提でさえ、if間違っている可能性があると思います。最適化されていないビルドでは、話していることを実行することに何らかの価値があることに気付くかもしれません。一般的なケースでは、いずれの場合も少なくとも 1 回はジャンプする必要があるため、(一般に) 条件を配置する利点はありません。しかし、それは最適化されていないビルドの場合です。

最適化されたビルドでは、コンパイラが if ステートメントに対して時々生成するものに驚くかもしれません。コンパイラは、どちらか一方 (または両方) のケースをどこか外れた場所に移動する場合があります。「最初に来る」条件で遊んでこれを素朴に最適化しようとしても、必ずしもあなたが望むことをするとは限りません。せいぜい、コンパイラが何を生成しているかを調べた後でのみ、これを行うべきです。そしてもちろん、これはコストのかかるプロセスになります。これは、ステートメントをわずかに変更しただけでも、コンパイラが出力コードの生成を決定する方法が変わる可能性があるためです。

さて、switch ステートメントに関する限り、switchコードを読みやすくする場合は常に a を使用します。switchステートメントと同等のステートメントに対してコンパイラーが行うべき最悪のことはif、同じコードを生成することです。多くの場合、通常、switch ステートメントはジャンプテーブルとしてコンパイルされます。しかしif、1 つの変数を一連の値と比較する一連のテストは、同じことを行うようにコンパイラーによって十分に認識される可能性があります。ただし、スイッチを使用すると、コンパイラが状況をより簡単に認識できるようになると思います。

その条件のパフォーマンスを最大限に活用することに本当に関心がある場合は、プロファイリングの実行結果を使用して条件の生成方法を最適化するMSVC の Profile Guided Optimization (PGO または 'pogo') のようなものを使用することを検討してください。GCC に同様の機能があるかどうかはわかりません。

score 2 · Accepted Answer

C＃コンパイラについてはよくわかりませんが、アセンブリでは、ifステートメントのように式を評価するのではなく、switchステートメントを特定の行へのジャンプとして実際にプログラムできることを知っています。選択ではすべての定数があるため、ケースは行番号として扱われ、評価なしで渡された行番号（ケース値）に直接ジャンプします。これにより、caseステートメントの順序はまったく重要ではなくなります。

score 1 · Accepted Answer

これがホットスポットである場合にのみ問題になることを認識していると思います。ホットスポットかどうかを判断する最善の方法は、コードを実行し、プログラムカウンターをサンプリングして、10% 以上の確率でそこにあるかどうかを確認することです。ホットスポットの場合は、またはを実行するのにどれくらいの時間が費やされているifかを確認しswitchます。ほとんど何もBlock 1しない場合を除き、通常は無視できます。これにはプロファイラーを使用できます。一時停止を繰り返すだけです。Block 2

アセンブリ言語に慣れていない場合は、コンパイラが生成するものを理解するのに十分な程度に学習することをお勧めします。面白くて難しくありません。

score 0 · Accepted Answer

他の人が言ったように、ケースの数、最適化の方法、実行しているアーキテクチャなど、多くのことに依存します。興味深い概要については、http://ols.fedoraproject.org/GCC/Reprints-2008/sayle-reprint.pdfを参照してください。

score -2 · Accepted Answer

最も頻繁に発生するケースを最初に置くと、コードがわずかに最適化されます。スイッチステートメントの動作方法により、同じことが当てはまります。プログラムがスイッチに入って真のケースを見つけると、プログラムはそれを実行してブレークをヒットし、ループを終了します。あなたの考えは正しいです。

ただし、この最適化はごくわずかであると思います。これを行うための開発時間が遅くなる場合は、おそらくそれだけの価値はありません。また、これに対応するためにプログラムフローを大幅に変更する必要がある場合は、おそらくそれだけの価値はありません。節約できるのはせいぜい数サイクルだけで、おそらく改善は見られないでしょう。

c# - case ラベルの順序は、switch ステートメントの効率にどの程度影響しますか?

9 に答える 9

Related

Reference