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 'normal' business programming optimization step is often left until really needed. Meaning you should not optmize until it is really needed.

Remember what Donald Knuth said "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil"

When is the time to optimize to make sure I am not wasting effort. Should I do it a method level? Class level? Module level?

Also what should my measurement of optimization? Ticks? Frame Rate? Total Time?

share|improve this question

11 Answers 11

up vote 16 down vote accepted

Where I've worked, we always use multiple levels of profiling; if you see a problem, you just move down the list a bit more until you figure out what's going on:

  • The "human profiler", aka just play the game; does it feel slow or "hitch" occasionally? Noticing jerky animations? (As a developer, note that you'll be more sensitive to some kinds of performance issues and oblivious to others. Plan extra testing accordingly.)
  • Turn on the FPS display, which is a sliding-window 5 second average FPS. Very little overhead to calculate and display.
  • Turn on the profile bars, which are just a series of quads (ROYGBIV colors) that represent different parts of the frame (e.g. vblank, preframe, update, collision, render, postframe) using a simple "stopwatch" timer around each section of code. To emphasize what we want, we set one screen width worth of bar to be representative of a 60Hz target frame, so it's really easy to see if you're e.g. 50% under budget (only a half-bar) or 50% over (the bar wraps and becomes one and a half bars). It's also pretty easy to tell what's generally eating most of the frame: red = render, yellow = update, etc...
  • Build a special instrumented build that inserts "stopwatch" like code around each and every function. (Note that you may take a massive performance, dcache, and icache hit when doing this, so it's definitely intrusive. But if you lack a proper sampling profiler or decent support on the CPU, this is an acceptable option. You can also be clever about recording a minimum of data on function enter/exit and rebuilding calltraces later.) When we built ours, we mimicked much of gprof's output format.
  • Best of all, run a sampling profiler; VTune and CodeAnalyst are available for x86 and x64, you've got various simulation or emulation environments that might give you data here.

(There's a fun story from a past year's GDC of a graphics programmer who took four pictures of himself -- happy, indifferent, annoyed, and angry -- and displayed an appropriate picture in the corner of the internal builds based on the framerate. The content creators quickly learned not to turn on complicated shaders for all of their objects and environments: they'd make the programmer angry. Behold the power of feedback.)

Note you can also do fun things like graph the "profile bars" continuously, so you can see spike patterns ("we're losing a frame every 7 frames") or the like.

To answer your question directly, though: in my experience, while it's tempting (and often rewarding -- I usually learn something) to rewrite single functions/modules to optimize number of instructions or icache or dcache performance, and we do actually need to do this sometimes when we've got a particularly obnoxious performance problem, the vast majority of the performance issues we deal with on a regular basis come down to design. For example:

  • Should we cache in RAM or reload from disk the "attack" state animation frames for the player? How about for each enemy? We don't have RAM to do them all, but disk loads are expensive! You can see the hitching if 5 or 6 different enemies pop in at once! (Okay, how about staggering spawning?)
  • Are we doing a single type of operation across all particles, or all operations across a single particle? (This is an icache/dcache tradeoff, and the answer isn't always clear.) How about pulling apart all the particles and storing the positions together (the famous "struct of arrays") vs keeping all particle data in one place ("array of structs").

You hear it until it becomes obnoxious in any university-level computer science courses, but: it really is all about the data structures and algorithms. Spending some time on algorithm and data flow design is going to get you more bang for the buck in general. (Make sure you've read the excellent Pitfalls of Object Oriented Programming slides from a Sony Developer Services fellow for some insight here.) This doesn't "feel" like optimization; it's mostly time spent with a whiteboard or UML tool or creating many prototypes, rather than making current code run faster. But it's generally much more worthwhile.

And another useful heuristic: if you're close to your engine's "core", it may be worth some extra effort and experimentation to optimize (e.g. vectorize those matrix multiplies!). The further from core, the less you should be worrying about that unless one of your profiling tools tells you otherwise.

share|improve this answer
  1. Use the right data structures and algorithms up front.
  2. Don't micro-optimize until you profile and know exactly where your hot spots are.
  3. Don't worry about being clever. The compiler already does all the little tricks you're thinking of ("Oh! I need to multiply by four! I'll shift left two!")
  4. Pay attention to cache misses.
share|improve this answer
1  
Relying on the compiler is only smart to a certain point. Yes, it will do some peephole optimizations you wouldn't think of (and couldn't do without assembly), but it is clueless about what your algorithm is supposed to do so it can't do intelligent optimizations. Also, you'd be surprised how much cycles you can win by implementing critical code in assembly or intrinsics....if you know what you're doing. Compilers aren't as smart as they're made out to be, they don't know things that you do unless you tell em explicitly everywhere (like using 'restrict' religiously). –  Kaj Aug 5 '10 at 5:19
1  
And again I must comment that if you only look for hot spots you'll miss out on a lot of cycles because you won't find any trickled out cycles across the board (for example smartpointers....dereferences anywhere, never showing up as a hotspot because effectively your whole program is a hotspot). –  Kaj Aug 5 '10 at 5:21
1  
I agree with both of your points, but I'd lump most of that under "use the right data structures and algorithms." If you're passing around ref-counted smart pointers everywhere and are bleeding cycles through counting, you've definitely picked the wrong data structure. –  munificent Aug 11 '10 at 23:56

Also remember however "premature pessimization". While there's no need to go hardcore on every line of code, there's justification for realizing you are actually working on a game, which has real-time performance implications.
While everyone tells you to measure and optimize the hot-spots, that technique won't show you performance that is lost in hidden places. For example, if every '+' operation in your code would take twice as long as it should, it won't show up as a hot-spot and thus you will never optimize it or even realize, however since it's being used allover the place it might cost you a lot of performance. You'd be surprised how many of those cycles trickle away without ever being detected. So be aware of what you do.
Apart from that, I tend to profile regularly to get an idea of what's there, and how much time is left per frame. To me time per frame is the most logical as it tells me directly where I'm at with framerate goals. Also try to find out where peaks are and what causes them - I prefer a stable framerate over a high framerate with spikes.

share|improve this answer
    
This seems so wrong to me. Sure, my '+' may take twice as long each time it's called, but this really only matters in a tight loop. Inside a tight loop, changing a single '+' can do orders of magnitude more than changing a '+' outside the loop. Why think about a tenth of a microsecond, when a millisecond can be saved? –  Wilduck Aug 5 '10 at 18:53
    
Then you don't understand the idea behind trickle loss. '+' (just as an example) is called hundreds of thousands of times per frame, not just in tight loops. If that loses a few cycles every time you lost a lot of cycles across the board, but it will never show up as a hotspot since the calls are evenly distributed across your codebase/execution path. So you're not talking about a tenth of a microsecond, but indeed thousands times those tenths of microseconds, adding up to multiple milliseconds. After going for the low hanging fruit (tight loops) I gained milliseconds this way more than once. –  Kaj Aug 5 '10 at 19:32
    
It's like a tap that drips. Why worry about saving that little drop? - "If your faucet is dripping at the rate of one drop per second, you can expect to waste 2700 gallons per year". –  Kaj Aug 5 '10 at 19:36
    
Oh, I guess it wasn't clear that I meant when operator+ was overloaded, so it would affect every '+' in the code - you indeed wouldn't want to optimize every '+' in the code. Bad example I guess....I meant it as an exaple for 'core functionality that gets called all over the place where the implementation might be slower than assumed, especially when hidden by operator overloading or other obfuscating C++ constructs'. –  Kaj Aug 5 '10 at 20:09

Once a game is ready to be released (either final or a beta), or it is noticeably slow, that's probably the best time to profile your app. Of course, you can always run the profiler at any point; but yes, premature optimization is the root of all evil. Unfounded optimization, too; you need actual data to show that some code is slow, before you should go try to "optimize" it. A profiler does that for you.

If you don't know about a profiler, learn it! Here's a good blog post demonstrating the usefulness of a profiler.

Most of game code optimization comes down to reducing the CPU cycles that you need for each frame. One way to do this is to just optimize every routine as you write it, and make sure it's as fast as possible. However, there is a common saying that 90% of the CPU cycles are spent in 10% of the code. This means that directing all of your optimization work to these bottleneck routines will have 10x the effect of optimizating everything uniformly. So how do you identify these routines? Profiling makes it easy.

Otherwise, if your small game is running at 200 FPS even though it has an inefficient algorithm in it, do you really have a reason to optimize? You should have a good idea of your target machine's specs, and make sure the game runs well on that machine, but anything beyond that is (arguably) wasted time that could be better spent coding or polishing the game.

share|improve this answer
    
While the low hanging fruit indeed tends to be in 10% of the code, and gets easily caught by profiling in the end, purely working by profiling for this will make you miss out on the routines that are called a lot but have just a little bit of bad code each - they won't show up in your profile but they bleed a lot of cycles per call. It really adds up. –  Kaj Aug 4 '10 at 23:06
    
@Kaj, Good profilers sum all of the hundreds of individual executions of the bad algorithm and show you the total. Next you'll say "But what if you had 10 bad methods and all called at 1/10th the frequency?" If you spend all of your time on those 10 methods, you'll be missing all of the low hanging fruit where you will get a much bigger bang for your buck. –  John McDonald Oct 28 '11 at 14:33

I find it useful to build profiling in. Even if you're not actively optimising it's good to have an idea on what is limiting your performance at any given time. Many games have some kind of overlayable HUD which displays a simple graphical chart (usually just a coloured bar) showing how long various parts of the game loop are taking each frame.

It would be a bad idea to leave performance analysis and optimisation to too late a late stage. If you've already built the game and you're 200% over your CPU budget and you can't find that through optimisation, you're screwed.

You need to know what the budgets are for graphics, physics, etc., as you write. You can't do that if you have no idea what your performance is going to be, and you can't guess at that without know both what your performance is, and how much slack there might be.

So build in some performance stats from day one.

As to when to tackle stuff - again, probably best not to leave it too late, lest you have to refactor half your engine. On the other hand, don't get too wrapped up in optimising stuff to squeeze out every cycle if you think you might change the algorithm entirely tomorrow, or if you haven't put real game data through it.

Pick off the low hanging fruit as you go along, tackle the big stuff periodically, and you should be fine.

share|improve this answer
    
To add to the ingame profiler (which I totally agree with), extending your ingame profiler to display multiple bars (for multiple frames) helps you correlate game behaviour to spikes and might help you find bottlenecks that won't show up in your average capture with a profiler. –  Kaj Aug 4 '10 at 23:04

If look at Knuth's quote in its context he goes on to explain, that we should optimize but with tools, like a profiler.

You should constantly profile and memory profile your application after the very basic architecture gets laid.

Profiling will not just help you increase the speed, it will help you find bugs. If your program suddenly drastically changes speed, this is usually because of a bug. If your not profiling it might go unnoticed.

The trick to optimizing is to do it by design. Don't wait till the last minute. Make sure the design of your program gives you the performance you need without really on nasty inner loop tricks.

share|improve this answer

For my project, I usually apply some VERY needed optimizations in my base engine. For example I always like to implement a good solid SIMD implementation using SSE2 and 3DNow! This ensures my floating point math is on cue with where I want it to be. Another good practice is to make a habit out of optimizations as you code instead of going back. Most of the time these little practices are just as time consuming as what you were coding anyway. Before coding a feature, make sure you research the most efficient way to do it.

Bottom line, in my opinion, its HARDER to make your code more efficient after it already suck.

share|improve this answer

I would say the easiest way would be using your common sense - if something looks like it's running slow, then have a look at it. See if it is a bottleneck.
Use a profiler to have a look at the speed functions are taking and how often they're being called.
There's absolutely no point optimizing or spending time trying to optimize something that doesn't need it.

share|improve this answer

If your code is running slow, then run a profiler and see what exactly is causing it to run slower. Or you could be proactive and already have a profiler running before you start to notice performance problems.

You will want to optimize when your framerate drops to a point that the game starts to suffer. Your most likely culprit will be your CPU being used up too much (100%).

share|improve this answer
    
I'd say GPU is just as likely as CPU. Indeed, depending on how tightly coupled things are, it's entirely possible to be heavily CPU bound in half the frame, and heavily GPU bound the other half. Dumb profiling may even show way less than 100% utilisation on either. Make sure your profiling is fine grained enough to show that (but not so fine grained as to be intrusive!) –  JasonD Aug 4 '10 at 21:14

You should optimize your code... as often as you need to.

What I've done in the past is just continuously run the game with profiling turned on (at the very least a framerate counter on screen at all times). If the game is getting slow (below your target framerate on your min spec machine, for example), turn on the profiler and see if any hot spots show up.

Sometimes it isn't the code. A lot of the problems I've run into the past have been gpu-oriented (granted, this was on the iPhone). Fillrate issues, too many draw calls, not batching enough geometry, inefficient shaders...

Other than inefficient algorithms for hard problems (i.e. pathfinding, physics), I've very rarely run into issues where the code itself was the culprit. And those hard problems should be things you spend a lot of your effort on getting the algorithm right and not worrying about smaller things.

share|improve this answer

For me is the best follow good prepared data model. And optimalization-before main step forward. I mean before start implementing something big new. Other reason for optimalization is when I'm loosing control on resources , App needs lot of CPU load/GPU load or memory and i don't know why :) or it's too much.

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.