Stable Addressing and Tombstones

In the previous lesson, we implemented $O(1)$ deletions in using the swap-and-pop idiom.

By swapping the victim with the last element in the array and popping the back, we avoided the $O(n)$ memory shifting associated with std::vector::erase().

However, deleting objects is dangerous. Any external system - a scoreboard, an AI controller, or a physics engine - that held a reference to the deleted object is now out of date. Additionally, any system that held a reference to an object that was moved as a side effect of the deletion is also out of date.

This is the index invalidation problem. In dynamic systems where entities are created and destroyed frequently, raw indices (and raw pointers) are unsafe.

Over the next two lessons, we will solve this. We will trade some of our raw memory density for safety. We will implement tombstones to stabilize our indices in this lesson, and then upgrade them to generational indices to solve the "ABA Problem" in the next lesson.

We will be continue working on the PlayerStorage we constructed in the previous lesson.

To recap, this system uses multiple std::vector columns to store data. It exposes a PlayerRef proxy object for convenience. It currently uses swap-and-pop for deletion.

If you're following along from previous lessons, you can continue to use your container. A simplified version is provided below:

1#pragma once
2#include <vector>
3#include <string>
4#include <ranges>
5#include <tuple>
6#include <array>
7
8struct PlayerRef {
9  int& id;
10  int& score;
11  float& health;
12  std::string& name;
13};
14
15class PlayerStorage {
16public:
17  // Structure of Arrays storage
18  std::vector<int> m_ids;
19  std::vector<int> m_scores;
20  std::vector<float> m_health;
21  std::vector<std::string> m_names;
22
23  void AddPlayer(
24    int id, int score, float hp, std::string name
25  ) {
26    m_ids.push_back(id);
27    m_scores.push_back(score);
28    m_health.push_back(hp);
29    m_names.push_back(std::move(name));
30  }
31
32  // THE PROBLEM: This changes indices!
33  void EraseAt(size_t index) {
34    if (index >= m_ids.size()) return;
35
36    // Swap-and-Pop
37    m_ids[index] = m_ids.back();
38    m_ids.pop_back();
39    m_scores[index] = m_scores.back();
40    m_scores.pop_back();
41    m_health[index] = m_health.back();
42    m_health.pop_back();
43    m_names[index] = std::move(m_names.back());
44    m_names.pop_back();
45  }
46
47  auto GetView() {
48    return std::views::zip(
49      m_ids, m_scores, m_health, m_names
50    ) | std::views::transform([](auto&& tuple) {
51          auto& [id, score, hp, name] = tuple;
52          return PlayerRef{id, score, hp, name};
53        });
54  }
55};

Let's visualize exactly why swap-and-pop is dangerous for long-term references.

Imagine we have a Scoreboard class that wants to track the "MVP". It stores the index of the player:

1class Scoreboard {
2  int mvp_index = -1;
3public:
4  void SetMVP(int index) { mvp_index = index; }
5  void PrintMVP(PlayerStorage& ps) {
6    // Dangerous access!
7    std::cout << ps.m_names[mvp_index];
8  }
9};

This is problematic because we have no idea if the underlying data that mvp_index represents has changed. For example:

1. We add Alice at index 0.
2. We add Bob at index 1.
3. We set the Scoreboard MVP to index 0 (Alice).
4. We call EraseAt(0) to remove Alice. This swaps "Bob" (from index 1) into index 0.
5. The Scoreboard now thinks Bob is the MVP.

If we want to support external references, we have two choices to solve this problem.

Proactive Solutions

Every time we move memory, we could notify every system that might be storing a reference to it that their reference is now stale. This is quite complex to set up, and it's very easy to mess up. If someone adds code that stores an index, but neglects to also listen to the notifications, we have a bug.

Reactive Solutions

Instead, when some external system requests access to something in our collection, we could have a mechanism to detect if their request is "stale", and react appropriately.

We will will implement a reactive, stable-addressing system here, which is more resilient. We'll use the two most common strategies - tombstones and generational indicies.

The simplest way to achieve stable addressing is to simply stop moving data.

When a deletion request is received, we don't physically delete the object or swap it. Instead, we just add a special marker (a "tombstone") in its place to designate the item as logically dead.

This means the entities in our collection will no longer move around when elements are deleted, but our collection will also contain holes:

