In-Depth: Quasi Compile-Time String Hashing

Author: by Stefan Reinalter

[In this reprinted #altdevblogaday-opinion piece, FH Technikum Wien lecturer and former Sproing Interactive senior programmer Stefan Reinalter walks readers through quasi compile-time string hashing step-by-step.] One scenario that is quite common in all game engines is having to look-up some resource (texture, shader parameter, material, script, etc.) based on a string, with e.g. code like the following:

Texture* tex = textureLibrary->FindTexture("my_texture");
ShaderParameter param = shader->FindParameter("matrixWVP");

For today, we are not so much concerned about how the key-value pairs are stored, and how the look-up is done internally (read this excellent post instead), but rather how to get rid of any hashing done at run-time. You might be surprised at how good C++ compilers have become when it comes to evaluating expressions known at compile-time, so let us put that to good use. Assuming all our textures are stored in a table using some kind of (Hash, Texture) key-value pair (be it in a std::map, a simple array, or something more advanced), the code for finding a texture would vaguely look as follows:

Texture* TextureLibrary
     ::FindTexture(const char* name)
{
 const unsigned int hash = CalculateHash(name);
 // lookup the texture in some container using 'hash'
}

So even for constant strings, CalculateHash() will still be called, and the hash has to be generated each and every time this function is called with a constant string. This is something we would like to get rid of. The first step is to ensure that each and every class dealing with hashes makes use of the same functionality, while still retaining the same syntax for users of those classes. So instead of taking a const char* as argument, we could define a simple class holding nothing more than a hash internally, which will be passed to the function by value instead:

class StringHash
{
private:
 unsigned int m_hash;
};

Texture* TextureLibrary::FindTexture(StringHash hash)
{
 // no more hash calculations in here
 // lookup the texture in some container using 'hash'
}

This way, our hashed string class can tackle the problem of distinguishing between constant and non-constant strings, and we can be sure that no hash calculations take place inside the function. But still, how do we make sure that constant strings are not re-hashed every time? A Simple Hash Function Let's assume that hashing strings is done using a simple FNV-1a hash with the following implementation:

unsigned int CalculateFNV(const char* str)
{
 const size_t length = strlen(str) + 1;
 unsigned int hash = 2166136261u;
 for (size_t i=0; i<length; ++i)
 {
  hash ^= *str++;
  hash *= 16777619u;
 }

 return hash;
}

Looking at the above FNV-1a hash implementation, let's try to figure out the resulting hash values for known strings (don't forget about the null terminator):

The algorithm's offset and prime are compile-time constants (I used 2166136261u and 16777619u in the example above), so these expressions really are constant. Helping The Compiler All we need to do is give the compiler some help, which can be achieved by providing concrete implementations for strings of different lengths. Let's put those into our StringHash class:

class StringHash
{
public:
 ME_INLINE StringHash(const char (&str)[1])
  : m_hash((2166136261u^ str[0]) * 16777619u)
 {
 }

 ME_INLINE StringHash(const char (&str)[2])
  : m_hash((((2166136261u^ str[0]) * 16777619u)^ str[1]) * 16777619u)
 {
 }

 // other implementations omitted
};

In case you're not familiar with the syntax (and admittedly it's one of the more awkward ones in C++), the constructors take references to const-char-arrays of sizes 1, 2, and so on. Providing different implementations for strings of different length tremendously helps the compiler/optimizer to fold the constant expressions into the final hash. In addition, we force each constructor to be inlined using ME_INLINE, which is a platform-independent variant of e.g. __forceinline (Visual Studio 2010), passing an additional hint to the optimizer. Spotting The Pattern Many of you may have already spotted the (offset^constant)*prime pattern in the above examples, and indeed we can easily implement our constructors by utilizing the preprocessor:

#define PREFIX(n, data)		((
#define POSTFIX(n, data)	^ str[n]) * 16777619u)

#define ME_STRING_HASH_CONSTRUCTOR(n)						\
ME_INLINE StringHash::StringHash(const char (&str)[n])				\
 : m_hash(ME_PP_REPEAT(n, PREFIX, ~) 2166136261u ME_PP_REPEAT(n, POSTFIX, ~))	\
{										\
}

class StringHash
{
public:
 ME_STRING_HASH_CONSTRUCTOR(1)
 ME_STRING_HASH_CONSTRUCTOR(2)
 ME_STRING_HASH_CONSTRUCTOR(3)
 ME_STRING_HASH_CONSTRUCTOR(4)
 ME_STRING_HASH_CONSTRUCTOR(5)
 ME_STRING_HASH_CONSTRUCTOR(6)
 ME_STRING_HASH_CONSTRUCTOR(7)
 ME_STRING_HASH_CONSTRUCTOR(8)

 // other constructors omitted
};

Did It Work? With this in place, let's take a look at the assembly code generated by the compiler to see whether our trick really worked. We will use the following simple example for that:

printf("Hash test: %d", StringHash("").GetHash());
printf("Hash test: %d", StringHash("test").GetHash());
printf("Hash test: %d", StringHash("aLongerTest").GetHash());
printf("Hash test: %d", StringHash("aVeryLongTestWhichStillWorks").GetHash());

The resulting assembly code (Visual Studio 2010) looks like this:

printf("Hash test: %d", StringHash("").GetHash());
 01311436 push    50C5D1Fh
 0131143B push    offset string "Hash test: %d" (13341ECh)
 01311440 call    printf (1328DD0h)
