04 · Pool¶
What it is¶
A pool stores every instance of one component type, packed together. It is the sparse-set storage of the ECS: a sparse array to find an entity, and dense arrays holding the entities, their component bytes and their change ticks, all in the same order.
In code it is rtype::ecs::storage::SparseSetStorage, built on a ByteColumn (a growable, aligned
array of raw bytes).
Why we need it¶
- Fast iteration: systems walk the dense arrays linearly, which is what CPUs are fastest at.
- Cheap structural changes: adding or removing a component is O(1). R-Type adds and removes
constantly (bullets, tags like
Invincible, script components). - R2 (Luau): the pool stores raw bytes described by a
ComponentInfo, so it works for components that have no C++ type. - R3 (network): the tick columns are what change detection and replication read.
How others do it¶
| ECS | Per-component storage |
|---|---|
| EnTT | basic_storage: sparse set + packed components, typed (templates) |
| Bevy | ComponentSparseSet for sparse components, type-erased (BlobVec), with tick columns |
| flecs | Columns inside archetype tables; sparse storage option in recent versions |
| Unity / Unreal Mass | Columns inside chunks |
Our choice¶
A type-erased sparse set with tick columns, like Bevy's ComponentSparseSet. One pool per
component of storage kind kSparseSet (every component in v1).
How it works¶
Layout¶
Example: a Position pool holding e3, e6 and e1.
Sparse array (page 0; later pages not allocated), indexed by entity index:
| Entity index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Dense position | – | 2 | – | 0 | – | – | 1 |
Dense arrays, packed and in the same order:
| Dense position | 0 | 1 | 2 |
|---|---|---|---|
| Entity | e3 |
e6 |
e1 |
Data (Position bytes) |
P3 | P6 | P1 |
| Added tick | 12 | 40 | 40 |
| Changed tick | 50 | 41 | 40 |
flowchart LR
get["get(e6)"] --> sparse["sparse entry of index 6<br/>→ dense position 1"]
sparse --> check{"entities[1] == e6?<br/>(same generation)"}
check -- "yes" --> data["data[1]"]
check -- "no: stale handle" --> absent["absent"]
miss["get(e2)"] --> empty["sparse entry of index 2<br/>is empty"] --> absent
namespace rtype::ecs::storage {
/// @brief Type-erased sparse-set pool for one component.
class RTYPE_ECS_API SparseSetStorage {
public:
explicit SparseSetStorage(const ComponentInfo& info);
[[nodiscard]] bool contains(Entity entity) const noexcept;
[[nodiscard]] void* get(Entity entity) noexcept; ///< nullptr if absent.
void* emplace(Entity entity, Tick tick); ///< Default-constructs, returns the bytes.
bool remove(Entity entity) noexcept; ///< Swap-and-pop.
[[nodiscard]] std::span<const Entity> getEntities() const noexcept;
private:
const ComponentInfo* _info; ///< Owned by the registry.
PagedSparseArray _sparse; ///< Entity index -> dense index.
std::vector<Entity> _dense; ///< Entities, packed.
ByteColumn _data; ///< Component bytes, aligned.
std::vector<Tick> _added; ///< When each component was added.
std::vector<Tick> _changed; ///< When each component was last written.
};
} // namespace rtype::ecs::storage
The byte column¶
ByteColumn is a std::vector-like buffer of size × count bytes, allocated with the component's
alignment. It never knows the C++ type; it calls the hooks from
ComponentInfo when it must construct, move or destroy elements, or uses memcpy / nothing when the
hooks are null (plain data, and every Luau component).
Operations¶
emplace(e):
- Append
eto the dense entity array. - Grow the data column by one element:
constructhook, or zero-fill when it is null. - Append the current tick to the added and changed tick arrays.
- Set the sparse entry of
e's index to the new dense position (size - 1).
remove(e), swap-and-pop:
flowchart LR
subgraph before ["Before remove(e3)"]
direction TB
b0["0 · e3 · P3"]
b1["1 · e6 · P6"]
b2["2 · e1 · P1"]
end
subgraph after ["After"]
direction TB
a0["0 · e1 · P1"]
a1["1 · e6 · P6"]
end
b2 -- "1. move the last element into the hole<br/>(move hook or memcpy, ticks too)" --> a0
b1 -- "unchanged" --> a1
- Update the moved entity's sparse entry: index 1 → position 0.
- Clear the removed entity's sparse entry: index 3 → empty.
- Pop the back of every array, destroying the old last element if it has a
destructhook.
| Operation | Cost |
|---|---|
contains, get |
O(1): one sparse lookup + one comparison |
emplace |
Amortized O(1) (vector growth) |
remove |
O(1): one move + pops |
| Iterate | Linear over getEntities() and the data column |
Tags¶
A tag (size == 0, e.g. Dead) has no data column: its pool is only the entity set and the
ticks. Tags are therefore almost free, which encourages using them for states.
Iteration order¶
The dense order is the insertion order, disturbed by swap-and-pop. It is not stable and not meaningful; systems that need an order (draw layers) sort explicitly.
Connections¶
- Uses: Entity, Component registry (size, alignment, hooks), Sparse array, Hooks.
- Used by: World (one pool per sparse-set component), Queries (driver
pool and
containschecks), Change detection (tick columns), Replication (scans changed ticks per pool).
Pitfalls¶
- Pointer and reference invalidation.
emplacecan reallocate the column;removemoves the last element. Never keep aT*orT&across structural changes. This is why structural changes inside systems go through commands, and why scripts hold entities, not pointers. - Forgetting a parallel array. Every operation must update entities, data, both tick arrays and the sparse entry together; keep them behind one function each.
- Alignment. A
ByteColumnofglm::vec4s must be 16-byte aligned; allocate with the component's alignment, notalignof(std::max_align_t).
Open questions¶
- Shrink policy: never shrink, or shrink when a pool drops below a quarter of its capacity? (ECS)