問題タブ [data-oriented-design]

Position、Color、などのさまざまなタイプのコレクションを考えてみてくださいName。これらのインスタンスは、コレクション内の同じキーを使用して接続できます。キーは、64 ビット長のグローバル一意識別子です。現在、ハッシュ マップを使用していますが、これは理想的ではありません。

コレクションを分離しようとしていますが、ご覧のとおり、複数のコレクションの収集されたインスタンスが同時に必要になることもあります。もちろん、時々 1 つの要素を追加または削除する必要もありますが、これらのケースはパフォーマンス クリティカルではありません。

ここで、個々のコレクションの反復処理を最適化したいと考えています。したがって、コレクションを連続して保存するようにしています。これは、データ指向設計の考え方の一部です。ただし、個々のインスタンスに非常に迅速にアクセスする必要があります。配列を直接使用すると、あまりにも多くのメモリが割り当てられ、あるタイプのすべてのインスタンスが別のタイプの対応するインスタンスを持つとは限らないため、機能しません。一方、ハッシュマップは反復には最適ではありません。

データ構造は内部的に配列を使用する必要があると思います。ここではどのデータ型を使用すればよいですか? また、C++ 標準ライブラリに実装されているそのようなデータ構造はありますか?

C/C++ のバックグラウンドから来て、キャッシュ ミスの削減に関するオブジェクトのメモリ レイアウトは、特にコンソールで作業する場合に重要です。データ指向の設計は、オブジェクト指向の設計よりも好まれることがよくあります。これは、関連するオブジェクトをメモリ内で (特にパフォーマンスが重要な領域で) 互いに近くに保つのに役立つためです。

最近、私はいくつかの Javascript 開発を行っていますが、Javascript コミュニティー内で一般的なコンセンサスがどのようなものか疑問に思っています。

Javascript の経験が限られているため、プロファイリング時にまったく予想外の結果が得られて驚くことがよくあります。Javascript オブジェクト/構造の内部メモリ レイアウトと実装は、ブラウザーによって大きく異なるため、最適化を試みる価値があるかどうか疑問に思います。

