Gamasutra: The Art & Business of Making Gamesspacer
arrowPress Releases








If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 

The Big O means less

by Brad Wardell on 12/09/15 10:28:00 am   Expert Blogs   Featured Blogs

The following blog post, unless otherwise noted, was written by a member of Gamasutra’s community.
The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company.

 

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.


Related Jobs

Subset Games
Subset Games — Seattle, Washington, United States
[04.23.19]

Platform Engineer
Disbelief
Disbelief — Cambridge, Massachusetts, United States
[04.23.19]

Junior Programmer, Cambridge, MA
Disbelief
Disbelief — Cambridge, Massachusetts, United States
[04.23.19]

Senior Programmer, Cambridge, MA
Disbelief
Disbelief — Chicago, Illinois, United States
[04.23.19]

Senior Programmer, Chicago





Loading Comments

loader image