Implementing Tombstones

We will add a new column to keep track of whether each player is alive: m_alive.

However, there is some unexpected complexity with using arrays of booleans, particularly in an SoA layout. We'll cover this in the next chapter but, for now, let's just use a small numeric type like uint8_t. A value of 0 will represent false (dead) whilst 1 will represent true (alive):

1// ...
2
3class PlayerStorage {
4public:
5  // New column for liveness tracking
6  // 1 = Alive, 0 = Dead/Tombstone
7  std::vector<uint8_t> m_alive;
8
9  // ...
10
11  void AddPlayer(
12    int id, int score, float hp, std::string name
13  ) {
14    m_ids.push_back(id);
15    m_scores.push_back(score);
16    m_health.push_back(hp);
17    m_names.push_back(std::move(name));
18
19    // Mark as alive
20    m_alive.push_back(1);
21  }
22
23  void EraseAt(size_t index) {
24    if (index >= size()) return;
25
26    // Tombstoning: Just mark it as dead
27    m_alive[index] = 0;
28  }
29};

By removing the swap-and-pop logic, the player at index 0 remains there forever. Even if Alice is "deleted," the slot at index 0 is simply marked dead. Bob stays at index 1. The indices are stable.

Iterating over Tombstones

Stability comes at a cost. Our GetView() function, which we use to iterate over the players, currently iterates over everything. If we use it now, we will include players that we promised we erased.

We need to update GetView() to filter out the tombstones. Our view-based pipeline makes this easy - we just insert a std::views::filter() step to filter out the "dead" players:

1// ...
2
3class PlayerStorage {
4public:  
5  // ...
6  auto GetView() {
7    return std::views::zip(
8      m_ids, m_scores, m_health, m_names, m_alive
9    )
10    // Filter out the tombstones
11    | std::views::filter([](const auto& tuple) {
12        // The last element of the tuple is 'm_alive'
13        // tuple structure is based on zip arguments order
14        // Indexing starts at 0, so the 5th element is at index 4
15        const auto& is_alive = std::get<4>(tuple);
16        return is_alive == 1;
17      })
18    // Transform into Proxy
19    | std::views::transform([](auto&& tuple) {
20        auto& [id, score, hp, name, alive] = tuple;
21        return PlayerRef{id, score, hp, name};
22      });
23  }
24  // ...
25};

Now that we have stable indices, we can expose an API for random access. However, because a slot might contain a tombstone, we cannot just return PlayerRef. The index that is being requested might map to a tombstone, which we're claiming has been erased.

We can handle this in a few ways, with the typical options being either exceptions, or the use of a result type - a simple container than holds either a value or an error.

The standard library's implementation of a result type is std::expected, added in C++23. It's a template where the first argument is what we'll return in the "expected" case (where the function call was successful) and the second is what we'll return in the unexpected case (where the function call was unsuccessful).

Below, we add a GetPlayer() method that returns the PlayerRef if the requested index is valid, or a std::string explaining the error if it wasn't:

1// ...
2#include <expected> // For std::expected (C++23)
3
4class PlayerStorage {
5public:
6  // ...
7  std::expected<PlayerRef, std::string> GetPlayer(size_t i) {
8    if (i >= m_ids.size()) {
9      return std::unexpected("Index out of bounds");
10    }
11
12    if (m_alive[i] == 0) {
13      return std::unexpected("Player is dead (Tombstone)");
14    }
15
16    return PlayerRef{
17      m_ids[i],
18      m_scores[i],
19      m_health[i],
20      m_names[i]
21    };
22  }
23};

The Cost of Tombstones

This is clean, simple, and keeps our addresses stable, but there is an overhead associated with the filtering. We introduce techniques to make filtering much faster later in the chapter, but clogging our system up with these tombstones will always carry a cost.

Additionally, if our system is regularly adding new entities, but not physically deleting the old ones, we have a very obvious memory leak. In real world applications, this could be solved by having a coordinated "clean up" event where our tombstones get cleared out, and associated systems can be notified that their indices or pointers are no longer valid.

This might happen every few seconds in a dynamic system, or as an end-of-day process in a slower system where memory grows more slowly. Some contexts also naturally provide opportune moments to perform clean up. For example, a player completing a level in a video game and then loading the next is the perfect opportunity to do cleanup tasks.

