Entity System creating Components

Question

Over every entity system I see implemented in C++, or even in Java/C# (e.g. the Artemis framework). I see components not allocated via a new operator (or something similar, e.g. std::make_shared). For example:

entity.addComponent(new Position(32, 4, 5));
entity2.addComponent(new Position(5, 6, 7));
// those two position components that were just created
// may/may not be together in memory

// or even:
// how can you avoid using new here? (in the implementation)
entity.addComponent<Position>(32, 4, 5); 

Doesn't this harm performance, as there would be cache misses (since new can allocate data anywhere from the heap)? How would you implement a system in such a way that the components of each type are allocated contiguously in memory, so you avoid cache misses? I mainly want to know how one would do so in C++.

Answer 1

Most entity systems don't use Data Oriented Design. Note that entity system doesn't necessarily imply DOD, it just means splitting gameplay functionality into different component classes giving entities certain features and behavior. You can (very easily) create a bloated and horribly slow Object-Oriented version of an entity system. So entity systems are just a design concept. DOD is a completely orthogonal code design concept that can however be applied very easily to entity systems.

So on to your questions:

Doesn't this harm performance, as there would be cache misses (since new can allocate data anywhere from the heap)?

Yes. Well, maybe. It all depends on access patterns. But yeah, if you want to update all Position components in one go, well designed and aligned data can be far more efficient. Still, know your data and know how you use your data te be sure.

How would you implement a system in such a way that the components of each type are allocated contiguously in memory, so you avoid cache misses?

There are multiple ways to do that using preallocated memory and such, you could use multiple smaller pools for finegrained memory control or if you know how much a level is going to use, you can just allocate that much memory etcetera etcetera. This is all described in the answers the others gave.

That could be a solution, but I think you're treating a symptom, not the real problem: You want to use classes. Don't do that, if possible. It's bad for a number of reasons, among which is cache locality. There is no reason for either the entity or the components to be classes. Now I've talked about this at more length in my answer here: When/where to update components I'll give you a very quick rundown though, or just read the long answer there and skip the next two paragraphs

All the entity is is an identifier that binds together a number of components. The entity could just be a unique integer. It can also be a class with a set of pointers pointing to all component data if you need that. Still, I don't see the necessity for that. If an entity is a unique integer, you could just as easily write a helper function to get a component given an entity id.

So now to get rid of the component classes themselves. There's no actual need for that either. What you need is two things: some data stored somewhere for each component (component data) and some way to update that data (component behavior). What a component class does is combine those two, but there are other ways. For instance, creating a component system where there are managers for each component type. All component data is stored in arrays in the manager, accessed using the entity id (which is just an integer as I said above, more about that in my answer here). The behavior is one simple update() function in the manager class which updates all components it manages in one go, fully utilizing the cache locality and optimization benefits a single update loop provides.

The same thing could be done using component classes which are aligned in memory, but there are still a lot of issues with that approach, most important of which are memory/cache related. What happens when you delete a component from memory? You can't just move one of the other components into the empty space, since that would mess up all pointers pointing to that component. How big is your component class data? It may very well be about the size of one cache line (64 bytes in modern x86). If that's the case, your system will hardly be any faster than one where data is all over memory.

The biggest issue is how you use your data. How much component data do you need each update? Say you have a component with a position (vec3), velocity (vec3) and two other 4 byte variables. That's 32 bytes of data per component (assuming you don't use any virtual function crap). Now when you update your component, you may need all variables and you need to load all data. That's fine. Cache line size is 64 and your components are all packed in memory, so when you load one component, you automatically load the next one into cache. Great. Now what happens when you only need to access the position for another unrelated update loop. You load 64 bytes of data, but it's only got 2 vec3's you need. You've just wasted 40 loaded bytes of data. This is exactly what DOD is about avoiding.

If on the other hand, you had a component manager class which stores component data in number of arrays, one for positions, one for velocities and two for the other data, your cache will be utilized fully in both situations. So if you only need velocities, when it loads one, it will load 64 bytes around it into cache. That's more than five velocity vectors. When you need all data, it will do the same for the data in the other arrays.

