skip to content

How do archetype storage and sparse-set storage differ in an ECS, and which suits a status that is added and removed every few frames?

level: seniorimportance: should knowfreq 55%

answer

  1. tables per component combination
  2. move the whole row on add
  3. sparse index into a dense array
  4. the smallest pool drives the join
  5. per-component storage choice

basics

~20 s

Archetype storage keeps entities with identical component sets in shared tables: dense multi-component iteration, but adding a component copies the whole entity. Sparse sets store each type separately: constant-time add and remove, indirect joins. A frequently toggled status suits sparse sets.

solid answer

~50 s

**Archetype** storage keeps one table per distinct combination of component types, a column per type, and a query walks the columns of every matching table linearly, which is ideal for swarm positions and velocities. The price is structural change: adding `Burning` copies all of the entity's components into the table for its new combination, and each independently toggled tag can double the table count. **Sparse-set** storage keeps, per component type, a dense array of values plus a sparse array mapping entity index to dense slot, so add and remove are constant time and touch one pool. Its weakness is joins: a query iterates the smallest pool and looks the others up through their sparse arrays, in a different order, so access scatters. For a status toggled every few frames I'd store it sparse, or as a flag if most units are visited anyway, and keep the movement data in archetype tables.

code

pseudocode · 14 lines
pseudocode
add(entity, value):                    // caller has checked the entity is not already present
    sparse[entity.index] = count
    dense_values[count] = value
    dense_entities[count] = entity
    count = count + 1

remove(entity):                        // caller has checked the entity is present
    slot = sparse[entity.index]
    last = count - 1
    dense_values[slot] = dense_values[last]
    dense_entities[slot] = dense_entities[last]
    sparse[dense_entities[slot].index] = slot
    sparse[entity.index] = INVALID     // set last, so removing the final element still ends invalid
    count = last

go deeper

for a junior

Recall the two layouts: one table per component combination, or one pool per component type with a sparse index into a dense array.

for a middle

Explain what adding a component costs in each, how swap-and-pop keeps arrays dense, and why a sparse-set join scatters its lookups.

for a senior

Pick storage per component from its access pattern, as with stable swarm movement data versus a status toggled every few frames, and know the fragmentation and grouping effects.

for a principal

Set the storage policy and the defaults a team uses for new component types, and the profiling evidence required before a component changes storage.

## Archetype storage An **archetype** is one distinct set of component types, for example {Position, Velocity, Health}. Archetype storage keeps one **table** per archetype: - each component type in the set is a **column**, a contiguous array, alongside a column of entity ids; - each entity is a **row**, and an entity record maps its id to the pair (archetype, row); - some designs split each table into fixed-size blocks so memory is allocated in units and rows stay compact; - a **query**, such as has Position and Velocity but not Frozen, matches every archetype whose set contains the required types and none of the excluded ones. The match list is cached and extended when a new archetype appears. Iteration is as good as it gets: for each matching table, the system walks two or three columns from start to end, linearly and in step. That is exactly what a movement update over fifty thousand swarm units wants. The cost is paid on **structural changes**. Adding `Burning` to a unit changes its archetype, so the engine finds or creates the table for {Position, Velocity, Health, Burning}, copies every one of the entity's components into a new row there, removes the old row by moving the last row into its slot, and updates the records of both entities involved. The work grows with the number and size of the entity's components. A second effect is **fragmentation**: with three independently toggled status tags, the same swarm can spread over up to 2 × 2 × 2 = 8 tables, and the more small tables a query matches, the shorter each linear run. ## Sparse-set storage **Sparse-set** storage keeps each component type in its own pool, independent of the others. A pool holds: - a **dense** array of component values and a parallel dense array of the entities that own them; - a **sparse** array indexed by entity index, giving each entity's slot in the dense arrays or an invalid marker, often allocated in pages so a large index range does not cost one large allocation. Adding and removing are constant time and touch only that one pool: 1. To add, write the value at the end of the dense arrays and store that slot in the sparse array. 2. To remove, move the last dense element into the removed slot, update the sparse entry of the entity that moved, mark the removed entity invalid and shrink by one. 3. To test membership, read the sparse entry and confirm the dense entity at that slot matches. The weakness is the **join**. A query over Position, Velocity and Health iterates the smallest of the three pools and, for each entity, looks up its slot in the other two through their sparse arrays. Each pool is in its own order, so those lookups jump around memory. Some sparse-set designs offer **groups**, which keep the entities that own every component of a group packed at the front of each pool in the same order, restoring in-step iteration at the price of extra swaps on every add and remove. ## The costs side by side | | Archetype tables | Sparse sets | |---|---|---| | Iterate a multi-component query | Dense, linear, in step | Smallest pool drives, others looked up | | Add or remove one component | Copy the whole entity to another table | Constant time, one pool touched | | Many optional tags | Multiplies tables, fragments iteration | No effect on other pools | | Single-component iteration | Dense within each table | Dense | | Extra memory | Entity records, cached query matches | A sparse array per component type | ## Applying it to the swarm and the burning status 1. **The hot, stable data**, position and velocity read every frame for every unit, belongs in dense, in-step storage, which archetype tables give without extra work. 2. **A status toggled every few frames** on a changing subset of units would cost an archetype ECS a full entity copy per toggle and double the swarm's table count. In sparse-set storage it is a constant-time insert or removal in one pool, and a system that only cares about burning units iterates that small pool. 3. If most units are burning most of the time and every system visits them anyway, a **flag** inside an existing component avoids structural changes altogether. So for this access pattern the answer is sparse-set storage for the toggled status and archetype storage for the movement data. ## Hybrids and refinements - Several ECS designs let each component type **choose its storage**: table storage for hot data, sparse storage for tags that come and go. - **Enabled bits** per component, where a design offers them, switch a component off without a structural change; iteration then skips disabled rows. - Structural changes in either scheme are usually **deferred** to a sync point, so neither has to cope with storage moving under a running loop. - Measure before deciding: the right storage is a property of each component's access pattern, not of the ECS as a whole.

  • How does an archetype ECS keep a query's list of matching tables current?
    The query caches the archetypes whose component set contains its required types and none of its excluded ones. When a new archetype is created, the engine tests it against registered queries and appends it to those that match, so iteration never searches every archetype. Many designs also cache transition edges, this archetype plus Burning leads to that one, so repeated adds skip the set lookup.
  • How can a sparse-set ECS make a multi-component query iterate densely?
    By grouping: it keeps the entities that own every component in a chosen group packed at the front of each of those pools, in the same order. Iterating the group then walks all the arrays in step. The price is that adding or removing a grouped component must swap entities into or out of that packed prefix in every pool of the group, and each pool can sit in only a limited number of groups.
  • What does declaring which components a system reads and which it writes give the storage layer?
    It lets the engine order systems that touch the same columns, flag two writers to one component, and bump a change version only on columns a system may write, so a later system can skip tables or blocks nothing changed. Running non-conflicting systems at the same time builds on these declarations, but that scheduling is the job system's subject.

  • Adding a component in an archetype ECS is as cheap as writing one field.
  • Sparse sets iterate multi-component queries as densely as archetype tables.
  • More status tags cost nothing in an archetype ECS.
  • Sparse sets need no memory beyond the components themselves.
  • One storage scheme is best for every component in a game.