2 つのメソッドのパフォーマンスを比較するために jsPerfで簡単なテスト ケース ( http://jsperf.com/object-vs-data ) を作成しました。Chrome ではパフォーマンスの向上が示されていますが、Safari では顕著なスピードアップは見られませんでした。

Javascript では、オブジェクトのメモリ レイアウトにさえ気を配る必要がありますか? それとも、「ある方法で実装し、必要に応じて最適化する」タイプのものですか？

この 2 番目のオプションは、特に従うべき適切なガイドラインがある場合は、(開発時間の点で) 無駄に思えます。

ありがとう〜

補足情報: これは基本的に、Javascript で 2 つのアプローチを実装する方法です。上記の jsPerf テスト ケースは次のように実装されます。

I'm testing how reading multiple streams of data affects a CPUs caching performance. I'm using the following code to benchmark this. The benchmark reads integers stored sequentially in memory and writes partial sums back sequentially. The number of sequential blocks that are read from is varied. Integers from the blocks are read in a round-robin manner.

Here are the timings for splitting 1-80 ways on an Intel Core 2 Quad CPU Q9550 @ 2.83GHz:

The bump in the speed soon after 8 streams makes sense to me, as the processor has an 8-way associative L1 cache. The 24-way associative L2 cache in turn explains the bump at 24 streams. These especially hold if I'm getting the same effects as in Why is one loop so much slower than two loops?, where multiple big allocations always end up in the same associativity set. To compare I've included at the end timings when the allocation is done in one big block.

However, I don't fully understand the bump from one stream to two streams. My own guess would be that it has something to do with prefetching to L1 cache. Reading the Intel 64 and IA-32 Architectures Optimization Reference Manual it seems that the L2 streaming prefetcher supports tracking up to 32 streams of data, but no such information is given for the L1 streaming prefetcher. Is the L1 prefetcher unable to keep track of multiple streams, or is there something else at play here?

Background

I'm investigating this because I want to understand how organizing entities in a game engine as components in the structure-of-arrays style affects performance. For now it seems that the data required by a transformation being in two components vs. it being in 8-10 components won't matter much with modern CPUs. However, the testing above suggests that sometimes it might make sense to avoid splitting some data into multiple components if that would allow a "bottlenecking" transformation to only use one component, even if this means that some other transformation would have to read data it is not interested in.

Allocating in one block

Here are the timings if instead allocating multiple blocks of data only one is allocated and accessed in a strided manner. This does not change the bump from one stream to two, but I've included it for sake of completeness.

And here is the modified code for that:

Edit 1

I made sure that the 1 vs 2 splits difference was not due to the compiler unrolling the loop and optimizing the first iteration differently. Using the __attribute__ ((noinline)) I made sure the work function is not inlined into the main function. I verified that it did not happen by looking at the generated assembly. The timings after these changed were the same.

次のようなツリー構造があります。モデルにはルート ノードがあり、各ノードには任意の数の子ノードと任意の数のメッシュがあります。

私のアプリケーションでは、多くの時間がこのツリーをたどり、視錐台カリングや行列乗算などの計算に費やされています。現在、各ノードには子ノードとメッシュのベクトルがあり、ツリーは再帰的に走査されます。これは非常に遅いです。

私はデータ指向の設計を見てきましたが、非常にキャッシュフレンドリーであるという考えが気に入っています。私はこのようなことを考えてきました：

ここで、ツリーを走査して可視メッシュのリストを取得する必要があります。各ノードで、ノードが表示されているかどうかを確認する必要があります。次のブランチ:

• ノードが表示されます。その下のすべての子ノードとメッシュも表示されます。このブランチに深く入り込まないでください。同じ深さの他のノードを確認してください。
• ノードは表示されません。このノードまたはその下の子ノードまたはメッシュは表示されません。このブランチに深く入り込まないでください。同じ深さの他のノードを確認してください。
• ノードが部分的に表示されます。一部のノードおよび/または一部のメッシュが表示されます。階層をさらに深くする必要があります。

ツリーは静的です。モデルがアプリケーションに読み込まれると、ツリーが変更されることはありません。したがって、この情報を使用して効率的な構造を取得できるはずです。

私はこれにどのようにアプローチするか困惑しています。

いくつか質問があります。

1. ノードをメモリに配置するにはどうすればよいですか? 最初のインデックスのルート ノードですか? 他のノードは深度に基づいて追加されますか?
2. 再帰を使用せずにツリーを反復するにはどうすればよいですか? 本当に必要でない限り、各ノードにアクセスしたくありません。たとえば、depth=2 のノードが表示されない場合、そのすべてのメッシュと子 (およびそれらのメッシュ) をテストするのではなく、完全にスキップする必要があります。

データ指向設計に関する多くの著作で重要な役割を果たしている 1 つの特徴は、AoS (構造体の配列) ではなく、多くのケースがあることです。

データを SoA (配列の構造体) に配置する方が効率的です。

今私が探しているのは、呼び出しインターフェイスを変更せずに AoS と SoA を切り替えることができるソリューションです。たとえばcs[42].foo;、使用しているデータの配置に関係なく呼び出します。

上記の構文例は理想的なケースであり、不可能である可能性が非常に高いことに注意してください。ただし、近い近似にも非常に興味があります。テイカーはいますか？

私の単純な物理エンジンにデータ指向設計 (この記事などに基づく) を適用したいと考えています。また、最もコストがかかる部分である衝突テストの最適化に注力しています。

プレイヤーと衝突する可能性のある境界球を 1 つの にまとめましたvector。

そして、単一の関数/メソッド内でそれらとの衝突をテストします。その時点まで、すべてが私にははっきりと見えます。

問題は、次のようなより一般的な構造もいくつかあることです。

ネストされた( ) はメモリ内で多くの場所を占める (予約する)ためstd::vector<Polygon>、同じ方法で作成するのは良い習慣ではないと思います。vectorpoints

一方、常に 2、3、4、または 10 ポイントがあるとは限りません (最大で約 20 で大きく異なりますが、通常ははるかに少ないです)。

そして、一般的な構造からたとえば一連の三角形に切り替えたくありません（多くの計算で分離された三角形よりも高速であるため）。Polygon

じゃあどうすればいいの？データ指向設計の精神に沿って、メモリ/キャッシュを効率的に使用したいと考えていPolygonます。

vector内側の( )を取り除く必要がありpointsますか? もしそうならどうですか？

このような HTML 構造があるとします。それぞれの left-context-field と right-context-field は関連しており、バックエンドで left をその右の同僚にリンクできる必要があります。

ユーザーは好きなだけ行を追加できます。値を PHP ファイルに投稿するにはどうすればよいですか?

すべての行を 1 つの巨大なフォームにラップしてから呼び出す必要があり.serializeArray()ますか? それとも行ごとに 1 つのフォームですか?

データ指向のアプローチから、これに対処する最善の方法は何ですか? データをバックエンドに送信しますが、バックエンド開発者がデータにできるだけ簡単にアクセスできるようにしたいと考えています。