# 手撕ECS #2: Archetypes and Vectorization

## 操作：获得实体与组件

row 是指实体对应的组件在 Archetype::components 中的位置。此时如果想获得 10 号实体的 A 组件，我们可以这样做：

## 操作：添加、删除组件

• 找到目标原型(Find destination archetype)
• 在目标原型中插入该实体(Insert entity into component arrays of destination)
• 复制原有的组件数据(Copy overlapping components from source to destination)
• 从原来的原型中移除实体(Remove entity from component arrays of source)

## 操作：获得或创建目标原型

An important factor in how well add / remove operations perform is how fast an ECS framework can find an archetype. A simple approach would be to hash the component ids of an archetype, and then use a hash map to lookup an archetype:

This approach is neither slow nor is it particularly fast:

First we need to create our destination type. If we take our previous example where we add C to [A, B], we need to create [A, B, C]. In our case, where a type is stored as a vector of component ids this is an O(n) operation (to avoid adding duplicates). Then we need to compute the hash, which is another O(n) operation, followed by a hash table lookup which is O(1) on average, and O(n) worst case.

This seems like a lot of work for one of the most common ECS operations.

A faster approach is to build a graph, where each archetype represents a node in the graph, and the components to add / remove are the edges. Consider this example:

Each arrow to the right represents an “add” operation, and each arrow to the left represents a “remove” operation. Now, to move from archetype [A, B] to [A, B, C] we simply follow the C edge, which is an O(1) operation. When we follow an edge that does not have an archetype yet, we create it.

Let’s add the graph to our previous archetype data structure:

We can now write this function to find our next archetype:

Note how we use a type to traverse the graph. If we only add a single component to an entity, the type will only contain a single element, but by writing the function this way, we can quickly traverse multiple nodes.

## AoS vs. SoA

So far we assumed that an archetype stores an array per component. This is usually referred to as the “struct of arrays” (SoA) approach. The reason it is named like this is because the way data is stored resembles that of a struct with array members:

It turns out that SoA works really well in combination with ECS. This is because a system is usually not interested in all components of an entity, and the SoA approach lets us load only the arrays into the CPU cache that we need. There is another valid approach though which is called “array of structs” (AoS). AoS can be represented like this:

This example stores the same data, but it is laid out differently in memory. The biggest difference between AoS and SoA is that with AoS, all data of an entity is loaded into the CPU cache. This may slow down applications when only iterating a few components. AoS can however perform better when randomly accessing components. Flecs uses the SoA approach.

## Summary

Our ECS framework is starting to shape up nicely. Let’s combine the data structures of our archetype with those of the previous post:

Archetypes are a popular approach that provide good general performance, but they are not the only way to implement an ECS. I hope this gave you some background on their pro’s and con’s.

If you liked what you read, consider checking out the Flecs repository (https://github.com/SanderMertens/flecs) and the Flecs Discord channel!

Share