Does Big O really matter?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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).

Answer 6

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.

Answer 7

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.

Answer 8

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'.

Answer 9

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.

Answer 10

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.)

Answer 11

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)

Answer 12

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.

Answer 13

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

Answer 14

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.