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 mapid -> Entity(id)
-
_components
that mapEntity.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.
Top comments (0)