So to summarize, I'll quote a bit from another answer I gave here

So the goal of DOD isn't using linear arrays, it's maximizing cache utilization by placing data that is accessed at (about) the same time adjacent in memory. If you nearly always access 3 variables at the same time, you don't need to create 3 arrays for each variable, you could just as easily create a struct which contains only those 3 values and create an array of these structs. The best solution always depends on the way you use the data. If your access patterns are linear, but you don't always use all variables, go for separate linear arrays. If your access patterns are more irregular but you always use all variables at the same time, put them in a struct together and create an array of those structs.

Hope this helps! Let me know if anything is unclear or if I missed something!

Answer 2

entity.addComponent<Position>(32, 4, 5);

Is definitely possible using C++11 variadic templates, with no performance difference from the original versions.

struct Entity
{
    std::vector<std::unique_ptr<Component>> components;

    template<typename T, typename... TArgs> T& createComponent(TArgs&&... mArgs)
    {
        auto result(new T(std::forward<TArgs>(mArgs)...));
        components.push_back(std::unique_ptr<Component>(result));
        return *result;
    }
}

Entity entity;
entity.createComponent<Position>(32, 4, 5); // valid

Cache misses will be present when allocating with new, but it's not so bad. In my entity system I can create/destroy >10000 components without noticeable frame loss. It will probably never be a bottleneck, unless you require an amazingly high amount of entities/components.

If you want to check my implementation, it's on GitHub.

If you want to check a data-oriented component entity system, check out Artemis.

Answer 3

It's my ComponentContainer code:

  #pragma once
#include <cassert>
#include <vector>
#include <unordered_map>
#include "tool/config.h"
#include "component.h"

struct ComponentContainerData {
    ComponentType type;
    size_t sizeOfComponent;
    size_t capacity;
    size_t freeIndex;
};

template<typename ComponentClass>
struct Components {
    size_t size;
    ComponentClass* components;

    ComponentClass& operator[](size_t index) {
        return components[index];
    }
};

class ComponentContainer {
public:
    bool componentExist(ComponentHandle component) {
        assert(component != 0 && "Null component request (null component is always invalid)");
        return componentHandles.find(component) != componentHandles.end();
    }

    template<typename ComponentClass>
    ComponentClass* getComponent(ComponentHandle component) {
        assert(componentExist(component));
        return (ComponentClass*) componentHandles[component];
    }

    template<typename ComponentClass>
    ComponentClass* getComponent(Entity owner) {
        assert(entityExist(owner));

        for (unsigned int i = 0; i < containers.size(); i++) {
            if (containers[i].second.type == ComponentClass::type) {
                for (unsigned int j = 0; j < containers[i].second.freeIndex; j++) { //TODO: possible optimalization - owner is sorted
                    ComponentClass* component = (ComponentClass*) containers[i].first + j;
                    if (component->owner == owner)
                        return component;
                }
                return nullptr;
            }
        }
        return nullptr;
    }

    template<typename ComponentClass>
    Components<ComponentClass> getComponents() { //when optimalization mentioned in comment below(containers field) will be done, it will be simple return {containers[ComponentClass::type.....
        for (unsigned int i = 0; i < containers.size(); i++) {
            if (containers[i].second.type == ComponentClass::type) {
                return {containers[i].second.freeIndex, (ComponentClass*) containers[i].first};
            }
        }
        return {0, nullptr};
    }

    template<typename ComponentClass, typename ...CmpArgs>
    ComponentClass* createComponent(Entity owner, CmpArgs&& ...cmpArgs) {
        assert(entityExist(owner));

        auto container = locateAndPrepareComponentContainer<ComponentClass>();
        if (!container)
            return nullptr;

        ComponentClass* createdComponent = new (container->first + sizeof(ComponentClass) * container->second.freeIndex)
                ComponentClass(owner, nextComponentHandle, std::forward<CmpArgs>(cmpArgs)...);

        componentHandles[nextComponentHandle] = (Component*) &container->first[sizeof(ComponentClass) * container->second.freeIndex];
        ComponentHandle currentHandle = nextComponentHandle++;
        container->second.freeIndex++;

        logger.info("Created new component. Owner: %u, Handle: %llu, (int)Type: %d", (unsigned int) owner, currentHandle, (int) ComponentClass::type);
        return createdComponent;
    }

