問題タブ [data-oriented-design]

私はこの記事を読んでいましたが、この男は、データ指向設計とOOPを組み合わせると誰もがどのように大きな利益を得ることができるかについて話し続けています。ただし、彼はコードサンプルを表示していません。

私はこれをグーグルで検索しましたが、コードサンプルは言うまでもなく、これが何であるかについての実際の情報を見つけることができませんでした。この用語に精通していて、例を提供できる人はいますか？これはおそらく他の何かの別の言葉ですか？

完全にブランチ フリーのメモリ マネージャー (C++ で) を作成する方法を考えた人はいますか? プール、スタック、キュー、およびリンク リスト (プールから割り当てる) を作成しましたが、ブランチ フリーの汎用メモリ マネージャーを作成することがどれほど妥当か疑問に思っています。

これはすべて、確実な同時実行、順序付けされた CPU、およびキャッシュに適した開発を行うための、本当に再利用可能なフレームワークを作成するのに役立ちます。

編集:ブランチレスとは、直接または間接の関数呼び出しを行わず、ifs を使用しないことを意味します。私はおそらく、最初に要求されたサイズを false 呼び出しのゼロに変更する何かを実装できると考えていましたが、実際にはそれ以上のものはありませんでした。不可能ではないと思いますが、この演習のもう 1 つの側面は、前述の「友好的でない」プロセッサでプロファイリングして、分岐を回避するためにこれほど努力する価値があるかどうかを確認することです。

私は独自の「配列の構造体」コーディングを始めましたが、メモリに制約のあるハードウェアで強力なデータ変換を行うためのライブラリまたはテンプレートが既に存在することを誰かが知っているかどうか疑問に思いました。

私が探しているのは、同期点まで挿入をキューに入れ、反復の途中で「削除」できる一種の「メモリ内」コンテナだと思います。実際の削除である必要はありません (物を移動するオーバーヘッドがあります)。削除済みとしてマークしても問題ありません。また、コンテナは、キャッシュ ウォーミングなどのパフォーマンスのために、ほとんどの場合連続している必要があります。完全に連続するのではなく、連続するブロックも問題ありませんが、通常、配列は非常に小さな要素で構成されているため、リンク リスト ベースのコンテナーは、メモリや速度のためにそれを削減することはできません。

これが、コンテナが主キーでソートされたテーブルのようなものになるため、ある種のテーブル クラスが適合すると考える理由です。

意味はありますが、std::vector を使用するという考えは、反復中に何かを削除すると、配列の末尾と先頭 (カウント) へのアクセスでキャッシュが台無しになるため、実際には不可能です。

また、複数の反復子が同じデータに対して操作できない理由はないため、swap as delete のようなことを行うと、他の反復子が特定の要素をスキップすることになります。これが、挿入をキューに入れることに言及する理由です。

挿入と削除はコンテナーの形状を変更するため、同期操作で処理できると想定していますが、現在のコンテンツの反復中に挿入と削除のアクションがキューに入れられる可能性があります。

データ指向設計とは何かについての質問がもう 1 つあります。また、よく参照される記事が 1 つあります (すでに 5 ～ 6 回読んでいます)。私はこれの一般的な概念を理解しています。特に、たとえば 3D モデルを扱う場合、すべての頂点を一緒に保ち、面を法線などで汚染したくない場合などです。

ただし、データ指向の設計が最も些細なケース (3d モデル、パーティクル、BSP ツリーなど) 以外でどのように機能するかを視覚化するのに苦労しています。データ指向設計を実際に採用し、これが実際にどのように機能するかを示す良い例はありますか? 必要に応じて、大規模なコードベースを掘り下げることができます。

私が特に興味を持っているのは、「1 つあるところには多くのものが存在する」というマントラです。はい、常に複数の敵がいますが、それでも各敵を個別に更新する必要があります。なぜなら、敵は同じように動いていないからです? 上記の質問に対する受け入れられた回答の「ボール」の例にも同じことが言えます（実際にその回答へのコメントでこれを尋ねましたが、まだ回答を得ていません）。単純に、レンダリングには位置のみが必要で速度は必要ないのに対し、ゲーム シミュレーションには両方が必要で、マテリアルは必要ないということですか? または、何か不足していますか？おそらく私はすでにそれを理解しており、それは私が思っていたよりもはるかに単純な概念です.

どんなポインタでも大歓迎です！

現在、コンソール用に3Dエンジンを少し最適化したいと思っています。より正確には、キャッシュをより使いやすくし、構造をよりデータ指向に調整したいだけでなく、優れたユーザーインターフェイスを維持したいと考えています。

例えば：

したがって、ユーザーは自分のコードでインターフェイスポインターを操作できます。

しかし
、私のエンジンには現在、シーンノードへのポインタを格納しています。

したがって、データ指向の設計では、構造体の配列ではなく、配列の構造体を使用することをお勧めします。だから私のノードはから取得します...

これに...

したがって、DOPを適用する場合、ここで2つの問題が発生します。まず、ユーザーがIDやインデックスなどを操作しなくても、優れたユーザーインターフェイスを維持するにはどうすればよいでしょうか。

次に、一部のベクトルのサイズが変更されたときに、ユーザーインターフェイスポインターがニルヴァーナを指さないようにした場合に、プロパティの再配置を処理するにはどうすればよいですか？

