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?