    template<typename ComponentClass>
    void deleteComponent(Entity owner) {
        assert(entityExist(owner));

        for (auto& container : containers) {
            if (container.second.type == ComponentClass::type) {
                ComponentClass* currentComponent = (ComponentClass*) container.first;
                for (unsigned int i = 0; i < container.second.freeIndex; i++, currentComponent++) {
                    if (currentComponent->owner == owner) {
                        logger.info("Deleted component %llu. Type: %d, Owner: %u", currentComponent->handle, (int) ComponentClass::type, (unsigned int) owner);

                        componentHandles.erase(currentComponent->handle);
                        currentComponent->~ComponentClass();

                        ComponentClass* lastComponent = (ComponentClass*) container.first + --container.second.freeIndex;
                        if (currentComponent != lastComponent) {
                            memcpy(currentComponent, lastComponent, sizeof(ComponentClass));
                        }
                        return;
                    }
                }
                logger.warn("Cannot delete component type %d with owner %u: component not in container", (int) ComponentClass::type, (unsigned int) owner);
                return;
            }
        }
        logger.warn("Cannot delete component type %d with owner %u: component not found, even container don't exist", (int) ComponentClass::type, (unsigned int) owner);
    }

    bool entityExist(Entity entityID) {
        assert(entityID < entityExistingTable.size() && "Entity with this id cannot exist (and we're reading garbage)");
        return entityID < entityExistingTable.size() && entityExistingTable[entityID];
    }

    Entity createEntity() {
        entityExistingTable.push_back(1);
        return Entity(entityExistingTable.size() - 1);
    }

    void deleteEntity(Entity owner) {
        assert(entityExist(owner));

        for (auto& container : containers) {
            Component* currentComponent = (Component*) container.first;
            for (unsigned int i = 0; i < container.second.freeIndex; i++) {
                if (currentComponent->owner == owner) {
                    logger.info("deleteEntity: Deleted component %llu. Type: %d, Owner: %u", currentComponent->handle, container.second.type, (unsigned int) owner);

                    componentHandles.erase(currentComponent->handle);
                    currentComponent->~Component();

                    Component* lastComponent = (Component*) container.first + --container.second.freeIndex;
                    if (currentComponent != lastComponent) {
                        memcpy(currentComponent, lastComponent, container.second.sizeOfComponent);
                    }
                    continue;
                }
                char* rawCurrent = (char*) currentComponent;
                currentComponent = (Component*) (rawCurrent + container.second.sizeOfComponent);
            }
        }
    }

    ~ComponentContainer() {
        for (auto& container : containers) {
            free(container.first); //FIXME: this only deallocates memory, won't call destructors. (components shouldn't have destructors but...)
        }
    }

private:
    std::vector<std::pair<char*, ComponentContainerData> > containers; //TODO: possible optimalization: it should be containers[i].second.type == i. So a)change it to map, b)when creating container fill fields with 0 while
    std::unordered_map<ComponentHandle, Component*> componentHandles; //untill desired type is if containers.size < type, else just change this 0 to appropiate type. 0 can be indicated by pair {nullptr, {}} or sthk
    ComponentHandle nextComponentHandle = 1; //maybe even component handle stuff will be unnecessary, since it will be fast.

    std::vector<char> entityExistingTable;


    template<typename ComponentClass>
    std::pair<char*, ComponentContainerData>* locateAndPrepareComponentContainer() {
        for (auto& container : containers) {
            if (container.second.type == ComponentClass::type) {
                if (container.second.freeIndex >= container.second.capacity) {
                    if (!resizeContainer(container, sizeof(ComponentClass), (int) ComponentClass::type)) {
                        return nullptr;
                    }

                    for (unsigned int i = 0; i < container.second.freeIndex; i++) {
                        ComponentClass* elem = (ComponentClass*) container.first;
                        componentHandles[elem[i].handle] = &elem[i];
                    }
                }
                return &container;
            }
        }

        if (!createNewContainer<ComponentClass>()) {
            return nullptr;
        }
        return &containers.back();
    }