However, if these tombstones are a problem, and we don't have an an obvious way to get rid of them, we need to reuse the slots. An immediate problem arises if we try to do this - how do we even know where the free slots are?

The simplest way to find an empty slot is to just scan for it. When AddPlayer() is called, we could loop through the m_alive vector from the beginning, looking for the first 0:

1size_t find_free_slot() {
2  for (size_t i = 0; i < m_alive.size(); ++i) {
3    if (m_alive[i] == 0) {
4      return i; // Found one!
5    }
6  }
7  return m_alive.size(); // None found, append
8}

This works, but it means that adding a player, which should be a fast operation, now becomes an $O(n)$ problem. As our container grows, adding new players gets slower and slower. Is there an $O(1)$ way to find a free slot?

The efficient solution is to maintain a list of all the indices that are currently "dead." This is called a free list, where each element in the collection is the index of a free slot within our system.

When we delete a player, we push their index onto the list, where it becomes the new head. When we need a new slot, we pop an index from the free list and use it.

There's no need for the free list be contiguous. We're only ever interested in the "next" free slot, so we just interact with the head of the list. We could just add a linked list such as a std::forward_list to our system to keep track of this, but we can be a little more efficient.

Before we allocate more space to our system, we should ask if it's really needed.

• If our collection is full, meaning there no tombstones, we don't need the space. Our free list would be empty.
• If our collection contains tombstones, we already have enough space for our list. We can just place the nodes of our list in the gaps left by the "dead" entities.

Instead of creating a new linked list, we can just chose one of the columns - let's say m_ids - and create an implicit linked list within those gaps. We then just need to add a single integer to our container to store which index is the next free slot, or -1 if there are no further slots:

We can choose any of our arrays (except m_alive) for this embedded list. We selected m_ids here just we need to store a linked list of integers, and m_ids is a std::vector<int> which makes things easier. We'll discuss alternatives later in the section.

Implementing the Implicit Free List

First, we need a member variable in PlayerStorage to act as the "head" of our linked list. We'll initialize it to some sentinel value that indicates that the list is empty.

We can't use 0 for this, because 0 is a valid index representing the first player in our system. If we're using int as our index type, a typical "sentinel" value we can use instead is -1. We cover unsigned index types such as size_t later in the section.

1// ...
2
3// ...
4
5class PlayerStorage {
6public:
7  // Head of the implicit linked list of free slots
8  int m_next_free_slot = -1;
9  
10  // ...
11};

Next, we update EraseAt(). When a player is deleted, their index becomes the new head of the free list. We repurpose their m_ids slot to point to the old head.

1// ...
2
3class PlayerStorage {
4public:
5  // ...
6  void EraseAt(size_t index) {
7    if (index >= size() || m_alive[index] == 0) return;
8
9    m_alive[index] = 0; // Mark as dead
10
11    // Repurpose the ID slot to be a link in the
12    // free list chain
13    m_ids[index] = m_next_free_slot;
14
15    // This index is now the newest free slot
16    m_next_free_slot = index;
17  }
18};

Finally, we update AddPlayer(). It now checks the free list first. If the free list is not empty, it pops an index off the list and reuses that slot. If the list is empty, it expands the collection using push_back().

1// ...
2
3class PlayerStorage {
4public:
5  // ...
6  void AddPlayer(int id, int score, float hp, std::string name) {
7    if (m_next_free_slot != -1) {
8      // A free slot is available
9      // 1. Read it from the free list
10      int index_to_use = m_next_free_slot;
11
12      // 2. "Pop" it off the the free list by updating
13      // the head to the next link in the chain
14      m_next_free_slot = m_ids[index_to_use];
15
16      // 3. Overwrite the slot with new data
17      m_ids[index_to_use] = id;
18      m_scores[index_to_use] = score;
19      m_health[index_to_use] = hp;
20      m_names[index_to_use] = std::move(name);
21      
22      // 4. The slot is no longer a tombstone
23      m_alive[index_to_use] = 1;
24    } else {
25      // No free slots available, so we create create
26      // a new slot at the end
27      m_ids.push_back(id);
28      m_scores.push_back(score);
29      m_health.push_back(hp);
30      m_names.push_back(std::move(name));
31      m_alive.push_back(1);
32    }
33  }
34};

