Is it a bad idea to use a map data structure (an associative array or dictionary) in game development?
According to this flowchart, the ideal container for storing game object's container would actually be a map for many games. But I've heard anecdotal claims that maps are a very bad choice for games.
Is this true?
Are associative arrays a good idea for games? Perhaps, depending on your needs.
However, you need to differentiate between comments about "associative arrays" and specifically about the class std::map.
Associative arrays are just some kind of data structure that allows you to associate one kind of value with another, such that you can look up a value with another value. There are many kinds of associative arrays, some of which are really implemented with a regular array.
Hash tables are a form of associative array.
The "conventional wisdom" among many C-style game developers is that looking up entities by name is not worth it. This "wisdom" effectively says that your entities should be in one big global fixed-size array. When you create a new one, you find an unused index, set it to be used, and you pass the "index" around as the name.
Entities may have an actual string name, but you won't be using that to find the entity by name very often; generally speaking, you will reference entities by either pointer or index. This is still an associative array; it just uses an index rather than a name as its key value.
One pitfall you may have with associative arrays is that you may need to collate entities based on different properties. Things like "find all entities with blue hands" or whatever. Your associative array isn't going to help you; you'll have to take a linear walk down the entire list of entities to deal with that.
If your game does this kind of collation a lot, then adding other data structures might be a better way to go. Of course, that's rather complex.
std::map is a specific implementation of an associative array. And while it is the shortest associative array in the standard library, it has certain performance quirks.
Specifically, every insertion is a memory allocation. But more than that, because the memory is likely not contiguous, accessing different elements will likely miss the cache. If you ever need to walk through the list of all entities (to render them, update their position, etc), every entity is basically going to be a full cache miss.
You can read more in this PDF; it talks about std::set, but they're both the same under the hood.
The "conventional wisdom" I stated earlier tends to avoid that issue. But really, it's bad coding for C++. It's really just a poorly-designed pool allocator, and an actual pool allocation system would be far better at achieving the same effect.
A better alternative would be using Boost.Container's flat_map class. It essentially takes the concept of a sorted vector from the PDF and implements a variation of set and map from it. Insertion and deletion will be slightly painful, as it will have to shuffle elements around. They'll be more painful than the pool allocator case, certainly. But iteration will be quite fast.
However, what matters most is that you think about how much this matters. Is your game performance heavy at all? More specifically, is your game's performance going to be contingent on the memory performance of the class that contains your entities? If not, then what matters for you is user convenience. Do what it takes to get the job done. And if map does the job, use it. If it starts to become a performance issue, you should be able to replace it with something else.
boost::flat_map from this.
\$\endgroup\$
Commented
Jun 19, 2013 at 17:09
Take blanket statements like that with a grain of salt. Only a tiny fraction of the code in a game is performance sensitive. If a map is the collection you need, use it. Otherwise don't.
You're trying to be specific with an example of holding a bunch of "GameObjects" in a map. What are you mapping to/from? Why do you need to sort your GameObjects? If you can answer both of those questions well, then a map may very well be what you need.
From my experience, when dealing with any sort of entity system, the entity container does not have any additional data that needs to be stored outside of the GameObject, nor does the container have to be sorted. I just need everything in one place so I can quickly complete actions on all of them, an array or vector is perfect for that.
But perhaps your game, for some reason, needs a LOT of arbitrary communication between GameObjects. You give each GameObject and ID and want to be able to tell your container to get another GameObject by it's ID. After some profiling, you realize that searching through an unsorted array of GameObjects is your bottleneck because of how much searching you have to do. You figure you can refactor the ID outside of the GameObject and you want your data to stay sorted to make searching quicker. In this case you could try replacing the array with a map and see if there are any noticeable performance improvements.
On the other hand, there is something to be said about a map not being stored contiguously in memory. Looking at it through a data-oriented programming lens, maps (and all hierarchical data structures) are a nightmare. Flat data structures have less iteration overhead and cause less cache misses. Additionally, it makes parallelizing code much easier. Give each thread an index and a length and tell them to go. Assigning nodes to threads from a tree is significantly more complicated.
A data structure is a tool, like any other. That means it has places where it is appropriate and places where it is not, and a map is no different.
If it fulfills the need of your program, makes logical sense in the use case and contributes to the improved readability of your code, then use a map.
If that use case ever becomes a performance concern (which you'll know through regular profiling of your game), address that concern then.
You've provided no references or citations to the assertions that maps have no place in game development, but if you had I suspect those claims would be easy to dismiss as overgeneralized hand-wavy FUD.
Ill add that it's also very dependent on the data you're modelling, and the operations that you perform on the data. If you're just writing something simple, you're not likely to suffer the same performance problems that people who are actively pushing the hardware very hard.
Maps, or associative containers, as your diagram suggests, are fantastic for random access patterns. they're not so great for linear access. They're also pretty decent for when you need to insert and remove a lot of items. being STL, they're also going to work with very very minimal bugs (read "if it breaks, its 99.99% your code).
As always make it work first, make it fast later. The key to doing that effectively is good API design which is optimised around your access patterns, but hides the underlying data structures. Once you've got it working. profile profile profile. Its quite likely that any performance issues you will have wont be based on your usage of std::map.
The only data structure you should try and avoid at all costs is the linked list. They're terrible for linear processing due to being cache inefficient, and they're horrible for random access as you have no way to jump to a particular node without iterating the list. doubly linked lists are somewhat better, but you're far better off just using an array, or a tree.
