1
\$\begingroup\$

I have an ECS implementation I wish to make more cache friendly and I'm stuck on what I should do.

Let me first present you with the implementation.

ECSManager.h:

class ECSManager
{
private:
    std::unordered_map<unsigned int, std::vector<std::unique_ptr<ComponentBase>>> m_Components;
    std::unordered_map<unsigned int, std::unique_ptr<Entity>> m_Entities;
    std::vector<std::unique_ptr<System>> m_Systems;
public:

    void Update()
    {
        for (const auto& system : m_Systems)
        {
            auto entities = GetEntities(system->GetComponentsList());
            system->Update(std::move(entities), this);
        }
    }

    const Entity& CreateEntity(std::string&& name)
    {
        std::unique_ptr<Entity> e(new Entity(std::forward<std::string>(name)));
        unsigned int id = e->GetID();
        m_Entities.try_emplace(id, std::move(e));
        return *m_Entities[id].get();
    }

    template <typename TSystem, typename... Args>
    const System& CreateSystem(Args&&... args)
    {
        static_assert(std::is_base_of<System, TSystem>::value, "type parameter of this class must derive from System");
        m_Systems.push_back(std::unique_ptr<TSystem>(new TSystem(std::forward<Args>(args)...)));
        return *m_Systems[m_Systems.size() - 1].get();
    }

    template <typename TComponent, typename... Args>
    void AddComponent(unsigned int entityId, Args&&... args)
    {
        unsigned int componentID = TComponent::ID;
        if (m_Components.find(componentID) == m_Components.end())
            m_Components[componentID] = std::vector<std::unique_ptr<ComponentBase>>();
        m_Components[componentID].push_back(std::unique_ptr<TComponent>(new TComponent(std::forward<Args>(args)...)));

        m_Entities[entityId]->AddComponent(componentID, m_Components[componentID].size() - 1);
    }

    template <typename TComponent>
    TComponent& GetComponent(const Entity& entity)
    {
        static_assert(std::is_base_of<ComponentBase, TComponent>::value, "type parameter of this class must derive from Component");
        auto componentsIndex = entity.GetComponentsIndex();
        return *dynamic_cast<TComponent*>(m_Components[TComponent::ID][componentsIndex[TComponent::ID]].get());
    }

    template <typename TComponent>
    std::vector<TComponent>& GetComponents()
    {
        unsigned int componentID = TComponent::ID;
        return m_Components[componentID];
    }

    std::vector<std::vector<std::reference_wrapper<Entity>>> GetEntities(const std::vector<DynamicBitset>& componentsList)
    {
        std::vector<std::vector<std::reference_wrapper<Entity>>> entities;
        for (unsigned int i = 0; i < componentsList.size(); i++)
        {
            auto& componentIDs = componentsList[i];
            size_t count = componentIDs.size();
            entities.push_back(std::vector<std::reference_wrapper<Entity>>{});
            for (const auto& entity : m_Entities)
            {
                const auto& entitySignature = entity.second->GetSignature();
                if (count > entitySignature.size())
                    continue;

                bool equal = true;
                for (std::size_t i = 0; i != count; i++)
                {
                    if (componentIDs[i]() && !entitySignature[i]())
                    {
                        equal = false;
                        break;
                    }
                }
                if (!equal)
                    continue;

                entities[i].push_back(*entity.second.get());
            }
        }
        return entities;
    }
};

ECSManager is responsible for holding the different kind of Components, Entities, and Systems as-well as creating them (no need for removing ATM).

When adding a Component to an Entity the ECSManager will not only keep track of the Component but will also call AddComponent(componentID, m_Components[componentID].size() - 1); on the Entity which will make the Entity keep hold of the index of that component ID inside an internal data structure so later this could be used as a lookup method to find an Entity's specific component type inside m_Components using template <typename TComponent> TComponent& GetComponent(const Entity& entity).

ECSManager also call Update each frame and calls the Update method of each System with the relevant entities the system wish to operate on by calling GetEntities(system->GetComponentsList()); and finding which entities' components signature match the component signature the System wants to operate on.

