# Grouping entities of the same component set into linear memory

We start from the basic systems-components-entities approach.

Let's create assemblages (term derived from this article) merely out of information about types of components. It is done dynamically at runtime, just like we would add/remove components to an entity one by one, but let's just name it more precisely since it is only about type information.

Then we construct entities specifying assemblage for every of them. Once we create the entity, its assemblage is immutable which means we cannot directly modify it in place, but still we can obtain existing entity's signature to a local copy (along with contents), make proper changes to it, and create a new entity out of it.

Now for the key concept: whenever an entity is created, it is assigned to an object called assemblage bucket, which means that all entities of the same signature will be in the same container (e.g. in std::vector).

Now the systems just iterate through every bucket of their interest and do their job.

• components are stored in a few (precisely: number of buckets) contiguous memory chunks - this improves memory friendliness and it is easier to dump whole game state
• systems process components in a linear manner, which means improved cache coherency - bye bye dictionaries and random memory jumps
• creating a new entity is as easy as mapping an assemblage to bucket and pushing back needed components to its vector
• deleting an entity is as easy as one call to std::move to swap the last element with the deleted one, because order doesn't matter at this moment

If we have a lot of entities with completely different signatures, benefits of cache coherency kind of diminish, but I don't think it would happen in most applications.

There is also a problem with pointer invalidation once vectors are reallocated - this could be solved by introducing a structure like:

struct assemblage_bucket {
struct entity_watcher {
assemblage_bucket* owner;
entity_id real_index_in_vector;
};

std::unordered_map<entity_id, std::vector<entity_watcher*>> subscribers;

//...
};


So whenever for some reason in our game logic we want to keep track of a newly created entity, inside the bucket we register an entity_watcher, and once the entity has to be std::move'd during removal, we lookup its watchers and update their real_index_in_vector to new values. Most of the time this imposes just a single dictionary lookup for every entity deletion.

Are there any more disadvantages to this approach?

Why is the solution nowhere mentioned, despite being pretty obvious?

you lose the dynamic nature of pluggable components, which was created specifically to get away from static class construction.

I don't. Maybe I did not explain it clearly enough:

auto signature = world.get_signature(entity_id); // this would just return entity_id.bucket_owner->bucket_signature or so
signature.remove(bar_component);
world.delete_entity(entity_id); // entity_id would hold information about its bucket owner
world.create_entity(signature); // automatically assigns new entity to an existing or a new bucket


It's as simple as just taking existing entity's signature, modifying it and uploading again as a new entity. Pluggable, dynamic nature? Of course. Here I'd like to emphasize that there is only one "assemblage" and one "bucket" class. Buckets are data-driven and created at runtime in an optimal quantity.

you'd need to go through all buckets that might contain a valid target. Without an external data structure, collision detection could be equally as difficult.

Well, this is why we have the aforementioned external data structures. The workaround is as simple as introducing an iterator in System class that detects when to jump to next bucket. The jumping would be purely transparent to the logic.

• I also read the Randy Gaul article about storing all components in vectors and let their systems just process them. I see two big problems there: what if I want to update only a sub-set of entities (think of culling for example). Because of that components will be coupled again with entities. For each component iteration step I'd need to check if the entity it belongs to has been selected for an update. The other problem is that some systems need to process multiple different component types taking the cache coherency advantage away again. Any ideas how to deal with these issues? – tiguchi Oct 2 '13 at 16:43

You have essentially designed a static object system with a pool allocator and with dynamic classes.

I wrote an object system that works almost identically to your "assemblages" system back in my school days, though I always tend to call "assemblages" either "blueprints" or "archetypes" in my own designs. The architecture was more of a pain in the butt than naive object systems and had no measurable performance advantages over some of the more flexible designs I compared it to. The ability to dynamically modify an object without needing to reify it or reallocate it is hugely important when you are working on a game editor. Designers will want to drag-n-drop components onto your object definitions. Runtime code might even have need to modify components efficiently in some designs, though I personally dislike that. Depending on how you link up object references in your editor, simply being able to add and remove components to existing objects with zero extra shenanigans will come in handy.

You're going to get worse cache coherency than you think in most non-trivial cases. Your AI system for instance doesn't care about Render components but ends up being stuck iterating over them as part of each entity. The objects being iterated over are larger, and cacheline requests end up pulling in unnecessary data, and fewer whole objects are returned with each request). It'll still be better than the naive method, and the naive method object composition is used even in big AAA engines, so you probably don't need better, but at least don't go thinking you can't improve it further.

Your approach does make most sense for some components, but not all. I dislike ECS strongly because it advocates always putting each component in a separate container, which makes sense for physics or graphics or whatnot but no sense at all if you allow multiple script components or composable AI. If you let the component system be used for more than just built-in objects but also as a way for designers and gameplay programmers to compose object behavior then it can make sense to group together all AI components (which will often interact) or all script components (since you want to update them all in one batch). If you want the most performant system then you're going to need a mix of component allocation and storage schemes and put in the time to figure out conclusively which is best for each particular type of component.

