When it comes to developing a game at some point you want to have some data that defines it for it not being a black screen. The naive solution is of course to rely on the object oriented aspects C++ gives you. We will now check why that is not necessarily the best idea when it comes to performance, but also maintainability. We will implement as much compile time / meta programming aspects as possible

Investigating OOP

In order to have some runtime dispatch allowing OOP in C++ the compiler generates a VTable for every polymorphic type. That then tells us for inherited pointer types which function pointer to jump to and so on. Of course this has performance implications already, which we will address later on. The main problem comes when we look at how the data then is organized. Take the naive (default allocated) implementation here, where we are ignoring the vtable dispatch for now.

graph TD
    subgraph MemoryA
        A["Array of Structures"];
        A --> P1["IEntity*"];
        A --> P2["IEntity*"];
        A --> P3["IEntity*"];
        A --> P4["IEntity*"];
    end
    subgraph MemoryB 
        P1 --> val1["EntityA"];
        P2 --> val2["EntityB"];
        P3 --> val3["EntityC"];
        P4 --> val4["EntityB"];
    end

Now the question may arise, why we do not store the entities itself, rather than pointers. The reason for that is the design of C++, where we need indirection in order to allow OOP via virtual dispatch. Yet, the graph shows that the data may be (and most likely is) scattered in memory that way. Iterating this would result potentially in cache misses for each dereference. To avoid this it’s possible to use custom allocators in C++. Now we could allocate a huge page / linked list of pages where we store our entities. Then they at least are consecutive in memory along pages, which then results in more cache efficiency. Yet, that is still not perfect, due to the vtable dispatch. If we want to call a virtual update() method on IEntity assuming that Entity[A-C] are seperate classes, it could (not making statements here due to different compilers, etc. The concept still holds) look like this:

graph TD
    subgraph MemoryA["MemoryA"]
        A["Array of Structures"];
        A --> P1["IEntity*"];
        A --> P2["IEntity*"];
        A --> P3["IEntity*"];
        A --> P4["IEntity*"];
    end
    subgraph MemoryB["MemoryB"]
        P1 --> val1["EntityA"];
        P2 --> val2["EntityB"];
        P3 --> val3["EntityC"];
        P4 --> val4["EntityB"];
        val1 --> vptr1["vptrA"];
        val2 --> vptr2["vptrB"];
        val3 --> vptr3["vptrC"];
        val4 --> vptr2
        vptr1 --> VTableA;
        vptr2 --> VTableB;
        vptr3 --> VTableC;
    end
    subgraph text[".text"]
        VTableA --> updateA["EntityA::update()"]  
        VTableB --> updateB["EntityB::update()"]  
        VTableC --> updateC["EntityC::update()"]  
        end

Even though using our custom allocator MemoryA to MemoryB access does not necessarily result in a cache miss, yet naturally there’s still overhead from the vtable dispatch. Of course one can argue that this is negligible on modern hardware and that is a fair point. But even ignoring that argument then still we are facing challenges. First, we need to maintain the custom allocator, which is extra work. Second, our data is still heterogenous. This is visualized here: (Note, that we ignore the vptr in this, because its position is implementation dependent, which only strengthens the point anyway)

block-beta
columns 1
  EA["EntityA"]
  block:EntityA
    AA["Vec2 position"]
    AB["Vec2 movement"]
    AC["Box hitbox"]
    AD["std::array<4, Buff> buffs"]
  end
  space
  EB["EntityB"]
  block:EntityB
    BA["Vec2 position"]
    BB["Vec2 movement"]
    BC["Box hitbox"]
    BEmpty[" "]
    style BEmpty fill:transparent,stroke:transparent
  end
  space
  EC["EntityC"]
  block:EntityC
    CA["Vec2 position"]
    CB["Box hitbox"]
    CEmpty1[" "]
    CEmpty2[" "]
    style CEmpty1 fill:transparent,stroke:transparent
    style CEmpty2 fill:transparent,stroke:transparent
  end

Because of this and each entry potentially being huge we can’t really use SIMD on our data while also changes on the entities kill all previous SIMD implementations. That’s why it is not the best solution and we need to investigate a solution that uses homogenous arrays while being modular and therefore incremental. This would solve our disadvantages here.

Investigating ECS

ECS is a data oriented programming design and therefore exactly what we need to face the previously declared challenges. Where we before had an Array of Structures, we now have a Structure of Arrays (SoA). This distributes all the components linked to an entity into homogenous arrays. This can be achieved in quite some ways, where we want to focus here on how I dealt with it in my engine/framework. We are dealing with a statically typed Archetype ECS. Whereas in other ECS implementations you can dynamically add components to your SoA during runtime we don’t want that for now. This of course is a downside when it comes to adaptability, but it is a huge plus when it comes to performance and controlling exactly where your memory goes. So, now let’s step back a little from theory and actually look at some C++ code, introducing some concepts.

SemiDynamicArray (SDA)

