6
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ But at the same time, I feel that you're doing premature optimization. The thing is, maybe that the part of your game that will perform the physics simulation will be the bottleneck, while the cache misses you try to avoid will make you gain only a few nano seconds. I suggest you implement the first idea, and then profile and see if your bottlenecks are with data access, or with something else. \$\endgroup\$ – Alexandre Vaillancourt Feb 10 '17 at 13:30
  • \$\begingroup\$ Most of the time I agree with the "first measure then optimize" logic but I feel like if I do it somehow different it would be too hard to redesign this system because nearly everything depends on this. However I've just found a problem with this approach (edited the OP) \$\endgroup\$ – csisy Feb 10 '17 at 13:56
  • 1
    \$\begingroup\$ The suggestion in this case, as I have read often, is to not use the ECS for everything. For instance, you can keep your hierarchy and your physics simulation related items in a more "conventional" architecture of your software, and have your components refer to these. If you need to use a 3rd party library (e.g. a physics simulation library), you'll have a hard time to integrate it into your ECS, so you just reference to it. \$\endgroup\$ – Alexandre Vaillancourt Feb 10 '17 at 14:01
  • \$\begingroup\$ That's a good idea, however if I split the hierarchy so that the transform component only refers to the hierarchy's structure then there flies away the performance gain. :) It seems like this structure is not viable. Maybe you're right, I should try to implement a simple approach and profile if I have performance problems. \$\endgroup\$ – csisy Feb 10 '17 at 14:09
  • 2
    \$\begingroup\$ You still have huge gaps in your access. Even assuming a position component of 1 byte, 64 position instances is generally enough to not have the velocity in the same cache line. Accessing two separate arrays is fine; the (prefetched) memory may end up on different cache lines, but that's no problem at all. Putting everything in one big array doesn't magically make this fit in a cache line nor in the cache itself. Down the hardware there is no actual notion of arrays. Also, these big arrays are not easy to manage due to size differences of components \$\endgroup\$ – Athos vk Feb 10 '17 at 21:28
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Those are not claims made of thin-air, but rock solid testing and experience with all ECS frameworks for C++/C++11. If you have suggestions to improve by making a more in depth explaination just tell :). \$\endgroup\$ – GameDeveloper Feb 10 '17 at 17:47
  • \$\begingroup\$ I'm not sure why anyone want to find a system based on the component set. I think it's pretty obvious to do the opposite (write a system for a set of components). If I understand your description, your system is similar to the Entitas framework. My problem with the "entity group" is that that way the components are accessed in a random order. Maybe the entity grouping works well for higher level code (like gameplay code) but IMHO not for low-level code where the performance matters more. However I don't understand the downvote, so.. +1 :) \$\endgroup\$ – csisy Feb 10 '17 at 18:13
  • \$\begingroup\$ @csisy actually my system is quite the opposite of Entitas (which I used for a while and now replaced with SveltoECS when using C# + Unity). If you look there: github.com/sschmid/Entitas-CSharp-Example/blob/master/Assets/… you will see that actually Entitas find entities based on a filter on components. \$\endgroup\$ – GameDeveloper Feb 13 '17 at 8:53
  • 1
    \$\begingroup\$ Well, I don't know, based on your description: "then why not having group of entity types? That's it, for every different Entity type you make a group" which is the same approach as finding entities by a filter (aka. a group). But probably I'm just misunderstading you. \$\endgroup\$ – csisy Feb 13 '17 at 10:00
  • 1
    \$\begingroup\$ The problem with talking about ECS is you have to define ECS.... every time. :) \$\endgroup\$ – Engineer May 30 '17 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.