使用映射结合向量和缓存影响 [英] Using map in conjunction with vector and cache impact

问题描述

我想使用 map 将自定义ID映射到向量索引，如;

I'm thinking of using a map to map custom ID's to vector indexes, like;

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）将不得不加载一个新的缓存行到缓存，这将垃圾缓存，并导致大量的缓存未命中

Since the std::map does not store its elements on contiguous memory, on each new iteration gMeshIDIndexMap.at(id) will have to load a whole new cache line into the cache. This will trash the cache and cause alot of cache misses right? What can I do to improve on this and get as few cache misses as possible?

推荐答案

如果你（1）先填充你的地图与数据，然后（2）使用它进行查找，和（3）最终当你完成你毁了它然后 boost :: container :: flat_map 可能是您。它基本上是一个排序的向量。优点（无耻地从网站被盗）：

If you (1) first fill your map with data, then (2) use it for lookups, and (3) finally when you are done you destroy it then boost::container::flat_map might be a good choice for you. It is basically a sorted vector. Advantages (shamelessly stolen from the website):

• 比标准关联容器更快的查找




• 减少内存消耗小型对象（如果使用shrink_to_fit
  ，则用于大对象）


• 改进的缓存性能（数据存储在连续的内存中）

• Faster lookup than standard associative containers
• Much faster iteration than standard associative containers
• Less memory consumption for small objects (and for big objects if shrink_to_fit is used)
• Improved cache performance (data is stored in contiguous memory)

潜在的缺点：

• 最差的情况是线性时间插入和线性时间删除

观察结果是容器经常被使用根据上面的模式（填充数据 - 用于查找 - 销毁）。如果你的用法符合这种模式，一个排序的向量可能是一个不错的选择。

The observation is that the containers are often used according to the above pattern (fill with data - use for lookups - destroy). If your usage fits this pattern, a sorted vector is likely to be a good choice.

您需要将MeshID放入网格中。如果你知道或者你可以给出地图中元素的数量的合理估计，你甚至可以预先保留空间，所以元素不必移动由于底层向量的缓冲区重新分配。

You need to put the MeshID into the Mesh. If you know or you can give a reasonable estimate for the number of elements in your map, you can even reserve the space in advance so the elements don't have to be moved due to buffer reallocations of the underlying vector.

我的建议基本上与 ComicSansMS的回答相同;我只建议你使用boost容器而不是滚动自己的flat_map。

My advice is basically the same as ComicSansMS' answer; I only suggest that you use the boost container instead of rolling your own flat_map.

当然，使用模式看起来像这样：你做（a）查找或（b）在随机位置删除或（c）在随机位置插入;在你的地图的整个生命周期，你做（a）或（b）或（c）看似随机。在这种情况下，基于节点的容器，例如 std :: map 可能是一个更好的选择。

Of course, it might happen that your usage pattern looks like this: you do either (a) a lookup or (b) deletion at a random position or (c) insertion at a random position; during the entire lifetime of your map you do either (a) or (b) or (c) seemingly random. In this case, a node-based container, such as std::map is likely to be a better choice.

这篇关于使用映射结合向量和缓存影响的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！