Sponsored By

Featured Blog | This community-written post highlights the best of what the game industry has to offer. Read more like it on the Game Developer Blogs.

Game development still focuses heavily on "BIG O" costs of algorithms. But they're increasingly not where performance costs come from.

Brad Wardell, Blogger

December 9, 2015

2 Min Read

For most of my development career, code-review has emphasized looking for unnecessary complexity in algorithms.  

The Big O notation goes something like this:

O(1), O(N), O(N^2), O(2^N), etc.

On the whole, developers would focus on creating algorithms that performed as few operations as possible.

Examples:

If(a == 0)return false;

That's an O(1).

Or

for (i = 0; i

 dothething(i);

That would be O(N).

From there, you woudl look for things like nested for loops or unanticipatd recursion.

The game has changed

However, in the past several years, our CPUs have gotten so fast that the big O is not necessarily the biggest issue.  Instead, it's memory accessing.

Our CPUs are really fast.  Memory, however, remains pretty slow to deal with.  Unfortunately, most developers are not trained to think about the cost of reading and writing to memory.  In fact, many developers are outright hostile to using "old school" methods like fixed arrays and pre-allocation in favor of more elegant solutions.

When O(N) is far slower than O(N^2)

Imagine you have a vector of units in your game.   In fact, let's say you have all the units in yoru game as a big vector but you want to only deal with a small subset of them in order to improve performance due to some expensive operation.

Classic example:

I have 5,000 robots in the world.  I want to do an "expensive" operation on the robots that the player can "see".   Many engineers will try to create a vector or just the robots they can see so that they can avoid doing the "expensive" set of operations to them.

Thus they might do something like this (forgive my crappy syntax, i'm lazy):

for(i = 0; i

{

if(alltherobots[i]->IsVisibleOnScreen())

robotsvisible.push_back(alltherobots[i];

}

Seems straight forward right?  But it turns out that that call might be one of the most performance draining calls in your game.  That's because allocating and deallocating, on modern CPUs, is incredibly expensive.  

Reading and writing memory is often far more performance intensive than doing any number of mathematical operations to them.  

In the above example, you might even find that it's faster to just do the "expensive" operations to all the robots whether they're on screen or not rather than allocating a new vector.  Or, at the very least, filtering out the robots in a series of inelegant IF/THEN checks which many new developers are loathe to do because it looks hackish.

CPUs vs. Memory

The main point is that increasingly, CPU power is cheap, memory management is expensive.  Avoid allocating and deallocating memory when possible.

Read more about:

Featured Blogs

About the Author(s)

Brad Wardell

Blogger

Brad Wardell is currently the CEO and president of Stardock Corporation, one of the leaders in Windows customization software with massively popular software products like Windowblinds and MyColors. Recently, Wardell successfully steered the company into the PC gaming space, developing and publishing smash-hit titles such as the award-winning Galactic Civilizations series and Sins of a Solar Empire. Wardell’s passion for gaming excellence has inspired the company to expand even further to develop a one-stop-shop platform for PC game downloads called Impulse, which launches Q2 of 2008. Wardell resides in Plymouth, Michigan and can bench 350 pounds. Additionally, he can leap tall buildings in a single bound.

Daily news, dev blogs, and stories from Game Developer straight to your inbox

You May Also Like