Entity Component System, How? (Part2)

Cute implements a ECS using C++17 features, trying to solve as much as possible during compile time and allowing the compiler to inline as much as possible.

I will try to simplify as much as possible the implementation details with some pseudo code.

Each component is defined as a normal struct, for example:

  

struct Position
{
...
};

struct Speed
{
...
};

Then the user needs to define a list of possible entities type, each entity type is just defined with the list of the components that defines the type. The database is just defined with the list of components and the list of entity types:

using SquareType = ecs::EntityType<Position, Speed, Size, Square>;
using TriangleType = ecs::EntityType<Position, Speed, Size, Triangle>;
using CircleType = ecs::EntityType<Position,Speed,Size,Circle>;

using GameComponents = ecs::ComponentList<Position,Speed, Size, Square, Triangle, Circle>;
using GameEntityTypes = ecs::EntityTypeList<SquareType,TriangleType,CircleType>;

using GameDatabase = ecs::DatabaseDeclaration<GameComponents, GameEntityTypes>;

Cute ECS has the concept of zone as well, that means that all the instances in the database are grouped in zones, so when the system loops all the instances we can define the zones that we need to access. For example, we can group of our instances in 8x8 2D tiles (64 zones), then when we loop all the instances we can define which zones we want to include in the loop (for example if we look for instances in a radius distance, we can only loop the tiles, zones, that are touching the search radius). But zones can be used for more things, like filtering instances, for example you can differentiate entities by some important access pattern (like if they are touching the floor, can be hit by the player,...).

Component data storage

Each instance in the database is defined by a unique index, that will allow to identify an instance inclusive when is moving from one zone to another or when we move the component data for fragmentation reason. The database will keep for each index an instance descriptor, that includes the zone, the entity type and the index inside the components arrays.

The database is defined by an array of zone containers (size defined during init), each zone container will have an array of entity types containers and each entity type container will have an array of component containers. Each component container is a virtual buffer (explain in Uses of Virtual Memory), that will allow this memory to grow without doing copies.

Accessing the component data

So, if we want to access to a component from a instance, defined by an index.

struct EntityDescriptor
{
   int zone, entity_type, index;
};

EntityDescritor entity_descriptor = database.m_instance_table[instance_index];

Then, it can access to the component data with:

//Entity descriptor
EntityDescritor ed;

return database.m_zone_storage[ed.zone].m_entity_type_storage[ed.entity_type].m_components_storage[component_index][ed.index];

Of course, it seems quite a lot of access from a component, but this type of access is not the most common in a ECS, what we expect are is a lot of access with a kernel operation been executed for all the instances that contain specific components, using this storage pattern the kernel operation will access the component data in a cache friendly way, making the ECS approach to work. 

template<typename FUNCTION>
void LoopInstances(FUNCTION&& kernel, ComponentList components)
{
   for (auto& zones : database.m_zones)
   {
       for (auto& entity_types : zones.GetEntityTypesThatContain(components))   
       {
           //Get components storage
           auto components = entity_types.GetComponents(components);
           for (size_t i = 0; i < entity_types.NumInstances(); ++i)
           {
               //Components are accessed lineally in memory
               kernel(components[i]);
           }
       }
   }
}

Conclusions and more details

OO will allow really fast access from a pointer to all the data associated to it, but the line caches will not be aligned to the data type that you access, so inclusive having all the array access it could have good results, especially if you mix read and write operation and multi threading. ECS is a winner if you need to loop to all the instances.

Cute ECS has two functions for looping instances, one it will be run the the same thread and other will create all the jobs needed and sync them in a fence. Because we know the size of the cache line, we can create jobs that will not touch memory between them.

For this approach, all the memory needs to be compacted. Cute ECS has a tick database function, where all the deferred deletes and moves will happen. 

Having fixed number of entity types maybe seems a problem (it helps to extract details in compile time), but we always can create a more dynamic allocation for the entity_types, so we can create all possible combinations in realtime or adding/removing components to an entity.

Source code: https://github.com/JlSanchezB/Cute/blob/master/engine/ecs/entity_component_system.h

Part 1: https://middlelifegraphicsprogrammercrisis.blogspot.com/2019/05/entity-component-system-why-part1.html

Part 3: https://middlelifegraphicsprogrammercrisis.blogspot.com/2020/06/entity-component-system-testing-it-part3.html