Problem I think there's with this implementation being cache friendly:

  • System operates on a vector of matching entities based on component signature std::vector<std::vector<std::reference_wrapper<Entity>>> while the vectors are stored and served to the System in linear fashion, when iterating them let's assume there will be one line cache load for the vector's items but also a line cache for each of the item since references are pointers behind the scene. So optimally System could be served a vector of value type entities but this will be a problem since systems potentially modify entities so we can't pass copies, and we can't pass the whole original m_Entities vector (let's assume m_Entities is now std::vector<Entity> instead of what it is in my implementation) since the System needs to operated only on a subset of entities.
    I think an option would be to pass ALL entities to the Update method of a System with a descriptor array of what entities should be used by this system (as suggested in Scott Meyer's article) so the whole descriptor array will be loaded into cache and not the whole entity array but I find A problem with this approach: Entity in my implementation could be simplified to just an ID of type uint32_t for example so if we had 100 entities let's say we'll load into cache 100 * sizeof(bool) + sizeof(Entity) * number_of_valid_entities_for_specific_system bytes instead of 100 * sizeof(uint32_t) which IS a nice micro optimization but if we had say 10000000000 entities we would still iterate over 10000000000 items which I'm not sure if this micro optimization will outweigh its benefits as more entities are presented.
  • Lets now assume we tackled somehow the first problem. Now each system gets a linear set of entities by value to operate on. Now each system will query each entity for the relevant components it wants to operate on with a call to template <typename TComponent> TComponent& GetComponent(const Entity& entity). This is also not cache friendly since m_Components is stored in an std::unordered_map which is not stored linearly and another problem here again is that we have vector of pointers so we'll have a cache line load for each dereference of the component which is inevitable since I'm holding a vector of pointers. I do this because ComponentBase is an abstract class and I can't have std::vector<T> where T is abstract. One way this can be solved is that instead of System Update operating on entities it will operate on contiguous array of components.A possible implementation could be as follows:

    template <typename TComponent>
        class ComponentManager {
            std::vector<TComponent> m_Components;
            std::vector<Entity> m_Entities;
    
            Component& Create(Entity entity)
            {
                m_Components.push_back(TComponent());
                m_Entities.push_back(entity);
                return m_Components.back();
            }
        };
        ComponentManager<Transform> transforms;
        transforms.Create(entity);
        // System update loop
        for(size_t i = 0; i < transforms.GetCount(); ++i)
        {
            Transform& transform = transforms[i];
        }
    

But the problem with this is if we have the system operates on more entities with more than on component that we would have to either reference another ComponentManager<TComponent> and use a lookup method with a map involved again causing alot of cache misses and loading of new cache lines or if we could somehow sync the indices of different ComponentManager<TComponent> to match to the index of the same entity but that wouldn't be possible because take this example:

Entity e1;
// add Mass component to e1
// Now ComponentManager<Mass>[0] is e1 mass
Entity e2;
// add Transform component to e2
// Now ComponentManager<Transform>[0] is e2 transform
// add Mass component to e2
// Now ComponentManager<Mass>[1] is e2 mass
...
Entity e3;
// add RigidBody component to e3
// Now ComponentManager<RigidBody>[0] is e3 rigidbody
// add Mass component to e3
// Now ComponentManager<Mass>[2] is e3 mass

we can either sync e2 mass to be the first mass at index 0 or e3 mass to be the first mass at index 0 but we can't have them both at index 0.

  • Beside these 2 points which I think they're the main issue there're so easy to fix issues such as change std::vector<std::unique_ptr<System>> m_Systems; to std::vector<System> m_Systems; to avoid cache line loading for each dereferenced system and other issues are really dependent on what solution I'll go with so I don't wanna talk to much about them.

So these are basically the issues as I SEE THEM, maybe I'm wrong, maybe there're more, I'm not sure and would like people who have better understanding give me their opinions and hear their ideas.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.