Using map in conjunction with vector and cache imp

Question

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);

    ....  
}     

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?

Answer 1

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):

• 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)

A potential drawback:

• Worst case linear-time insertions and linear-time deletions

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.

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.

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.

---

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.