This is a basically static array when it comes to memory, because the capacity is capped. Yet, implementing a dynamic size member, we allow some runtime dynamics. That is actually something that wouldn’t have needed to be implemented by our own in C++26 (std::inplace_vector), yet waiting for the compilers to adapt it is also no solution. It’s still quite interesting that it took that long for such a useful data structure to be implemented in the STL. Some may now wonder why std::vector is no option here, where the name of the STL data structure gives the necessary hint. Our SDA is in-place, meaning the values are embedded in it, rather than indirectly referenced, because it uses a std::array as an underlying container. So, wherever the SDA is placed, this will follow and the size of the class is defined by the size of the dynamic size member and the elements in the array times the size of each one. For std::vector that is not the case, because it holds a pointer to heap allocated memory. Hence, we have an unnecessary indirection resulting in a potential cache miss, we want to avoid. For most games we have a cap of entities and there just is no reason to keep it dynamic. Those are exactly the games we want to tackle with the engine, and SDA is very helpful for this.

Structure of Arrays

As we have an array that can hold a component (like e.g. position) with the SDA, we need another data structure that can hold multiple of those. Of course, here we want to keep our values in-place as well. The perfect STL class for that would be std::tuple. As this is the first data structure that actually has some interesting aspects to it, we will look at the class with the relevant functionalities:

    template<typename T, typename... Containers>
    struct ContainerOf {
        // this whole logic only works if we have our element ensured to be exclusive
        static_assert(
            ((std::is_same_v<T, typename Containers::value_type> ? 1 : 0) + ... + 0) == 1,
            "type not found or duplicated"
        );

        static constexpr std::size_t index =
                []<std::size_t... Is>(std::index_sequence<Is...>) constexpr {
                    return ((std::is_same_v<T, typename Containers::value_type> ? Is : 0) + ...);
                }(std::index_sequence_for<Containers...>{});
        using type = std::tuple_element_t<index, std::tuple<Containers...> >;
    };

    template<typename T, typename... ContainerTs>
    using ContainerOf_t = ContainerOf<T, ContainerTs...>::type;

    // everything needs to be synchronized in here. if you mess up with the arrays in this then this is on you
    template<typename... arrayTs>
    class SoA {
    public:

        template<typename T>
        constexpr ContainerOf_t<T, arrayTs...> &get() {
            return std::get<ContainerOf_t<T, arrayTs...> >(arrays_);
        }

        void emplace_back() {
            std::apply([](auto &&... arrays) { (arrays.emplace_back(), ...); }, arrays_);
            ++size_;
        }

        std::size_t getSize() {
            return size_;
        }

    private:
        std::size_t size_{0};
        std::tuple<arrayTs...> arrays_;
    };

The whole ContainerOf stuff is just there to access elements by the component type rather than knowing the underlying container type. We will here assume that we will only use SDAs, while the class obviously offers quite some flexibility in that respect. In the end this is just a wrapper holding all our SDAs embedded in the class. Now, because we do not only have one entity normally, we need to have a data structure that holds our SoAs, where we use a class called EntityManager.

EntityManager

Depending on what implementation you look at, this may be also called World, yet this is not precise enough in my opinion. This then also is just a wrapper of a std::tuple, yet this time we use SoAs in there. Those we then access by the SoA type of our entity.

template<typename... SoATs>
    class EntityManager {
    public:
        EntityManager() = default;

        ~EntityManager() = default;

        template<typename SoAT>
        auto create() {
            auto &soa{std::get<SoAT>(entities_)};
            soa.emplace_back();
            return extract_entity(soa.getSize() - 1, soa);
        }

        template<typename SoAT>
        auto get(std::size_t index) {
            auto &soa{std::get<SoAT>(entities_)};
            return extract_entity(index, soa);
        }

        template<typename SoAT, typename ComponentT>
        auto getArray() {
            return std::get<SoAT>(entities_).template get<ComponentT>();
        }

    private:
        template<typename... arrayTs>
        auto extract_entity(std::size_t entity_index, SoA<arrayTs...> &entities) {
            return Entity<arrayTs...>{entity_index, &entities};
        }

        std::tuple<SoATs...> entities_;
    };

You can see that we use an Entity class here, which we use in order to iterate.

Iterate over Entities

To iterate we obviously have multiple options. One is that you use C++ iterators. That can make sense, yet offers abstractions and potential overhead (becauses we iterate multiple arrays at the same time, where we only need some components), we don’t want and need here. The other one is to create an object that on each iteration, which holds the entity index (row in the SoA) and a pointer to the SoA. This way we can use get<ComponentT>() and set<ComponentT>(ComponentT) function on the entity to retrieve and change components.

