String Interning

In the previous lesson, we confronted the performance implications of using std::string as a key in our flat data structures. We fought back by implementing hash caching to bypass expensive memory comparisons, and we integrated std::string_view to execute heterogeneous lookups, eliminating hidden heap allocations.

But the physical footprint of our slot is still huge. Because a std::string manages its own internal pointers and capacities, it forces our slot size to balloon past 32 bytes.

As we've learned, the CPU fetches memory from main RAM in chunks known as cache lines - usually 64-bytes. When our slot is 40 bytes after alignment padding, we can only fit a single slot into a cache line. Every single step we take during a linear probe requires the processor to stall and fetch a brand new chunk of memory.

Furthermore, if a complex system stores the string "HealthPotion" in 10,000 different player inventories, we are duplicating that 24-byte string footprint - and its associated heap-allocated character array - 10,000 separate times. This causes massive memory fragmentation and completely thrashes the bandwidth of the system.

In this lesson, we will solve this by embracing a fundamental data-oriented design philosophy: our performance-critical logic shouldn't know what a string is. We will implement string interning, globally deduplicating our strings and transforming them into the raw, 4-byte integer handles that the hardware loves.

We encountered the concept of handles earlier in the course when we built generational indices for our Entity-Component-System. The philosophy here is the same.

A massive string like "assets/textures/characters/player_diffuse_map.png" is incredibly heavy. We do not want to pass this 53-character array around our supposedly high-performance systems.

Instead, we want to intern that string, storing it in memory exactly once in a central, globally accessible vault.

When we deposit the string into the vault, the vault gives us a simple integer receipt - an ID - like 42. From that moment forward, the rest of our system completely forgets about the string. The rendering pipeline asks for texture 42. The asset manager loads asset 42. Our hash sets store the key 42.

Only when we absolutely need the underlying string do we take our 42 receipt, walk back to the vault, and ask to see the original.

A Brief History of Interning

String interning is not a new concept. Early Lisp environments in the 1950s used "atoms" to ensure that any two identical symbols were represented by the same pointer in memory, allowing for instant $O(1)$ equality checks.

Modern managed languages like Java and C# maintain a global string pool by default. If we hardcode "Hello" in ten different files in Java, the virtual machine intercepts them at load time, allocates exactly one string, and points all ten references to that single allocation.

In C++, we only pay for what we use, so the standard does not enforce global interning. We have to build the vault ourselves.

To build our vault, we will design a StringPool class. The pool serves as a two-way translation layer at the boundary of our system. It has two primary responsibilities:

1. Ingestion (Intern): We hand it a string we want to store. If the pool has never seen this text before, it interns it and generates a new integer ID. If the pool has seen it before, it simply returns the existing integer ID.
2. Retrieval (GetString): We hand it an integer ID, and it returns the original text.

Solving this two-way mapping efficiently needs two data structures- an IdToString container that maps handles (integers) to strings, and a StringToId container that maps strings to handles.

Retrieval and IdToString is the easiest part to solve. If our IDs are generated sequentially (0, 1, 2, 3...), we can simply use a std::vector to map the ID to the string.

Looking up an ID becomes an instant $O(1)$ array access:

1#pragma once
2#include <string>
3#include <string_view>
4#include <vector>
5
6class StringPool {
7private:
8  // Maps an integer ID back to the string data
9  std::vector<std::string_view> IdToString;
10
11public:
12  std::string_view GetString(int id) const {
13    return IdToString[id];
14  }
15};

Ingestion is harder. When we call Intern("HealthPotion"), the pool needs to search millions of existing strings to see if "HealthPotion" is already in the vault.

We can't use a linear scan over our std::vector - that'd be an $O(N)$ traversal of slow string comparisons. We also can't keep the container sorted to enable $O(\text{log}N)$ binary search, as that would invalidate all of the existing handles.

Our StringToId structure needs to be a hash map.

The std::unordered_map Redemption

Our IdToString vector stores std::string_view objects. Each std::string_view is fundamentally just a pointer to a std::string that is physically stored elsewhere.

If that string ever moves to a different physical address, our std::string_view will become invalid. We need a guarantee that once a string is inserted into the map, it will never physically move.

Earlier, we saw that the standard library's hash-based containers like std::unordered_map resolve collisions using a separate chaining strategy. We learned that this approach isn't great for performance, but it is perfect for pointer stability. And pointer stability is exactly what we need in this scenario:

