Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

In academia worst case Big O is taught over everything else. Compared to space complexity, normal case analysis, simplicity over complexity, etc.

In particular to game programming and industry, what really matters most and why?

References would be very helpful.

share|improve this question
    
Big-O = Optimization. Took me a bit to figure out what big-0 was. –  AttackingHobo Aug 31 '10 at 6:28
12  
Big-O isn't "optimization". Big-O is a form of analysis that tells you how different algorithms will behave, in terms of efficiency, as the number of elements acted upon increases. See en.wikipedia.org/wiki/Big_O_notation for more detail. –  ZorbaTHut Aug 31 '10 at 7:11
2  
I can assure you the people that came up with octrees and BSP/PVS knew all about big-O. In the end, the only thing that matters is the performance of the application. But to get there you have to consider all manner of things, including the asymptotic complexity of the algorithms that handle a lot of data. –  drxzcl Aug 31 '10 at 7:32
1  
Remember the rule of when to optimize: 1) Don't do it. 2) (experts only) Don't do it yet. –  zaratustra Aug 31 '10 at 17:00
    
Well first of all Big O can be used for space or computational complexity, so "over everything else" isn't exactly true. Second, Big O is usually a lot simpler to compute for something than normal case analysis, and would be used as a quick mental check for whether you are doing something wrong. If drawing a sprite takes O(2^n) time, you should probably choose a different algorithm. If you want a more practical approach to software design look into SE practices rather than CS. CS is theoretical in nature, whereas SE is more based on industry. –  Deleter Sep 1 '10 at 3:01

14 Answers 14

up vote 25 down vote accepted

As with every other question regarding "what's the One True Path", these are all tools in your toolbox and there are cases where big-O trumps everything, and places where it doesn't matter(tm).

You would "never" write a physics solver without being concerned about big-O. You wouldn't implement a sorting algorithm (for any but the smallest of datasets) without being concerned about it. If you're writing a networked game, you're going to be concerned with the way performance and network traffic scales per user.

You might not be so concerned about big-O when, well, I can't really think of a time but I'm sure there are some. :) Thankfully, most of the things that we do in games scale linearly; you want to read a file off of disc? It'll take an amount of time linearly proportional to the file size (discounting the constant factor of seeking and possible ramifications of sector size).

However, what if you want to find a specific entity in the entity list? That's a linear search each time you do it. If you need to find the player once for every entity in the world, this approach will kill you for all but the most trivial of games, and even then it's probably worth "optimizing" this lookup to be constant time (e.g. store off the index of or a pointer to the player somewhere), giving you more time to do other things that actually are visible to the player.

I guess that sums it up, though; any time the processor is doing something that isn't directly representable to the player, it's wasting time. Maximizing the amount of time that the processor is computing data that will be shown to the player is maximizing the WOW! you're giving the player.

share|improve this answer
8  
This. It's important to understand the performance characteristics of your code. You just never know when a designer will use something you've added in a way you didn't expect, and suddenly the bit of code you thought would only have to handle 5 items is now handling 5000 and being pinged 100 times a frame. Do you optimise that? Can you? How many is actually reasonable? A profile will only tell you how slow it is, not why. Knowing the complexity will tell you whether you need to optimise the code, or replace it with something different. –  JasonD Aug 31 '10 at 10:48
3  
Agreed. Universities teach you the 'Big-O' because it handles many of the problems you'll face. When you're asked 'oh, we can make this infinite rather than just 5? the testers hate the limitation' that's when the training pays off. You shouldn't just say 'no I can't'. It's vital to be able to problem solve out of that and say 'yes I can'. Your game needs a searchable galaxy? 'No problem'. Those million units need to be ordered? 'No problem'. 'Didn't study that enough' just doesn't cut it. –  Rushyo Aug 31 '10 at 12:50
    
"You might not be so concerned about big-O when..." processing input keys. I inherited an input system that went to lengths to resolve key->action mappings in constant time, using a lookup table. Switching it to a linear search of an array of (key, action) pairs saved memory and had no performance impact, since users rarely press more than a few keys a frame, and the array is usually only 20-30 items long. It also let us add (key, key, action) for chords. –  user744 Sep 2 '10 at 10:16
    
Joe, sure, although that's a different sort of concern. Do you want O(1) where the constant factor is high, or O(n) with a small 'n' and a low constant factor? Knowing big-O in this case isn't a problem but can help you work out whether or not the solution makes sense for the circumstances in which it'll be used. –  dash-tom-bang Mar 20 '12 at 1:23