現在の私の考えは、永続的な「ポインタ」のハンドルを取得する一種のhandle_vectorを実装することです。

したがって、インターンstd :: vectorのサイズが変更されると、ハンドルが更新されます。「ハンドル」は実際のオブジェクトへのポインタを格納し、「->」演算子は適切なラッピングを実現するためにオーバーロードされます。しかし、このアプローチは私には非常に複雑に聞こえますか？！

どう思いますか？優れたインターフェイスを維持しながら、キャッシュの使用率を高めるためにメモリ内で連続して考える方法はありますか？

助けてくれてありがとう！

対

使用例

2番目のケースは、すべてのデータがインターリーブされてお​​り、同時にキャッシュにロードする必要があるため、空間的な局所性が優れていると思います。どちらの場合も、すべての球を同時に処理します。何か入力はありますか？

そこから中小規模の静的ハッシュ テーブルを作成する必要があります。通常、これらには 5 ～ 100 のエントリがあります。ハッシュ テーブルが作成されると、すべてのキー ハッシュが事前に認識されます (つまり、キーは既にハッシュです)。現在、私は HashMap を作成しています。気になるサイズの平均ルックアップ。ウィキペディア連鎖を伴う単純なハッシュテーブルは、完全なテーブルに対して平均で 3 回のルックアップをもたらすと主張しているため、これはまだ私にとって面倒なことではありません (つまり、最初のエントリとして hash%n を取得し、連鎖を実行します)。ハッシュを前もって、高速で静的な完全なハッシュを取得する簡単な方法があるように思われます-しかし、私はどのように良いポインタを見つけることができませんでした. つまり、追加のオーバーヘッドなしで (ほとんど?) 償却された O(1) アクセス。このような静的テーブルをどのように実装すればよいですか?

メモリ使用量は重要なので、保存する必要が少ないほど良いです。

編集: 衝突を 1 つほど手動で解決する必要がある場合は問題ないことに注意してください。つまり、たとえば、平均して直接アクセスし、最悪の場合 3 つの間接アクセスを持つ連鎖を行うことができれば、それで問題ありません。完全なハッシュが必要というわけではありません。

この質問に答える前に、分岐予測も考慮してください。

関数ポインタを使用して、条件文を関数の呼び出しに置き換えることができるシナリオがいくつかあります。このようなものがあります。（同様のタイプのシナリオでは、継承よりもコンポーネントベースのプログラミングを考えることができます）

同じクラスをこのように書くことができます。

上記の場合を考えれば、どちらも同じ結果になりますが、パフォーマンスのオーバーヘッドを考えています.2番目のケースでは、関数呼び出しを行うことで分岐予測の問題を回避しています。

ここで、この種のシナリオでどちらがより良いプラクティスであり、「より適切に最適化されたコード」であるかを教えてください（ところで、「時期尚早の最適化はすべての悪の根源である」というステートメントは好きではありません。コードの最適化を検討してください！）

PS：アセンブリコードでも、「分岐予測がいかに悪いか」について詳細な概要を説明してもかまいません。

更新：プロファイリング後（上記のコードと同様の種類）、
Conditionがこの種のシナリオで成功した場合、誰かがこれの理由を説明できますか？分岐コードがないので、機能呼び出しコードをプリフェッチできますか？しかし、ここでは逆に見えます。分岐コードが勝ちます！：O Intel Mac Osx、GCC O3/Os最適化でプロファイルされます。

オブジェクト指向プログラミング (OOP) ソリューションとボールの束を更新するデータ指向設計 (DOD) ソリューションを比較するサンプル コードを次に示します。

さて、これはVisual Studioでコンパイルして実行しますが、これを行うことが許可されているかどうか疑問に思っていますが、これを確実に行うことができるはずです:

私の理解では、 std::vector のデータは連続しているはずですが、これが別のプラットフォームで問題になるかどうか、標準に違反するかどうか、内部でどのように保存されているかはわかりません。また、これは私が DOD ソリューションを OOP ソリューションよりも優れたものにすることができた唯一の方法であり、反復の他の方法はそれほど良くありませんでした。イテレータを使用することもできますが、最適化が有効になっている、別名リリース モードの OOP よりも高速であると確信しています。

それで、これは DOD を行う良い方法ですか (最善の方法ですか?)、これは正当な c++ ですか?

[編集] さて、国防総省の場合、これは悪い例です。x、y、z は Vector3 にパッケージ化する必要があります。したがって、DOD は OOP よりもデバッグで高速に実行されましたが、リリースでは別の話でした。繰り返しますが、これは DOD を効率的に使用する方法の悪い例ですが、同時に多数のデータにアクセスする必要がある場合は短所であることを示しています。DODを使いこなすコツは、「アクセスパターンに基づいたデータ設計」です。

データ指向設計を使用してキャッシュを可能な限り効率的に使用するようにコードを方向付けようとしていますが、そのようなことについて考えるのは初めてです。画面上にスプライトを描画するのと同じ命令をループする方法を考案しました。この関数に送信されるベクトルには、すべてのゲーム エンティティの位置とスプライトが含まれます。

私の質問は、条件文が命令キャッシュから描画関数を取り除き、それによって私の計画を台無しにすることですか? それとも、私がしていることは一般的に非常識ですか？