Efficient way of matching entities to systems in an entity component system

Question

I'm working on a data-oriented entity component system where component types and system signatures are known at compile-time.

---

An entity is an aggregate of components. Components can be added/removed from entities at run-time.

A component is a small logic-less class.

A signature is a compile-time list of component types. An entity is said to match a signature if it contains all component types required by the signature.

---

A short code sample will show you how the user syntax looks and what the intended usage is:

// User-defined component types.
struct Comp0 : ecs::Component { /*...*/ };
struct Comp1 : ecs::Component { /*...*/ };
struct Comp2 : ecs::Component { /*...*/ };
struct Comp3 : ecs::Component { /*...*/ };

// User-defined system signatures.
using Sig0 = ecs::Requires<Comp0>;
using Sig1 = ecs::Requires<Comp1, Comp3>;
using Sig2 = ecs::Requires<Comp1, Comp2, Comp3>;

// Store all components in a compile-time type list.
using MyComps = ecs::ComponentList
<
    Comp0, Comp1, Comp2, Comp3
>;

// Store all signatures in a compile-time type list.
using MySigs = ecs::SignatureList
<
    Sig0, Sig1, Sig2
>;

// Final type of the entity manager.
using MyManager = ecs::Manager<MyComps, MySigs>;

void example()
{
    MyManager m;

    // Create an entity and add components to it at runtime.
    auto e0 = m.createEntity();
    m.add<Comp0>(e0);
    m.add<Comp1>(e0);
    m.add<Comp3>(e0);

    // Matches.
    assert(m.matches<Sig0>(e0));

    // Matches.
    assert(m.matches<Sig1>(e0));

    // Doesn't match. (`Comp2` missing)
    assert(!m.matches<Sig2>(e0));

    // Do something with all entities matching `Sig0`.
    m.forEntitiesMatching<Sig0>([](/*...*/){/*...*/}); 
}

---

I'm currently checking if entities match signatures using std::bitset operations. The performance, however, quickly degrades as soon as the number of signatures and the number of entities increase.

Pseudocode:

// m.forEntitiesMatching<Sig0>
// ...gets transformed into...

for(auto& e : entities)
    if((e.bitset & getBitset<Sig0>()) == getBitset<Sig0>())
        callUserFunction(e);

This works, but if the user calls forEntitiesMatching with the same signature multiple times, all entities will have to be matched again.

There may also be a better way of pre-caching entities in cache-friendly containers.

I've tried using some sort of cache that creates a compile-time map (implemented as std::tuple<std::vector<EntityIndex>, std::vector<EntityIndex>, ...>), where the keys are the signature types (every signature type has a unique incremental index thanks to SignatureList), and the values are vectors of entity indices.

I filled the cache tuple with something like:

// Compile-time list iterations a-la `boost::hana`.
forEveryType<SignatureList>([](auto t)
{
    using Type = decltype(t)::Type;
    for(auto entityIndex : entities)
        if(matchesSignature<Type>(e))
            std::get<idx<Type>()>(cache).emplace_back(e);
});

And cleared it after every manager update cycle.

Unfortunately it performed more slowly than then "raw" loop shown above in all of my tests. It also would have a bigger issue: what if a call to forEntitiesMatching actually removes or adds a component to an entity? The cache would have to be invalidated and recalculated for subsequent forEntitiesMatching calls.

---

Is there any faster way of matching entities to signatures?

A lot of things are known at compile-time (list of component types, list of signature types, ...) - is there any auxiliary data structure that could be generated at compile-time which would help with "bitset-like" matching?

Answer 1

For matching, are you checking for each component type one bit at a time? You should be able to plow through the entities by checking if all components for a signature are available in one instruction against a bit mask.

For example, we might use:

const uint64_t signature = 0xD; // 0b1101

... to check for the presence of components 0, 1, and 3.

for(const auto& ent: entities)
{
     if (ent.components & signature)
          // the entity has components 0, 1, and 3.
}

That should be fast as hell if your entities are stored contiguously in an array. It doesn't matter, performance-wise, whether you are checking for 3 component types or 50 component types at a time. I don't use this type of rep for my ECS, but definitely this shouldn't take long at all even if you have a million entities. That should complete in the blink of an eye.

It's pretty much the fastest practical way achievable to see what entities provide a given set of components while storing the minimal amount of state -- only reason I don't use this rep is because my ECS revolves around a plugin architecture where people register new component types and systems at runtime through plugins and scripts so I can't effectively anticipate an upper bound on how many component types there will be. If I had a compile-time system like yours that is designed to anticipate all this stuff in advance, then definitely I think this is the way to go. Just don't check one bit at a time.

You should be able to easily process a million components several hundred times a second using the above solution. There are people achieving similar rates applying CPU image filters processing that many pixels multiplied by that many times per second, and those filters have far more work to do than a single bitwise and and a single branch per iteration.

I also wouldn't even bother caching this super cheap sequential loop unless you have some systems that only want to process, say, a dozen out of a million entities. But at that point you can potentially cache those rare case scenarios where one system barely processes any entities local to the system instead of trying to cache things centrally. Just make sure systems that are interested can find out when entities are added to the system or removed from the system so that they can invalidate their local cache.

Also you don't necessarily need fancy metaprogramming for these signatures. At the end of the day you aren't really saving anything using template metaprogramming since it can't avoid looping through entities checking for something since the list of entities is only known at runtime. There's not really theoretically anything worth optimizing away at compile-time here. You can just do like:

static const uint64_t motion_id = 1 << 0;
static const uint64_t sprite_id = 1 << 1;
static const uint64_t sound_id = 1 << 2;
static const uint64_t particle_id = 1 << 3;
...

// Signature to check for entities with motion, sprite, and 
// particle components.
static const uint64_t sig = motion_id | sprite_id | particle_id;

If you use entity-associated bits to indicate what components an entity has, I recommend setting an upper bound on the total number of component types your system can handle (ex: 64 is probably plenty, 128 is a boatload) so that you can just check for components against bitmasks like these in one go.

[...] what if a call to forEntitiesMatching actually removes or adds a component to an entity?

If, say, you have a system which is adding/removing components every frame, then I wouldn't even bother to cache in the first place. The above version should be able to loop through entities super fast.

The worst-case scenario of looping through all entities sequentially is if you have a system that, say, is only going to process 3% of those entities. If your engine design has systems like that, then it's a bit awkward, but you might just notify them when components are added/removed that they are specifically interested in at which point they can invalidate their entity cache and then recache the next time the system kicks in. Hopefully you don't have a system adding/removing components every single frame of the types that are that 3% minority of components. If you do have that worst-case scenario though, probably best not to bother with caching at all. There's no use for a cache which is just going to be discarded every frame and trying to update it in a fancy way is probably not going to net you much.

Other systems which, say, process 50% or more of the entities probably shouldn't even bother caching, since the level of indirection is probably not worth it over just plowing through all the entities sequentially and doing a dirt cheap bitwise and over each one.