This week I started working on my engine for the Vagabond game and started implementing the entity-component-system pattern.

In this article I want to talk about my implementation, which is freely available on GitHub . But instead of simply commenting on the code, I want to explain how its structure was designed. Therefore, I will start with the first implementation I wrote, analyze its strengths and weaknesses, and then show how I improved it. At the end I will list a list of aspects that can also be improved.

Introduction

Motivation

I will not talk about the benefits of ECS over an object-oriented approach, because many people have done it well before me. One of the first about ECS told at GDC 2002 Scott Bilas. Other famous introductions of the theme include Mike West's Evolve Your Hierarchy and Chapter Components from Robert Nystrom's stunning book Game Programming Patterns .
')
In short, I’ll say that the ECS task is to create a data-centric approach to game entities and convenient separation of data and logic. Entities are composed of components containing data. And systems containing logic process these components.

If you go into details, instead of inheriting , ECS uses composition . Moreover, this data-oriented approach makes better use of the cache, which means it achieves excellent performance.

Examples

Before delving into the code, I would like to show you what we are going to design.

The task of the components is very simple:

struct Position : public Component<Position> { float x; float y; }; struct Velocity : public Component<Velocity> { float x; float y; }; 

As you can see, we will use the CRTP template.

Then, for technical reasons, which I will explain later, we need to fix the number of components and the number of systems:

 constexpr auto ComponentCount = 32; constexpr auto SystemCount = 8; 

Next, you can define a system that will take all entities that have both components, and update their positions:

 class PhysicsSystem : public System<ComponentCount, SystemCount> { public: PhysicsSystem(EntityManager<ComponentCount, SystemCount>& entityManager) : mEntityManager(entityManager) { setRequirements<Position, Velocity>(); } void update(float dt) { for (const auto& entity : getManagedEntities()) { auto [position, velocity] = mEntityManager.getComponents<Position, Velocity>(entity); position.x += velocity.x * dt; position.y += velocity.y * dt; } } private: EntityManager<ComponentCount, SystemCount>& mEntityManager; }; 

To declare the components of interest to it, the system simply uses the setRequirements method. Then, in the update method, it can call getManagedEntities to iteratively traverse all the entities that meet the requirements.

Finally, let's create an entity manager, register the components, create a system and several entities, and then update their positions using the system:

 auto manager = EntityManager<ComponentCount, SystemCount>(); manager.registerComponent<Position>(); manager.registerComponent<Velocity>(); auto system = manager.createSystem<PhysicsSystem>(manager); for (auto i = 0; i < 10; ++i) { auto entity = manager.createEntity(); manager.addComponent<Position>(entity); manager.addComponent<Velocity>(entity); } auto dt = 1.0f / 60.0f; while (true) system->update(dt); 

Benchmarks

I will not pretend to have created the best ECS library. I just wanted to write it myself. In addition, I worked on it for only a week.

However, this is not a reason to create something completely ineffective. So let's set the benchmarks:

• The first will create entities;
• The second will use the system for iteratively traversing entities;
• The latter will create and destroy entities;

The parameters of all these benchmarks are the number of entities, the number of components of each entity, the maximum number of components and the maximum number of systems. This way, we can see how well our implementation scales. In particular, I will show results for three different profiles:

• Profile A: 32 components and 16 systems;
• Profile AA: 128 components and 32 systems;
• AAA profile: 512 components and 64 systems.

Despite the fact that these benchmarks will give us an idea of ​​the quality of the implementation, they are quite simple. For example, in these benchmarks we use only homogeneous entities, and their components are small.

Implementation

Essence

In my implementation, an entity is just an id:

 using Entity = uint32_t; 

Moreover, in Entity.h we also define the alias Index , which will come in handy later:

 using Index = uint32_t; static constexpr auto InvalidIndex = std::numeric_limits<Index>::max(); 