I have no references but Big O is at least handy to be aware of when analyzing a problem and discussion. On the other hand, of course, if the O(log n) version has a way more involved O than the O(n) version it's a moot comparison. And as with everything, there's always a trade off. Space complexity could be an issue, although that could be expressed in O in general as well. Normal case analysis...less so, as you don't want outliers to spike either. Simplicity over complexity, in my opinion, is relatively useless in game development as speed is almost always an issue, so unless the simplicity leads to to speedups (but then it means your complex case was wrong for the wrong reasons) simplicity will have to go out of the window in favour of speed. But Big O is definitely useful, as failing to grasp it will fail to help you analyze possible solutions and their impact.

share|improve this answer

My rule of thumb is that unless you're O(scary), your other issues are more pertinent.

My other rule of thumb is that data is king. Unless you profile your code with a realistic data set you're just making guesses.

Edit: To go into a little more detail, your big O isn't that important since (at least in my experience) most of your data sets are relatively tiny. You probably don't care about your upper bound of performance when you're working with a data structure with fewer than a few hundred elements. And if your lists have 100k+ elements then you really need to consider all aspects of your algorithms. That, and from my experience memory is more of a limiting factor than CPU speed. A faster memory hogging algorithm might not be as good as a leaner but slower one depending on your use cases.

share|improve this answer

When you prototype a game function or an aspect of a game, you shouldn't worry about optimizing it at all.

In the course of prototyping it and learning about the idiosyncrasies of that functionality, the necessary optimizations will become obvious & will factor into the final design like 2nd nature... most of the time.

Don't sweat it.

share|improve this answer
    
"When you prototype a game function or an aspect of a game, you shouldn't worry about optimizing it at all." This is true sometimes but not always. Certain games, like Dead Rising, rely on fast execution to make the core game mechanic - hundreds of zombies in real-time - feasible. –  user744 Aug 31 '10 at 14:45
    
What percentage of game development is prototyping? Eventually you want to ship something, right? –  dash-tom-bang Sep 1 '10 at 19:08

Big-O notation is by definition asymptotic complexity - i.e., it shows how time scales when N (or whatever variables you have) gets "very" large. To re-iterate on Tetrad's comment (which I upped) "data is king". If N is "very large" in your specific situation, it matters, if N is "very small" it doesn't matter. Experience and practice will give you a feel for how to quantify "very large" and "very small".

Obviously, always profile first, and optimize last (unless you are doing a feature feasibility study).

share|improve this answer

It can be handy, but it can also be irrelevant. Take, for example, my most recent game, which is something of a Smash TV clone. Top-down game, monsters pour in from the sides, you shoot them.

Now there's a lot of clever ways to determine collisions. You can use KDtrees to partition out the space so you're not testing bullets against monsters that they couldn't possibly hit. And, sure, I could have been clever, and I could have done that.

But I was feeling lazy so I just compared every bullet against every monster. Even in the most hectic situations, the collision code was using far less than 10% of the game CPU at 60fps. Big-O: Unimportant.

Similarly, I had a 4x-style game where you built cities on islands, and sometimes the cities got destroyed. I could have been clever and tried to subtract the destroyed city's income from the income variables. But I didn't. I just wiped out the income and recalculated it from scratch every time something changed. Totally irrelevant in terms of CPU.

Big-O is just as important in games as it is in everything else: that is to say, utterly unimportant, right up until it becomes critical.

Go write some code. If it's too slow, then profile it.

share|improve this answer
    
+1 for real life examples –  Krom Stern Feb 20 '13 at 5:19

In the real world only raw performance counts. Now, the Big-O of an algorithm might serve as a first indication of what to use, but depending on the hardware the implementation might be terribly inefficient. For example doing a linear search can often be faster then a binary search because you get linear memory access and no branches.

Also, because of the current direction in multi-threaded platforms and architectures, Big-O is losing a lot of significance as it's only taking into account the vertical scalability of memory or data touches per operation instead of also taking into account into how the algorithm scales with a larger number of threads.

share|improve this answer
3  
This is incorrect, Big O notation is used to show upper bounds of parallel algorithms just the same as linear algorithms. Big O can be used for concurrent read/concurrent write architectures etc. You can even do crazy things like sorting in O(1) with n^2 processors hah –  David Young Aug 31 '10 at 8:13
    
