I'm working on an ECS and I've already read a lot of articles about it. Most of these articles are talking about a simple case (store data contiguously, read it in a single for loop). However the real world is more complex: one system reads multiple components and those have to be read fast.
So I'm thinking on a new data storage model but before I start to implement it, I'd like to know what do you think: I'm not sure if this design would solve any (future) performance problem (I'm thinking about cache coherency, prefetching, etc. optimization).
So the basics are the same:
- Each Entity is a handle (id + version number together).
- Each Component is a(n ideally small) POD.
- Each System is responsible for the processing of a set of components.
The first idea in every article is to store the component data in an array (of each type) and use a fast-lookup map (eg. hash_map) for the entity_id->component_id relation.
Eg. the Position component pack looks like this:
component data: [pos_0][pos_1]...[pos_n] entity->component map: [entity_0 -> 1][entity_2 -> 0]...[entity_m -> n]
This works well if the systems are reading a single type of component linearly. If a system wants to read another component as well, it will generate at least two additional cache misses:
- one for the entity_id->component_id lookup (to find the other component from the entity)
- and one for the actual component data
So my idea is that instead of separating the components I could create groups. Each group has the same behaviour like before (the data laid out contiguously and an entity_id->component_id map is stored for fast component lookup) but the data stores multiple component data.
The point is that the component data is stored in the same order as the other components so if a system wants to read eg. the Position + Velocity component set it can iterate linearly on the array. Each component type has an offset to indicate where it starts on the big array.
So the Position+Velocity group looks like this:
component data: [pos_0][pos_1]...[pos_n][... some space ...][vel_0][vel_1]...[vel_n]... and so on entity->component map: [entity_0 -> 1][entity_2 -> 0]...[entity_m -> n]
And if I'm interested in a component set of a single entity, I can use the map to find the component id then read the components using this id:
component_id = find(entity_id); comp_0 = data[offset_of(comp_0_type) + component_id] comp_1 = data[offset_of(comp_1_type) + component_id]
The biggest drawback is the larger array: when the array has to grow it has to allocate and copy more data at once. But IMHO the whole idea could work because most of the time (in my experience at least) an entity's components are not changing at run-time.
Note: I tagged c++ as well, because I'm using c++.
Actually I've found a problem with this approach. This way the components cannot refer to each other. Eg a Transform component is responsible for structuring the "objects" in a tree, so each Transform component has a parent and a children property. However with this design I don't know how I could refer to the other Transform component since it can be in any group's array.
For the first iteration I'm going to implement a simple design, similar to the "Packed Array" described here.