I decided to use uint32_t instead of the 64-bit type or std::size_t to save space and improve cache optimization. We will lose not so much: it is unlikely that someone will have billions of entities.

Component

Now let's define the base class for the components:

 template<typename T, auto Type> class Component { public: static constexpr auto type = static_cast<std::size_t>(Type); }; 

The template class is very simple, it only stores the type id, which we will later use to index data structures by component type.

The first parameter of the template is the type of the component. The second is the value converted to std::size_t , which will serve as the id of the component type.

For example, we can define the Position component as follows:

 struct Positon : Component<Position, 0> { float x; float y; }; 

However, it may be more convenient to use an enumeration:

 enum class ComponentType { Position }; struct Positon : Component<Position, ComponentType::Position> { float x; float y; }; 

In the introductory example, there is only one template parameter: we do not need to specify the type id manually. Later we will see how to improve the structure and generate type identifiers automatically.

EntityContainer

The EntityContainer class will be responsible for managing entities and storing the std::bitset for each of them. This set of bits will denote the components that the entity owns.

Since we will use entities to index containers and in particular std::vector , we need id to be as small as possible and take up less memory. Therefore, we will reuse the id of the destroyed entities. To do this, the free id will be stored in a container called mFreeEntities .

Here is the EntityContainer :

 template<std::size_t ComponentCount, std::size_t SystemCount> class EntityContainer { public: void reserve(std::size_t size); std::vector<std::bitset<ComponentCount>>& getEntityToBitset(); const std::bitset<ComponentCount>& getBitset(Entity entity) const; Entity create(); void remove(Entity entity); private: std::vector<std::bitset<ComponentCount>> mEntityToBitset; std::vector<Entity> mFreeEntities; }; 

Let's see how the methods are implemented.

getEntityToBitset and getBitset are the usual small getters:

 std::vector<std::bitset<ComponentCount>>& getEntityToBitset() { return mEntityToBitset; } const std::bitset<ComponentCount>& getBitset(Entity entity) const { return mEntityToBitset[entity]; } 

The create method is more interesting:

 Entity create() { auto entity = Entity(); if (mFreeEntities.empty()) { entity = static_cast<Entity>(mEntityToBitset.size()); mEntityToBitset.emplace_back(); } else { entity = mFreeEntities.back(); mFreeEntities.pop_back(); mEntityToBitset[entity].reset(); } return entity; } 

If there is a free entity, he uses it again. Otherwise, the method creates a new entity.

The remove method simply adds an entity to delete in mFreeEntities :

 void remove(Entity entity) { mFreeEntities.push_back(entity); } 

The last method is reserve . Its task is to reserve memory for various containers. As we possibly know, memory allocation is a costly operation, so if we approximately know the number of future entities in the game, then memory reservation will speed up the work:

 void reserve(std::size_t size) { mFreeEntities.resize(size); std::iota(std::begin(mFreeEntities), std::end(mFreeEntities), 0); mEntityToBitset.resize(size); } 

In addition to simply backing up memory, it also fills in mFreeEntities .

ComponentContainer

The ComponentContainer class will be responsible for storing all components of the specified type.

In my architecture, all components of a given type are stored together. That is, there is one large array for each type of component, called mComponents .

In addition, in order to be able to add, get, or remove a component from an entity in constant time, we need a way to go from entity to component and from component to entity. To do this, we need two more data structures called mComponentToEntity and mEntityToComponent .

Here is the ComponentContainer ad:

 template<typename T, std::size_t ComponentCount, std::size_t SystemCount> class ComponentContainer : public BaseComponentContainer { public: ComponentContainer(std::vector<std::bitset<ComponentCount>>& entityToBitset); virtual void reserve(std::size_t size) override; T& get(Entity entity); const T& get(Entity entity) const; template<typename... Args> void add(Entity entity, Args&&... args); void remove(Entity entity); virtual bool tryRemove(Entity entity) override; Entity getOwner(const T& component) const; private: std::vector<T> mComponents; std::vector<Entity> mComponentToEntity; std::unordered_map<Entity, Index> mEntityToComponent; std::vector<std::bitset<ComponentCount>>& mEntityToBitset; }; 

