Beyond profiling

You probably know most of what I'm going to say, but I'll put it out there anyways.

1) Are all of your compiler optimization switches turned on? I'm assuming you're attempting to profile the release build version.
2) Have you looked at what the program is doing, and not just how fast it is doing it?
2a) Are the algorithms used efficient?
2b) Are the tasks that the algorithms are performing the correct tasks?
2c) Are there any redundant/unnecessary calculations being done?
3) Are your profiling techniques really covering everything?
3a) Is everything running as fast/slow as what would be expected?
3b) Do you have any reason to believe it should be running faster?

Sometimes, your system just doesn't have the horsepower to do what you want to do. If that's the case, you need to bite the bullet and raise a red flag saying you're screwed.

Quote:

Original post by Mantear You probably know most of what I'm going to say, but I'll put it out there anyways. 1) Are all of your compiler optimization switches turned on? I'm assuming you're attempting to profile the release build version. 2) Have you looked at what the program is doing, and not just how fast it is doing it? 2a) Are the algorithms used efficient? 2b) Are the tasks that the algorithms are performing the correct tasks? 2c) Are there any redundant/unnecessary calculations being done? 3) Are your profiling techniques really covering everything? 3a) Is everything running as fast/slow as what would be expected? 3b) Do you have any reason to believe it should be running faster? Sometimes, your system just doesn't have the horsepower to do what you want to do. If that's the case, you need to bite the bullet and raise a red flag saying you're screwed.

1. There are several different build modes in the project; I'm profiling exclusively against the fastest/most optimized mode.

2. Yes; unfortunately there's not much stuff that we can stop doing. Almost everything is critical, and that which is not critical has negligible performance impact in the first place.

2A. Usually; there are a few bits of low-hanging fruit here still but I'm not confident that they will be enough.

2B. Yes.

2C. Rarely, and most of those cases have been fixed following profiling

3. I haven't run any code-coverage tools but I do know that the vast bulk of the system is getting flexed, just by virtue of the nature of the program.

3A. Lots of things are slower than expected; the problem is that they are distributed across many functions and therefore don't appear as profile hotspots. Hunting these areas down by hand takes precious time, so I'm wondering if there's not a better way.

3B. Yeah - everyone else's games can manage to hit 30 FPS, so I should think that we can, too [wink]

I don't know if this will help you but a while ago i had a similiar problem, when running the application in Release mode would still had poor performance comparing with running it directly. (NB: this happened using Visual Studio)

Quote:

Original post by ApochPiQ 3A. Lots of things are slower than expected; the problem is that they are distributed across many functions and therefore don't appear as profile hotspots. Hunting these areas down by hand takes precious time, so I'm wondering if there's not a better way.

Don't your profiling tools allow you to break a functions cycle-count between inclusive and exclusive cycles? Inclusive being all cycles used within the function and any other function called within it, and exclusive being only cycles used within the function and not those used in other functions called within it. The tools I've used that do this can become tricky with full optimizations turned on as functions get inlined, etc, but it'll still point out your hotspots.

Can you combine some of the functions?
If there are so many functions perhaps the function-calls themselves become a problem, if they can't be inlined.

At this point, you have very few options. You can try and squeeze a bit of performance out by micro assembly tuning, but that is not going to give you 5x performance, especially if you are using a good compiler and have optimizeds your algorithms.

Your best bet is to trace the data paths in your process, and determine how data gets from point A to point B. Then determine if you have parallel paths that can be broken up into multiple threads/fibers. If find that you have a quite heavy load of parallel execution, you can even look into attempting to use CUDA as a possible solution. It just seems that multithreading naturally parallel data execution paths would be the only way you will realize 5-6x performance (that is, if you are not already doing this).

I am sure you have considered this, so feel free to ignore if you have already gone down this route.

Are you profiling on your dev machine? Dedicated hardware?

Is it possible that the test rig machine has old/bad drivers or something else that's precluding a good profile?

Personally, I've just thrown up my hands in this case. Mostly because I'm lazy, and don't make actual products.

Quote:

Original post by ApochPiQ So I'm curious - who has encountered situations like this, and what did you do? Are there any dirty tricks I can pull to help speed things up? Am I using my profilers to the best of their capabilities (i.e. is there something else I can do with them to help locate problem points)?