printf("Hash test: %d", StringHash("test").GetHash());
 01311445 push    0AA234B7Fh
 0131144A push    offset string "Hash test: %d" (13341ECh)
 0131144F call    printf (1328DD0h)
printf("Hash test: %d", StringHash("aLongerTest").GetHash());
 01311454 push    444D1A47h
 01311459 push    offset string "Hash test: %d" (13341ECh)
 0131145E call    printf (1328DD0h)
printf("Hash test: %d", StringHash("aVeryLongTestWhichStillWorks").GetHash());
 01311463 push    6D9D8B39h
 01311468 push    offset string "Hash test: %d" (13341ECh)
 0131146D call    printf (1328DD0h)

As can be seen from the generated instructions (push 50C5D1Fh, push 0AA234B7Fh, push 6D9D8B39h and push 6D9D8B39h), the compiler/optimizer was indeed able to fold every string into its corresponding hash at compile-time, completely eliminating all traces to any StringHash constructor. Finishing Touches All is well for constant strings, but what about non-constant ones? Of course we might want to use some kind of non-hardcoded string (e.g. a std::string, or strings coming from a file) every now and then, and need to provide a constructor for those as well:

class StringHash
{
public:
 StringHash(const char* str)
  : m_hash(CalculateFNV(str))
 {
 }

 ME_STRING_HASH_CONSTRUCTOR(1)
 ME_STRING_HASH_CONSTRUCTOR(2)
 ME_STRING_HASH_CONSTRUCTOR(3)
 ME_STRING_HASH_CONSTRUCTOR(4)

 // other constructors omitted
};

Now we're in trouble. C++ overload resolution dictates that const char (&str)[N] is as good a match for any of the constructors as const char*, because every array decays into a pointer automatically. This means that our class no longer works, because every constructor call is ambiguous:

// error: constructor overload resolution was ambiguous
printf("Hash test: %d", StringHash("test").GetHash());

What we need to do is make the overload resolution process jump through another hoop for const char* arguments, so that constant string are considered first, and non-constant ones second. This can easily be achieved by using the following trick:

class StringHash
{
public:
 struct ConstCharWrapper
 {
  inline ConstCharWrapper(const char* str) : m_str(str) {}
  const char* m_str;
 };

 StringHash(ConstCharWrapper str)
  : m_hash(CalculateFNV(str.m_str))
 {
 }

 ME_STRING_HASH_CONSTRUCTOR(1)
 ME_STRING_HASH_CONSTRUCTOR(2)
 ME_STRING_HASH_CONSTRUCTOR(3)
 ME_STRING_HASH_CONSTRUCTOR(4)

 // other constructors omitted
};

By making the constructor take a ConstCharWrapper instead of a const char*, we have altered the outcome of the overload resolution process. All constructors taking a reference to an array are now considered better matches by the compiler, because the constructor taking a ConstCharWrapper has to go through one implicit conversion, making the other constructors win in the case of constant strings. Similarly, non-constant strings can only be converted to a ConstCharWrapper implicitly, again disambiguating overload resolution. Note that in order for this to work the ConstCharWrapper constructor is non-explicit on purpose. Conclusion Using the StringHash class introduced above, you can turn run-time hashing of constant strings into quasi compile-time constants without having to change calling code. I say "quasi" because the results of course cannot be used as a true compile-time constant (e.g. in a switch-statement, or as a non-type template argument), but rather relies on the compiler/optimizer instead. Therefore, it should be pointed out that this works in Visual Studio, as well as all major console platforms (Xbox360, PS3, Wii). In addition, employing this trick reduces the size of the executable, because the constant strings are not used anymore and will therefore never end up in the read-only section of the executable, resulting in maybe a few extra KB of memory to use. This could also be beneficial for other applications making use of the above, e.g. compile-time string encryption, because the source strings are nowhere to be found. Note: You don't need to use the preprocessor in order to define different constructors, but can use template meta-programming for that. One such possible template solution is the following:

template <unsigned int N, unsigned int I>
struct FnvHash
{
 ME_INLINE static unsigned int Hash(const char (&str)[N])
 {
  return (FnvHash<N, I-1>::Hash(str) ^ str[I-1])*16777619u;
 }
};

template <unsigned int N>
struct FnvHash<N, 1>
{
 ME_INLINE static unsigned int Hash(const char (&str)[N])
 {
  return (2166136261u ^ str[0])*16777619u;
 }
};

class StringHash
{
public:
 template <unsigned int N>
 ME_INLINE StringHash(const char (&str)[N])
  : m_hash(FnvHash<N, N>::Hash(str))
 {
 }
};

Instead of writing several different constructors, we only need one templated constructor for constant strings now. This constructor in turn simply calls the Hash() function of the class template FnvHash. As can be seen, the FnvHash::Hash function just calls itself recursively, working its way from the end of the string to the beginning. The partial template specialization FnvHash serves as a mechanism to end the recursion. The resulting assembly generated is the same, though it should be noted that the template solution probably is more taxing for the compiler, and depending on the compiler you use, you might have to alter options like inline recursion depth in order to make it work for longer constant strings. [This piece was reprinted from #AltDevBlogADay, a shared blog initiative started by @mike_acton devoted to giving game developers of all disciplines a place to motivate each other to write regularly about their personal game development passions.]