5

ノード上で大量の処理を行う非常に大きなグラフがあるとします (ノードごとに数千万の操作など)。コア ルーチンは各ノードで同じですが、内部条件に基づいていくつかの追加操作があります。4 つのケース (0,0)、(1,0)、(0,1)、(1,1) を生成する 2 つの条件が存在する可能性があります。たとえば、(1,1) は、両方の条件が成立することを意味します。条件は、プログラム内で 1 回 (ノードごとに個別に 1 つ設定) 確立され、それ以降変更されることはありません。残念ながら、それらは実行時に完全に予測不可能な方法で決定されます (外部サーバーから HTTP 経由で受信したデータに基づいて)。

そのようなシナリオで最も速いのは何ですか? （私にはわからない最新のコンパイラの最適化を考慮に入れています）

  • 単純に「IF」を使用する: if (条件 X) は追加の操作 X を実行します。
  • 継承を使用して基本クラスから 4 つのクラスを派生させ (メソッド OPERATION を公開)、適切な操作を行い、何千万もの "if" を節約します。[しかし、これが本当に節約になるかどうかはわかりません。継承にもオーバーヘッドが必要です)
  • 関数へのポインタを使用して、条件に基づいて関数を一度割り当てます。

自分でテストできるようになるまでには時間がかかります（まだそのような大きなデータはありません。これはより大きなプロジェクトに統合されるため、すべてのバージョンをテストするのは簡単ではありません）。

回答を読む: 私はおそらくそれを試してみる必要があることを知っています. しかし、すべてを除けば、これは一種の質問です。より速いのは次のとおりです。

数千万の IF ステートメントと通常の静的に既知の関数呼び出し VS 関数ポインターは VS 継承を呼び出しますが、これはこの場合、最良のアイデアではないと思います。今後の検査から除外することを考えています。そんな些細なことは気にしないでください(;_;)

4

5 に答える 5

3

実際のデータで実際のコードを測定する以外に、本当の答えはありません。時々、私はそのような問題に対処しなければなりませんでしたが、実際に測定した場合、仮想関数はifよりも高速でした. しかし、それはあまり意味がありません。なぜなら、私が測定したケースは、あなたのものとは異なるプログラム (したがって異なるコンテキスト) にあったからです。たとえば、仮想関数呼び出しは一般にインライン展開を防ぎますが、if は本質的にインラインであり、インライン展開は追加の最適化の可能性を開く可能性があります。

また、私が測定したマシンは、仮想機能をかなりうまく処理しました。他のマシン (HP の PA など) では、間接ジャンプ (仮想関数呼び出しだけでなく、関数からの戻りも含む) の実装が非常に効果的ではないと聞いています。 ）。

于 2013-11-14T14:03:57.803 に答える
2

絶対に最速の方法が必要で、ノードの処理順序が関係ない場合は、ケースごとに 1 つずつ、4 つの異なるタイプを作成し、それぞれに処理関数を定義します。次に、コンテナ クラスに、ノード タイプごとに 1 つずつ、合計 4 つのベクトルを配置します。新しいノードの作成時に、ノードを作成するために必要なすべてのデータ (条件を含む) を取得し、正しいタイプのノードを作成して正しいベクターにプッシュします。次に、すべてのノードを処理する必要がある場合は、タイプごとに処理します。最初に最初のベクトルのすべてのノードを処理し、次に 2 番目のベクトルを処理します。

なぜこれをしたいのですか：

  • 状態切り替えの ifs なし
  • vtable がありません
  • 関数の間接化なし

しかし、もっと重要なこと:

  • 命令キャッシュのスラッシングなし (次のノードごとにコードの別の部分にジャンプすることはありません)
  • 状態切り替え if の分岐予測ミスはありません (存在しないため)

仮想関数を継承し、vtable を介して関数の間接化を行ったとしても、ベクトル内のノードをタイプ別にソートするだけで、パフォーマンスに大きな違いが生じる可能性があります。分岐予測の方法 分岐予測ミスも減らすことができます。

また、ポインターのベクトルを作成するのではなく、オブジェクトのベクトルを作成します。それらがポインターである場合、余分なアドレス指定の間接性があり、それ自体はそれほど気になりませんが、問題は、オブジェクトがメモリ全体にかなりランダムに分散している場合、データ キャッシュのスラッシングにつながる可能性があることです。一方、オブジェクトがベクトルに直接配置される場合、処理は基本的にメモリを線形に通過し、キャッシュは基本的に毎回ヒットし、キャッシュのプリフェッチは実際にはうまくいく可能性があります。

ただし、正しく行わないと、データ構造の作成に多額の費用がかかることに注意してください。ベクトルがすべてのノードに対してすぐに十分な容量を確保し、ベクトルがなくなるたびに再割り当てと移動を行う場合、可能であれば可能です。スペースが高価になる可能性があります。

ああ、そうです、ジェームズが言ったように、常に、常に測定してください! 最適化、パイプライン処理、分岐予測、キャッシュのヒット/ミス、データ構造のレイアウトなど、あらゆる種類の要因に応じて、非常に直感に反する場合があります。かなり一般的なアプローチですが、最速であることが保証されているわけではなく、間違いなく間違った方法があります。測る、測る、測る。

仮想関数を使用した PS 継承は、関数ポインターを使用することとほぼ同じです。仮想関数は通常、クラスの先頭にある vtable によって実装されます。これは、基本的に、オブジェクトの実際の型の特定の仮想の実装への関数ポインターのテーブルにすぎません。ifs が virtuals より速いか、またはその逆かは、答えるのが非常に難しい質問であり、使用する実装、コンパイラ、およびプラットフォームに完全に依存します。

于 2013-11-14T14:44:36.850 に答える
1

多くのプログラマーは、パイプライン処理、キャッシング、分岐予測、仮想関数、コンパイラーの最適化、big-O アルゴリズムなど、およびそれらのパフォーマンスなど、特定の好きなテーマに関するクラスを受講したり、本を読んだりしています。

ボートに例えると、ウェイトのトリミング、パワーの調整、バランスの調整、合理化などです。すでに最適に近いスピードボートから始めると仮定します。

実際にクイーン メリー号から出発している可能性があります。

脂肪がどこにあるのかを知っていれば、脂肪を取り除くだけで (良いデザインを装う)、コードを大幅に高速化する方法がある可能性が非常に高いです。まあ、それがどこにあるのかわからないし、間違っていることを評価しない限り、どこにあるかを推測するのは時間の無駄です.

人々が「プロファイラーを測定して使用する」と言うとき、彼らは正しい方向を指していますが、十分ではありません。 これが私のやり方の例です.FWIW.

于 2013-11-14T21:16:06.117 に答える
1

私は実際、分岐予測がどれほど効果的であるかに非常に感銘を受けており、ifソリューションのみがインライン展開を可能にし、これも劇的になる可能性があります。仮想関数と関数へのポインターもメモリからの読み込みを伴うため、キャッシュ ミスが発生する可能性があります

ただし、条件が 4 つあるため、ブランチ ミスは高くつく可能性があります。

答えをテストして検証する能力がなければ、答えを出すことはできません。特に、これが最適化の取り組みを保証するのに十分なパフォーマンスのボトルネックになるかどうかさえ明らかではないため.

このような場合。私は読みやすさとデバッグの容易さの面で誤りを犯し、もし

于 2013-11-14T14:33:11.663 に答える