With these changes, AddPlayer() is now an efficient $O(1)$ operation again.

I have more than 2 billion items

In the previous example, we used int for our indices and -1 as our sentinel to indicate the "end of the list." This works perfectly fine for most applications, as the maximum value of an int is around 2 billion.

But what if we're managing more entities than this, and we need larger indices? We usually prefer size_t for this, which is guaranteed to address the full range of an array. This type is slightly larger (usually 8 bytes, whilst int is usually 4) and the memory footprint of our indicies will become important later.

Additionally, this type is unsigned, meaning we cannot use -1 as our sentinel. Instead, we can use the maximum possible value of the type. The standard library provides std::numeric_limits for this:

1// ...
2#include <limits> // for std::numeric_limits
3
4// ...
5class PlayerStorage {
6  // The sentinel is the largest possible number
7  size_t SENTINEL = std::numeric_limits<IndexType>::max();
8
9  IndexType m_next_free_slot = SENTINEL;
10
11  // ...
12
13  void AddPlayer(...) {
14    if (m_next_free_slot != SENTINEL) {
15       // ... 
16    }
17  }
18};

I don't have an integer column

Our indicies need to be integers, but what if we're unlucky and don't have an integer column?

Remember, this implicit linked list technique is just a small optimization at the expense of complexity. Performance is not the only thing that matters, and the complexity cost ramps up when don't have a column that can naturally store our indices. It's totally reasonable to just add a dedicated list such as a std::forward_list to our system to keep things simple.

However, if we wanted to force the issue, then as long as a column has enough bits to store what we need, we can put our data there even if there is a type mismatch:

1#include <vector>
2#include <bit>
3#include <cstdint>
4
5// A 4-byte struct
6struct Color {
7  uint8_t r, g, b, a;
8};
9
10struct ParticleStorage {
11  // Don't abuse floating point numbers for
12  // this technique. This creates additional
13  // risks (NaN patterns, denormal values) 
14  std::vector<float> m_x; 
15  std::vector<double> m_y; 
16  
17  // The column we will abuse for the free list
18  // Assuming sizeof(int) == sizeof(Color)
19  std::vector<Color> m_color;
20  
21  // 1 = Alive, 0 = Dead
22  std::vector<uint8_t> m_alive;
23  
24  int m_next_free = -1;
25};

We can do this using std::memcpy() or ideally, if our types have the same size, C++20 added std::bit_cast. This lets us interprets the raw bits into any type we want. Below, we use our 4 byte Color column as an int when maintaining our free list:

1void EraseAt(ParticleStorage& ps, int index) {
2  // Sanity checks
3  if (index >= ps.m_alive.size()) return;
4  if (ps.m_alive[index] == 0) return;
5  
6  // Mark as dead
7  ps.m_alive[index] = 0;
8
9  // Cast the current head (int) to Color
10  Color next_node = std::bit_cast<Color>(
11    ps.m_next_free
12  );
13
14  // Store in the Color column
15  ps.m_color[index] = next_node;
16
17  // Update the head to point to this new hole
18  ps.m_next_free = index;
19}
20
21void AddParticle(ParticleStorage& ps) {
22  if (ps.m_next_free != -1) {
23    // A free slot is available
24    int index_to_use = ps.m_next_free;
25
26    // Retrieve the hidden 'next' pointer from
27    // the Color column
28    Color stored_val = ps.m_color[index_to_use];
29    int next_node_index = std::bit_cast<int>(stored_val);
30
31    // Update the system head
32    ps.m_next_free = next_node_index;
33
34    // Initialize actual data
35    ps.m_color[index_to_use] = {255, 0, 0, 255}; 
36    ps.m_x[index_to_use] = 0.0f;
37    ps.m_y[index_to_use] = 0.0f;
38    
39    // Mark as Alive
40    ps.m_alive[index_to_use] = 1;
41        
42  } else {
43    // No slots available - create a new slot
44    ps.m_color.push_back({255, 0, 0, 255});
45    ps.m_x.push_back(0.0f);
46    ps.m_y.push_back(0.0f);
47    ps.m_alive.push_back(1);
48  }
49}

Here is a complete version of PlayerStorage.h incorporating the tombstones, the free list, and the implicit linked list logic we implemented in this lesson:

