String Interning with Hash Maps

1. The Problem with Strings

In high-performance contexts, strings are problematic for two main reasons:

1. Memory Overhead & Allocations: Every time you create or manipulate a string, you often trigger heap memory allocations and data copies. For a profiler capturing thousands of events per second, this overhead is unacceptable.
2. Slow Comparisons: Comparing two strings, like "PlayerJumped" and "PlayerLanded", requires iterating over each character until a difference is found or the strings end. Comparing two integer IDs is a single, lightning-fast CPU instruction.

The solution is string interning: a process where we store only one copy of each unique string. Every time that string appears, we refer to it using a unique identifier (an "interned ID").

To see the dramatic performance impact of this technique, let's watch a short video.

As the video shows, the performance gain from interning can be an order of magnitude or more. For our telemetry engine, this means we can log more events with less impact.

2. The Right Tool: std::unordered_map

To implement string interning, we need a data structure that can quickly answer the question: "Have I seen this string before, and if so, what is its ID?" This is a perfect use case for a hash map.

In C++, the standard library provides std::unordered_map, a hash map implementation that gives us fast key-value lookups. The key will be the std::string we want to intern, and the value will be its uint32_t ID.

Since you're building your C++ foundations, it's worth getting a solid grasp of how to use maps.

The key takeaways from the video are:

• std::unordered_map is built on a hash table, making it very fast for lookups (our primary use case).
• std::string can be used as a key directly because the C++ standard library already knows how to hash it.
• The find() method is the correct tool for checking if a string already exists in our table, as it avoids unintended insertions.

3. Implementing the String Interning Table

Now, let's design and implement a StringInterner class. This class will manage the mapping between strings and their IDs. For simplicity in our project, we can treat this as a singleton—a single, globally accessible object.

Our interner needs two core data structures:

1. A map from string to ID for fast lookups: std::unordered_map<std::string, uint32_t> m_string_to_id;
2. A vector to store the actual string data, allowing us to look up a string by its ID if needed (e.g., for the UI later): std::vector<std::string> m_id_to_string;

Here is a complete implementation of a basic StringInterner.

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <cstdint>

class StringInterner {
public:
    // Get the singleton instance
    static StringInterner& get() {
        static StringInterner instance;
        return instance;
    }

    // The main function: returns an ID for a given string
    uint32_t intern(const std::string& str) {
        // 1. Check if the string is already in the map
        auto it = m_string_to_id.find(str);
        if (it != m_string_to_id.end()) {
            // If found, return the existing ID
            return it->second;
        }

        // 2. If not found, create a new ID
        uint32_t new_id = m_id_to_string.size();
        
        // 3. Add the new string to the reverse-lookup vector
        // Note: In a real-world high-perf scenario, we might use a more
        // memory-efficient storage, but std::vector is fine for now.
        m_id_to_string.push_back(str);

        // 4. Add the new string-to-ID mapping to the map
        m_string_to_id[str] = new_id;
        
        return new_id;
    }

    // Optional: A way to get the string back from an ID
    const std::string& lookup(uint32_t id) const {
        return m_id_to_string[id];
    }

private:
    // Private constructor to enforce singleton pattern
    StringInterner() = default;
    
    std::unordered_map<std::string, uint32_t> m_string_to_id;
    std::vector<std::string> m_id_to_string;

public:
    // Delete copy and move operations to prevent copies of the singleton
    StringInterner(const StringInterner&) = delete;
    void operator=(const StringInterner&) = delete;
};

// --- Example Usage ---
int main() {
    uint32_t id1 = StringInterner::get().intern("Player.Health");
    uint32_t id2 = StringInterner::get().intern("Engine.FPS");
    uint32_t id3 = StringInterner::get().intern("Player.Health");

    std::cout << "ID for 'Player.Health': " << id1 << std::endl;
    std::cout << "ID for 'Engine.FPS':    " << id2 << std::endl;
    std::cout << "ID for 'Player.Health': " << id3 << std::endl;

    // We can verify that id1 and id3 are identical.
    if (id1 == id3) {
        std::cout << "The IDs for the same string are identical, as expected." << std::endl;
    }

    // We can also look up the original string from an ID
    std::cout << "ID " << id2 << " corresponds to string: '" << StringInterner::get().lookup(id2) << "'" << std::endl;

    return 0;
}

When you run this code, you'll see that "Player.Health" is assigned an ID (e.g., 0) the first time, and the exact same ID is returned on the second call. A new ID (e.g., 1) is created for the new string "Engine.FPS".

uint32_t intern_buggy(const std::string& str) {
    if (m_string_to_id[str]) { // Incorrect check!
        return m_string_to_id[str];
    }
    // ... logic to create new ID ...
}

4. Under the Hood: Performance and Data-Oriented Design

As someone interested in low-level systems, it's valuable to look past the std::unordered_map abstraction. How does it work?

A hash map is an array of "buckets". To find a value, you first compute a hash of the key (a number), then map that hash to a bucket index. If multiple keys hash to the same bucket (a "collision"), a common strategy is separate chaining, where each bucket points to a linked list of items.

This linked-list approach is common, but traversing lists can be slow due to poor cache locality (nodes can be scattered all over memory). For ultimate performance, some designs favor more data-oriented layouts.

While std::unordered_map's internal implementation is up to the library vendor, understanding these trade-offs is crucial for a systems programmer. Knowing that even standard containers have performance characteristics can inform future design decisions, especially when you might need to write your own specialized data structures.

Conclusion

You have now implemented a core optimization for our telemetry engine. By replacing raw strings with interned IDs, you have drastically reduced the per-event data size and made comparisons trivial.

Key Takeaways:

• String Interning is a crucial pattern in high-performance applications like compilers and profilers. It involves storing a single copy of each unique string and referencing it via an ID.
• This technique significantly reduces memory usage and makes comparisons orders of magnitude faster.
• std::unordered_map is the ideal C++ standard library tool for building an interning table, providing fast key-value lookups.
• Using .find() is the correct way to check for a key's existence without causing side effects.

What's Next?

Our PROFILE_EVENT macro now generates several pieces of data for each event: a timestamp, file/line information, and now an interned string ID. In the next lesson, we will learn how to serialize event data into a compact binary format before pushing to the ring buffer. This is the final step in preparing our event data for efficient, high-speed transport from the application threads to our background consumer thread.