Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Gamasutra: The Art & Business of Making Gamesspacer
View All     RSS
July 15, 2019
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

DMG Entertainment
DMG Entertainment — Beverly Hills, California, United States
[07.12.19]

Game Engineer
Giant Army
Giant Army — Remote, Washington, United States
[07.11.19]

Graphics Developer for Universe Sandbox
Build A Rocket Boy Games
Build A Rocket Boy Games — Edinburgh, Scotland, United Kingdom
[07.11.19]

Senior Animation Programmer
Build A Rocket Boy Games
Build A Rocket Boy Games — Edinburgh, Scotland, United Kingdom
[07.11.19]

Gameplay Networking Programmer - All Levels





Loading Comments

loader image