====== String IDs in C++ ======
{{tag>devel cpp}}
Lately, while reading the book **Game Engine Architecture (2018)** from **Jason Gregory**, I discovered the concept of **String IDs** which could be used when we need very high performances (for instance when building games!):
The idea is simple: comparing and creating strings in C++ is expensive, so, this should be avoided at runtime, whereas comparing integers is really efficient. But for human readability, we cannot just get rid of strings obviously :-). So we keep using them while writing code, but using the recent **user-defined string literals** and **constexpr** features from C++, we convert those strings into integer at **compile time**. Nice, isn't it ?!
====== ======
In the book from Jason Gregory, they used CRC32 and then CRC64 to build string hashes. But for my part I'm just going to experiment with another hashing algorithm: FNV-1a, which seems pretty famous for this kind of usage. I found an simple implementation of that algorithm at this link: https://notes.underscorediscovery.com/constexpr-fnv1a/
So, I've written a simple code snippet to add support for string IDs generation: constexpr U32 val_32_const = 0x811c9dc5;
constexpr U32 prime_32_const = 0x1000193;
constexpr U64 val_64_const = 0xcbf29ce484222325;
constexpr U64 prime_64_const = 0x100000001b3;
inline constexpr U32 hash_32_fnv1a_const(const char* const str, const U32 value = val_32_const) noexcept {
return (str[0] == '\0') ? value : hash_32_fnv1a_const(&str[1], (value ^ U32(str[0])) * prime_32_const);
}
inline constexpr U64 hash_64_fnv1a_const(const char* const str, const U64 value = val_64_const) noexcept {
return (str[0] == '\0') ? value : hash_64_fnv1a_const(&str[1], (value ^ U64(str[0])) * prime_64_const);
}
// Implementation of StringID mechanism:
// cf. https://en.cppreference.com/w/cpp/language/user_literal
inline constexpr StringID operator "" _sid(const char* str, std::size_t n) noexcept {
return hash_64_fnv1a_const(str);
}
inline StringID strId(const char* str, std::size_t n) noexcept {
return hash_64_fnv1a(str, n);
}
inline StringID strId(const char* str) noexcept {
return hash_64_fnv1a(str, strlen(str));
}
inline StringID strId(const std::string& str) noexcept {
return hash_64_fnv1a(str.data(), str.size());
}
inline constexpr StringID strId_const(const char* str) noexcept {
return hash_64_fnv1a_const(str);
}
And from there we can just define a simple macro to generate our string IDs when required: #define SID(str) nv::strId_const(str)
And that's it! I also added a unit test to ensure the behavior is correct, and there was no surprise there, so we are all good.