This sounds rather obvious, but still (and your post doesn't give too much to go on).. The best way to improve performance is to do less work. Find better algorithms, reduce problem instance sizes and precompute or cache stuff to avoid unnecessary ops.

If you're doing too much, you're doing too much.

I don't think my experience with profiling is at your level, but I'll attempt a bit of a brainstorm. Maybe something will shake loose.

Have you broken down the profile by time, rather than percentagewise? Usually proportion of time spent is what you want, but sometimes time values can jump out at you.

Are compiling to specific hardware? That's worth up to a 10% boost, but probably won't fly in the market.

Are there asynchronous calls that you are waiting for that might not show up in the profiler?

Would another compiler do better? You might squeeze a few % points out of hand porting the assembly.

Are you caching absolutely everything it makes sense to cache?

----
Im my experience, the step after optimizing based on profiling data is the drawing board. Sometimes you've made your design about as fast/efficient it can be, but that's just not fast enough.

I had to bite that bullet recently with some network code. It wasn't fun, but the result was worth it.

When this happens for me, usually it's because my issue is either at a lot lower level or a lot higher level than I thought to look at:
- Jumping around in memory access in many places completely killing the purpose of the computer's cache
- Same with code
- Copying large amounts of data too much, or many many chunks of small amounts of data way too much, when, though the memory cost is higher, doing the ol' double buffer trick solved the problem. Other solutions: Copy-on-write semantics, etc.
- Function is large enough in size that the compiler doesn't think it should inline (and is usually right), but it turns out this function is called a gazillion times.
- All your systems might need some heavy tweaking! Can you separate them and profile each one individually?
- To contrast other posts, maybe you're caching something that should be re-calculated every time instead?

I guess the point is that even though you're confident you're doing everything right, you're also confident that you're doing something wrong. There's nearly) always going to be some stupidly simple high level optimization, though whether it's feasible for your system or would require a complete applicaion or system rewrite is another story. Likewise, there are (nearly) always low-low level optimizations that can actually be a major benefit... but finding them isn't always so fun.

Whether it's some way I've gone wrong or not, profiling is like a first step for me, but eventually I hit the same place you have where nothing really sticks out and have to thing outside the profiling box. And sometimes, even though I know the answer is out there... I don't find it :/

Good luck!

[edit] If you haven't already, perhaps try compiling for "size" instead of "full optimization" or "speed".

We had several months of intensive optimization effort at the end of Dawn of War 2 to try and get performance where we wanted. We had an in house profiling tool which we found invaluable. We used macros to instrument our code and we could dump out profiling data for a run of the game and then view it as a hierarchical timeline view for a given frame in a custom C# app. The app would display a bar chart of frame times for a particular run of the game and then we could zoom in on spikes to identify why a particular frame was slow.

This was very useful for identifying general areas that were problematic (e.g. 'why are we spending 10ms searching for new targets when there are certain unit types on the map?'). It also picked up problems that would not be obvious from a sampling profiler, either because they didn't show up as one obvious expensive function or because they were only happening on certain frames and so were causing hitches that did not show up when averaged out across multiple frames by a sampling profiler. Having some kind of frame-based profiling tool is essential for optimizing games.

Without a custom tool like this you might be able to get some similar capabilities using PIX (assuming you're on a platform where PIX is available). PIX allows you to place user markers and view them on the timeline which might help spot problem areas. PIX is also very useful for optimizing rendering on the CPU side. If you have, for example, code that is sorting draw calls to eliminate redundant state changes, use PIX single frame captures to verify that it is working as expected. Take a reasonably simple scene and look through the entire single frame capture to help identify performance issues like redundant render target changes, duplicated calls and other 'bugs' that don't show up as errors but rather just reduce performance.

For GPU performance tuning NVPerfHUD is pretty useful. It lets you easily run experiments to identify where your major bottlenecks are, (CPU/vertex bound/pixel bound/texture bound?) and lets you see which shaders are particularly demanding. The timeline scrub with live update is also useful for verifying draw order and sanity checking of how your frame is built up.

In the last few months before ship when most of the game is pretty close to finished it's very useful to focus some optimization on the content side. We had automated overnight tools that would do scripted flyovers of the maps and produce 'heat maps' for the artists to see where frame rates were poor so they could focus on improving performance in those areas. Any info you can provide in your tools to the artists to help them identify performance issues caused by content - excessive use of decals, too many or too high res meshes, etc. - will allow them to optimize content without too much programmer involvement. Tools that help designers identify bottlenecks caused by overly complex scripts, pathfinding choke points, excessive numbers of units, etc. are also valuable.

If you have a QA team testing the game it's very useful to have them running profile captures at all times (if you have a tool that supports this) so they can provide you with captures if they experience poor performance while playtesting. Towards the end of development we had QA capturing profile runs every day, working through all the missions over the course of a week or so. We would have bi-weekly meetings with the senior programmers, artists and designers to identify problem areas in particular missions and assign people to address them. Generally you want to be focusing your efforts on the top performance issues in your actual shipping content, rather than on general optimization based on test levels or non-representative profiling runs.

Quote:

Original post by force_of_will I don't know if this will help you but a while ago i had a similiar problem, when running the application in Release mode would still had poor performance comparing with running it directly. (NB: this happened using Visual Studio)

We've seen similar things, but I'm running the app directly, not starting from VS.

Quote:

Original post by Mantear Don't your profiling tools allow you to break a functions cycle-count between inclusive and exclusive cycles? Inclusive being all cycles used within the function and any other function called within it, and exclusive being only cycles used within the function and not those used in other functions called within it. The tools I've used that do this can become tricky with full optimizations turned on as functions get inlined, etc, but it'll still point out your hotspots.

Sure; but I've been through the number of visits, self time, child time, et. al. using each as an indicator for potential problem areas. However, the kind of stuff that's showing up is that our main game loop function takes a lot of time (duh!) but that time is amortized across dozens of sub-functions. Even after accounting for inlining and compiler optimizations, there's just not a lot of time being spent in any one code path that can be reduced in scope.

Quote:

Original post by Erik Rufelt Can you combine some of the functions? If there are so many functions perhaps the function-calls themselves become a problem, if they can't be inlined.

Without going into a ton of detail on our code architecture, I don't think this is really a big issue for us. Overall the code is pretty well divided up in terms of function size and number of total function calls.

Quote:

Original post by arbitus At this point, you have very few options. You can try and squeeze a bit of performance out by micro assembly tuning, but that is not going to give you 5x performance, especially if you are using a good compiler and have optimizeds your algorithms. Your best bet is to trace the data paths in your process, and determine how data gets from point A to point B. Then determine if you have parallel paths that can be broken up into multiple threads/fibers. If find that you have a quite heavy load of parallel execution, you can even look into attempting to use CUDA as a possible solution. It just seems that multithreading naturally parallel data execution paths would be the only way you will realize 5-6x performance (that is, if you are not already doing this). I am sure you have considered this, so feel free to ignore if you have already gone down this route.

Yeah, parallelism is something we're trying to exploit, but adding a lot of parallel processing to existing serial code is a nightmare. Due to certain design choices, it can actually end up slowing us down because there's too much contention for shared resources - a nasty side effect of poor planning up front.

Quote:

Original post by Telastyn Are you profiling on your dev machine? Dedicated hardware? Is it possible that the test rig machine has old/bad drivers or something else that's precluding a good profile? Personally, I've just thrown up my hands in this case. Mostly because I'm lazy, and don't make actual products.

I'm personally profiling on my dev workstation, which is basically our target mid-range spec. However, we have quite a few other machines that exhibit the same slowness. Just by sheer probability this leads me to think that the problem is indeed in our code.

Quote:

Original post by clb This sounds rather obvious, but still (and your post doesn't give too much to go on).. The best way to improve performance is to do less work. Find better algorithms, reduce problem instance sizes and precompute or cache stuff to avoid unnecessary ops. If you're doing too much, you're doing too much.

At this point, anything that radically reduces code size is probably going to mean axed features, and that's a non-starter for a host of reasons that I can't really get in to.

Quote:

Original post by Valere I don't think my experience with profiling is at your level, but I'll attempt a bit of a brainstorm. Maybe something will shake loose. Have you broken down the profile by time, rather than percentagewise? Usually proportion of time spent is what you want, but sometimes time values can jump out at you. Are compiling to specific hardware? That's worth up to a 10% boost, but probably won't fly in the market. Are there asynchronous calls that you are waiting for that might not show up in the profiler? Would another compiler do better? You might squeeze a few % points out of hand porting the assembly. Are you caching absolutely everything it makes sense to cache? ---- Im my experience, the step after optimizing based on profiling data is the drawing board. Sometimes you've made your design about as fast/efficient it can be, but that's just not fast enough. I had to bite that bullet recently with some network code. It wasn't fun, but the result was worth it.

Yep, I've examined the performance from just about every angle I can, with 4 different tools now. We're past the point of obvious things jumping out, unfortunately.

We do some minor CPU detection for SIMD purposes, and usage of SIMD has helped notably in a few areas. However, we're limited on the CPU-specifics side because of minimum hardware requirements, etc.

Asynchronous calls are highlighted nicely in all of the profilers I've used. It's fairly straightforward to ignore (or focus on) async calls just by being selective in how you interpret the profiling data.

As far as compilers, we're limited again there for reasons I can't get in to.

We do a lot of application-level caching, and it helps - just not enough.

Massive design changes may indeed be necessary, but they're going to be a very hard sell.

This is a method I use in addition to the usual profilers:

(I'm gonna assume you're on a C++ project using msvc or gcc for a minute.)

You can add the compiler switches /GH /Gh to MSVC or -finstrumented-functions to gcc.

This will add a function call to the beginning and end of each function/method. You'll have to write the code to fetch the return address from the stack (IIRC this is easier than it sounds). The functions should for obvious reasons be pretty quick to execute. Usually I just fetch the address and store them in an array, along with the time when it happened (I use RDTSC for this since there's no way this code will make it into production).
For the return call, I just put down the time and 0 for the return address. This lets you reconstruct the callstack and the time it took in each function as a post process. The snag with this is that it is a bit intrusive. The more function calls you have the slower it gets. I've seen it take from 5% to about 50% extra with the instrumented build.

To turn the addresses into readable symbols, I use "nm" and a text lookup for gcc and Dbghelp for msvc.

At the end I use a cruddy little C# tool to view the results. Once you see the data you gather, you'll see how this tool has to work. Just be a little careful when computing the total time spent in recursive functions etc.

I use this method a lot when I'm trying to get things to run fast.

Sorry I'm not bringing any solution here, I just wanted to ask -- how do you end up to the point where you need 500% speed improvement? Not by "avoiding premature optimization" I hope.

I've been in your situation (a dire and ridiculous need of improvement of the framerate), trying to port a game from Xbox360 to the Wii. The game was already ridiculously heavy on the xbox, so on the wii it was a nightmare. We invested a lot of efforts in making the code more optimal, taking advantage of the wii when we could, but we wouldn't have made it without the support of the other departments (artists reducing the polygon count, designer reducing the enemy count, physics objects, etc, sound designers reducing the number of sounds, etc.) Retrospectively I'd say that almost any feature is worth removing for the sake of the holy frame rate. In the end, our game got a lot of negative criticism because of the inconsistent frame rate but almost no positive ones for the cool features responsible causing that issue in the first place...

Oh well... That was my 2 min of Anonymous Programmers.

Good luck

I used Intel Parallel Studio during the past few months. (the beta) It was pretty good for finding concurrency problems and was very easy to use: just click a button in Visual Studio's toolbar.

There was even an option to "parallelize" serial code into parallel code during compilation. Although it probably won't solve all your problems, but it might be worth a try.

You said you have tuned hotspots, that individual code paths are not easily improved, and so on.

I'll go through as many of the tricks I can recall.




First, are you certain you can actually accomplish your goal?

I'm assuming you have a target of a regular home computer. A reasonably equipped Windows PC at 30 FPS will give your game threads a total of about 50 million cycles per frame, or about 5 million bytes of non-streamed data per frame. You can exchange cycles for data. You can have a better 'exchange rate' for time and data with multithreading, but doing so reduces the total amount of both.

Come up with CPU budgets for roughly how long each subsystem actually takes, try to get the actual numbers out of your profiler. You may have to change your scope to fit within the actual hardware limits.

As a few people hinted, you may simply be trying to do too much for that hardware.





We'll assume it should be possible with your target hardware.


You said you have removed the obvious hotspots.
You said you tried to remove obvious bad algorithm choices.

The fastest functions are the ones you never run. Are you culling everything you can? Don't update systems when they are off screen. Don't animate models that aren't visible. Don't process occluded objects. Don't run complex AI on off-screen objects when a trivial ai (or even random number) is sufficient.

Keep your work load steady. Are you distributing your work evenly across frames? Limit yourself to running the pathfinder n times per frame. Limit your particle updates to exactly once per frame. Limit your AI to distribute the work over time.

Don't be idle. Are you blocking (waiting) for anything? Or do you have serious number-crunching that never really changes? Both could be changed to asynchronous calls.

Back in the old days there were asynchronous dividers and asynchronous floating point co-processors. Later there were asynchronous vector units. Today we have asynchronous rendering and asynchronous physics processing. It can be a major design change that comes too late, but it might make sense to have a dedicated number-crunching thread to fill in the time spent on other tasks. For example, it can do the repetitive work of updating particle systems. Even running at a lower priority, there is usually enough dead time spent in blocking operations that this can run before the main thread actually needs it.




You said that all your functions are individually small and fast, so next visit is the map file for the optimized build.

On the PC, you are less concerned about the size of your executable and more concerned about how it is used.

Analyze the sizes of the functions.

Inline all small functions. Any function smaller than the cost of calling it should be made inline. Generally this means all functions smaller than 64 bytes. You will need to measure it to find the details, but depending on the number of parameters there will be a few thresholds near 100, 150, and 200 bytes where it becomes faster to be inline rather than call. The exact number will be different based on the actual CPU, your compiler options, and the actual optimizations the optimizer takes.

When you are done, the only small functions left in the map file should be virtual functions that can't be inlined. Every one of those should be critically reviewed --- do you really need to use virtual functions for that?

Review all the large functions. Those are frequent sources of bugs, and can often be rewritten to execute faster or simpler.


Next in your map file, look for duplicate template functions that were not combined, focusing on those that are frequently used. The PC processor caches the branches it takes in code. If you can get your templates combined you get the benefit of a smaller executable, but can also have better branch prediction.

Still in your map file, look at the data.

Review the various static objects. Are any of them larger than you might expect? You might discover that an object hierarchy is much more complex than was anticipated, and therefore requires both more space and more processing than expected.

Is everything aligned on 4-byte boundaries? Are there gaps for padding? Those are symptoms of a bigger problem --- all your data needs to be cache friendly. See the next point for more on that.

Review your header files. Hopefully your team is strict about this, but some people will just throw data together in no particular order. Always sort your data largest to smallest, and align it on cache boundaries if possible. Your optimizer will do the rest.


This is a favorite of mine, since it misuses a tool for excellent results:

Use Doxygen, or a similar tool that can analyze how your objects are composed. Set the options to generate all the class diagrams, collaboration diagrams, and class hierarchies. Generate the comments to verify that all your source code was evaluated. Open the directory containing the generated diagram .png files, and sort by size (preferably by pixel size, but file size works well too). The largest diagrams represent parts of your system that you should try to simplify.

1. Does your tool chain support PGO?

2. If possible, get someone that's never seen the code to look at it after explaining the basic structure. There's a good chance they'll spot things that you haven't and question things that you've been taking for granted. Hopefully those things will be big. You need big things; I don't think you'll get 5x speedup by tweaking.

You would have to say quite a lot about your design, to get effective help.

But here's a brute force approach. Beg, borrow or steal a high Ghz, quad core system. Run your game and watch CPU utilization. If all the CPUs are pretty busy and game performance becomes acceptable - remember, this is a 4x improvement in available computes, here - then it's very likely you're simply trying to do too much. If performance stays poor - and especially if the CPUs aren't near to maxed out - then you have lock contention problems, bad assumptions involving polling for state changes at the wrong times, or other good old fashion "we're not getting it done because Sally is waiting for Frank, who's busy feeding Mary data" misdesign.

Another approach is the *experimental* feature cut. Turn off functionality, one feature at a time. If performance suddenly gets reasonable, take a good hard look at what just got cut - especially in terms of how much data it moves, what locks it uses, what resources it goes after. If, on the other hand, each cut makes a tiny improvement, but nothing ever makes a dramatic one, then you are very likely simply doing too much. Profilers can only tell you about the current mass of code - they can't predict what a change will do. Maybe some operation is smashing CPU caches and slowing everything else, in a uniformly bad way.

Combine functions where you can. The result is less elegant, but sometimes optimizers, when faced with very large projects, break down. It's possible you're spending a lot of time just setting up, and exiting, little functions. There's not much point in spending six instructions to set up a stack and call something, to do eight instructions worth of work. Look at the assembly listings for clues. Use a brute force approach if needed: write (gasp!) macros instead of proper functions, to absolutely force the effect of inlining, over the compiler's wishes. If that helps, you've been betrayed by a confused optimizer. (It can also hurt, but it's still an interesting experiment.)

And never, ever stop looking for the better algorithm. In almost every case, the algorithm rules the costs.

To get the performance gains your looking for (5-6x speedup), spot optimization will not do it, unless there is some ungodly function which is taking up 95% your time.

You have to analyze each subsystem, identify dependencies and do algorithm optimization, ie rewriting entire graphic pipelines, better multi-core utilization, cache computation, cheat, etc...

What kind of application/game are you working on? Platform?

Good Luck!

-ddn