    bool resizeContainer(std::pair<char*, ComponentContainerData>& container, size_t sizeOfElement, int typeID) {
        logger.info("Resizing component container for type %d. Current Capacity: %u", typeID, container.second.capacity);

        size_t capacity = container.second.capacity * config.get("ECS.growFactor", 2);
        char* result = (char*) realloc(container.first, capacity * sizeOfElement);
        if (!result) {
            //try to get at least necessary amount of memory
            capacity = container.second.capacity + 1;
            result = (char*) realloc(container.first, capacity * sizeOfElement);
            if (!result) {
                logger.fatal("Cannot resize component container, even by 1 element. Desired capacity: %d, Sizeof(Type): %d, type: %d", capacity, sizeOfElement, typeID);
                assert(!"resizeContainer: cannot allocate memory for new element");
                return false;
            }
        }

        container.second.capacity = capacity;
        container.first = result;
        return true;
    }

    template<typename ComponentClass>
    bool createNewContainer() {
        ComponentContainerData metadata;
        metadata.type = ComponentClass::type;
        metadata.capacity = config.get("ECS.initialCapacity", 128);
        metadata.sizeOfComponent = sizeof(ComponentClass);
        metadata.freeIndex = 0;

        char* rawComps = (char*) malloc(sizeof(ComponentClass) * metadata.capacity);
        if (!rawComps) {
            //try to get at least necessary amount of memory
            metadata.capacity = 1;
            rawComps = (char*) malloc(sizeof(ComponentClass));
            if (!rawComps) {
                logger.fatal("Cannot create new container, even for 1 element. Sizeof(Type): %d, Type: %d", sizeof(ComponentClass), (int) ComponentClass::type);
                assert(!"Create component: cannot allocate memory for new container; even for 1 element");
                return false;
            }
        }

        containers.push_back({rawComps, metadata});
        return true;
    }
};

It has all components of the same type in array, and all arrays are in one array, so there is no need to update ComponentClass if new components are added. It also forwards arguments to components.

component.h:

    #pragma once
#include <boost/serialization/strong_typedef.hpp>

enum class ComponentType {
    SampleComponent, //for unit test
    PositionComponent,
    SpriteComponent,
    RectComponent,
    MovementComponent,
    CollisionComponent,
    SizeComponent
};

using ComponentHandle = unsigned long long;

BOOST_STRONG_TYPEDEF(unsigned
        int, Entity);

struct Component {
    Component(Entity owner, ComponentHandle handle) : owner(owner), handle(handle) {
    }

    virtual ~Component() {
    }

    Entity owner;
    ComponentHandle handle;
};

tool/config.h is unneded, it's only config.get calls, their second value is default.

All derived Components must have static variable of type ComponentType and name type

Answer 4

If you absolutely want to do this, you can use a custom memory allocator that reserves a chunk for each Entity and places its components continously inside that chunk. However this may waste memory again, which can (in theory) cause more cache misses too...

However... unless you have solid proof that this causes slowdowns for you, don't worry about it. Premature optimization can eat up a lot of your time, not only when creating the system, but also when maintaining it later. Most likely your game engine's speed isn't going to be determined by trivial things like this, not to mention that complex components (the ones that may actually slow things down for you) are most likely larger and would cause cache misses anyway.

Having said that, your particular example may be somewhat valid. I think the position of an entity should be bundled together with the entity itself (part of the class, not a component) for two reasons. First of all, if you do a lot of data processing on the entities, it may improve performance. But more importantly, each entity can only have one position, and the possibility of adding several position components breaks this rule, causing problems.

Answer 5

A possible solution is a ComponentManager class. This one is similar to a tuple of vectors in that it should keep a mapping of types to the index of each Component type vector. After that it all comes down to representing the components of an entity using indices to the appropriate vectors.