Entity-Component-System data storage design

Question

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++.

Edit

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.

Edit 2

For the first iteration I'm going to implement a simple design, similar to the "Packed Array" described here.

Answer 1

There are some problems with this data approach I want to point out.

First of all you assume that you have a fixed number of components for each type. If not, you either waste memory if you have to few of one component type, or no memory for to many. And you can't easily expand your it

Second is, you most likely still have the cache misses from your first idea, since the whole array won't fit into the L1-cache. Since your data is contiguous it's less problematic, but depending on what component your system is working on, it might be a problem: first you compare data from component type 1 with type 12 (maybe already out of cache), then read data from component 3 to write to component 12 again.

Third is just a speculation: do you create every component from the beginning or when you need it? It seems you want to do the first, in that case you have to check if a component is active or not. If you want to do it (or even iterate) over the hashmap, those will most likely generate cache misses again and again.

My approach is to have some sort Node, that has an ID and a copy of some components with the same ID. The systems are only working on those Nodes and only Nodes with all required components with the same ID exist. It has a bit of redundancy, but that's intentional with networking in mind and data changes are gated by its own system.

Answer 2

There is no perfect ECS. Each architetural approach to ECS have pros & cons.

Let me evolve your idea a bit. You have groups, then why not having group of entity types? That's it, for every different Entity type you make a group, so you know the Entity ID because when you are iterating you just need to know the index:

Pros:

• you already know the ID of the processed entity in your group
• you just need to store a short ID if you need to reference the ID of another entity in the same group (16 bits may suffice).
• best cache coerency for data
• Extremely simple to use (you don't have to manage groups, those are automatic)

Cons:

• Update order undefined (if you use instant event dispatch this is not a problem, you just need to be carefull with the few "Updated" stuff).
• Not best cache coerency for instructions (but usually this is ok).
• To refer another entity you need to identify both Group and Index inside group, but the good news is that you can probably just use 16 bits for Group and 16 bits for index.

How to implement:

foreach( var x in entityTree.EntityTypes())  // tree breadth traversal
    foreach( var s in x.UpdatableSystems()) // only a bunch of systems need actually udpating
        s.Update( x.ComponentsForSystem(s));

where

x.ComponentsForSystem(s)

is actually a IEnumerator, or another kind of structure that allow to decouple data layout from iteration so you can use what you want:

• Struct of Arrays
• Array of structs
• Linked List

The usual error with ECS is to find System based on "which" components, instead you have to find Components based on your system.

Usually I see people creating entities by randomly sticking components togheter, then the ECS frameworks figure out how to map Entities to Systems, Instead I find much more natural just "registering" a empty entity in a system, it will be the system to add the components it needs (if those are not already added by another system, in that case we can even log a warning if desired). There's no longer need to filter entities to find them.

The only little problem to solve is how to identify "EntityType", but that is pretty simple:

• You sort components, then you just need to make a "types tree", if you find a leaf of your type you know already in which group spawn the entity, if you don't find the leaf you create a new group. (the previous code snippet infact refers to a "tree traversal").

You EntityHandle will be a 32 bit integer:

Actually I use:

• 1 bit to identify a special case, where groups have more than 65k entities (7 bit identify group, 24 bit identify entity)
• if the bit flag is not set then 15 bit are for group and 16 bit for entities.

And I can achieve better performance than ECS frameworks that have "Manual Groups". Still I have also less code to write, I just compose entities and new groups are added on the fly.