I realized about a week ago that the slow performance of Crescendo (the game I am creating) was due, not to the slow Windows graphics library I am prototyping in, but due to a portion of my code called a quad tree that is supposed to be making the game faster. (Oops! )
 
Read on to see the results of optimizing the quad tree to make it 10 times faster.
 
The problem was my use of the Standard Template Library’s set data structure (used in the code as std::set). Each quad tree node used a set to store all the game objects residing in its area of the game field.
 
This is all well and good, but sets are fast at finding a random object in the set or determining if it is not in the set. Sets are not good at copying all their objects into another set.
 
It turns out that the quad tree node’s most common operation is copying all of its objects into another collection, as the main game code wants to know which objects are around a given object at any given time, so the set was a poor choice for a data structure.
 
Therefore, I replaced the std::set with a std::vector. A vector is another STL data structure that allows random access into any object it contains but is not optimal for finding a particular object. Then I used the std::copy algorithm to copy all the elements of the vector into another one when it needed to cough up all its objects.
 
I got a good speed improvement from using the vector (2 to 4 times faster), but it was still pretty slow, and I figured that I could make something even faster, so I made my own vector class that stored the objects in a single block of memory and then did an old-school memcpy to copy its objects. The result was a 10x speed up from the set code.
 
Here are the numbers (in milliseconds (ms) per game iteration):
set speed: 1.6 ms
vector speed: 0.44 ms
my fast vector speed: 0.12 ms