0

mapカスタム ID をvectorインデックスにマップするためにa を使用することを考えています。

struct Mesh
{
    GLsizei mIndices;
    GLuint mVBO;
    GLuint mIndexBuffer;
    GLuint mVAO;

    size_t vertexDataSize;
    size_t normalDataSize;
};

typedef uint32_t MeshID;

std::map<MeshID, uint16_t> gMeshIDIndexMap;
std::vector<Mesh> gMeshes;


std::vector<MeshID> drawCmds = {1, 1, 2, 3, 4, 5, 8, ,8 ,8, 9, 10, ...};  //sorted
std::for_each(drawCmds.begin(), drawCmds.end(), [](MeshID& id) 
{
    Mesh& mesh = gMeshes[gMeshIDIndexMap.at(id)];
    glBindVertexArray(mesh.mVAO);
    glDrawElements(GL_TRIANGLES, mesh.mIndexBuffer, GL_UNSIGNED_INT, 0);
    glBindVertexArray(0);

    ....  
}

std::map はその要素を連続したメモリに保存しないため、新しい反復ごとに、gMeshIDIndexMap.at(id)新しいキャッシュ ライン全体をキャッシュにロードする必要があります。これにより、キャッシュが破棄され、多くのキャッシュ ミスが発生しますよね? これを改善してキャッシュミスをできるだけ少なくするにはどうすればよいですか?

4

1 に答える 1

2

(1) 最初にマップにデータを入力し、次に (2) ルックアップに使用し、(3) 最後にマップを破棄する場合はboost::container::flat_map、適切な選択になる可能性があります。これは基本的にソートされたベクトルです。利点（ウェブサイトから恥知らずに盗まれた）：

  • 標準の連想コンテナよりも高速なルックアップ
  • 標準の連想コンテナーよりもはるかに高速な反復
  • 小さなオブジェクト (および、shrink_to_fit が使用されている場合は大きなオブジェクト) のメモリ消費量が少ない
  • キャッシュ パフォーマンスの向上 (データは連続したメモリに格納されます)

潜在的な欠点:

  • 最悪の場合の線形時間の挿入と線形時間の削除

コンテナは、上記のパターン (データで埋める - 検索に使用する - 破棄する) に従って使用されることが多いことがわかります。使用法がこのパターンに当てはまる場合は、並べ替えられたベクターが適している可能性があります。

MeshID を Mesh に入れる必要があります。マップ内の要素数がわかっている場合、または合理的な見積もりができる場合は、事前にスペースを予約して、基になるベクターのバッファーの再割り当てのために要素を移動する必要がないようにすることもできます。

私のアドバイスは基本的にComicSansMS の回答と同じです。独自の flat_map をローリングする代わりに、boost コンテナーを使用することをお勧めします。

もちろん、使用パターンが次のようになる場合もあります。(a) 検索、(b) ランダムな位置での削除、または (c) ランダムな位置での挿入のいずれかを行います。マップの存続期間全体で、(a) または (b) または (c) のいずれかを一見ランダムに実行します。この場合、 などのノードベースのコンテナstd::mapがより適切な選択になる可能性があります。

于 2013-10-02T11:47:37.820 に答える