You can see that it is inherited from BaseComponentContainer , which is defined as:

 class BaseComponentContainer { public: virtual ~BaseComponentContainer() = default; virtual void reserve(std::size_t size) = 0; virtual bool tryRemove(Entity entity) = 0; }; 

The sole purpose of this base class is to be able to store all ComponentContainer instances in a container.

Let's now look at the definition of methods.

First, consider the constructor: it gets a reference to a container containing sets of entity bits. This class will use it to check whether the entity entity has a component and to update the entity bit set when adding or removing a component:

 ComponentContainer(std::vector<std::bitset<ComponentCount>>& entityToBitset) : mEntityToBitset(entityToBitset) { } 

The get method is simple, we just use mEntityToComponent to find the index of the entity entity in mComponents :

 T& get(Entity entity) { return mComponents[mEntityToComponent[entity]]; } 

The add method uses its arguments to insert a new component at the end of the mComponents , and then it prepares links to go from entity to component and from component to entity. At the end, it assigns a true bit to the entity bit set bit that corresponds to the component:

 template<typename... Args> void add(Entity entity, Args&&... args) { auto index = static_cast<Index>(mComponents.size()); mComponents.emplace_back(std::forward<Args>(args)...); mComponentToEntity.emplace_back(entity); mEntityToComponent[entity] = index; mEntityToBitset[entity][T::type] = true; } 

