Issues with ECS performance

Question

I'm currently implementing ECS in "classic" sense, as defined by this wonderful post, where we have Entities, Components and Systems. And I'm having a serious (for me) performance issues. They come from the fact that System may need access to several components of the entity:

IList<int> es = _ecsManager.GetComponentEntities(ComponentType.RENDER);

int cacheRender = -1;
int cacheMovement = -1;
foreach (var entityId in es) {
    var rc = _ecsManager.GetEntityComponent<RenderComponent>(entityId, ComponentType.RENDER, ref cacheRender);
    var mc = _ecsManager.GetEntityComponent<MovementComponent>(entityId, ComponentType.MOVEMENT, ref cacheMovement);
    rc.Sprite.Position = mc.Position;
    QueueSprite(rc.Sprite);
}

the QueueSprite is my sprite batching, it's backed by regular arrays and Lists with no dynamic in long run. And GetEntityComponent is:

public T GetEntityComponent<T>(int entityId, int componentId, ref int idxCache) where T : PslComponent {
    var cs = GetEntityComponents(entityId);
    // try for cache
    if (idxCache != CACHE_NULL && idxCache < cs.Count) {
        var tmp = cs[idxCache];
        if (tmp.TypeId == componentId) {
            return (T)tmp;
        }
        // cache miss
        idxCache = CACHE_NULL;
    }
    // cache failed, sequental search            
    for (var i = 0; i < cs.Count; i++) {
        var component = cs[i];
        if (component.TypeId == componentId) {
            // update cache
            idxCache = i;
            return (T)component;
        }
    }
    // not found
    return null;
}

and GetEntityComponents:

public IList<PslComponent> GetEntityComponents(int entityId) {
    return _componentsByEntity[entityId];
}

with _componentsByEntity being a array, GetComponentEntities works similarly backed by regular array too:

public IList<int> GetComponentEntities(int componentId) {
    return _entitiesByComponent[componentId];
}

the abovementioned foreach loop is taking a lot of time. More than rendering.

As you can see, I'm pretty much tried to optimize a lot of things already, removing all Dictonary<>-type lookups, replacing all by arrays and Lists. There is no dynamic allocation in long-run. The only problem, as I see it, is sequental search in entity Component loookup.

1. Is there any possibility to improve component lookup speed, while remaining true to classic implementation?
2. Is this major performance penalty is usually assumed then ECS is used? Are ECS "bad" then high performance is required?

Answer 1

You could store components two-dimensionally in a list of lists:

List<List<PslComponent>> _componentsByType;

You use the component type ID as the index into the outer list...

List<PslComponent> componentByEntity = _componentsByType[componentTypeId];

...and then use the entity ID to look up the component of that type on that entity (or null if the entity does not have that type of component.

PslComponent component = componentByEntity[entityId];

You can lazily create the inner lists of components when you add a component of a particular type to an entity for the first time (when _componentsByType[componentTypeId] == null). Also, instead of using List, you could create a special kind of array backed list that allows you to set a value at any index in it by automatically growing the backing array to be big enough when setting.

Answer 2

To answer your question simply:

1. Get list of all the RenderComponents, and a list of all the Movement Components. We assume each component has a field which gives the entity is is a part of.
2. Sort them by entity ID. Obviously, if you keep these lists sorted in the systems themselves, then this is very inexpensive (maintaining the sorting is cheap).
3. Initialize an index of 0 into each sorted list. These indices will point to components.
4. If the two pointed to components have the same entity ID, then process them, and increment both indices.
5. If the two indices are different, then increment the index which points to the component with a smaller entity ID.
6. If either index points off the end of it's array after incrementing, you are done. Otherwise, goto 4. Note at least one index is incremented every iteration.

Why does this work? Essentially, everything before the two indices have already been processed, which includes entities with only one of the two components. We can never miss a pair because when the pointer reaches a certain component in the array, we know that it cannot move to the next component until the other pointer is at the same or a higher entity index. This mean that either we process the pair, or that the entity did not have a corresponding component of the other type. Symmetric reasoning from the other array means we won't miss any pairs there either.

This procedure is about as efficient as you can get. Further, if you pack the components themselves (not just the references) in sorted order, then it is extremely cache friendly. It can also be extended to more than two components, but that is slightly trickier.

This algorithm is exactly order O(n+m), where n and m are the counts of components in each list, but excluding the cost of sorting.

All we need from the ECS manager is the ability to get an iterable of the sorted components of a system. That's a pretty minimal interface. Looking up arbitrary components is important for interactions between entities, but in this case is not necessary.

Vectors/arrays are not magical, switching from a dictionary was a poor idea in this case, without realizing the above algorithm. O(1) lookup is useless if you use it to implement O(n) search.

Answer 3

Don't iterate over all entities and see if they have an interesting components - only iterate over entities that have your interesting component attached.

One way is to use a nested dictionary of the following type (no particular language here):

components: Dictionary<TypeIdentifier, Dictionary<Int, Component>>

This lets you look up the Entity -> Component mapping in O(1) time.

TypeIdentifier is some kind of metatype's hashable identifier that is provided at compile time based on the class in which you are interested (Swift: ObjectIdentifier - C++: type_index)

Entities are just integers (in my mind).

The Component would be some sort of abstract base class or interface/protocol type which you can statically cast to the more specific Position type – this is safe because you know for certain what type it will be based on the first layer of the dictionary.

Lots of languages have some notion of a hashable type id (C++ has type_index, Swift has ObjectIdentifier, Python has classes, etc.).

For example, in Swift, I might do something like the following:

class Component {}

class Position : Component {
    var x: Int
    var y: Int
    init(x: Int, y: Int) {
        self.x = x
        self.y = y
    }
}

typealias Entity = Int
var components = [ObjectIdentifier : [Entity : Component]]

for (entity, component) in components[ObjectIdentifier(Position.self)] {
    let position = component as Position
    println("Entity \(entity) has x: \(position.x), y: \(position.y)")
}

In C++, I might do something similar to this for the nested dictionary type:

std::unordered_map<std::type_index, std::unordered_map<int, std::shared_ptr<Component>>

or something like that.

At runtime, I can attach a Position component dynamically by just setting (abstractly speaking, without regard to a particular language):

components[Position][entity] = position

Later, if I key in with components[Position], I'll get another dictionary whose keys are only the entities that have a position. No side cache needed.

It's not without its problems, hashing isn't free, but give it a try. It'll limit the search space quite a bit if you have a lot of entities.