1#pragma once
2#include <vector>
3#include <string>
4#include <ranges>
5#include <tuple>
6#include <array>
7#include <expected>
8#include <limits>
9
10struct PlayerRef {
11  int& id;
12  int& score;
13  float& health;
14  std::string& name;
15};
16
17class PlayerStorage {
18public:
19  // Data columns
20  std::vector<int> m_ids;
21  std::vector<int> m_scores;
22  std::vector<float> m_health;
23  std::vector<std::string> m_names;
24
25  // Lifecycle columns
26  // 1 = Alive, 0 = Dead
27  std::vector<uint8_t> m_alive;
28
29  // Free List Head
30  // We use -1 to indicate "End of List"
31  // or "No free slots"
32  int m_next_free_slot = -1;
33
34  void AddPlayer(
35    int id, int score, float hp, std::string name
36  ) {
37    if (m_next_free_slot != -1) {
38      // REUSE PATH
39      // Grab the index
40      int index = m_next_free_slot;
41
42      // Update head to point to the next free slot
43      // The 'next' index is stored inside m_ids
44      m_next_free_slot = m_ids[index];
45
46      // Overwrite data
47      m_ids[index] = id;
48      m_scores[index] = score;
49      m_health[index] = hp;
50      m_names[index] = std::move(name);
51      
52      // Mark alive
53      m_alive[index] = 1;
54    } else {
55      // APPEND PATH
56      m_ids.push_back(id);
57      m_scores.push_back(score);
58      m_health.push_back(hp);
59      m_names.push_back(std::move(name));
60
61      // Mark alive
62      m_alive.push_back(1);
63    }
64  }
65
66  void EraseAt(size_t index) {
67    // Safety checks
68    if (index >= m_ids.size()) return;
69    if (m_alive[index] == 0) return; // Already dead
70
71    // 1. Mark as dead (Tombstone)
72    m_alive[index] = 0;
73
74    // 2. Add to Free List
75    // Store the old head in this slot
76    m_ids[index] = m_next_free_slot;
77    
78    // Make this slot the new head
79    m_next_free_slot = static_cast<int>(index);
80  }
81
82  // Safe Random Access
83  std::expected<PlayerRef, std::string> GetPlayer(size_t i) {
84    if (i >= m_ids.size()) {
85      return std::unexpected("Index out of bounds");
86    }
87    if (m_alive[i] == 0) {
88      return std::unexpected("Player is dead");
89    }
90
91    return PlayerRef{
92      m_ids[i], m_scores[i], m_health[i], m_names[i]
93    };
94  }
95
96  auto GetView() {
97    return std::views::zip(
98      m_ids, m_scores, m_health, m_names, m_alive
99    )
100    // Filter out tombstones
101    | std::views::filter([](const auto& tuple) {
102        const auto& alive = std::get<4>(tuple);
103        return alive == 1;
104      })
105    // Project into PlayerRef
106    | std::views::transform([](auto&& tuple) {
107        auto& [id, score, hp, name, alive] = tuple;
108        return PlayerRef{id, score, hp, name};
109      });
110  }
111};

In this lesson, we updated our deletion logic to stop moving objects around in memory, thereby implementing stable addressing.

1. Tombstones: We stopped shifting memory. By marking deleted slots as "dead" (m_alive), we ensure that index 5 always refers to the same physical slot in memory.
2. Free Lists: To optimize our memory use and prevent memory leaks (holes that never get filled), we implemented a free list.
3. Implicit Lists: We don't need a separate container for the free list. We can store the linked list nodes inside the empty holes of our existing data columns, saving memory.
4. Result Types: We used std::expected to provide a safe random-access API that rejects requests for "dead" indicies.

With stable addressing, objects remain in the same slot throughout their lifecycle. However, by recycling the slots of dead objects, we have reintroduced a new problem.

Previously, if an external system held a reference to index 5 (Alice), and we deleted Alice, we could reject future requests for that slot because there was a tombstone there - m_alive[5] was 0.

But if we recycle that slot to add a new player, Bob, m_alive[5] becomes 1. The external system still holding "index 5" thinks it is pointing to Alice and, when they ask us for that slot, we no longer can tell if their reference is stale. We give them Bob.

This is the ABA Problem. In the next lesson, we will solve this by upgrading our indices to generational handles.