David, do you have any real-life examples? I mean, I can also Big-O the number of apples a group of people can carry, but that doesn't mean that it's used or useful. From my experience, most of the time gamedev choose their (parallel) algorithms based on raw performance, not on their growth functions. –  Jasper Bekkers Aug 31 '10 at 9:20
3  
"sorting in O(1) with n^2 processors" I generally feel that this usage of O is misleading as the resource usage is still O(n^2) no matter what way you slice the problem. A larger number of threads does not only mean a larger number of cpu cycles per second. –  Richard Fabian Aug 31 '10 at 12:55
    
Sorting in O(1) with n^2 processors isn't the best example, this type of Big-O notation is probably most often seen in academia. Something like this cs.bu.edu/~best/crs/cs551/homeworks/hw1/pram.html More realistic parallel algorithms can use log(n) processors. This type of stuff is better suited to overloading onto GPU processing or super computing where there are hundreds of cores available. –  David Young Aug 31 '10 at 16:21
    
err I meant offloading, not overloading. Can't edit my original comment anymore. –  David Young Aug 31 '10 at 17:41

It shouldn't be the be-all and end-all. But it does help sort out obvious issues which could cause performance hits; why use something in O(n^2) time, when you can do the same thing in O(log n) time?

I think it applies to games more than most other industries, since the market is the one who would most notice speed problems. Someone using a word processor won't care if there is a half-second delay for doing action X, but gamers will probably go 'omg omg game Y is so slow it takes ages to do action Z'.

share|improve this answer

Big O matters most of the time, but sometimes an apparently "worse" algorithm in theory turns out to be much faster in practice.

Check out a great example from Tony Albrecht: http://seven-degrees-of-freedom.blogspot.com/2010/07/question-of-sorts.html

You find this all over the place in games development where the number of items in the operation is either so large that a very different algorithm is quicker, or so small that a dumber algorithm is sufficient (or fits in cache so well it overrides the efficiency of the better algorithm).

The problem with Big O is that it's a generic designation of complexity of the task and doesn't take into account the complexity of modern target hardware, nor does it offer any insight into the setup time overhead.

In many cases, the best optimal solution is two step. In practice, games developers tend to tend towards low O algorithms but balanced against cost in time developing, or debugging. Once you have a reasonable solution you always have to look at how the hardware is handling the task, and how to let the hardware get more done in less time.

share|improve this answer
    
"The problem with Big O" is that people seem to forget that it is algorithmic complexity wrt performance relative to large dataset sizes. In games we don't (usually) hit those values of N so we need to be concerned about the other pieces of the puzzle. I suspect that bubble sort will always outperform quicksort when you have a list of two elements. –  dash-tom-bang Aug 31 '10 at 16:46

When I'm coding in-engine, I'm often only concerned with a fixed n: I've already got a spacial partition limiting the number of objects receiving update(), physics(), and render() to approximately those on screen and surrounding areas. The maximum batch size is usually pretty well-defined per-game, although it invariably is a little bit larger than you've planned.

In this case I'm not as much concerned with big-O as I am concerned with the constant factor multiplier and lower-order terms. For a function with runtime like a*n^2 + b*n + c (which is O(n^2)), I'm often much more concerned with reducing a and possibly eliminating c. A setup or teardown cost c may become proportionally large vs. a small n.

However, this is not to say that big-O (or more particularly big-theta) is a great code smell indicator. See an O(n^4) somewhere, or worse yet an O(k^n) geometric time, and it's time to make sure you're considering other options.

I'm generally much more concerned about big-O optimality and jumping through hoops to find algorithms with lower big-O when I'm dealing with data make tools. While the number of objects in a given level/streaming area generally is well-defined, the total number of objects/art assets/configuration files/etc across an entire game may not be. It's also a lot larger number. Even running a parallel data make, we still wait on the order of a minute (I know, whine whine -- data make for consoles can take hours -- we're mostly small handheld games) to go through a jam data-clean && jam data cycle.

To give a specific example: this got really out of hand with a background tile-streaming algorithm that streams 8x8 256-color tiles. It's useful to share streaming buffers between background "layers", and we might have up to 6 of them in a given level sharing the same buffer. The problem is that estimating the size of the buffer needed is based on the possible positions of all 6 layers -- and if they're a prime-number width/height/scroll rate, you quickly start getting into an exhaustive search -- which starts approaching O(6^numTiles) -- which is in the "longer than the universe will be around" category in many cases. Fortunately most cases are just 2-3 layers, but even then, we're up above half an hour runtime. At the moment, we sample a very small subset of these possibilities, increasing granularity until a set amount of time has passed (or we've completed the task, which may happen for small double-layer configurations). We bump this estimate up a bit based on prior statistics of how often we've been proved wrong, and then add a bit of extra padding for good measure.

