Understanding cache-friendly, data-oriented objects and handles

Question

using namespace std;

Consider a traditional OOP approach to entity/object management:

struct Entity { bool alive{true}; }

struct Manager {        
    vector<unique_ptr<Entity>> entities; // Non cache-friendly

    void update() {
        // erase-remove_if idiom: remove all !alive entities
        entities.erase(remove_if(begin(entities), end(entities),
            [](const unique_ptr<Entity>& e){ return !e->alive; }));
    }
};

struct UserObject {
    // Even if Manager::entities contents are re-ordered
    // this reference is still valid (if the entity was not deleted)
    Entity& entity;
};

However, I would like to try a data-oriented approach: not dynamically allocating Entity instances, but storing them in cache-friendly linear memory.

struct Manager {
    vector<Entity> entities; // Cache-friendly
    void update() { /* erase-remove_if !alive entities */ }
};

struct UserObject {
    // This reference may unexpectedly become invalid
    Entity& entity;
};

Seems nice. But... if std::vector needs to reallocate its internal array, all references to the entities will become invalid.

The solution is using an handle class.

struct Entity { bool alive{true}; };
struct EntityHandle { int index; };

struct Manager {
    vector<Entity> entities; // Cache-friendly      
    void update() { /* erase-remove_if !alive entities */ }
    Entity& getEntity(EntityHandle h) { return entities[h.index]; }
};

struct UserObject { EntityHandle entity; };

If I'm only adding/removing entities at the back of the vector, it seems to work. I can use the getEntity method to retrieve the entity I want.

But what if I remove an Entity from the middle of the vector? All EntityHandle instances will now hold the incorrect index, since everything was shifted. Example:

---

The handle points to index: 2

---

Entity A gets removed during update()

Now the handle points to the wrong entity.

---

How is this problem usually dealt with?

Are the handle indices updated?

Is the dead entity replaced with a placeholder?

---

To clarify:

This and this are examples of what I mean by cache-friendly design.

Also, component systems such as Artemis claim to be in a linear cache-friendly design, and they use solutions similar to handles. How do they deal with the problem I describe in this question?

Answer 1

There's a great powerpoint done by insomniac, their solution was something like this

template<typename T, size_t SIZE>
class ResourceManager
{
    T data[SIZE];
    int indices[SIZE];
    size_t back;

    ResourceManager() : back(0)
    {
        for(size_t i=0; i<SIZE; i++)
            indices[i] = static_cast<int>(i);
    }

    int Reserve()
    { return indices[back++]; }

    void Release(int handle)
    {
        for(size_t i=0; i<back; i++)
        {
            if(indices[i] == handle)
            {
                back--;
                std::swap(indices[i], indices[back]);
                return;
            }
        }
    }

    T GetData(size_t handle)
    { return data[handle]; }
};

I hope this example demonstrates the idea plainly.