Efficient Queries in an archetype-based Entity Component System

Question

I am currently writing an archetype-based ECS for learning purposes. What I noticed is that my current implementation is incredibly slow with large amounts of archetypes.

Each of my queries iterates over ALL archetypes and uses a dynamic bitset to check if the archetype is eligible for the query or not. So there are unnecessary iterations every time a query is executed. This is slow because the bitsets are also different sizes to support "infinite components". The bitsets are too long to be fast and too small to get a speed up by vectorization.

// Pseudo code, In query iterator
foreach(var archetype : archetypes){

    unit[] queryBitSet = myQuery.BitSet;
    unit[] archetypeBitSet = archetype.BitSet;

    // Checking if query matches archetype
    var min = Math.min(queryBitSet.Length, archetypeBitSet.Length);
    for(var index = 0; index < min; index++){
       
        if(queryBitSet[index] & archetypeBitSet[index] != queryBitSet[index]){
           ...
        }
    }

    ... Process archetype if query matches
}

The bitsets are all quite small, have only a few uint items. Nevertheless, with a large mass of archetypes, the queries become incredibly slow. I can't think of any improvement.

Therefore, something else is needed: query caching. But how would this be implemented in an archetype-based ECS anyway? What would this look like in pseudo code? What else would you improve for ideal and performant archetype queries?

DMGregory · Accepted Answer · 2023-08-29 02:05:21Z

As I sketched in a previous answer, the way I'd approach this would be to...

Register each needed query at system start-up (ie. once)
Store the cached query as an object containing a list of matching archetypes
Add matching archetypes to the query only at registration or when a new archetype is instantiated

That means that however expensive the matching might be, it does not occur every frame (or every system evaluation within a frame) - all that work happens at game boot or level load, or on the rare occasion where you need to spawn an object from a never-seen-before archetype.

All the high-frequency iteration happens over the cached list of matching archetypes, so there's no search/matching workload there.

public static class QueryManager {

    // I used a SortedSet here so you can get O(log n) lookups
    // and insertion, since your bit sets can be ordered 
    // lexicographically for a binary search via Query.CompareTo()
    static SortedSet<Query> _queryCache = new();

    static List<Archetype> _archetypes = new();

    static Query _tempQuery;

    // When a new query is registered, cache all matching
    // archetypes known at that time and return the cached query.
    // Cached queries are shared/de-duplicated between multiple requests.
    public static Query RegisterQuery(ComponentSignature components) {

        _tempQuery.signature = components;
        if (!_queryCache.TryGetValue(_tempQuery, out Query cached)) {

            _tempQuery.matches = new List<Archetype>();
            foreach(var archetype in _archetypes) {
                if (_tempQuery.Matches(archetype)) {
                    _tempQuery.matches.Add(archetype);
                }
            }

            cached = _tempQuery;
            _queryCache.Add(cached);
 
            // Set aside a fresh temporary for the next attempt,
            // since our old one got promoted to a permanent cached version.
            _tempQuery = new Query();
        }
        return cached;
    }


    // When a new archetype is registered, add it to all
    // cached queries that match it.
    public static void RegisterArchetype(Archetype archetype) {
        _archetypes.Add(archetype);

        foreach(var query in _queryCache) {
            if (query.Matches(archetype)) {
                query.matches.Add(archetype);
            }
        }
    }
}

Your system might then look something like...

public class FallingSystem {

     Query _positionAndFallComponents;

     public void Initialize() {
         // Potentially expensive matching, done only when initializing:
         _positionAndFallComponents = QueryManager.RegisterQuery(
                                        new ComponentSignature(
                                           typeof(PositionComponent), 
                                           typeof(FallComponent)
                                      ));
     }

     public void Update(float timeStep) {
         // Within a frame, we can iterate the query immediately,
         // without paying for any matching logic per use.
         foreach(var archetype in _positionAndFallComponents.matches) {
             var positions = archetype.GetComponents<PositionComponent>();
             var falls = archetype.GetComponents<FallComponent>();

             int count = archetype.EntityCount;
             for (int i = 0; i < count; i++) {
                 positions[i].y -= falls[i].speed * timeStep;
             }
         }
     }
}

(And the archetypes could be similar to the ones I sketch in this answer)

Stack Exchange Network

Efficient Queries in an archetype-based Entity Component System

1 Answer 1

You must log in to answer this question.

Linked

Hot Network Questions

Efficient Queries in an archetype-based Entity Component System

1 Answer 1

You must log in to answer this question.

Linked

Related

Hot Network Questions