Uses of virtual memory

Virtual memory seems a low level OS feature, but you can use it for solving really common patterns.

One pattern where I have been using virtual memory a lot before is for implementing a vector that doesn't need to reallocate and move all the memory when it needs to grow. Specially it is an issue if you keep a pointer somewhere to this memory.

So, instead to use std::vector, you just reserve a piece of virtual memory, that memory would be in continuous address space and it can be huge, but you only commit (ask for physical memory) for the range of addresses that you are using.

For example, you can reserve a buffer of 20 megabytes in memory but only commit 64 kb and then you can grow the committed memory if it is needed; each time that you need more memory, the memory doesn't need to be reallocated and moved, you just need to commit more memory.

Of course, there are some issues:

• You need to know the reserve memory, but it can be huge as we are using 64 bits memory addresses and doesn't consume memory until you commit memory.
• Virtual memory uses pages, that means that when you grow memory you are using a new page or several of physical memory; page size are different between OS/Architectures.

I use these buffers for a lot of situations in Cute; my implementation is really simple and easy to use:

https://github.com/JlSanchezB/Cute/blob/master/engine/core/virtual_alloc.h

https://github.com/JlSanchezB/Cute/blob/master/engine/core/pc/virtual_alloc.cpp

Another interesting use of virtual memory is to block access inside a memory address range, that could be really useful for finding tricky bugs in you code.

Entity Component System, Why? (Part1)

During the last few years we have improved CPU speed and quantity in our systems, but memory has been lagging; specially in a multi processor environment, memory access could be really slow.
So new patterns for programming have become more important (they have been always there) before continuing this article I must recommend reading and understanding as much as possible about cache coherence in a multi processor system and data oriented programming.

https://en.wikipedia.org/wiki/Cache_coherence
https://en.wikipedia.org/wiki/Data-oriented_design

Conclusion:

- If you bring a cache line close to the CPU (L1), always use all data in it.
- Avoid writing shared cache lines between processors, you can read cache lines from all the processors but if you write into a cache line, make sure that other processors are not reading or writing into it.
- Help the pre-fetcher, always try access data in a lineal pattern.

Object oriented?

If you try to follow these rules, OO seems the worst fit as all data of the objects are mixed in lineal storage without thinking in cache lines.
- There are a lot of accesses for a full cache line just for reading a value or a bit. Classic "bool IsActive()".
- Writing and reading is happening in the cache lines without any control from different processors.
- Access can not be pre-fetch, virtual functions are a really good sample of that.

- Virtual functions produce a lot of access to different code, that can produce a lot of cache misses in the instruction cache.

Are there "solutions"?
- Moving the storage position of the data inside the objects, making close accessed data to be in the same cache line, but usually it is difficult to maintain.
- Moving common data outside of the object and access it. The classic example is moving the bounding box and the visibility flag of the object outside of the object, so you can calculate the visibility in a data oriented pattern.

Entity Component System:

The idea is to implement the last "solution" but in a more generic way, so everything inside the object is stored outside of it in a lineal pattern, same type of data share the same cache lines (the classic vector of structs vs structs of vectors).

An object is defined by a list of components and each component is stored in continuous memory. This approach is not only going to help us implement the data-oriented approach, but it is going to implement a component based approach for defining the behaviour of our objects, it is going to avoid the classic inheritance object oriented programming and it is going to remove the need of runtime polymorphism and virtual functions.

Instead of looping the objects and call virtual functions, we generate a kernel function that processes data for a list of components, that kernel function will be executed only for the objects that have all the components needed.

Without defining a lot of the implementation details, it is easy to realise the benefits of this approach:

- The kernel only access the components needed.

- Components are stored in lineal buffers, so the kernel access the data in a lineal pattern (next component is in the same cache line or next cache line, that helps a lot the pre-fetch).

- It will not just help a lot the data cache coherency, it will help the instruction cache coherency because kernel functions will be small pieces of code that gets executed for a lot of components without changing of each type of entity.

- It can be distributed using multiple processors, as the kernel function only needs to access the components and the task can be split in jobs really easily (without sharing cache lines between jobs).

- If you write into a component, only your processor is going to have write access of the cache line.

- Virtual functions are not needed, as you don't need runtime polymorphism in the component.

part 2

String hashes

