Debugging and Profiling Your Game - Game Coding Complete - page 847

'

perfect because you ll get different results on different CPUs, but the results should

be relatively accurate when run on the same CPU. All you ' re looking for is a delta so
you can see if you were able to speed up some particularly complex algorithm.

Optimizing Code
Once you s time to fix the code. Optimizing

code is very much an art form. You need to examine the code and try to understand
why it

' ve isolated the offending algorithm, it '

' s so slow. For example, consider the following code:

// assume this is defined
std::list<Actor*> actorList;

Actor* FindActor(ActorId id)
{

for (auto it = actorList.begin(); it != actorList.end(); ++actorList)
{

Actor* pActor = (*it);
if (pActor->GetId() == id)
return pActor;

}
return NULL; // actor not found

}

This function loops through a list of actors to find the one that matches the ID. On
the surface, it may appear okay, but this function is extremely inefficient. Once you
have a few hundred or even a few dozen actors in the world, this function will cause
some major performance issues in your game.
Computer scientists use a form of notation to estimate the performance cost of an
algorithm with relation to the data that it operates on. This is called Big-O notation.
The algorithm above is O(n), where n is the number of elements in the data struc-
ture. This means that as n goes up, so does the amount of time it takes to run this
algorithm. In other words, the time it takes to run this algorithm scales linearly with
the number of items in the list.
Let s say for the sake of argument that the evaluation of each iteration through the

list costs 1ms. That means that if there are 100 elements in the list, it would cost
100ms to go through the entire list in the worst case.
The easiest fix for this problem is to create a map, which is typically implemented as
a balanced binary tree (specifically a red-black tree for Visual Studio). Here is the
revised code:

'

// assume this is defined
std::map<ActorId, Actor*> actorMap;