How fast is the code

Question

I'm developing game. I store my game-objects in this map:

std::map<std::string, Object*> mObjects;

std::string is a key/name of object to find further in code. It's very easy to point some objects, like: mObjects["Player"] = .... But I'm afraid it's to slow due to allocation of std::string in each searching in that map. So I decided to use int as key in that map.

The first question: is that really would be faster?

And the second, I don't want to remove my current type of objects accesing, so I found the way: store crc string calculating as key. For example:

Object *getObject(std::string &key)
{
   int checksum = GetCrc32(key);
   return mObjects[checksum];
}

Object *temp = getOject("Player");

Or this is bad idea? For calculating crc I would use boost::crc. Or this is bad idea and calculating of checksum is much slower than searching in map with key type std::string?

Answer 1

Calculating a CRC is sure to be slower than any single comparison of strings, but you can expect to do about log2N comparisons before finding the key (e.g. 10 comparisons for 1000 keys), so it depends on the size of your map. CRC can also result in collisions, so it's error prone (you could detect collisions relatively easily detect, and possibly even handle them to get correct results anyway, but you'd have to be very careful to get it right).

You could try an unordered_map<> (possibly called hash_map) if your C++ environment provides one - it may or may not be faster but won't be sorted if you iterate. Hash maps are yet another compromise:

• the time to hash is probably similar to the time for your CRC, but
• afterwards they can often seek directly to the value instead of having to do the binary-tree walk in a normal map
• they prebundle a bit of logic to handle collisions.

(Silly point, but if you can continue to use ints and they can be contiguous, then do remember that you can replace the lookup with an array which is much faster. If the integers aren't actually contiguous, but aren't particularly sparse, you could use a sparse index e.g. array of 10000 short ints that are indices into 1000 packed records).

Bottom line is if you care enough to ask, you should implement these alternatives and benchmark them to see which really works best with your particular application, and if they really make any tangible difference. Any of them can be best in certain circumstances, and if you don't care enough to seriously compare them then it clearly means any of them will do.