c++ - スイッチケースまたはstd::mapの方が効率的です

Question

ここでトークナイザーについて考えています。
各トークンは、パーサー内で異なる関数を呼び出します。
より効率的なもの：

• std :: Functions / boost::functionsのマップ
• スイッチケース

Answer 1

switch() とルックアップ テーブルを読むことをお勧めしますか? Joel on Software から。特に、この応答は興味深いものです。

「最も重要でないものを最適化しようとして時間を浪費する人々の典型的な例。」

はいといいえ。VM では、通常、それぞれがほとんど実行しない小さな関数を呼び出します。各関数のプリアンブルとクリーンアップ ルーチンが実行時間のかなりの割合を占めていることが多いのと同じくらい、あなたを傷つけるのは呼び出し/戻りではありません。これは、特にスレッド化されたインタープリターを実装した人々によって、死ぬほど研究されています。

仮想マシンでは、通常、呼び出すために計算されたアドレスを格納するルックアップ テーブルがスイッチよりも優先されます。(ダイレクト スレッド、または「値としてのラベル」。ルックアップ テーブルに格納されているラベル アドレスを直接呼び出します) これは、特定の条件下で、パイプラインの長い CPU では非常に高価な分岐予測ミスを減らすことができるためです (強制的にフラッシュする必要があります)。パイプライン)。ただし、コードの移植性が低下します。

この問題は VM コミュニティで広く議論されています。詳しく知りたい場合は、この分野の学術論文を探すことをお勧めします。ErtlとGreggは 2001 年にこのトピックに関する素晴らしい記事を書きました。

しかし、前述したように、これらの詳細はコードには関係ないと確信しています。これらは些細なことであり、あまり注目すべきではありません。Python インタープリターは、コードが読みやすくなると考えているため、スイッチを使用しています。一番使いやすい使い方を選んでみませんか？パフォーマンスへの影響はかなり小さいので、今はコードの読みやすさに重点を置いたほうがよいでしょう ;)

編集:問題がある場合、ハッシュテーブルを使用すると、ルックアップテーブルよりも常に遅くなります。ルックアップ テーブルの場合、「キー」に列挙型を使用し、単一の間接ジャンプを使用して値を取得します。これは単一のアセンブリ操作です。O(1)。ハッシュ テーブル ルックアップでは、最初にハッシュを計算し、次に値を取得する必要がありますが、これははるかにコストがかかります。

関数のアドレスが格納されている配列を使用し、列挙型の値を使用してアクセスするのが適切です。しかし、ハッシュテーブルを使用して同じことを行うと、重要なオーバーヘッドが追加されます

要約すると、次のようになります。

• コスト(Hash_table) >> コスト(direct_lookup_table)
• cost(direct_lookup_table) ~= cost(switch) コンパイラがスイッチをルックアップ テーブルに変換する場合。
• cost(switch) >> cost(direct_lookup_table) (O(N) vs O(1)) コンパイラがスイッチを変換せず、条件を使用しない場合、これを行うコンパイラは考えられません。
• ただし、インライン ダイレクト スレッドでは、コードが読みにくくなります。

Answer 2

Visual Studio 2008に付属のSTLマップは、下にあるツリー構造を非表示にするため、関数呼び出しごとにO（log（n））を提供します。最新のコンパイラ（実装によって異なります）では、switchステートメントはO（1）を提供し、コンパイラはそれをある種のルックアップテーブルに変換します。したがって、一般的に、切り替えは高速です。

ただし、次の事実を考慮してください。

マップとスイッチの違いは次のとおりです。マップは動的に作成できますが、スイッチは作成できません。マップにはキーとして任意の型を含めることができますが、スイッチはc ++プリミティブ型（char、int、enumなど）に非常に制限されています。

ちなみに、ハッシュマップを使用してほぼO（1）のディスパッチを実現できます（ただし、ハッシュテーブルの実装によっては、最悪の場合はO（n）になることもあります）。とはいえ、切り替えはさらに高速になります。

編集

私は楽しみと議論の問題のためだけに以下を書いています

私はあなたのために素晴らしい最適化を提案することができますが、それはあなたの言語の性質とあなたがあなたの言語がどのように使われるかを期待できるかどうかに依存します。

コードを書くとき：トークンを2つのグループに分割します。一方のグループは非常に頻繁に使用され、もう一方のグループは使用頻度が低くなります。また、頻繁に使用されるトークンを並べ替えます。頻度の高いトークンの場合は、使用頻度の高いものが最初に来るif-elseシリーズを作成します。使用頻度が低い場合は、switchステートメントを記述します。

アイデアは、別のレベルの間接参照を回避するためにCPU分岐予測を使用することです（ifステートメントでの条件チェックにほとんど費用がかからないと仮定します）。ほとんどの場合、CPUは間接参照のレベルなしで正しいブランチを選択します。ただし、ブランチが間違った場所に移動することはほとんどありません。言語の性質によっては、統計的にはパフォーマンスが向上する場合があります。

編集：以下のいくつかのコメントにより、変更されましたコンパイラが常にスイッチをLUTに変換することを示す文。

Answer 3

「効率的」の定義は何ですか? より速いという意味であれば、おそらく、明確な答えを得るためにいくつかのテスト コードをプロファイリングする必要があります。ただし、柔軟で拡張しやすいコードを求めている場合は、マップ アプローチを使用してください。他のすべては時期尚早の最適化です...

Answer 4

yossi1981が言ったように、スイッチは高速ルックアップテーブルになるように最適化できますが、保証はありません.すべてのコンパイラには、スイッチを連続ifとして実装するか、高速ルックアップテーブルとして実装するか、または両方の組み合わせとして実装するかを決定する他のアルゴリズムがあります。

高速な切り替えを行うには、値が次のルールを満たす必要があります。値は連続している必要があります。たとえば、0、1、2、3、4 です。一部の値を省略できますが、0、1、2、34、43 などは最適化される可能性が非常に低くなります。

問題は、アプリケーションでそのような重要なパフォーマンスが得られるかどうかです。また、ファイルから値を動的にロードするマップは、複数ページのコードにまたがる巨大なステートメントよりも読みやすく保守しやすいのではないでしょうか?

Answer 5

あなたのトークンがどのタイプであるかは言いません。それらが整数でない場合、選択の余地はありません。スイッチは整数型でのみ機能します。

Answer 6

C++ 標準は、その要件のパフォーマンスについては何も述べておらず、機能が必要であるとだけ述べています。

どちらが優れているか、より高速であるか、またはより効率的であるかについてのこの種の質問は、どの実装について話しているかを述べない限り意味がありません。たとえば、JavaScript の特定の実装の特定のバージョンでの文字列処理はひどいものでしたが、それが関連する標準の機能であると推定することはできません。

switchとによって提供される機能std::mapが異なるため (重複はありますが) 、実装に関係なく問題ではないとさえ言えます。

私の意見では、この種のマイクロ最適化はほとんど必要ありません。