c++handledata-oriented-design

Understanding cache-friendly, data-oriented objects and handles


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

Diagram 1


Entity A gets removed during update()

Now the handle points to the wrong entity.

Diagram 2


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?


Solution

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