One scenario that is quite common in all game engines is having to look-up some resource (texture, shader, material, script, etc.) based on a string, which could look like the following:

Texture* tex = TextureManager::FindTexture("my_texture");

Whenever we have to find a certain resource based on a name, we could do one of the following:

1. Store each resource’s name, and compare it with the name of the desired resource using strcmp() (or equivalent).
2. Hash each resource’s name, and compare it with the hash of the desired resource’s name.

Option 1 is clearly going to be a lot slower, so everybody should be using Option 2 these days. But even using hashes often does a lot of redundant work at run-time, especially when dealing with constant strings like the above “my_texture”. For example, TextureManager::FindTexture() could be implemented as follows:

Texture* TextureManager::FindTexture(const char* name)
{
  size_t 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, and here’s how.

Instead of taking a ‘const char*’ as argument, we could define a simple class holding a hashed string which will be passed to the function, like so:

class HashedString
{
public:
  // implementation here
private:
  size_t m_hash;
};

Texture* TextureManager::FindTexture(HashedString hash)
{
  // no more hash calculations in here!
}

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?

First, we need to come up with a mechanism of distinguishing between constant and non-constant strings. Luckily, this is something we discussed last time. Using what we ended up with, our initial HashedString interface could look something like this:

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

  template <size_t N>
  inline explicit HashedString(const char (&str)[N]);

  explicit HashedString(ConstCharWrapper str);

private:
  size_t m_hash;
};

Hashing strings is done using a simple FNV-1a hash with the following implementation:

namespace
{
  static size_t CalculateFNV(const char* str, size_t offset, size_t prime)
  {
    unsigned int hash = offset;
    while (*str != 0)
    {
      hash ^= *str++;
      hash *= prime;
    }

    return hash;
  }
}

HashedString::HashedString(ConstCharWrapper str)
  : m_hash(CalculateFNV(str.str, OFFSET, PRIME))
{
}

The above implementation takes care of hashing non-constant strings, so all that is left is hashing constant strings. Of course, we could just call CalculateFNV() for constant strings as well, but this doesn’t get rid of unnecessary re-hashing. Instead, we’ll provide template specializations for strings of different length, which tremendously helps the compiler/optimizer at folding constant expressions into the final hash.

Looking at the above FNV-1a hash implementation, let’s try to figure out the resulting hash values for known strings:

• “” = offset
• “a” = (offset^ ‘a’)*prime
• “ab” = (((offset^ ‘a’)*prime)^ ‘b’)*prime
• “abc” = (((((offset^ ‘a’)*prime)^ ‘b’)*prime)^ ‘c’)*prime)

Offset and prime are compile-time constants (I use 2166136261u and 16777619u, respectively), so the above expressions really are constant. All we need to do is give the compiler some help, which can be achieved by providing template specializations for different N’s:

template <>
inline HashedString::HashedString(const char (&str)[1])
  : m_hash(OFFSET)
{
}

template <>
inline HashedString::HashedString(const char (&str)[2])
  : m_hash((OFFSET^str[0])*PRIME)
{
}

// etc.

By providing inline template specializations, the optimizer is able to fold the constant expressions in the constructor initialization list into the resulting hash value during compile-time!

As you may already have guessed by spotting the ‘OFFSET^constant*PRIME’ pattern in the above examples, the specializations can be nicely put into macros:

#define ME_HASHED_STRING_1            OFFSET
#define ME_HASHED_STRING_2            ((ME_HASHED_STRING_1 ^ str[0]) * PRIME)
#define ME_HASHED_STRING_3            ((ME_HASHED_STRING_2 ^ str[1]) * PRIME)
#define ME_HASHED_STRING_4            ((ME_HASHED_STRING_3 ^ str[2]) * PRIME)
#define ME_HASHED_STRING_5            ((ME_HASHED_STRING_4 ^ str[3]) * PRIME)
// etc.

#define ME_HASHED_STRING_SPECIALIZATION(n)                                    \
  template <>                                                                \
  inline HashedString::HashedString(const char (&str)[n])                    \
    : m_hash(ME_JOIN(ME_HASHED_STRING_, n))                                \
  {                                                                            \
    ME_UNUSED(str);                                                            \
  }

ME_HASHED_STRING_SPECIALIZATION(1)
ME_HASHED_STRING_SPECIALIZATION(2)
ME_HASHED_STRING_SPECIALIZATION(3)
ME_HASHED_STRING_SPECIALIZATION(4)
ME_HASHED_STRING_SPECIALIZATION(5)
// etc.

Finally, let’s take a look at the generated assembly code to check whether our template trickery really worked:

void Test(HashedString hash)
{
  ME_LOG("Hash is: %d", hash);
}

// calling code for constant string
334:     HashedString hash1("Hello");
335:     Test(hash1);
00263D79 B8 4B 31 5C F5       mov         eax,0F55C314Bh
00263D7E 50                   push        eax
00263D7F 68 A4 35 27 00       push        offset string "Hash is: %d" (2735A4h)
...
00263DAD E8 4E EF FF FF       call        me::core::logDispatch::Log (262D00h)

// calling code for non-constant string
337:     std::string str("Hello");
338:     me::core::HashedString hash2(str.c_str());
339:     Test(hash2);
...
00263E07 8D 4D E8             lea         ecx,[hash2]
00263E0A E8 B1 09 00 00       call        HashedString::HashedString (2647C0h)
00263E0F 8B 55 E8             mov         edx,dword ptr [hash2]
00263E12 52                   push        edx
00263E13 68 A4 35 27 00       push        offset string "Hash is: %d" (2735A4h)
...
00263E3A E8 C1 EE FF FF       call        me::core::logDispatch::Log (262D00h)

As you can see, the compiler inserted the resulting hash value for “Hello” directly into the code:

mov         eax,0F55C314Bh

Voila! Mission accomplished, this works in MSVC as well as on console compilers. See the BitSquid blog for a different approach to hashing constant strings.