Arrays, Post Haste!

Almost any chance I get, I like to dabble in crazy things ranging from code optimizations to patterns and data structures. Well the last few weekends I had a some of time to kill and with my ever growing disgust of the STL Vector class, I decided to write my own (Growable Array class), just for the hell of it. Out of the box, Vectors are slow, especially when being run in debug mode. There are a slew of iterator checks, data verifications (during memory swaps, etc) and so on which completely turned me off of using the Vector class in time-critical applications such as games.

In that case, lets bust out some numbers. After I wrote my Array class (and optimized it, heavily) , I decided to test it against the Vector class in various different compilation modes. First was a regular debug build (without compiler optimizations), the second test was with full compiler optimizations, and lastly was a test using full compiler optimizations and that neat trick I mentioned in a previous post about disabling iterator checks (#define _SECURE_SCL 0). I was surprised to see the numbers once they came in, check them out:

 
Lots of Numbers! Let me explain what I did to get these numbers. The tests were conducted on 1 million integers within a loop, with the exception of the equals operator (operator=), comparison operator (==), the not equals operator (!=), and the Erase/Remove functions which were reduced considerably since they took so long. The numbers in brackets are the number of iterations that were done to get the result. Due to the debugging information that is added into the Vector class, the performance of the class will slow down to about one-seventh of the speed it should run at. But once all the debugging information is removed, you can really see the class fly. But I guess that was not enough for me. Once the Debugging information was removed and the compiler fully optimized the code, the Vector class was raised to the level of my Array class. It was on par with the majority of the tests, with the exception of push_back(), back(), and front().

One advantage that my Array class has over the Vector class is that it tries to use realloc() in order to grow, rather then trying to allocate new space and copying over the old info. Secondly, I scoured the web for some assembly tricks and stumbled upon an optimization paper written by AMD that mentioned the use of a buffer when copying information from one memory address to another. This is all done on the CPU, using registers. This function out preforms the stock memcpy() or memmove() functions that are included with Visual Studio. I also read that tapping into the MMX or SSE technology would give potential gain, but currently I don’t know enough about that technology.

Either way, I’m releasing the source for everyone to check out under the zlib/libpng license. If anyone has questions/comments/improvements to this class, please feel free to email me. Enjoy :).

This entry was posted on September 17, 2007 at 1:02 am and is filed under C/C++, win32. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response or trackback from your own site.