Strings are evil... but they are human friendly.
The common implementation of strings is heavy in dynamic memory and slow, specially for simple comparisons. There are several alternatives, like pooled strings and string hashes.

With modern C++ you can calculate the hashes for literal strings in compile time, that gives string hashes solution a lot of potential. So all literal strings get converted to hashes, memory is under control and the comparisons are fixed cost.

But it is not perfect:
- Collisions, you need a way to detect collisions as having a collision in your implementation could be disastrous.
- Converting back to strings for logging.
- Debugging, you need to be able to see the string value during debugging.

All these issues can be fixed if you maintain a map that converts from hash to string. It will allow detecting collisions and conversions. It solves the debugging issue if you access the map using a natvis file. And in release configuration you can just strip out this map and, as an extra, no more literal strings inside the executable.

But string hashes solves a pattern that I always fight against in big projects.
Usually there are a group of tools for processing data, for example shader, material and meshes. Those tools are independent executable (usually), but they need some dependencies between them. For example, if the shader defines the pass where it needs to be rendered and the pass is inside an enum; usually you create a common include file between the tools, so you can serialise the correct index for the enum. But this pattern has a lot of issues, a change of this include file invalidates all the tools and the data, wasting a lot of cached data.

So, why not instead of using integers we just serialise the string? that would break the dependency, making all the serialise data more data driven and not based of a fixed enum. Thanks to the string hashes you can just serialise the hash, as hashes are the same between executables.

Extra:

My string hash base class has two template parameters:
- Namespace: That allows the hashes to collide between different namespaces and block assignments between string hashes from different namespaces (strong type string hashes).
- Size: Thanks to the namespace, you can now reduce the size of the hash, for example for the pass name you can use 16 bits integers (or 8 bits).

If your project is big, with a lot of different tools using string hashes, you can use an external database instead of a global map inside each tool.
Benefits:

- Better collision detection: You will detect the collision from the tool that first introduced the duplicated hash.

- Once in shipping configuration, you can convert hashes to strings from the logs without leaking the strings and you can still use the natvis for debugging (You need to implement a natvis custom visualized, changed in VS2019 to UIVisualizers plugin).

Code: https://github.com/JlSanchezB/Cute/blob/master/engine/core/string_hash.h

Share pointers vs integers as handles

Shared pointers seems the solution for handles in a library, so you can forget the classic integer returned by a function as a handle and just use shared pointers. So no more double deletions, no more crossed handles and no more leaks. But shared pointers are not perfect; they are slow (more in debug), big in memory (16 bytes) and hiding ownership is not good.

Unique pointers look interesting as well; you can still control life of the object quite easy and they are faster and smaller in memory (still 8 bytes). But forward declared unique pointers have some issues.

So, integers can be small in memory (2-4 bytes are sufficient); but there are a lot of issues with integer as handles, but thanks to Modern C++ you can improve a lot of them.

A template class wrapping the integer could hide it and avoid assignations between different types of handles. But you can do more; it can control the ownership and leaks as well. The template class will look like:

template <typename DATA, typename TYPE>
class Handle
{
 Handle()
 {
  m_index = kInvalid;
 }
 ~Handle()
 {
  assert(m_index == kInvalid);
 }

 Handle(const Handle& a) = delete;
 Handle& operator=(const Handle& a) = delete;
private:
 TYPE m_index;
 static TYPE kInvalid = static_cast<TYPE>(-1);
};

Similar to unique pointers; you can only move them, copy will fail to compile. During the destruction the index MUST be invalid, that happens only if you have destroyed it. So if a Handle calls the destructor and still has a valid handle; you found a leak.

But sometimes you need to copy handles, so we can introduce a WeakHandle template class; a WeakHandle can be copied but it can not be used for destroying the handle (only a Handle can).

Conclusion:

You can have the best of shared pointers or unique pointers but the size and simplicity of an integer with a minimal implementation of a wrapper class.

Extra:

What happens when a Handle is deleted and still there is a WeakHandle alive?
It can produce issues as you can still use a deleted handle in the system, but it is quite easy to track. WeakHandles can increase a ref count for the index (maintained in the library) during construction and decrease it during destruction, that will allow us to check if all the WeakHandles have been deleted at the moment of the Handle destruction (this code can be activated just for tracking these issues).

Code: https://github.com/JlSanchezB/Cute/blob/master/engine/core/handle_pool.h