Appropriate Cache Friendly Associative Container For An Entity Component System

Question

The intro to this problem is a bit of a long one so my apologies in advance. In short I am asking for suggestion as to what type of collection I should use to store data for a particular part of my system.

I have an entity component system in place where a static EntityManager creates and stores components within vectors of their own type, and creates Entities storing them in either a vector for dynamic entities or a vector for static entities. Something like this:

#define COMPONENTS X(MeshComponent) X(CameraComponent) X(PointLightComponent) X(DirectionLightComponent)
#define X(ARG) std::vector<ARG>,
using ComponentTuple = std::tuple<COMPONENTS Empty>;
#undef X

class EntityManager {
    static ComponentTuple components;

    vector<Entity>& getDynamicEntities() {
        static vector<Entity> entities;
        return entities;
    }

    vector<Entity>& getStaticEntities() {
        static vector<Entity> entities;
        return entities;
    }
}

Without getting into too much detail each Entity has an id (stored as a short which determines its dynamic or static status and its index within the respective vector).

Each Component has its own id (an unsigned short referring to its index in its respective vector) and an Entity id, referring to the entity it is "attached" to.

At this point all the Entity object is, is an ID and useful functions. To make it more useful I decided to let the Entity object store a collection of id's (unsigned shorts) of its own components (to make searching for the entities specific components faster). My initial plan was to use an unordered_map data structure it like so:

class Entity {
    friend class EntityManager;
private:
    short id = SHRT_MAX;
    std::unordered_map<std::type_index, vector<unsigned short>> components;
}

Thinking on it though, this introduces at least two (from what I can see) levels of indirection. One to the hash table produced by the unordered map and another to the vector storing the actual id's. With this in mind I was wondering if anyone else would be able to suggest a more cache friendly data structure. If not a simple reassurance that my choice was a correct one will also suffice (as right now I can't help but feel that there is a better way).

Some of the things that I would like the collection to do:

1) I would like to be able to search the collection by ComponentType (because components may share the same ID but be stored in different vectors)

2) I would like the collection to be expansive (not all entities will have the same components and it just seems wasteful to have an array for all potential Component Types when the entity may only have one)

3) I would like the potential to have multiple Components of the same Component Type in the collection (in the example given above maybe some Components have two PointLightComponents)

Any suggestions or comments would be greatly appreciated as I've been wracking my brain on this one for some time now. Thanks in advance.

Answer 1

Do the simplest thing that works, especially early on.

If you've ever seen videos of triple-A titles in alpha, you'll know how slow / buggy they are. This is normal; in fact, it's desirable. And it's often because they used the naive solution to problems.

Agile development philosophy states Refactor Mercilessly; I couldn't agree more, from experience. Expect to refactor in phases, every few days. It is a far safer approach than spending countless hours fussing over the fine details, never realising they will never even come to fruition as you usually end up choosing a different approach. Software dev works in phases like this: for now, use the simplest thing that works. It's how the big companies work, too.

The most important thing is to write code that does something, otherwise you don't even know what you ultimately have to optimise. Making progress means glossing over fine performance details.

What this means in your case is: don't expect a one-size-fits-all data structure. What I suggest is you start with the essential needs data structure (for which I think unordered_map will do fine), and either

1. use more optimal data structures "alongside" (can be fraught with peril, as you must keep various data structures in sync) or
2. sort / search that primary data structure in non-optimal ways, and maintain just that one. (This means for example doing O(n) searches over your map)

It is far more productive to code this way and aim for lower thresholds e.g. in unit count, number of AI updates per minute, and so on, than to try to aim high from the start. Then you have the basic principle and can focus later on the finer implementation details once the concept has crystallised.

If you're struggling with the idea of gutting your game, my view is you need to spend more time practicing refactoring, as it is an unavoidable necessity in our field. Write code to throw it away.

Closing tip When you find yourself wanting to access the same data structure in a variety of different ways (even worse, potentially), there is problem in your conceptualisation of the problem. I got this a lot as a younger programmer. That's the point at which, in order to get meaningful work done, you need to decide what is the primary thing you need, start coding that up in the simplest way possible, and go from there. You'll usually find along the way that you didn't need all the rest!

Answer 2

ArcaneEngineer's advice is good, particularly for early development (to an extent - once you configure your engine to work a particular way, it can be significantly hard to rework it later).

For best performance, look into slot maps (also known as slot arrays, packed arrays) and colony.

A slot map has the advantage of already having the map (id) functionality built in, and the unordered iterative performance of an array. A colony has the advantage of stable pointers to elements regardless of insertion/erasure, and a faster insertion/erasure mechanism than slot maps. It has slightly lower iteration speed. I would not recommend unordered_map, as it has well-known and significant performance issues due to way it was conceived in the standard preventing better cache-friendly implementations.

A couple of slot_x implementations:

SG14 slot_map

Masstronaut slot_array