The remove method sets the corresponding component bit to false , and then moves the last mComponents component to the index of the one we want to remove. It updates the links to the component we just moved and removes one of the components we want to destroy:

 void remove(Entity entity) { mEntityToBitset[entity][T::type] = false; auto index = mEntityToComponent[entity]; // Update mComponents mComponents[index] = std::move(mComponents.back()); mComponents.pop_back(); // Update mEntityToComponent mEntityToComponent[mComponentToEntity.back()] = index; mEntityToComponent.erase(entity); // Update mComponentToEntity mComponentToEntity[index] = mComponentToEntity.back(); mComponentToEntity.pop_back(); } 

We can move in constant time by moving the last component on the index that we want to destroy. And in fact, then we just need to remove the last component, which can be done in std::vector in constant time.

The tryRemove method checks whether an entity has components before attempting to delete it:

 virtual bool tryRemove(Entity entity) override { if (mEntityToBitset[entity][T::type]) { remove(entity); return true; } return false; } 

The getOwner method returns the entity that owns the component, for this it uses pointer arithmetic and mComponentToEntity :

 Entity getOwner(const T& component) const { auto begin = mComponents.data(); auto index = static_cast<std::size_t>(&component - begin); return mComponentToEntity[index]; } 

The last method is reserve , it has such a purpose as a similar method in the EntityContainer :

 virtual void reserve(std::size_t size) override { mComponents.reserve(size); mComponentToEntity.reserve(size); mEntityToComponent.reserve(size); } 

System

Now let's take a look at the System class.

Each system has a set of mRequirements bits describing the components it needs. In addition, it stores a set of mManagedEntities entities that meet these requirements. Again, to be able to implement all operations in constant time, we need a way to transition from an entity to its index in mManagedEntities . To do this, we will use std::unordered_map called mEntityToManagedEntity .

This is what the System declaration looks like:

 template<std::size_t ComponentCount, std::size_t SystemCount> class System { public: virtual ~System() = default; protected: template<typename ...Ts> void setRequirements(); const std::vector<Entity>& getManagedEntities() const; virtual void onManagedEntityAdded([[maybe_unused]] Entity entity); virtual void onManagedEntityRemoved([[maybe_unused]] Entity entity); private: friend EntityManager<ComponentCount, SystemCount>; std::bitset<ComponentCount> mRequirements; std::size_t mType; std::vector<Entity> mManagedEntities; std::unordered_map<Entity, Index> mEntityToManagedEntity; void setUp(std::size_t type); void onEntityUpdated(Entity entity, const std::bitset<ComponentCount>& components); void onEntityRemoved(Entity entity); void addEntity(Entity entity); void removeEntity(Entity entity); }; 

To set the bit values setRequirements uses a convolution expression :

 template<typename ...Ts> void setRequirements() { (mRequirements.set(Ts::type), ...); } 

getManagedEntities is the getter that will be used by the generated classes to access the processed entities:

 const std::vector<Entity>& getManagedEntities() const { return mManagedEntities; } 

It returns a constant reference so that the generated classes do not attempt to modify the mManagedEntities .

onManagedEntityAdded and onManagedEntityRemoved are empty. They will be redefined later. These methods will be called when an entity is added to mManagedEntities or deleted.

The following methods will be private and accessible only from EntityManager , which is declared as a friendly class.

setUp will be called by the entity manager to assign an id to the system. It can then use it to index arrays:

 void setUp(std::size_t type) { mType = type; } 

onEntityUpdated is called when the entity changes, i.e. when adding or removing a component. The system checks whether the requirements are satisfied and whether the entity has already been processed. If it meets the requirements and has not yet been processed, the system adds it. However, if the entity does not satisfy the requirements and has already been processed, the system deletes it. In all other cases, the system does nothing:

 void onEntityUpdated(Entity entity, const std::bitset<ComponentCount>& components) { auto satisfied = (mRequirements & components) == mRequirements; auto managed = mEntityToManagedEntity.find(entity) != std::end(mEntityToManagedEntity); if (satisfied && !managed) addEntity(entity); else if (!satisfied && managed) removeEntity(entity); } 

onEntityRemoved is called by the entity manager when deleting an entity. If the entity has been processed by the system, it deletes it:

 void onEntityRemoved(Entity entity) { if (mEntityToManagedEntity.find(entity) != std::end(mEntityToManagedEntity)) removeEntity(entity); } 

addEntity and removeEntity are just helper methods.

addEntity sets a link to navigate from an added entity by its index in mManagedEntities , adds an entity, and calls onManagedEntityAdded :

 void addEntity(Entity entity) { mEntityToManagedEntity[entity] = static_cast<Index>(mManagedEntities.size()); mManagedEntities.emplace_back(entity); onManagedEntityAdded(entity); } 

removeEntity first calls onManagedEntityRemoved . It then moves the last processed entity to the index of the one that is deleted. It updates the link to the moved entity. At the end, it deletes the entity to be deleted from mManagedEntities and mEntityToManagedEntity :

 void removeEntity(Entity entity) { onManagedEntityRemoved(entity); auto index = mEntityToManagedEntity[entity]; mEntityToManagedEntity[mManagedEntities.back()] = index; mEntityToManagedEntity.erase(entity); mManagedEntities[index] = mManagedEntities.back(); mManagedEntities.pop_back(); } 

EntityManager

All important logic is in other classes. The entity manager simply links everything together.

Let's take a look at his announcement:

 template<std::size_t ComponentCount, std::size_t SystemCount> class EntityManager { public: template<typename T> void registerComponent(); template<typename T, typename ...Args> T* createSystem(Args&& ...args); void reserve(std::size_t size); Entity createEntity(); void removeEntity(Entity entity); template<typename T> bool hasComponent(Entity entity) const; template<typename ...Ts> bool hasComponents(Entity entity) const; template<typename T> T& getComponent(Entity entity); template<typename T> const T& getComponent(Entity entity) const; template<typename ...Ts> std::tuple<Ts&...> getComponents(Entity entity); template<typename ...Ts> std::tuple<const Ts&...> getComponents(Entity entity) const; template<typename T, typename... Args> void addComponent(Entity entity, Args&&... args); template<typename T> void removeComponent(Entity entity); template<typename T> Entity getOwner(const T& component) const; private: std::array<std::unique_ptr<BaseComponentContainer>, ComponentCount> mComponentContainers; EntityContainer<ComponentCount, SystemCount> mEntities; std::vector<std::unique_ptr<System<ComponentCount, SystemCount>>> mSystems; template<typename T> void checkComponentType() const; template<typename ...Ts> void checkComponentTypes() const; template<typename T> auto getComponentContainer(); template<typename T> auto getComponentContainer() const; }; 

The EntityManager class has three member class variables: mComponentContainers , which mComponentContainers std::unique_ptr to BaseComponentContainer , mEntities , which is simply an instance of EntityContainer and mSystems , which stores unique_ptr pointers to System .

The class has many methods, but in fact they are all very simple.

Let's first take a look at getComponentContainer , which returns a pointer to a container of components that processes components of type T :

 template<typename T> auto getComponentContainer() { return static_cast<ComponentContainer<T, ComponentCount, SystemCount>*>(mComponentContainers[T::type].get()); } 

Another helper function is checkComponentType , which simply checks that the id of the component type is below the maximum number of components:

 template<typename T> void checkComponentType() const { static_assert(T::type < ComponentCount); } 

checkComponentTypes uses a convolution expression to perform a check of several types:

 template<typename ...Ts> void checkComponentTypes() const { (checkComponentType<Ts>(), ...); } 

registerComponent creates a new container of components of the specified type:

 template<typename T> void registerComponent() { checkComponentType<T>(); mComponentContainers[T::type] = std::make_unique<ComponentContainer<T, ComponentCount, SystemCount>>( mEntities.getEntityToBitset()); } 

createSystem creates a new system of the specified type and sets its type:

 template<typename T, typename ...Args> T* createSystem(Args&& ...args) { auto type = mSystems.size(); auto& system = mSystems.emplace_back(std::make_unique<T>(std::forward<Args>(args)...)); system->setUp(type); return static_cast<T*>(system.get()); } 

The reserve method calls the reserve methods of the ComponentContainer and EntityContainer :

 void reserve(std::size_t size) { for (auto i = std::size_t(0); i < ComponentCount; ++i) { if (mComponentContainers[i]) mComponentContainers[i]->reserve(size); } mEntities.reserve(size); } 

The createEntity method returns the result of the EntityManager manager's create method:

 Entity createEntity() { return mEntities.create(); } 

hasComponent uses a set of entity bits to quickly verify that this entity has a component of the specified type:

 template<typename T> bool hasComponent(Entity entity) const { checkComponentType<T>(); return mEntities.getBitset(entity)[T::type]; } 

hasComponents uses a convolution expression to create a bit set denoting the required components, and then use it with the entity bit set to check whether the entity has all the required components:

 template<typename ...Ts> bool hasComponents(Entity entity) const { checkComponentTypes<Ts...>(); auto requirements = std::bitset<ComponentCount>(); (requirements.set(Ts::type), ...); return (requirements & mEntities.getBitset(entity)) == requirements; } 

getComponent request to the correct container of components:

 template<typename T> T& getComponent(Entity entity) { checkComponentType<T>(); return getComponentContainer<T>()->get(entity); } 

getComponents returns a tuple of links to the requested components. To do this, it uses std::tie and a convolution expression:

 template<typename ...Ts> std::tuple<Ts&...> getComponents(Entity entity) { checkComponentTypes<Ts...>(); return std::tie(getComponentContainer<Ts>()->get(entity)...); } 

addComponent and removeComponent forward the request to the desired component container, and then call the onEntityUpdated system onEntityUpdated :

 template<typename T, typename... Args> void addComponent(Entity entity, Args&&... args) { checkComponentType<T>(); getComponentContainer<T>()->add(entity, std::forward<Args>(args)...); // Send message to systems const auto& bitset = mEntities.getBitset(entity); for (auto& system : mSystems) system->onEntityUpdated(entity, bitset); } template<typename T> void removeComponent(Entity entity) { checkComponentType<T>(); getComponentContainer<T>()->remove(entity); // Send message to systems const auto& bitset = mEntities.getBitset(entity); for (auto& system : mSystems) system->onEntityUpdated(entity, bitset); } 

Finally, getOwner request to the required container component:

 template<typename T> Entity getOwner(const T& component) const { checkComponentType<T>(); return getComponentContainer<T>()->getOwner(component); } 

That was my first implementation. It consists of only 357 lines of code. All code can be found in this thread .

Profiling and benchmarks

Benchmarks

Now it's time to conduct benchmarks of my first ECS implementation!

Here are the results:




The template scales well enough! The number of processed per second is approximately the same as the number of entities increases and profiles change (A, AA, and AAA).

In addition, it scales well with an increase in the number of components in the entities. When we iterate over entities with three components, they occur three times slower than iterations over entities with one component. This is expected because we need to get three components.

Cache misses

To check the number of cache misses, I launched the cachegrind example from here .

Here is the result for 10,000 entities:

==1652== D refs: 277,577,353 (254,775,159 rd + 22,802,194 wr)
==1652== D1 misses: 20,814,368 ( 20,759,914 rd + 54,454 wr)
==1652== LLd misses: 43,483 ( 7,847 rd + 35,636 wr)
==1652== D1 miss rate: 7.5% ( 8.1% + 0.2% )
==1652== LLd miss rate: 0.0% ( 0.0% + 0.2% )

Here is the result for 100,000 entities:

==1738== D refs: 2,762,879,670 (2,539,368,564 rd + 223,511,106 wr)
==1738== D1 misses: 207,415,181 ( 206,902,072 rd + 513,109 wr)
==1738== LLd misses: 207,274,328 ( 206,789,289 rd + 485,039 wr)
==1738== D1 miss rate: 7.5% ( 8.1% + 0.2% )
==1738== LLd miss rate: 7.5% ( 8.1% + 0.2% )

The results are pretty good. Just a little weird why so many LLd slips at 100,000 entities.

Profiling

To understand which parts of the current implementation take more time, I have profiled the example with gprof .

Here is the result:

Flat profile:

Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
57.45 1.16 1.16 200300000 0.00 0.00 std::__detail::_Map_base<unsigned int, std::pair<unsigned int const, unsigned int>, std::allocator<std::pair<unsigned int const, unsigned int> >, std::__detail::_Select1st, std::equal_to<unsigned int>, std::hash<unsigned int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true>, true>::operator[](unsigned int const&)
19.31 1.55 0.39 main
16.34 1.88 0.33 200500000 0.00 0.00 std::_Hashtable<unsigned int, std::pair<unsigned int const, unsigned int>, std::allocator<std::pair<unsigned int const, unsigned int> >, std::__detail::_Select1st, std::equal_to<unsigned int>, std::hash<unsigned int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::_M_find_before_node(unsigned long, unsigned int const&, unsigned long) const
3.96 1.96 0.08 300000 0.00 0.00 std::_Hashtable<unsigned int, std::pair<unsigned int const, unsigned int>, std::allocator<std::pair<unsigned int const, unsigned int> >, std::__detail::_Select1st, std::equal_to<unsigned int>, std::hash<unsigned int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::_M_insert_unique_node(unsigned long, unsigned long, std::__detail::_Hash_node<std::pair<unsigned int const, unsigned int>, false>*)
2.48 2.01 0.05 300000 0.00 0.00 unsigned int& std::vector<unsigned int, std::allocator<unsigned int> >::emplace_back<unsigned int&>(unsigned int&)
0.50 2.02 0.01 3 3.33 3.33 std::_Hashtable<unsigned int, std::pair<unsigned int const, unsigned int>, std::allocator<std::pair<unsigned int const, unsigned int> >, std::__detail::_Select1st, std::equal_to<unsigned int>, std::hash<unsigned int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::~_Hashtable()
0.00 2.02 0.00 200000 0.00 0.00 std::_Hashtable<unsigned int, std::pair<unsigned int const, unsigned int>, std::allocator<std::pair<unsigned int const, unsigned int> >, std::__detail::_Select1st, std::equal_to<unsigned int>, std::hash<unsigned int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::find(unsigned int const&)

The results may be slightly distorted, because I compiled with the -O1 flag -O1 that gprof -O1 something meaningful. It seems that as the level of optimization increases, the compiler starts building in everything aggressively and gprof reports almost nothing.

According to gprof, the obvious bottleneck in this implementation is std::unordered_map . If we want to optimize it, then it is worth trying to get rid of them.

Comparison with std::map

I was curious about the difference in performance between std::unordered_map and std::map , so I replaced in the code all std::unordered_map with std::map . This implementation is posted here.

Here are the benchmark results:




We can see that this time the implementation doesn’t scale well as the number of entities increases. And even with 1000 entities, it is two times slower in iterations than version c std::unordered_map.

Conclusion

We have created a simple but already practical library of the entity-component-system template. In the future, we will use as a foundation for improvements and optimizations.

In the next part, we will show how to improve performance by replacing std::unordered_mapwith std::vector. In addition, we will show how to automatically assign type id to components.

Replacing std :: unordered_map with std :: vector

As we have seen, there std::unordered_mapwas a bottleneck of our implementation. Therefore, instead std::unordered_mapwe use in mEntityToComponentfor ComponentContainerand in mEntityToManagedEntityfor Systemvectors std::vector.

Changes

The changes will be very simple, you can look at them here .

The only subtlety is that vectorin mEntityToComponentand mEntityToManagedEntitybe long enough to be indexed by any entity. To do this in a simple way, I decided to store these vectorin EntityContainer, in which we know the maximum id of the entity. Then I pass the vectors to the vectorcomponent containers by reference or pointer in the entity manager.

Modified code can be found in this thread .

results

Let's check how much better this version works than the previous one:




As you can see, the creation and removal with a large number of components and systems have become a little
slower.

However, the iteration has become much faster, almost ten times! And it scales very well. This acceleration is far outweighed by the delay in creation and deletion. And this is logical: the iterations of the entity will occur many times, and it is created and deleted only once.

Now let's see if this reduces the number of cache misses.

Here is the output of the cachegrind with 10,000 entities: And here is the output for 100,000 entities: We see that this version creates about three times less links and four times less cache misses.

==1374== D refs: 94,563,949 (72,082,880 rd + 22,481,069 wr)
==1374== D1 misses: 4,813,780 ( 4,417,702 rd + 396,078 wr)
==1374== LLd misses: 378,905 ( 9,626 rd + 369,279 wr)
==1374== D1 miss rate: 5.1% ( 6.1% + 1.8% )
==1374== LLd miss rate: 0.4% ( 0.0% + 1.6% )



==1307== D refs: 938,405,796 (715,424,940 rd + 222,980,856 wr)
==1307== D1 misses: 51,034,738 ( 44,045,090 rd + 6,989,648 wr)
==1307== LLd misses: 5,866,508 ( 1,997,948 rd + 3,868,560 wr)
==1307== D1 miss rate: 5.4% ( 6.2% + 3.1% )
==1307== LLd miss rate: 0.6% ( 0.3% + 1.7% )

Automatic types

The last improvement, which I will discuss, will be the automatic generation of component type identifiers.

Changes

All changes for the implementation of automatic generation of id types can be found here .

In order to be able to assign one unique id to each type of component, you need to use CRTP and a function with a static counter:

 template<typename T> class Component { public: static const std::size_t type; }; std::size_t generateComponentType() { static auto counter = std::size_t(0); return counter++; } template<typename T> const std::size_t Component<T>::type = generateComponentType(); 

You may notice that the type id is now generated at runtime, and it was previously known at compile time.

The code after the changes can be viewed in this thread .

results

To test the performance of this version, I spent benchmarks:




For creation and deletion, the results are about the same. However, it can be noted that the iteration has become slightly slower, by about 10%.

This slowdown can be explained by the fact that earlier the compiler knew the type identifiers at compile time, which means it could better optimize the code.

Manually assigning id types is a little awkward and can lead to errors. Thus, even if we have slightly reduced performance, it is still an improvement in the usability of our ECS library.

Ideas for further improvements.

Before completing the article, I would like to share with you ideas for other improvements. So far I have not implemented them, but maybe I will do it in the future.

Dynamic number of components and systems

It is inconvenient to specify in advance the maximum number of components and systems in the form of template parameters. I think it will be possible to replace std::arrayin EntityManageron std::vectorwithout a strong performance degradation.

However, it std::bitsetrequires to know the number of bits at compile time. For now, I’m thinking of fixing this problem by replacing std::vector<bitset<ComponentCount>>in EntityContainerwith std::vector<char>and allocating enough bytes to represent the bit sets of all the entities. Then we implement a lightweight class BitsetViewthat receives as input a pair of pointers to the beginning and end of the bit set, and then perform all the necessary operations with std::bitsetin that memory range.

Another idea: no longer use sets of bits and just check mEntityToComponentwhether the entity has components.

Simplified Component Iteration

At the moment, if the system wants to iteratively bypass the components of the entities it processes, we need to do it like this:

 for (const auto& entity : getManagedEntities()) { auto [position, velocity] = mEntityManager.getComponents<Position, Velocity>(entity); ... } 

It would be more beautiful and easier if you could do something like this:

 for (auto& [position, velocity] : mEntityManager.getComponents<Position, Velocity>(mManagedEntities)) { ... } 

It will be easy to implement this with the help of the ranges librarystd::view::transform in C ++ 20 . Unfortunately, it is not yet. I could use Eric Niebler's range library , but I don't want to add dependencies. The solution would be to implement a class that would receive as the template parameters the types of components to be obtained, and as a parameter of the constructor a reference to the entities. Then we would have had only to realize , and the iterator type to achieve the desired behavior. This is not particularly difficult, but a little time consuming to write.




EntityRangeViewstd::vectorbeginend

Event Management Optimization

In the current implementation, when adding or removing a component from an entity, we call onEntityUpdatedall systems. This is a bit inefficient because many systems are not interested in the type of component that has just been modified.

To minimize damage, we can store pointers to systems that are interested in the specified type of component in a data structure, for example std::array<std::vector<System<ComponentCount, SystemCount>>, ComponentCount>. Then, when adding or removing a component, we would simply call the method of onEntityUpdatedsystems interested in that component.

Entity subsets managed by an entity manager instead of systems

My last idea would lead to more extensive changes in the structure of the library.

Instead of systems that manage their own sets of entities, this would be the entity manager. The advantage of this scheme is that if two systems are interested in one set of components, we do not duplicate a subset of entities that satisfy these requirements.

Systems could simply declare their requirements to the entity manager. Then the entity manager would store all the different subsets of the entities. Finally, systems would request entities using this syntax:

 for (const auto& entity : mEntityManager.getEntitiesWith<Position, Velocity>()) { ... } 

Conclusion

So far, this is the completion of an article about my entity-component-system implementation. If I make other improvements, I may write new articles in the future.

The implementation described in the article is quite simple: it consists of less than 500 lines of code, and also has good performance. All transactions are implemented in (amortized) fixed time. Moreover, in practice, it optimally uses the cache and very quickly receives and iterates entities.

I hope this article was interesting or even useful for you.

Additional reading

Here are a couple of useful resources for learning more about the entity-component-system pattern:

• Michelle Kayni, the author of entt , writes a very interesting series of articles about entity-component-system called ECS back and forth .
• The Entity Systems Wiki contains very useful information and links.