58

次のコードがあるとします。

private static int DoSwitch(string arg)
{
    switch (arg)
    {
        case "a": return 0;
        case "b": return 1;
        case "c": return 2;
        case "d": return 3;
    }
    return -1;
}

private static Dictionary<string, Func<int>> dict = new Dictionary<string, Func<int>>
    {
        {"a", () => 0 },
        {"b", () => 1 },
        {"c", () => 2 },
        {"d", () => 3 },
    };

private static int DoDictionary(string arg)
{
    return dict[arg]();
}

両方の方法を繰り返して比較することにより、「a」、「b」、「c」、「d」がより多くのキーを含むように拡張された場合でも、辞書がわずかに高速になることがわかります。なんでそうなの？

これは循環的複雑度と関係がありますか？これは、ジッターがディクショナリ内のreturnステートメントをネイティブコードに1回だけコンパイルするためですか？辞書のルックアップがO（1）であるためですか？これはswitchステートメントには当てはまらない可能性がありますか？（これらは単なる推測です）

4

4 に答える 4

57

簡単に言うと、switchステートメントは線形に実行され、ディクショナリは対数的に実行されます。

ILレベルでは、小さなswitchステートメントは通常、スイッチ変数と各ケースの同等性を比較する一連のif-elseifステートメントとして実装されます。したがって、このステートメントは、myVarの有効なオプションの数に直線的に比例する時間で実行されます。ケースは表示された順序で比較されます。最悪のシナリオは、すべての比較が試行され、最後の1つが一致するか、まったく一致しないかのいずれかです。したがって、32個のオプションがある場合、最悪の場合はそれらがないことであり、コードはこれを決定するために32個の比較を行います。

一方、ディクショナリは、インデックスに最適化されたコレクションを使用して値を格納します。.NETでは、ディクショナリはハッシュテーブルに基づいており、アクセス時間は実質的に一定です（スペース効率が非常に低いという欠点があります）。辞書のようなコレクションの「マッピング」に一般的に使用される他のオプションには、対数アクセス（および線形空間効率）を提供する赤黒木のようなバランスの取れたツリー構造が含まれます。これらのいずれも、switchステートメントが同じことを行うよりもはるかに速く、コードがコレクション内の適切な「ケース」に対応するキーを見つける（または存在しないと判断する）ことを可能にします。

編集：他の回答やコメント投稿者がこれに触れているので、完全を期すために私もそうします。Microsoftコンパイラは、私が最初に推測したように、スイッチをif/elseifにコンパイルするとは限りません。これは通常、少数のケース、および/または「スパース」ケース（1、200、4000などの非増分値）で行われます。隣接するケースのセットが大きい場合、コンパイラーはCILステートメントを使用してスイッチを「ジャンプテーブル」に変換します。スパースケースのセットが大きい場合、コンパイラはバイナリ検索を実装してフィールドを絞り込み、少数のスパースケースを「フォールスルー」するか、隣接するケースのジャンプテーブルを実装できます。

ただし、コンパイラーは通常、パフォーマンスとスペース効率の最良の妥協点である実装を選択するため、多数の密集したケースに対してのみジャンプテーブルを使用します。これは、ジャンプテーブルがカバーしなければならないケースの範囲のオーダーのメモリ内のスペースを必要とするためです。これは、スパースケースの場合、メモリ的には非常に非効率的です。ソースコードで辞書を使用することにより、基本的にコンパイラの手を強制します。メモリ効率を上げるためにパフォーマンスを妥協する代わりに、それはあなたのやり方でそれを行います。

したがって、ソースでswitchステートメントまたはDictionaryのいずれかを使用できるほとんどの場合、Dictionaryを使用するとパフォーマンスが向上すると思います。switchステートメントの多数のケースは、保守が難しいため、とにかく避ける必要があります。

于 2012-07-23T17:29:10.200 に答える
51

これは、マイクロベンチマークが誤解を招く可能性がある理由の良い例です。C＃コンパイラは、スイッチ/ケースのサイズに応じて異なるILを生成します。したがって、このような文字列をオンにすると

switch (text) 
{
     case "a": Console.WriteLine("A"); break;
     case "b": Console.WriteLine("B"); break;
     case "c": Console.WriteLine("C"); break;
     case "d": Console.WriteLine("D"); break;
     default: Console.WriteLine("def"); break;
}

それぞれの場合に本質的に以下を行うILを生成します。

L_0009: ldloc.1 
L_000a: ldstr "a"
L_000f: call bool [mscorlib]System.String::op_Equality(string, string)
L_0014: brtrue.s L_003f

以降

L_003f: ldstr "A"
L_0044: call void [mscorlib]System.Console::WriteLine(string)
L_0049: ret

つまり、それは一連の比較です。したがって、実行時間は線形です。

ただし、ケースを追加すると、たとえばazからのすべての文字を含めると、生成されるILがそれぞれ次のように変更されます。

L_0020: ldstr "a"
L_0025: ldc.i4.0 
L_0026: call instance void [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)

と

