Update: The post has been updated based on feedback from reddit users: http://www.reddit.com/r/gamedev/comments/2ykhpg/iterating_over_stl_containers/
In computer games speed is always crucial so you really have to know what are the advantages or disadvantages of containers you want to use. I’m writing this article as a small parenthesis of a larger article where I presented the render loop of a graphical engine. There I used a STL map container to hold the game objects. Now every frame I have to iterate over all objects from the map to render them on the screen. The question is : Is STL map fast enough to be used every frame?
To answer this question, we can measure the time required to iterate over the map and compare with time from other containers too. We are going to compare the following containers:
- STL map
- STL unordered_map
- STL vector
- STL list
All iterations are performed in O(N) time. But some containers use lots of instructions to achieve the same result. Also don’t get confused here, in this article we try to measure iteration not searching.
To begin, I have a simple class called Foo with one private int and two pointers to another class A and a public method Get which returns that integer and a another method called GetString which returns a string ( code is provided below). In the loop I’m iterating over the container and sum those values and assign the string.
There are a huge amounts of factors which influence the final result (e.g: CPU, Cache, Threads, Temperature, Ram, Windows, Compiler etc). The test will be different from configuration to configuration. Even if run the test once again I will not have the same exact results as before. However, every time I run this, there are big time differences between containers.
Results in release mode:
We can clearly see that the simple array is the fastest one and map is the most expensive and slow container for all examples from above. Maps should not be used in rapid iterations, they weren’t designed for this.
To measure the time (on Windows) I used three methods:
- Chrono available only in C++11
In the results displayed in the images above, I used QPC (on Windows) because it’s much more accurate than the other two methods. For cases with just a few elements chrono and clock() didn’t worked very well. The source code can be found here.
My opinion is that you can use the STL map for really small games where you don’t have lots and lots of objects to render and switch to a vector after you done some profile and saw that your container may be a part of a bottleneck.
While STL can seem enticing game devs that care about performance don’t use (or minimize) the use of STL. Console game developers have switched to DOD (Data-Orientated Design) for ultra performance because OOP does not scale up in performance.
- More on maps and vectors http://www.tilander.org/aurora2/The_Performance_of_map_vs_vector/index.html
- The classical introduction to DOD is Tony Albrecht’s “Pitfalls of Object Oriented Programming” www.slideshare.net/roycelu/
pitfalls-of- objectorientedprogramminggcap0 9
- Reddit’s game wiki has a section on DOD if you want to read more. http://www.reddit.com/r/gamedev/wiki/resources#wiki_oop_vs_dod_.28optimization.2C_performance.29