0

我正在考虑使用 amap将自定义 ID 映射到vector索引，例如；

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 的回答基本相同；我只建议你使用 boost 容器而不是滚动你自己的 flat_map。

当然，您的使用模式可能是这样的：您执行 (a) 查找或 (b) 在随机位置删除或 (c) 在随机位置插入；在您的地图的整个生命周期中，您会执行 (a) 或 (b) 或 (c) 看似随机的操作。在这种情况下，基于节点的容器（例如std::map）可能是更好的选择。

于 2013-10-02T11:47:37.820 回答