Skip to content

Slotmap Implementation

Jump to bottom
Dunkansdk edited this page Dec 8, 2025 · 1 revision

Slotmap Implementation

Table of Contents

What is a Slotmap?

A slotmap is a specialized data structure that combines the benefits of:

  • Packed Arrays - Dense, cache-friendly component storage
  • Stable Handles - Indices that remain valid across insertions/deletions
  • Generational Indices - Detection of use-after-free bugs

Problem It Solves

Traditional approaches have tradeoffs:

Container Stable References Cache-Friendly O(1) Random Access
std::vector ❌ (reallocation) ✅ ✅
std::unordered_map ✅ ❌ ✅ (average)
std::list ✅ ❌ ❌
Slotmap ✅ (via keys) ✅ ✅

Slotmap provides stable handles (keys) while keeping data packed and cache-friendly.

Real-World Use Case

In an ECS, entities need to reference components:

  • Components stored in packed arrays for iteration performance
  • Entities hold keys instead of pointers (safe against reallocation)
  • Keys include generation numbers to detect stale references

Architecture

graph TB
    subgraph "Slotmap Template Parameters"
        TP["Slotmap#60;DATA_TYPE, CAPACITY, INDEX_TYPE#62;"]
    end
    
    subgraph "Three Arrays #40;all size CAPACITY#41;"
        direction LR
        Index["m_index: array#60;key_type, CAPACITY#62;<br/>#40;Sparse: Maps slot IDs to data indices#41;"]
        Data["m_data: array#60;DATA_TYPE, CAPACITY#62;<br/>#40;Dense: Packed component data#41;"]
        Erase["m_erase: array#60;index_type, CAPACITY#62;<br/>#40;Reverse: Maps data indices to slot IDs#41;"]
    end
    
    subgraph "Metadata"
        Size["m_size: Current element count"]
        Freelist["m_freelist: Next available slot"]
        Gen["m_generation: Global generation counter"]
    end
    
    subgraph "Key Structure"
        Key["key_type {<br/>  index_type id;<br/>  gen_type generation;<br/>}"]
    end
    
    TP --> Index
    TP --> Data
    TP --> Erase
    TP --> Size
    TP --> Freelist
    TP --> Gen
    
    Index -.contains.-> Key
    
    style Index fill:#FFF3E0
    style Data fill:#E8F5E9
    style Erase fill:#E3F2FD
    style Key fill:#FCE4EC
Loading

Key Components

  1. m_index (Sparse Array)

    • Maps slot IDs → data indices + generation
    • Contains key_type structs: {id: data_index, generation: gen}
    • Slots can be occupied or in the freelist

  2. m_data (Dense Array)

    • Stores actual component data
    • Always packed: elements [0, m_size) are valid
    • Iteration-friendly (no gaps)

  3. m_erase (Reverse Mapping)

    • Maps data indices → slot IDs
    • Enables updating m_index during swap-and-pop deletion
    • Maintains bidirectional relationship

Generational Indices

Generational indices prevent accessing deleted elements by versioning each slot.

sequenceDiagram
    participant User
    participant Slotmap
    
    Note over Slotmap: Initial State<br/>generation = 0
    
    User->>Slotmap: push_back(data1)
    Slotmap-->>User: key {id: 0, gen: 0}
    Note over Slotmap: Slot 0 allocated<br/>generation = 1
    
    User->>Slotmap: erase(key {id: 0, gen: 0})
    Note over Slotmap: Slot 0 freed<br/>generation = 2<br/>Slot gen updated to 2
    
    User->>Slotmap: push_back(data2)
    Slotmap-->>User: key {id: 0, gen: 2}
    Note over Slotmap: Same slot, new generation<br/>generation = 3
    
    User->>Slotmap: operator[](key {id: 0, gen: 0})
    Slotmap-->>User: INVALID! (gen mismatch)
    
    User->>Slotmap: operator[](key {id: 0, gen: 2})
    Slotmap-->>User: data2 (valid)
Loading

Generation Timeline Example

Event Slot 0 State Global Gen User's Key
Initialize Free (gen=0) 0 -
Insert A Occupied (gen=0) 1 {id:0, gen:0}
Delete A Free (gen=1) 2 {id:0, gen:0} ❌
Insert B Occupied (gen:1) 3 {id:0, gen:1}
Access with old key - - {id:0, gen:0} → INVALID

This prevents use-after-free bugs at runtime.

Memory Layout

Visual representation of slotmap state:

graph TD
    subgraph "State: 3 elements inserted, 1 deleted"
        direction TB
        
        subgraph "m_index #91;CAPACITY=8#93; #40;Slot ID → Data Location#41;"
            I0["#91;0#93; {id:2, gen:3} #40;points to data#91;2#93;#41;"]
            I1["#91;1#93; {id:5, gen:1} #40;freelist next#41;"]
            I2["#91;2#93; {id:1, gen:2} #40;points to data#91;1#93;#41;"]
            I3["#91;3#93; {id:0, gen:1} #40;points to data#91;0#93;#41;"]
            I4["#91;4#93; {id:5, gen:0}"]
            I5["#91;5#93; {id:6, gen:0}"]
            I6["#91;6#93; {id:7, gen:0}"]
            I7["#91;7#93; {id:8, gen:0}"]
        end
        
        subgraph "m_data #91;CAPACITY=8#93; #40;Packed Component Data#41;"
            D0["#91;0#93; ComponentC"]
            D1["#91;1#93; ComponentA"]
            D2["#91;2#93; ComponentB"]
            D3["#91;3#93; #40;unused#41;"]
            D4["#91;4#93; #40;unused#41;"]
            D5["#91;5#93; #40;unused#41;"]
            D6["#91;6#93; #40;unused#41;"]
            D7["#91;7#93; #40;unused#41;"]
        end
        
        subgraph "m_erase #91;CAPACITY=8#93; #40;Data Index → Slot ID#41;"
            E0["#91;0#93; 3"]
            E1["#91;1#93; 2"]
            E2["#91;2#93; 0"]
            E3["#91;3#93; #40;unused#41;"]
            E4["#91;4#93; #40;unused#41;"]
            E5["#91;5#93; #40;unused#41;"]
            E6["#91;6#93; #40;unused#41;"]
            E7["#91;7#93; #40;unused#41;"]
        end
        
        Meta["m_size = 3<br/>m_freelist = 1<br/>m_generation = 4"]
    end
    
    I0 -.-> D2
    I2 -.-> D1
    I3 -.-> D0
    D0 -.-> E0
    D1 -.-> E1
    D2 -.-> E2
    E0 -.-> I3
    E1 -.-> I2
    E2 -.-> I0
    
    I1 -.freelist.-> I4
    
    style D0 fill:#C8E6C9
    style D1 fill:#C8E6C9
    style D2 fill:#C8E6C9
    style D3 fill:#EEEEEE
    style I1 fill:#FFCCBC
    style I4 fill:#FFCCBC
Loading

Key Insights:

  • m_data is densely packed: only indices [0, 3) are used
  • m_index has gaps: slot 1 is in the freelist
  • Freelist: Slot 1 → Slot 5 → Slot 6 → ... (linked via m_index[slot].id)

Operations

push_back - Insertion

Adds a new element and returns a generational key.