template<typename... ComponentsArrayT>
    class Entity {
    public:

        Entity(std::size_t entity_id, SoA<ComponentsArrayT...> *soa) : entity_id_(entity_id), soa_(soa) {
        }

        explicit operator bool() const {
           return entity_id_ < soa_->getSize();
        }
        Entity next() {
            return {entity_id_ + 1, soa_};
        }

        [[nodiscard]] std::size_t index() const {
            return entity_id_;
        }


        template<typename ComponentT>
        void set(ComponentT component) {
            soa_->template get<ComponentT>()[entity_id_] = component;
        }

        template<typename ComponentT, typename CastT>
        void casted_set(CastT component) {
            soa_->template get<ComponentT>()[entity_id_] = static_cast<ComponentT>(component);
        }

        template<typename ComponentT>
        constexpr ComponentT get() const {
            return soa_->template get<ComponentT>()[entity_id_];
        }

    private:
        std::size_t entity_id_;
        SoA<ComponentsArrayT...> *soa_;
    };

A valid workflow on this then looks like

for(auto entity{entity_manager->get<EntityA>(0)}; entity; entity = entity.next())
{
    entity.set<Position>(entity.get<Position>() + entity.get<Movement>());
}

A possible intel disassembly on O2 for this would look like

    9588:	f3 0f 7e 00          	movq   xmm0,QWORD PTR [rax]
    958c:	48 83 c0 08          	add    rax,0x8
    9590:	f3 0f 7e 88 c8 fc ff 	movq   xmm1,QWORD PTR [rax-0x338]
    9597:	ff 
    9598:	66 0f fe c1          	paddd  xmm0,xmm1
    959c:	66 0f d6 40 f8       	movq   QWORD PTR [rax-0x8],xmm0
    95a1:	48 39 c8             	cmp    rax,rcx
    95a4:	75 e2                	jne    9588 <systemEntryX+0x28>

We can see here, that we already have SIMD instructions operating our loop. That is the main strength of this approach. We did not even need to implement any SIMD ourselves, because we make it so easy for the compiler to do that for us. So, we see that the Entity class in fact has no extra overhead for us here, because in the disassembly there are no signs of it anymore.

Also note the casted_set in the Entity class. This exists to cast to the parent class, which is mostly used to ensure a form of type safety within over entities.

Typed Entities

Now it could still happen, that there are two entities that share the same components. For that we need to introduce some way of distinguishing between types. That can be done in any way but for me the most beneficial “non-memory-wasting” way was to let my components inherit from the class they represent. Therefore for example

struct EntityBComponents
{
    static constexpr std::size_t capacity{10};
   struct Position: Vec2 {
   };
   struct Movement : Vec2 {
   };
   struct Hitbox : Box {
   };
   using EntityB =  SoABuilder::FromComponents<capacity, SemiDynamicArray, Position, Movement, Hitbox>::type
};

That way we will not have another entity that matches if we want to handle that entity in a specific way without introducing new branches, but rather use its memory location, which will be close in terms of cache efficiency anyways.

The whole Deal

Now we have a static ECS in order to store our entities. The entities will be stored in memory like (Assuming we have 4 EntityA, 2 EntityB, and one EntityC)

block-beta
columns 1
  block:EntityA
    AA["Vec2 EntityA::Position"]
    AAA["Vec2 EntityA::Position"]
    AAAA["Vec2 EntityA::Position"]
    AAAAA["Vec2 EntityA::Position"]
  end
  block:EntityAA
    AA1["Vec2 EntityA::Movement"]
    AAA1["Vec2 EntityA::Movement"]
    AAAA1["Vec2 EntityA::Movement"]
    AAAAA1["Vec2 EntityA::Movement"]
  end
  block:EntityAAA
    AA2["Box EntityA::Hitbox"]
    AAA2["Box EntityA::Hitbox"]
    AAAA2["Box EntityA::Hitbox"]
    AAAAA2["Box EntityA::Hitbox"]
  end
  block:EntityAAAA
    AA3["std::array<4, Buff> EntityA::Buff"]
    AAA3["std::array<4, Buff> EntityA::Buff"]
    AAAA3["std::array<4, Buff> EntityA::Buff"]
    AAAAA3["std::array<4, Buff> EntityA::Buff"]
  end
  block:EntityB
    BB["Vec2 EntityB::Position"]
    BBB["Vec2 EntityB::Position"]
    BBBB["Vec2 EntityB::Movement"]
    BBBBB["Vec2 EntityB::Movement"]
  end
  block:EntityBC
    BB1["Box EntityB::Hitbox"]
    BBB1["Box EntityB::Hitbox"]
    CC1["Vec2 EntityC::Position"]
    CCC1["Box EntityC::Hitbox"]
  end

Of course the C++ standard doesn’t guarantee that the tuple will be ordered like we give our arguments to it, but besides the ordering our ECS storage will look like this. We can see that everything is stored close to each other in memory, which comes in handy when it comes to cache efficiency. This comes without the maintaining effort of custom allocators and VTables, while it is highly modular.

Future Work

The biggest downside of the ECS implementation is that now everything is stored in a block that also needs to be made available by the OS. The solution is to trade some of the locality for having multiple of those blocks linked together for a given memory cap. Yet, for now this is not necessary, because my game hasn’t encountered problems in that regard. So, this will be something for the future I will then add here.