4

これはグッドプラクティスについての質問です

3D エンジン、物理エンジン、有限要素法、または古典的な分子動力学ソルバーなどで典型的な状況を考えてみましょう: さまざまなタイプのオブジェクト (頂点、エッジ、面、境界のあるソリッド ボリュームなど) があり、それらは相互に架橋されています (例:頂点は、どのエッジがそれに接続されているかを認識しており、その逆も同様です)。そのようなエンジンのパフォーマンスと使用の利便性のためには、そのような接続のネットワークをすばやく閲覧できることが重要です。

問題は、リンクされたオブジェクトを配列内のインデックスで指定するのと、ポインタで指定するのとのどちらがよいかということです。...特にパフォーマンス面で

typedef index_t uint16_t;

class Vertex{
    Vec3 pos;
    #ifdef BY_POINTER
    Edge*   edges[nMaxEdgesPerVertex];
    Face*   faces[nMaxFacesPerVertex];
    #else
    index_t edges[nMaxEdgesPerVertex];
    index_t faces[nMaxFacesPerVertex];
    #endif
}

class Edge{
    Vec3   direction;
    double length;
    #ifdef BY_POINTER
    Vertex* verts[2];
    Faces*  faces[nMaxFacesPerEdge];  
    #else
    index_t verts[2];
    index_t faces[nMaxFacesPerEdge];
    #endif
}

class Face{
    Vec3   normal;
    double isoVal; // Plane equation: normal.dot(test_point)==isoVal
    #ifdef BY_POINTER
    Vertex* verts[nMaxVertsPerFace];
    Edge*   edges[nMaxEdgesPerFace];
    #else
    index_t verts[nMaxVertsPerFace];
    index_t edges[nMaxEdgesPerFace];
    #endif
}

#ifndef BY_POINTER
// we can use other datastructure here, such as std:vector or even some HashMap 
int nVerts,nEdges,nFaces;
Vertex verts[nMaxVerts];
Edge   edges[nMaxEdges];
Vertex faces[nMaxFaces];
#endif

インデックスの利点:

  • インデックスを使用すると、32 ビットまたは 64 ビットのポインターの代わりにインデックスにuint8_torを使用すると、メモリ効率が向上します。uint16_t
  • index は、いくつかのビットでエンコードされたいくつかの追加情報 (たとえば、エッジの向きに関する情報) を運ぶことができます。
  • 配列内のオブジェクトの順序付けは、構造に関する情報を運ぶことができます (たとえば、立方体の頂点は次のように順序付けできます{0b000,0b001,0b010,0b011,0b100,0b101,0b110,0b111})。この情報はポインタには表示されません

ポインターの利点:

  • オブジェクトを格納するために配列 (または他のデータ構造) を気にする必要はありません。オブジェクトは、 によってヒープ上に動的に割り当てることができますnew Vertex()。
  • 配列のベースアドレスを追加する必要がないため(?)、高速になる可能性があります (?)。しかし、これはメモリ レイテンシに関してはおそらく無視できる程度です (?)。
4

2 に答える 2

5

インデックスに 32 ビットまたは 64 ビット ポインターの代わりに uint8_t または uint16_t を使用すると、インデックスを使用するとメモリ効率が向上します。

真実。表現を小さくすると、構造体の合計サイズが小さくなり、走査時のキャッシュ ミスが減少します。

index は、いくつかのビットでエンコードされたいくつかの追加情報 (たとえば、エッジの向きに関する情報) を運ぶことができます。

真実。

オブジェクトを格納するために配列 (または他のデータ構造) を気にする必要はありません。オブジェクトは、new Vertex() によってヒープ上に動的に割り当てることができます。

これはまさに、パフォーマンスについて言えば、やりたくないことです。不必要なキャッシュの欠落を避けるために、頂点がすべてパックされていることを確認する必要があります。この場合、配列はその間違った誘惑からあなたを救います. また、キャッシュ ミスを最小限に抑えるために、少なくとも可能な限り順番にアクセスする必要があります。

データ構造がどれだけパックされ、小さく、シーケンシャルにアクセスされるかによって、実際にパフォーマンスが向上します。

配列のベースアドレスを追加する必要がないため (?)、高速になる可能性があります (?)。しかし、これはメモリ レイテンシに関してはおそらく無視できる程度です (?)。

無視できる可能性があります。おそらく、特定のハードウェアやコンパイラに依存します。

インデックスに関するもう 1 つの欠けている利点は、再割り当て時に管理が容易になることです。次のように、成長できる構造を考えてみましょう。

struct VertexList
{
  std::vector<Vertex> vertices;

  Vertex *start; // you can still access using vector if you prefer; start = &vertices[0];
}

ポインタを使用して特定の頂点を参照している場合、再割り当てが発生すると、無効なポインタになります。

于 2016-04-21T10:54:55.923 に答える
5

パフォーマンスに関して重要なのは、ホット パスで一般的に行われるトラバーサル順序で「次の」要素を読み取る速度です。

たとえば、あるパスを表す一連のエッジがある場合、new接続されている順序でメモリに連続して格納する必要があります (各エッジを使用するのではありません)。

この場合 (パスを形成するエッジ)、ポインタが必要ないことは明らかであり、インデックスも必要ありません。接続はストレージの場所によって暗示されるため、必要なのは最初のエッジとおそらく最後のエッジへのポインターだけです (つまり、パス全体を に格納できますstd::vector<Edge>)。

活用できるドメイン知識を示す 2 番目の例: 最大 8 人のプレイヤーをサポートするゲームがあり、「パスの各エッジを訪れたユーザー」を保存したいとします。ここでも、8 人のプレーヤーを参照するためのポインターやインデックスは必要ありません。uint8_t代わりに、単純にそれぞれにa を格納し、Edge各プレイヤーのフラグとしてビットを使用できます。はい、これは低レベルのビット バンギングですが、Edge*. しかし、プレーヤーからEdges への逆方向のルックアップを行う必要がある場合、最も効率的な方法は、たとえばuint32_t各プレーヤー内に のベクトルを格納し、Edge配列にインデックスを作成することです。

しかし、パスの途中でエッジを追加および削除できるとしたらどうでしょうか? それでは、リンクされたリストが必要になるかもしれません。この場合、侵入型のリンク リストを使用し、 をプールに割り当てる必要Edgeがあります。これを行うとEdge、各プレーヤー オブジェクトの へのポインターを格納できます。ポインターは決して変更されず、更新する必要もありません。は単一のパスの一部にすぎないという理解の下で侵入リンクリストを使用するEdgeため、リンクリストポインターの外部ストレージは無駄になります (std::list各オブジェクトへのポインターを格納する必要がありますが、侵入リストはそうではありません)。

そのため、各ケースを個別に検討する必要があり、事前に発見できるドメインに関する知識をできるだけ多く持つ必要があります。ポインターとインデックス作成のどちらも最初のアプローチではありません。

于 2016-04-21T09:39:24.883 に答える