1// ...
2#include <unordered_map>
3
4class StringPool {
5private:
6  // Maps a string to its integer ID
7  std::unordered_map<std::string, int> StringToId;
8
9  // ...
10};

Because std::unordered_map allocates a dedicated node for every element, the physical std::string lives inside that node on the heap. When the map gets too full and needs to rehash, it does not need to physically move the strings. It simply allocates a new array of bucket pointers, and re-links the existing nodes into the new buckets.

The nodes themselves never move, so pointers to them, including the internal pointer of a std::string_view, are never invalidated:

This means we can safely extract a std::string_view pointing to a key inside the map and drop that view into our IdToString array.

The performance issues of separate chaining aren't as relevant here. We don't care that much about insertion speed because we'll only call insert() once per unique string. That initial interning can often be done outside of any hot loop - even at compile time for all the static strings used in our program.

We also don't care much about lookup speed, because most systems that want to read the string should have the handle. That means those lookups will use the IdToString array rather than the StringToId map.

To make our Intern() method work, we want to perform a heterogeneous lookup. We want to search the map using the std::string_view we are handed, without accidentally triggering a std::string allocation just to run the search.

From C++20 onwards, we can use heterogeneous lookups in standard library hash sets and maps. However, they require us to explicitly opt in by providing a hash functor that includes operators for the heterogeneous comparisons we want to support, in addition to an is_transparent marker.

In this case, we want to support lookups only using std::string_view, so our functor would look something like this:

1// ...
2#include <functional>
3
4// A transparent hash functor that allows std::unordered_map
5// to accept std::string_view queries without allocating
6struct StringHash {
7  using is_transparent = void;
8
9  size_t operator()(std::string_view txt) const {
10    return std::hash<std::string_view>{}(txt);
11  }
12};
13
14// ...

We also need to explicitly provide our comparison function. The standard library implements == overloads that are interoperable between std::string_view and std::string, so our comparator just needs to accept two arguments, A and B, and return A == B.

The standard library provides the std::equal_to template, which creates a simple functor that does exactly this.

We can plug the hasher and comparator into our map's third and fourth template arguments:

1// ...
2
3class StringPool {
4private:
5  std::unordered_map<
6    std::string,
7    int,
8    StringHash,       
9    std::equal_to<>   
10  > StringToId;
11
12  std::vector<std::string_view> IdToString;
13
14public:
15  int Intern(std::string_view str) {
16    // Check if the string already exists.
17    // Thanks to our transparent hash, this search
18    // allocates absolutely zero memory
19    auto it = StringToId.find(str);
20    if (it != StringToId.end()) {
21      return it->second;
22    }
23
24    // The string is new. Calculate what its
25    // ID will be
26    int newId = static_cast<int>(IdToString.size());
27
28    // Emplace it into the map
29    // This allocates a stable Node
30    auto [insertedIt, success] = StringToId.emplace(
31      std::string(str), newId
32    );
33
34    // Grab a stable view to the string sitting
35    // inside the Map Node
36    std::string_view stableView = insertedIt->first;
37
38    // Store the stable view in our
39    // O(1) lookup array
40    IdToString.push_back(stableView);
41
42    return newId;
43  }
44
45  std::string_view GetString(int id) const {
46    return IdToString[id];
47  }
48};

With less than 50 lines of code, we have constructed a globally stable string vault. This concept can be replicated to any data type that we want to optimize similarly - we'd just replace std::string with whatever type we want to intern, and std::string_view with something that views that type, such as a simple pointer type.

Our dedicated lesson on standard library maps provides examples on how to make custom types compatible with hash-based containers.

Now that we have a mechanism to convert complex types to and from integers, we don't need techniques like hash caching. We can just use their pool IDs as our keys - simple integers that the CPU and memory controller love.

This is one of the goals of data-oriented design: we isolate complexity at the boundaries of our system.

When a JSON configuration file is loaded, or a network packet arrives, the parsing subsystem interacts with a StringPool or similar mechanism, trading heavy, complex data for simple integer IDs. Once that boundary translation is complete, the core systems - the physics loop, the rendering loop, the hash sets - process nothing but densely packed integers, executing with maximum efficiency.

We translate our fast integers back to the heavy payload data only when necessary:

1#include <iostream>
2#include <dsa/StringPool.h>
3#include <dsa/RobinHoodSet.h>
4
5int main() {
6  StringPool Pool;
7  RobinHoodSet RegisteredUsers;
8
9  // Boundary Ingestion: Translate heavy strings into fast integers
10  int AliceId = Pool.Intern("Alice");
11  int BobId = Pool.Intern("Bob");
12  int CharlieId = Pool.Intern("Charlie");
13
14  // Core Logic: The hash set only sees integers
15  RegisteredUsers.Insert(AliceId);
16  RegisteredUsers.Insert(BobId);
17
18  if (RegisteredUsers.Contains(AliceId)) {
19    // Boundary Output: Translate integer back to the original
20    // slow data only when we need it:
21    std::cout << "User " << Pool.GetString(AliceId)
22              << " is registered.\n";
23  }
24
25  if (!RegisteredUsers.Contains(CharlieId)) {
26    std::cout << "User " << Pool.GetString(CharlieId)
27              << " is not registered.";
28  }
29}

1User Alice is registered.
2User Charlie is not registered.

As expected, the following benchmarks show our original RobinHoodSet using integers representing string pool IDs outperforms std::unordered_set<std::string> and the previous lesson's StringRobinHoodSet by huge margins.

However, this performance gain excludes the cost of the initial interning. In most scenarios, it's possible to proactively intern our strings so we don't pay the performance cost in our hot loops, but not in all scenarios.

We include an InternedWorstCase benchmark below to simulate scenarios where the strings aren't already interned, or they are, but we don't know their IDs. Solving either of these scenarios requires Intern() calls to the StringPool followed by Contains() calls to the RobinHoodSet, which is relatively expensive:

1#include <benchmark/benchmark.h>
2#include <unordered_set>
3#include <vector>
4#include <string>
5#include <random>
6#include <algorithm>
7#include <dsa/RobinHoodSet.h>
8#include <dsa/StringRobinHoodSet.h>
9#include <dsa/StringPool.h>
10
11const int kNumElements = 2'000'000;
12const int kNumQueries = 1'000'000;
13
14std::string GenerateLongString(std::mt19937& rng) {
15  const char charset[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
16    "abcdefghijklmnopqrstuvwxyz0123456789";
17  std::uniform_int_distribution<int> dist(0, sizeof(charset) - 2);
18
19  std::string s;
20  s.reserve(32);
21  for (int i = 0; i < 32; ++i) s += charset[dist(rng)];
22  return s;
23}
24
25std::vector<std::string> GenerateData() {
26  std::vector<std::string> data(kNumElements);
27  std::mt19937 rng(42);
28  for (int i = 0; i < kNumElements; ++i) {
29    data[i] = GenerateLongString(rng);
30  }
31  return data;
32}
33
34const std::vector<std::string> Data = GenerateData();
35
36std::vector<std::string> GenerateQueries(double miss_rate) {
37  std::vector<std::string> queries;
38  queries.reserve(kNumQueries);
39
40  int misses = kNumQueries * miss_rate;
41  int hits = kNumQueries - misses;
42
43  for (int i = 0; i < hits; ++i) queries.push_back(Data[i]);
44
45  std::mt19937 rng(42);
46  for (int i = 0; i < misses; ++i) {
47    queries.push_back(GenerateLongString(rng));
48  }
49
50  std::shuffle(queries.begin(), queries.end(), rng);
51  return queries;
52}
53
54// Global String Pool for the benchmark
55StringPool GlobalPool;
56
57// Pre-intern the data ahead of the hot path
58std::vector<int> GetInternedData() {
59  std::vector<int> interned;
60  interned.reserve(Data.size());
61  for (const auto& str : Data) {
62    interned.push_back(GlobalPool.Intern(str));
63  }
64  return interned;
65}
66
67const std::vector<int> InternedData = GetInternedData();
68
69static void BM_StdUnorderedSet(benchmark::State& state) {
70  double miss_rate = state.range(0) / 100.0;
71  std::vector<std::string> queries = GenerateQueries(miss_rate);
72
73  std::unordered_set<std::string> set(Data.begin(), Data.end());
74
75  for (auto _ : state) {
76    for (const auto& query : queries) {
77      benchmark::DoNotOptimize(set.contains(query));
78    }
79  }
80}
81
82static void BM_StringRobinHood(benchmark::State& state) {
83  double miss_rate = state.range(0) / 100.0;
84  std::vector<std::string> queries = GenerateQueries(miss_rate);
85
86  StringRobinHoodSet set;
87  for (const auto& val : Data) set.Insert(val);
88
89  for (auto _ : state) {
90    for (const auto& query : queries) {
91      benchmark::DoNotOptimize(set.Contains(query));
92    }
93  }
94}
95
96static void BM_InternedRobinHood(benchmark::State& state) {
97  double miss_rate = state.range(0) / 100.0;
98  std::vector<std::string> queries = GenerateQueries(miss_rate);
99
100  // Pre-intern the queries ahead of the hot loop
101  std::vector<int> internedQueries;
102  internedQueries.reserve(queries.size());
103  for (const auto& q : queries) {
104    internedQueries.push_back(GlobalPool.Intern(q));
105  }
106
107  RobinHoodSet set;
108  for (int id : InternedData) set.Insert(id);
109
110  // The Hot Path: Pure integers
111  for (auto _ : state) {
112    for (int query_id : internedQueries) {
113      benchmark::DoNotOptimize(set.Contains(query_id));
114    }
115  }
116}
117
118static void BM_InternedWorstCase(benchmark::State& state) {
119  double miss_rate = state.range(0) / 100.0;
120  std::vector<std::string> queries = GenerateQueries(miss_rate);
121
122  RobinHoodSet set;
123  for (int id : InternedData) set.Insert(id);
124
125  // Intentionally NOT pre-interned. Each iteration re-runs
126  // the full string -> intern -> lookup pipeline, which is
127  // the realistic cost when callers do not know the string
128  // ID or whether it is interned
129  for (auto _ : state) {
130    for (const auto& query : queries) {
131      int id = GlobalPool.Intern(query);
132      benchmark::DoNotOptimize(set.Contains(id));
133    }
134  }
135}
136
137#define REGISTER_BENCHMARK(func) BENCHMARK(func) \
138  ->Unit(benchmark::kMillisecond) \
139  ->ArgName("MissRatePct") \
140  ->Arg(1) \
141  ->Arg(50) \
142  ->Arg(99)
143
144REGISTER_BENCHMARK(BM_StdUnorderedSet);
145REGISTER_BENCHMARK(BM_StringRobinHood);
146REGISTER_BENCHMARK(BM_InternedRobinHood);
147REGISTER_BENCHMARK(BM_InternedWorstCase);

1---------------------------------------------
2Benchmark                                 CPU
3---------------------------------------------
4BM_StdUnorderedSet/MissRatePct:1       224 ms
5BM_StdUnorderedSet/MissRatePct:50      180 ms
6BM_StdUnorderedSet/MissRatePct:99      219 ms
7
8BM_StringRobinHood/MissRatePct:1       135 ms
9BM_StringRobinHood/MissRatePct:50      130 ms
10BM_StringRobinHood/MissRatePct:99      134 ms
11
12BM_InternedRobinHood/MissRatePct:1    4.72 ms
13BM_InternedRobinHood/MissRatePct:50   4.46 ms
14BM_InternedRobinHood/MissRatePct:99   5.16 ms
15
16BM_InternedWorstCase/MissRatePct:1     294 ms
17BM_InternedWorstCase/MissRatePct:50    220 ms
18BM_InternedWorstCase/MissRatePct:99    239 ms

Here is the complete implementation of the StringPool, alongside our original integer-based RobinHoodSet:

In this lesson, we decoupled our underlying data types from our structural processing loops. By implementing a global string vault, we achieved the following:

1. Global Deduplication: Instead of scattering identical 24-byte string footprints and their heap allocations across main memory, we store each unique string exactly once, significantly reducing memory usage and fragmentation.
2. Pointer Stability: We used std::unordered_map's separate chaining as a feature. Because map nodes never move during a reallocation, we safely mapped fast std::string_views to our centralized strings without fear of dangling pointers.
3. Cache Maximization: By shrinking our keys back down to 4-byte integers, our data structures reclaimed their maximum cache efficiency, allowing the hardware prefetcher to load 8 slots in a single hardware cycle.
4. Boundary Isolation: We learned that high-performance systems translate heavy, inefficient data into machine-friendly Handle IDs at the boundaries, leaving the hot loops completely free to work with simple numbers at maximum speed.