One other fun example: on a PC game a while back, the lead engineer experimented for a while with skip lists. The memory overhead ends up causing more cache effects, which adds a sort of non-constant multiplier to the whole affair -- so they're really not a good choices at all for small n. But for larger sorted lists where searches are frequent, they provide a benefit.

(I often find that the naive algorithm is higher big-O, faster on smaller data sets, and easier to understand; the more interesting/complex ones (e.g. patricia trie) are harder for people to understand and maintain, but higher performance on larger data sets.)

share|improve this answer

Big-O analysis is important, but it's not the first thing to think about in game development. Since making games involved lots of complicated code, I'd always recommend Code Simplicity as the first criteria for an algorithm. Algorithms with complicated bookkeeping just waste your time.

I think it's really important that your game always run at 60 fps during development. When you dip below that, the first thing you do is run a profiler. Once you find the bottleneck, you attack it. A lot of the time you need to do non-coding stuff like tell level designers to put less stuff in an area (and give them them tools for that).

Sometimes you actually identify some code that needs to be sped up. I find this to be fun engineering! I wish I had more opportunities to do this. And of course you want to iterate changing one thing at a time and measuring performance. The tipical problems I find are:

  1. Make sure you aren't calling new or malloc each frame (this is always the #1 problem)
  2. Reduce work: fewer ray casts, less guys, etc.
  3. Big-O algorithm type problems
  4. Cache coherency: Put stuff in arrays rather than scattered memory
  5. Don't use STL in debug mode. (and you always want debug mode to work)
share|improve this answer

In game (and most other) development, we are whining about one extra operation performed per loop:

for (int i = 0; i < array.length; i ++) { /* ... */ }

vs.

for (int i = 0, l = array.length; i < l; i ++) { /* ... */ }

Most modern games have physics, and you will find the n-body simulation problem. In a naive algorithm, it's O(n^2), but there is an optimization that makes it O(n log n) (but sacrifices some accuracy).

You could say, you are not programming gravity and particle interactions, but what about the team behavior of an army (of zombies) where they move dependent on others locations (in a more specific word: swarming)?

In a conventional collision detection algorithm, the time complexity is O(n^2), like the n-body. However, there is a better way: Separate the world to many small parts so only objects inside same part are collision- detected. See http://www.videotutorialsrock.com/opengl_tutorial/collision_detection/text.php .

If you game is scriptable, do NOT make the scripter write O(n^2) (and up) number-crunching algorithms in the script, such as searching the user's bag. Make a built-in function in the code instead.

share|improve this answer
1  
Both of your code examples are O(n). Big-O discussions have nothing to do with "one extra operation per loop," but rather "one extra search through everything per iteration of the loop over everything." –  dash-tom-bang Sep 1 '10 at 19:11

The importance of Big-O in your software is O(N2). As N grows, the importance of having the right algorithm grows even more. :)

share|improve this answer
    
Doesn't that depend on how often that algorithm is called..? –  bobobobo Feb 20 '13 at 18:08
    
To some degree. But if it takes 3 days to run, it probably doesn't matter if you only call it once. :) –  Kylotan Feb 20 '13 at 22:05

Big-O is just a guideline -- something that tells you the rough performance you can expect from an algorithm -- and how you should expect performance to scale as you increase the size of the dataset. You have to remember two main things with regard to Big-O:

1) If you have two algorithms that mostly do the same thing but one has a better O, you should probably go for that one (obviously)

2) Big O is concerned with asymptotic analysis. Big-O only really comes into play when n is large. For example, an O(n) algorithm can be very similar in performance to an O(n^2) one .. for small n. If you're talking about an algorithm that requires n^2 operations per vertex, but n=2 or n=3, then there is not much difference between an O(n^2) algorithm (taking 4 and 9 ops resp) and an O(n) one (2 and 3 ops resp.). However, if n=9, then you are suddenly talking about 81 operations for the O(n^2) algorithm and only 9 for the O(n) one -- a bigger difference -- and if n=100, then you are talking about 100 ops vs 10000 -- a much bigger difference.

So you must always consider Big-O in that light: it is meant to compare algorithms that do the same thing based on worst case performance as n gets large. The differences between the algorithms may be all but negligible when n is very small.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.