Flipping Data Structures to optimize performance 🚀

What do I mean

When we want a high performance system, we can greatly benefit by thinking in terms of efficient data organization. When we have multilayered maps or hash tables, sometimes a simple reorientation of data is all that we need.

In my ECS system, I have:

• _entities that map id -> Entity(id)
• _components that map Entity.id -> Component.Type -> Set(Component())

So when we query for all Entities that have a Component of a specific type, we list all entities and then filter out those that do not have a Component.Type entry or where the set size is 0.

This works well enough to a certain point, but we can observe that this algorithm performs similarly when searching for both common and rare components, even though searching for a rare component should, intuitively be faster.

One optimization we can implement is to flip the _component map Entity.id and Component.Type:

_components that map Component.Type -> Entity.id -> Set(Component())

The benefit is that when a component is rare, we only have to traverse a short list to check if the set is empty and filter those entities accordingly. This could be further improved by deleting the entity entry for a type when the set is empty. This way, our query can simply return a set.

Here are the results of this optimization for 100_000 eateries and 600 rare Component instances:

queryCommon: 51.256ms -> 16.161ms

queryRare: 58.081ms -> 0.346ms

getComponentsCommon: 37.668ms -> 34.671ms

getComponentsRare: 21.635ms -> 9.959ms

Conclusion

By reorganizing how components are mapped within the ECS, we can significantly improve the performance of queries, especially for rare components. This simple yet effective change allows the system to handle query more efficiently.

Hope this helps developers not to forget to handle their data appropriately even when using something like JavaScript.