Introduction

Yesterday I posted a game loop speed test which I have taken down because it had some major flaws and bad data. This is the second iteration in my tests and I am here to provide my results. Here are a list of flaws that need to be addressed in my game loop test:

1. All data structures perform a sequential process with no adding or removing of entities
   
2. The test was with a small number of entities and needed to be expanded
   
3. The results only showed a basic idea and I had drawn some poor conclusion from the data sets
   
4. The lists are not sorted so searches will be slower then needed.
   
5. The differences between debug and release builds
   

For today I'm going to address items 2, 3, and 5. I will address 1 and 4 in my next journal entry.

Small to Large test group (2)

The initial tests were done with a small set of entities with and without frame rate management (Just means I paused the frame when there was extra time). Initially I wanted to provide some basic results on a small set of entities but the time it took to perform these tests were insignificant. We are talking about very small fractions of time so it was very difficult to see any difference between data structures. To change this and do a better stress test I have set the entity max to 128000 for the release builds and 6400 for the debug builds.

Debug vs Release (5)

In this version of the test I will provide times for both the debug version and release version on the graph so there will be a direct comparison. The reason for this is during my testing I found there was a very surprising result that I wanted to add to the findings.

New Results (3)
The conclusions of the tests will be provided with more of a analysis of the data and how it performs for this specific scenario. Data structures are like Golf Clubs, each one is designed for a specific obstacle and has their special use. The key here is how the golfer will use them in different situations and how programmers should really know how their data structures will perform.

Debug Test Results
Because I'm lazy and short of time these days I only tested this build with 6400 entities which gives a good example of the results. Here are the results of running the test 6 different times and then taking the average:



These results are very comparable to yesterday's tests but with the 6400 entities you can see that the standard link list is slow and couldn't keep up with the frame rate. If we stopped here and drew our results from these numbers it would be clear that the std::list would be a poor solution. But I didn't stop here so lets look at the release results and see what happens.

Release Test Results
With this build I cranked the entities up to 128000 because the engine needed a larger number in order to register time on the clock. So after cranking up the number of entities to handle in the test here are the results:


Now after running this test we can see that my crappy attempt at making a quality linked list template failed. Which means I maybe going back to the drawing board to fix it after these test results. Anyways the interesting thing here is the std::list performed way better in these tests. Still not at the speed of a solid array but still very decent for 128000 entities.

Release vs Build
This graph was just for fun to see a direct comparison between the two build. Even though this isn't apples to apples you can see the difference in times for the data structures. Every single one of them gained a major performance boost between the two different build types.



As you can see the time are significantly large in the debug build. Here is one simple optimization you can do to get more speed out of your game. Build with the release options. I'm sure there are more things we can do but this is a good start.

The Code
I've included a copy of the Visual Studio 2013 project files I used to perform these tests. As the sole author of this code I give the rights to anyone who wants to use it but with this simple warning: Use at your own risk I do not provide any warranty with this code. If you find it useful please let me know.

Conclusion

So after all the testing the question may remain which data structure should I use? Honestly it really boils down to what you need to do with the entities in your game. The real test is you need to take these data structures into your current build and test to see really which one will perform better for your situation. The other thing to also remember is what build are you using. As the numbers point out it doesn't matter if your using an array or a standard linked list. When your running under a debug build it will always be slower. In the case of the std::list it was massively slower compared to the other data structures.

In the big picture of things if you think about the time and frame rate each data structure performed optimally for their load even under the debug versions except the linked list. In theory each game loop should of ran for 60 seconds but because I disabled the frame rate manager we were able to process the same number of frames in 1 or 2 seconds with 128000 entities. Depending on your game though you may need to bleed as many calculations out of your processor each frame. This just means don't pick one data structure and think your done. Test it and make sure what you have added is not taking longer then it should.

Lastly I want to say don't be afraid to try something new! Just don't take my word that these are faster because of A,B, and C. Know they are faster because you have put the effort out to make sure your getting the best performance for your scenario. Take my project and play around with it to see what work and doesn't work. Try building different test cases and see how it performs and then compare results.