Skip to content

03 · Sparse Array

What it is

The sparse array answers one question very fast: "where is entity N's data in this pool?" It maps an entity's index to a position in the pool's packed (dense) arrays. It is "sparse" because most of its slots are empty: a component like Boss exists on one entity out of thousands.

Each pool owns one sparse array.

Why we need it

  • Fast lookups: world.getComponents().get<Health>(e), contains, and the joins inside queries all start with a sparse-array lookup.
  • R2 / R4: Luau games can declare many component types. A naive sparse array per type would cost memory proportional to the highest entity index for every type. Paging keeps that cost tied to where entities actually are.

How others do it

ECS Entity → data lookup
EnTT Paged sparse arrays inside each sparse_set (the model we follow)
Bevy (sparse-set components) Sparse array per component
Bevy / flecs / Unity (tables) One entity record → (table, row); no per-component sparse array
Tutorials One flat array per component, sized to the maximum entity count
Specs Hierarchical bitsets, plus storage-specific maps

Our choice

A paged sparse array: the index space is cut into pages of 4096 entries, and a page is allocated only when an entity in its range gets the component. Each entry is a 32-bit dense index, or a "none" value.

How it works

Entity indices 0 – 4095 4096 – 8191 8192 – 12287 …
Page page 0 not allocated page 2 …
Content 4096 entries: dense position or empty nothing 4096 entries …

Lookup of entity index i:

flowchart LR
    start["entity index i"] --> split["page = i >> 12 (i / 4096)<br/>offset = i & 4095 (i % 4096)"]
    split --> allocated{"page allocated?"}
    allocated -- "no" --> absent["absent"]
    allocated -- "yes" --> entry["entry = pages[page][offset]"]
    entry --> empty{"entry empty?"}
    empty -- "yes" --> absent
    empty -- "no" --> found["dense position = entry"]

Two arrays dereferenced, no hashing, no branching on hash collisions: a few nanoseconds.

Why the generation is not stored here

The sparse array stores only the dense index. To reject a stale entity (same index, older generation), the pool compares the full entity stored in its dense array:

bool contains(Entity e) {
    const std::optional<std::uint32_t> position = _sparse.get(e.getIndex());
    return position.has_value() && _dense[*position] == e;  // == compares the generation too
}

This keeps entries at 4 bytes and makes the dense array the single source of truth.

Memory

Situation Flat array per component Paged (4096-entry pages, 4 bytes each)
200 component types, max entity index 50,000 200 × 50,000 × 4 B ≈ 40 MB Only pages that contain entities: often a few pages per type, ~16 KB each
A component present on 1 entity 50,000 entries 1 page (16 KB)

Pages are never freed while the pool lives, which avoids allocation churn when entities come and go.

Page size

4096 entries × 4 bytes = 16 KB per page. Smaller pages waste less memory for very rare components but add more page-table entries; 4096 is the common choice (EnTT uses the same order of magnitude). It is a compile-time constant, easy to tune with benchmarks.

Connections

  • Uses: Entity (the index).
  • Used by: Pool, which owns one sparse array and keeps it in sync with its dense arrays.

Pitfalls

  • Forgetting to update on swap-and-pop. When the pool moves its last element into a hole, the moved entity's sparse entry must be rewritten. See Pool.
  • Trusting the entry without the generation check. An entry only says "this index has data"; the dense entity comparison says whether it is this entity.
  • Huge entity indices. The page table itself grows with the highest index. With LIFO reuse in the allocator, indices stay compact.

Open questions

  • Page size: keep 4096 or tune per component (rare vs common) after benchmarks? (ECS)