• I said: we cannot change entity's signature, and I meant that we cannot directly modify it in-place, but still we can just obtain existing assemblage to a local copy, make changes to it, and upload again as a new entity - and these operations are pretty cheap, as I have shown in the question. Once again - there is only ONE "bucket" class. "Assemblages"/"Signatures"/"let's name it however we want" can be created dynamically at runtime as in a standard approach, I would even go as far as thinking of an entity as a "signature". – Patryk Czachurski Jul 6 '13 at 20:38
• And I said you don't necessarily want to deal with the reification. "Making a new entity" could potentially mean breaking all existing handles to the entity, depending on how your handle system works. Your call if they're cheap enough or not. I found it to just be a pain in the butt to have to deal with. – Sean Middleditch Jul 6 '13 at 20:43
• Okay, now I've got your point about this one. Anyway I think that even if adding/removing were a bit more expensive it happens so ocassionaly that it is still worth greatly simplifying the process of accessing the components, which happens in real-time. So, the overhead of "changing" is negliglible. About your AI example, isn't it still worth these few systems that anyway need data from multiple components? – Patryk Czachurski Jul 6 '13 at 20:54
• My point there was that AI was a place where your approach is better, but for other components it is not necessarily so. – Sean Middleditch Jul 6 '13 at 21:09

What you've done is re-engineered C++ objects. The reason why this feels obvious is that if you replace the word "entity" with "class" and "component" with "member" this is a standard OOP design using mixins.

1) you lose the dynamic nature of pluggable components, which was created specifically to get away from static class construction.

2) memory coherence is most important within a data type, not within an object unifying multiple data types in one place. This is one of the reasons that component+systems were created, to get away from the class+object memory fragmenting.

3) this design also reverts to C++ class style because you are thinking of the entity as a coherent object when, in a component+system design, the entity is merely a tag/ID to make the inner workings understandable to humans.

4) it is just as easy for a component to serialize itself than a complex object to serialize multiple components within itself, if not actually easier to keep track of as a programmer.

5) the next logical step down this path is to remove Systems and put that code directly into the entity, where it has all the data it needs to work. We can all see what that implies =)

• 2) maybe I don't understand caching fully, but let's say there's a System that works with say 10 components. In a standard approach, processing each entity means accessing RAM 10 times, because components are scattered in random places in memory, even if pools are used - because different components belong to different pools. Wouldn't it be "important" to cache whole entity at once and process all components without a single cache miss, without even having to make dictionary lookups? Also, I made an edit to cover the 1) point – Patryk Czachurski Jul 6 '13 at 20:16
• @Sean Middleditch has a good description of this caching breakdown in his answer. – Patrick Hughes Jul 6 '13 at 20:48
• 3) They are not coherent objects in any way. About component A being just next to component B in memory, it's just "memory coherency", not "logical coherency", as John has pointed out. Buckets, on their creation, could even shuffle components in signature to any desired order and principles would still be maintained. 4) it may be equally easy to "keep track" if we have enough abstraction - what we're talking about is merely a storage scheme that provided with iterators and perhaps a byte offset map can make processing as easy as in a standard approach. – Patryk Czachurski Jul 7 '13 at 22:41
• 5) And I don't think anything in this idea points to this direction. It's not that I do not want to agree with you, I'm just curious where this discussion may lead, though anyway it will probably lead to kind of "measure it" or the well-known "premature optimization". :) – Patryk Czachurski Jul 7 '13 at 22:42
• @PatrykCzachurski but your systems don't work with 10 components. – user253751 Oct 9 '18 at 21:50

Keeping like entities together isn't as important as you might think, which is why it's hard to think of a valid reason other than "because it's a unit". But since you are really doing this for cache coherency as opposed to logical coherency, it might make sense.

One difficulty you could have is interactions between components in different buckets. It's not terribly straight forward to find something your AI can shoot at for example, you'd need to go through all buckets that might contain a valid target. Without an external data structure, collision detection could be equally as difficult.

To continue about organizing entities together for logical coherency, the only reason that I could have to keep entities together is for identification purposes in my missions. I need to know if you have just created entity type A or type B, and I get around this by... you guessed it: adding a new component that identifies the assemblage that put this entity together. Even then, I'm not gathering all the components together for a grand task, I just need to know what it is. So I don't think this part is terribly useful.

• I have to admit I don't quite understand your answer. What do you mean by "logical coherency"? About difficulties in interactions, I made an edit. – Patryk Czachurski Jul 6 '13 at 20:24
• "Logical coherence", as in: It makes "logical sense" to keep all components that make up a Tree entity close together. – John McDonald Jul 6 '13 at 20:26