L_0176: ldloc.1 
L_0177: ldloca.s CS$0$0001
L_0179: call instance bool [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::TryGetValue(!0, !1&)
L_017e: brfalse L_0314

そして最後に

L_01f6: ldstr "A"
L_01fb: call void [mscorlib]System.Console::WriteLine(string)
L_0200: ret

つまり、一連の文字列比較の代わりに辞書を使用するようになったため、辞書のパフォーマンスが得られます。

言い換えると、これらに対して生成されるILコードは異なり、これはILレベルにすぎません。JITコンパイラはさらに最適化する可能性があります。

TL; DR：つまり、ストーリーの教訓は、マイクロベンチマークに基づいて最適化しようとするのではなく、実際のデータとプロファイルを確認することです。

于 2012-07-23T17:57:47.383 に答える
4

コンパイラのcodegenの決定に関する多くの質問と同様に、答えは「状況によって異なります」です。

独自のハッシュテーブルの作成は、多くの場合、コンパイラが生成したコードよりも高速に実行されます。これは、コンパイラが他のコストメトリックを持っているためです。主に、メモリ消費です。

ハッシュテーブルは、少数のif-then-elseIL命令よりも多くのメモリを使用します。コンパイラがプログラム内のすべてのswitchステートメントに対してハッシュテーブルを吐き出すと、メモリの使用が爆発的に増加します。

switchステートメントのcaseブロックの数が増えると、コンパイラーが異なるコードを生成するのがわかるでしょう。より多くの場合、コンパイラーが小さくて単純なif-then-elseパターンを放棄して、より高速でより太い代替パターンを優先することの正当性が高まります。

C＃コンパイラまたはJITコンパイラがこの特定の最適化を実行するかどうかはわかりませんが、ケースセレクタが多く、ほとんどがシーケンシャルである場合のswitchステートメントの一般的なコンパイラトリックは、ジャンプベクトルを計算することです。これには、より多くのメモリが必要です（コードストリームに埋め込まれたコンパイラ生成のジャンプテーブルの形式で）が、一定時間で実行されます。arg-"a"を減算し、結果をジャンプテーブルへのインデックスとして使用して、適切なケースブロックにジャンプします。20件か2000件かに関係なく、ブームは終わりました。

スイッチセレクターのタイプがchar、int、またはenumであり、ケースセレクターの値がほとんどシーケンシャル（「密」）である場合、コンパイラーはジャンプテーブルモードに移行する可能性が高くなります。これらのタイプは簡単に減算してオフセットを作成できるためです。索引。文字列セレクターは少し難しいです。

文字列セレクターはC＃コンパイラーによって「インターン」されます。つまり、コンパイラーは文字列セレクターの値を一意の文字列の内部プールに追加します。インターンされた文字列のアドレスまたはトークンをそのIDとして使用できるため、インターンされた文字列をID/バイト単位の同等性について比較するときにintのような最適化が可能になります。十分なケースセレクターがあれば、C＃コンパイラーはarg文字列に相当するインターンをルックアップするILコードを生成し（ハッシュテーブルルックアップ）、インターントークンを事前計算されたケースセレクタートークンと比較（またはジャンプテーブル）します。

char / int / enumセレクターの場合にコンパイラーを誘導してジャンプテーブルコードを生成できる場合、これは独自のハッシュテーブルを使用するよりも高速に実行できます。

文字列セレクターの場合でも、ILコードはハッシュルックアップを実行する必要があるため、独自のハッシュテーブルを使用した場合とのパフォーマンスの違いはおそらく問題になります。

ただし、一般的に、アプリケーションコードを作成するときは、これらのコンパイラのニュアンスにこだわる必要はありません。Switchステートメントは、一般に、関数ポインターのハッシュテーブルよりもはるかに読みやすく理解しやすいものです。コンパイラーをジャンプテーブルモードにプッシュするのに十分な大きさのswitchステートメントは、多くの場合、大きすぎて人間が読み取れません。

switchステートメントがコードのパフォーマンスホットスポットにあり、それが具体的なパフォーマンスへの影響があることをプロファイラーで測定した場合、独自のディクショナリを使用するようにコードを変更することは、パフォーマンスを向上させるための合理的なトレードオフです。

この選択を正当化するためのパフォーマンス測定を行わずに、最初からハッシュテーブルを使用するようにコードを作成することは過剰なエンジニアリングであり、不必要に高いメンテナンスコストを伴う計り知れないコードにつながります。単純にする。

于 2012-07-23T18:26:30.550 に答える
2

デフォルトでは、文字列のスイッチはif / else / if/else構文のように実装されます。ブライアンが提案したように、コンパイラはスイッチが大きくなるとハッシュテーブルに変換します。Bart de Smetは、このchannel9ビデオでこれを示しています（スイッチは13:50に説明されています）

コンパイラーは、最適化のコストが利点を上回ることを防ぐために、保守的であるため、4つの項目に対してそれを実行していません。ハッシュテーブルの構築には、少しの時間とメモリがかかります。

于 2012-07-23T17:58:15.000 に答える