How fast is the code

Question

I am developing a game. I store my game objects on this map:

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

std::string is the key / name of the object for further search in the code. It is very easy to specify some objects, for example: mObjects["Player"] = ... But I'm afraid that it slows down due to the allocation of std :: string in every search on this map. So I decided to use int as a key on this map.

First question: will it really be faster?

And secondly, I do not want to delete my current type of objects, so I found a way: save the crc string that evaluates as a key. For instance:

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

Or is this a bad idea? To calculate crc I would use boost::crc . Or is this a bad idea, and calculating a checksum is much slower than searching on a map with the key type std::string ?

Answer 1

Computing a CRC will necessarily be slower than any string comparison, but you can count on matching with log2N before looking for a key (for example, 10 comparisons for 1000 keys), so this depends on the size of your map . CRC can also lead to collisions, so it is error prone (you can detect collisions relatively easily to detect and maybe even process them to get the correct results anyway, but you need to be very careful that everything is correct).

You can try unordered_map<> (possibly called hash_map ) if your C ++ environment provides one thing - it may or may not be faster, but it will not be sorted if you iterate. Hash maps are another tradeoff:

• the time for the hash probably looks like the time for your CRC, but
• after that, they can often search directly for the value, rather than perform a double tree movement in a normal map.
• they predetermine a bit of logic for handling conflicts.

(a dumb point, but if you can continue to use int and they can be contiguous, remember that you can replace the search with an array that is much faster. If integers are not contiguous, t is especially rare, you can use a sparse index, for example an array out of 10,000 short ints, which are indices in 1000 packed records).

Bottom line - if you care about asking, you should implement these alternatives and benchmark to see what really works best with your specific application, and if they really make any tangible difference. Any of them may be the best in certain circumstances, and if you care to seriously compare them, then this clearly means that any of them will do.

Answer 2

For real performance, you need a code profile and see it. But I would have a desire to use hash_map . Although this is not part of the C ++ standard library, most of the popular impressive features provide it. It provides a very quick search.

Answer 3

First question: will it really be faster?

yes - you compare int several times, comparing a potentially large map of strings of arbitrary length several times.

 checksum: Or this is bad idea? 

it is definitely not guaranteed to be unique. this is a bug waiting for a bite.

what would i do:

use multiple collections and enable type safety:

 // perhaps this simplifies things enough that t_player_id can be an int? std::map<t_player_id, t_player> d_players; std::map<t_ghoul_id, t_ghoul> d_ghouls; std::map<t_carrot_id, t_carrot> d_carrots; 

faster search, safer type. smaller collections. distributes / resizes less ... and further and further ... if your application is very trivial, then it does not matter. use this approach in the future and configure it after profiling / as needed for existing programs.

luck

Answer 4

If you really want to know that you need to profile your code and see how long the getObject function takes. Personally, I use valgrind and KCachegrind to profile and render data on a UNIX system.

I think using id will be faster. It is faster to compare int than string, so ...