flowchart TD
    Start([push_back called]) --> CheckCapacity{m_size < CAPACITY?}
    CheckCapacity -->|No| Error[Throw runtime_error]
    CheckCapacity -->|Yes| AllocateSlot[slotid = m_freelist]
    
    AllocateSlot --> UpdateFreelist[m_freelist = m_index#91;slotid#93;.id]
    UpdateFreelist --> InitSlot["m_index#91;slotid#93; = {<br/>  id: m_size,<br/>  gen: m_generation<br/>}"]
    
    InitSlot --> StoreData["m_data#91;m_size#93; = std::move#40;value#41;"]
    StoreData --> StoreReverse["m_erase#91;m_size#93; = slotid"]
    
    StoreReverse --> IncrementSize[++m_size]
    IncrementSize --> IncrementGen[++m_generation]
    
    IncrementGen --> ReturnKey["Return key {<br/>  id: slotid,<br/>  gen: m_generation-1<br/>}"]
    
    ReturnKey --> End([End])
    Error --> End
    
    style CheckCapacity fill:#FFF9C4
    style StoreData fill:#C8E6C9
    style ReturnKey fill:#B2DFDB
Loading

Step-by-Step Example:

Initial state: m_size=2, m_freelist=3, m_generation=5

auto key = slotmap.push_back(MyComponent{x, y, z});
Step Operation State After
1 Reserve slot slotid = 3
2 Update freelist m_freelist = m_index[3].id (was 4)
3 Initialize slot m_index[3] = {id:2, gen:5}
4 Store data m_data[2] = MyComponent{x,y,z}
5 Store reverse m_erase[2] = 3
6 Increment size m_size = 3
7 Increment gen m_generation = 6
8 Return key key = {id:3, gen:5}

operator[] - Lookup

Accesses an element by key (with validation).

[[nodiscard]] constexpr DATA_TYPE& operator[](key_type const& key) {
    assert(is_valid(key));
    auto index = m_index[key.id];  // Get data index from slot
    return m_data[index.id];       // Access packed data
}

Validation:

constexpr bool is_valid(key_type key) const noexcept {
    if (key.id >= CAPACITY) return false;                       // Out of bounds
    if (m_index[key.id].generation != key.generation) return false;  // Stale key
    return true;
}

Time Complexity: O(1)

  • Two array lookups
  • One comparison
  • No pointer chasing

erase - Deletion (Swap-and-Pop)

Removes an element while keeping data packed.

flowchart TD
    Start([erase called with key]) --> Validate{is_valid#40;key#41;?}
    Validate -->|No| ReturnFalse[Return false]
    Validate -->|Yes| GetSlot[slot = m_index#91;key.id#93;]
    
    GetSlot --> SaveDataId[data_id = slot.id]
    SaveDataId --> UpdateSlot["m_index#91;key.id#93; = {<br/>  id: m_freelist,<br/>  gen: m_generation<br/>}"]
    
    UpdateSlot --> UpdateFreelist[m_freelist = key.id]
    UpdateFreelist --> CheckLast{data_id == m_size-1?}
    
    CheckLast -->|Yes| SkipSwap[Skip swap #40;already last#41;]
    CheckLast -->|No| SwapData["m_data#91;data_id#93; = m_data#91;m_size-1#93;"]
    
    SwapData --> SwapReverse["m_erase#91;data_id#93; = m_erase#91;m_size-1#93;"]
    SwapReverse --> UpdateIndex["m_index#91;m_erase#91;data_id#93;#93;.id = data_id"]
    
    UpdateIndex --> DecrementSize
    SkipSwap --> DecrementSize[--m_size]
    DecrementSize --> IncrementGen[++m_generation]
    
    IncrementGen --> ReturnTrue[Return true]
    ReturnTrue --> End([End])
    ReturnFalse --> End
    
    style Validate fill:#FFF9C4
    style SwapData fill:#FFCCBC
    style UpdateIndex fill:#B2EBF2
Loading

Swap-and-Pop Visualization:

Before erasing element at data_id=1:

m_data:   [A] [B] [C] [D]  (size=4)
m_erase:  [0] [1] [2] [3]
          slot slot slot slot
          IDs:  0   1   2   3

After erasing (swap with last, then pop):

m_data:   [A] [D] [C] [?]  (size=3)
m_erase:  [0] [3] [2] [?]
          slot slot slot
          IDs:  0   3   2

m_index[3].id updated: 3 → 1  (D is now at index 1)

Why Swap-and-Pop?

  • Keeps m_data densely packed (no holes)
  • Maintains O(1) deletion
  • Preserves iteration performance

Freelist Management

The freelist is a linked list embedded in m_index:

graph LR
    FreePtrGreen["m_freelist = 2"] --> S2["Slot 2<br/>{id: 5, gen: X}"]
    S2 --> S5["Slot 5<br/>{id: 7, gen: X}"]
    S5 --> S7["Slot 7<br/>{id: 8, gen: X}"]
    S7 --> S8["Slot 8<br/>#40;out of bounds#41;"]
    
    style FreePtrGreen fill:#A5D6A7
    style S2 fill:#FFCCBC
    style S5 fill:#FFCCBC
    style S7 fill:#FFCCBC
    style S8 fill:#EEEEEE
Loading

Initialization (freelist_init):

for (index_type i = 0; i < CAPACITY; ++i) {
    m_index[i].id = i + 1;  // Each slot points to next
}
m_freelist = 0;  // Start at slot 0

Result: 0 → 1 → 2 → 3 → ... → CAPACITY-1 → CAPACITY (invalid)

Performance Analysis

Time Complexity

Operation Average Worst Case Notes
push_back O(1) O(1) Just array writes
operator[] O(1) O(1) Two array reads
erase O(1) O(1) Swap + pop
is_valid O(1) O(1) Two comparisons
Iteration O(n) O(n) Over packed array

Space Complexity

For Slotmap<T, CAPACITY>:

Memory = sizeof(key_type) * CAPACITY     // m_index
       + sizeof(T) * CAPACITY            // m_data
       + sizeof(index_type) * CAPACITY   // m_erase
       + sizeof(index_type) * 3          // m_size, m_freelist, m_generation

Example: Slotmap<PhysicsComponent, 1024> where PhysicsComponent = 48 bytes:

m_index:  8 bytes * 1024 = 8 KB
m_data:   48 bytes * 1024 = 48 KB
m_erase:  4 bytes * 1024 = 4 KB
metadata: 12 bytes
Total: ~60 KB

Cache Performance

✅ Iteration - Excellent (linear memory access)

for (auto& component : slotmap) {  // Iterates m_data[0..m_size)
    // Sequential access, perfect cache locality
}

⚠️ Random Access - Good (2 cache misses)

auto& component = slotmap[key];
// Cache miss 1: m_index[key.id]
// Cache miss 2: m_data[index.id]

Comparison with Standard Containers

vs. std::vector

Aspect std::vector Slotmap
Stable Handles ❌ Iterators invalidated on reallocation ✅ Keys remain valid
Cache-Friendly ✅ Contiguous ✅ Contiguous (m_data)
Random Access ✅ O(1) direct ✅ O(1) via key
Erase ❌ O(n) if order preserved ✅ O(1) swap-and-pop
Use-After-Free Detection ❌ None ✅ Via generations

vs. std::unordered_map

Aspect std::unordered_map Slotmap
Stable Handles ✅ Keys always valid ✅ Keys + generation
Cache-Friendly ❌ Scattered nodes ✅ Packed array
Random Access ⚠️ O(1) average ✅ O(1) worst-case
Iteration ❌ Poor cache locality ✅ Excellent
Memory Overhead High (buckets + nodes) Moderate (3 arrays)

When to Use Slotmap

✅ Use slotmap when:

  • You need stable handles across insertions/deletions
  • Iteration performance is critical (e.g., ECS systems)
  • You want to detect use-after-free bugs
  • You can tolerate fixed capacity

❌ Don't use slotmap when:

  • You need dynamic capacity (use secondary index with resizing)
  • Deletion order matters (slotmap changes order via swap)
  • Memory is extremely constrained (3x overhead)

Implementation Details

Template Parameters

template <
    typename DATA_TYPE,              // Component type
    std::size_t CAPACITY = 10,      // Maximum elements
    typename INDEX_TYPE = std::uint32_t  // Index/generation type
>
struct Slotmap;

Choosing INDEX_TYPE:

  • uint32_t (default): Up to 4 billion elements, 32-bit generations
  • uint16_t: Memory-constrained systems, max 65K elements
  • uint64_t: Extremely long-lived systems (avoid generation wrap-around)

key_type Structure

struct key_type {
    index_type id;          // Slot ID in m_index
    gen_type generation;    // Generation number for validation
};

Keys are:

  • Copyable - Cheap to pass around (8 bytes for uint32_t)
  • Comparable - Can check key1 == key2
  • Hashable - Can use as map keys if needed

Constexpr Support

Most operations are constexpr, enabling compile-time slotmap construction:

constexpr Slotmap<int, 10> compile_time_map;

This is useful for compile-time validation and zero-cost initialization.

Thread Safety

⚠️ Not Thread-Safe by default. Concurrent access requires external synchronization:

std::mutex slotmap_mutex;

// Thread 1
{
    std::lock_guard lock(slotmap_mutex);
    slotmap.push_back(component);
}

// Thread 2
{
    std::lock_guard lock(slotmap_mutex);
    auto& comp = slotmap[key];
}

Code Example: Full Lifecycle

#include "ecs/utils/slotmap.hpp"

struct Position {
    float x, y, z;
};

ADE::Slotmap<Position, 100> positions;

// Insert
auto key1 = positions.push_back(Position{1.0f, 2.0f, 3.0f});
auto key2 = positions.push_back(Position{4.0f, 5.0f, 6.0f});

// Access
positions[key1].x = 10.0f;

// Validate
if (positions.is_valid(key1)) {
    std::cout << "Key is valid\n";
}

// Delete
positions.erase(key1);

// Stale access (caught!)
if (!positions.is_valid(key1)) {
    std::cout << "Key is now invalid\n";  // This prints
}

// Iterate (only key2 remains)
for (auto& pos : positions) {
    std::cout << pos.x << ", " << pos.y << ", " << pos.z << "\n";
}
// Output: 4, 5, 6

Related Documentation

Next: Explore Template Metaprogramming to understand the compile-time magic powering the ECS.

Clone this wiki locally