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.

Assuming you already have the best-choice algorithm, what low-level solutions can you offer for squeezing the last few drops of sweet sweet frame rate out of C++ code?

It goes without saying that these tips only apply to that critical code section that you've already highlighted in your profiler, but they should be low-level non-structural improvements. I've seeded an example.

share|improve this question
1  
What makes this a game development question and not a general programming question like these: stackoverflow.com/search?q=c%2B%2B+optimization –  Danny Varod Jul 21 '10 at 19:01
    
@Danny - This probably could be a general programming question. It is also certainly a question related to games programming. I think it's a viable question on both sites. –  Smashery Jul 21 '10 at 23:03
    
@Smashery The only difference between the two is that game programming can require specific graphics engine level optimizations or shader coder optimizations, the C++ part is the same. –  Danny Varod Jul 23 '10 at 9:47
    
@Danny - True, some questions will be "more" relevant on one site or the other; but I wouldn't want to turn away any relevant questions just because they could also be asked on another site. –  Smashery Jul 26 '10 at 0:43

17 Answers 17

up vote 58 down vote accepted

Optimise your data layout! (This applies to more languages than just C++)

You can go pretty deep making this specifically tuned for your data, your processor, handling multi-core nicely, etc. But the basic concept is this:

When you are processing things in a tight loop, you want to make the data for each iteration as small as possible, and as close together as possible in memory. That means the ideal is an array or vector of objects (not pointers) that contain only the data necessary for the calculation.

This way, when the CPU fetches the data for the first iteration of your loop, the next several iterations worth of data will get loaded into the cache with it.

Really the CPU is fast and the compiler is good. There's not really much you can do with using fewer and faster instructions. Cache coherence is where it's at (that's a random article I Googled - it contains a good example of getting cache coherency for an algorithm that doesn't simply run through data linearly).

share|improve this answer
    
It's worth trying out the C example in the linked Cache coherence page. When I first found out about this I was shocked as to how much of a difference it makes. –  Neel Jul 22 '10 at 11:48
7  
See also the excellent Pitfalls of Object Oriented Programming presentation (Sony R&D) ( research.scee.net/files/presentations/gcapaustralia09/… ) -- and the cranky but fascinating CellPerformance articles by Mike Acton ( cellperformance.beyond3d.com/articles/index.html ). Noel Llopis's Games from Within blog also touches on this subject frequently ( gamesfromwithin.com ). I cannot recommend the Pitfalls slides enough... –  leander Aug 24 '10 at 2:24
2  
I'd just warn about "make the data for each iteration as small as possible, and as close together as possible in memory". Accessing non-aligned data can make things slower; in which case padding will give better performances. The order of data is important too, as well ordered data can lead to less padding. Scott Mayers can explain this better than I can though :) –  Jonathan Connell Aug 4 '11 at 9:45
    
+1 to the Sony presentation. I read that one before and it really gives sense at how to optimize data at the platform level, with consideration on splitting data into chunks and aligning it properly. –  ChrisC Oct 3 '11 at 19:11

Remove unnecessary branches

On some platforms and with some compilers, branches can throw away your whole pipeline, so even insignificant if() blocks can be expensive.

The PowerPC architecture (PS3/x360) offers the floating-point select instruction, fsel. This can be used in the place of a branch if the blocks are simple assignments:

float result = 0;
if (foo > bar) { result = 2.0f; }
else { result = 1.0f; }

Becomes:

float result = fsel(foo-bar, 2.0f, 1.0f);

When the first parameter is greater than or equal to 0, the second paramter is returned, else the third.

The price of losing the branch is that both the if{} and the else{} block will be executed, so if one is an expensive operation or dereferences a NULL pointer this optimisation is not suitable.

Sometimes your compiler has already done this work, so check your assembly first.

Here's more information on branching and fsel:

http://assemblyrequired.crashworks.org/tag/intrinsics/

share|improve this answer
    
float result = (foo > bar) ? 2.f : 1.f –  knight666 Jul 22 '10 at 11:52
3  
@knight666: That will still produce a branch anywhere that a longhand "if" would've done. I say it like that because on ARM, at least, small sequences like that can be implemented with conditional instructions which don;t require branching. –  chrisbtoo Jul 22 '10 at 13:40
1  
@knight666 if you're lucky the compiler can turn that into an fsel, but it's not certain. FWIW, I would normally write that snippet with a tertiary operator, and then later on optimise to fsel if the profiler agreed. –  tenpn Jul 22 '10 at 13:49
    
On IA32 you've got CMOVcc instead. –  Skizz Aug 23 '10 at 23:22
    
See also blueraja.com/blog/285/… (note that in this case, if the compiler is any good, it should be able to optimize this itself, so it's not something you normally have to worry about) –  BlueRaja - Danny Pflughoeft Jul 10 '11 at 8:26

Use SIMD (by SSE), if you don't do already. Gamasutra has a nice article on this. You can download the source code from the presented library at the end of the article.

share|improve this answer

Don't overlook your compiler -- if you are using gcc on Intel, you could easily get a performance gain by switching to the Intel C/C++ Compiler, for example. If you are targeting an ARM platform, check out ARM's commercial compiler. If you are on the iPhone, Apple just allowed Clang to be used starting with the iOS 4.0 SDK.

One issue that you will probably come into with optimization, especially on the x86, is that a lot of intuitive things end up working against you on modern CPU implementations. Unfortunately for most of us, the ability to out optimize the compiler is long gone. The compiler can schedule instructions in the stream based on it's own internal knowledge of the CPU. In addition, the CPU can also re-schedule instructions based on it's own needs. Even if you think of an optimal way to arrange a method, chances are the compiler or CPU has already come up with that on it's own and has already performed that optimization.

My best advice would be to ignore the low-level optimizations and focus on the higher level ones. The compiler and CPU can't change your algorithm from an O(n^2) to an O(1) algorithm, no matter how good they get. That's going to require you to look at exactly what you are trying to do and find a better way to do it. Let the compiler and CPU worry about the low level and you focus on the mid to high levels.

share|improve this answer
    
I see what you're saying, but there comes a point when you've reached O(logN) and you're not going to get any more out of structural changes, where the low-level optimisations can come into play and gain you that extra half a millisecond. –  tenpn Jul 21 '10 at 14:34
1  
See my answer re: O(log n). Also, if you look for half a millisecond, you might need to look at the higher level. That's 3% of your frame time! –  Rachel Blum Jul 21 '10 at 21:25

Remove unnecessary virtual function calls

The dispatch of a virtual function can be very slow. This article gives a good explaination of why. If possible, for functions that are called many many many times per frame, avoid them.

You can do this in a couple of ways. Sometimes you can just rewrite the classes to not need inheritence - maybe it turns out that MachineGun is the only subclass of Weapon, and you can amalgamate them.

You can use templates to replace run-time polymorphism with compile-time polymorphism. This only works if you know the subtype of your objects at runtime, and can be a major rewrite.

share|improve this answer

A very, very low-level tip, but one that can come in handy:

Most compilers support some form of explicit conditional hinting. GCC has a function called __builtin_expect which lets you inform the compiler what the value of a result probably is. GCC can use that data to optimize conditionals to perform as quickly as possible in the expected case, with slightly slower execution in the unexpected case.

if(__builtin_expect(entity->extremely_unlikely_flag, 0)) {
  // code that is rarely run
}

I've seen a 10-20% speedup with proper use of this.

share|improve this answer
    
I'd vote-up twice if I could. –  tenpn Jul 21 '10 at 16:53
5  
+1, The Linux kernel uses this extensively for microoptimizations in scheduler code, and it makes a significant difference in certain code paths. –  greyfade Jul 22 '10 at 4:53
    
Unfortunately, there seems to be no good equivalent in Visual Studio. stackoverflow.com/questions/1440570/… –  mmyers Jul 22 '10 at 14:41

My basic principle is: don't do anything that's not necessary.

If you've found that a particular function is a bottleneck, you could optimize the function -- or you could try to keep it from being called in the first place.

This does not necessarily mean you're using a bad algorithm. It might mean that you are running calculations every frame that could be cached for a short while (or entirely precalculated), for example.

I always try this approach before any attempts at really low-level optimization.

share|improve this answer
2  
This question assumes you've already done all the structural stuff you can. –  tenpn Jul 21 '10 at 16:27
2  
It does. But often you assume you have, and you haven't. So really, every time an expensive function needs to be optimized, ask yourself if you need to call that function. –  Rachel Blum Jul 21 '10 at 21:22
1  
...but sometimes it can actually be quicker to do the calculation even if you're going to throw away the result afterwards, rather than branch. –  tenpn Feb 24 '11 at 21:58

Reduce boolean expression evaluation

This one is really desperate, as it's a very subtle but dangerous change to your code. However if you have a conditional that is evaluated an inordinate number of times, you can reduce the overhead of boolean evaluation by using bitwise operators instead. So:

if ((foo && bar) || blah) { ... } 

Becomes:

if ((foo & bar) | blah) { ... }

Using integer arithmetic instead. If your foos and bars are constants or evaluated before the if(), this could be faster than the normal boolean version.

As a bonus the arithmetic version has less branches than the regular boolean version. Which is another way to optimize.

The big downside is that you lose lazy evaluation - the whole block is evaluated, so you can't do foo != NULL & foo->dereference(). Because of this, it's arguable that this is hard to maintain, and so the trade-off may be too great.

share|improve this answer
1  
That's a pretty egregious trade-off for the sake of performance, mainly because it's not immediately obvious that it was intended. –  Bob Somers Jul 22 '10 at 3:27
    
I almost completely agree with you. I did say it was desperate! –  tenpn Jul 22 '10 at 7:10
2  
Wouldn't this also break short-circuiting and make branch prediction more unreliable? –  egon Jul 22 '10 at 12:28
1  
If foo is 2 and bar is 1 then the code doesn't behave the same way at all. That, and not early evaluation, is the biggest downside I think. –  user744 Aug 11 '10 at 13:32
    
Do you know, you're absolutely right. So you need to know that either your foos and bars are all 1 or 0 (not guarenteed for booleans), or only use this for OR statements, or preferrably not do it all. :) –  tenpn Aug 12 '10 at 8:04

Keep an eye on your stack usage

Everything you add to the stack is an extra push and construction when a function is called. When a large amount of stack space is required, it can sometimes be beneficial to allocate working memory ahead of time, and if the platform you're working on has fast RAM available for use - all the better!

share|improve this answer

Use Compiler Intrinsics.

Ensure that the compiler is generating the most efficient assembly for certain operations by using intrinsics - constructs that look like function calls that the compiler turns into optimized assembly:

Here's a reference for Visual Studio, and here's one for GCC

share|improve this answer

First step: Think carefully about your data in relation to your algorithms. O(log n) is not always faster than O(n). Simple example: A hash table with only a few keys is often better replaced with a linear search.

Second step: Look at the assembly generated. C++ brings a lot of implicit code generation to the table. Sometimes, it sneaks up on you without you knowing.

But assuming it's really pedal-to-the-metal time: Profile. Seriously. Randomly applying "performance tricks" is about as likely to hurt as it is to help.

Then, everything depends on what your bottlenecks are.

data cache misses => optimize your data layout. Here's a good starting point: http://gamesfromwithin.com/data-oriented-design

code cache misses => Look at virtual function calls, excessive callstack depth, etc. A common cause for bad performance is the erroneous belief that base classes must be virtual.

Other common C++ performance sinks:

  • Excessive allocation/deallocation. If it's performance critical, don't call into the runtime. Ever.
  • Copy construction. Avoid wherever you can. If it can be a const reference, make it one.

All of the above are immediately obvious when you look at the assembly, so see above ;)

share|improve this answer

Avoid memory accesses and especially random ones at all costs.

That's the single most important thing to optimize for on modern CPUs. You can do a shitload of arithmetic and even a lot of wrong predicted branches in the time you wait for data from RAM.

You can also read this rule the other way around: Do as much calculations as possible between memory accesses.

share|improve this answer

The first thing you need to understand is the hardware you're running on. How does it handle branching? What about caching? Does it have a SIMD instruction set? How many processors can it use? Does it have to share processor time with anything else?

You may solve the same problem in very different ways - even your choice of algorithm should be dependent on the hardware. In some cases O(N) can run slower than O(NlogN) (depending on implementation).

As a crude overview of optimisation, the first thing I would do is look at exactly what problems and what data you are trying to solve for. Then optimise for that. If you want extreme performance then forget about generic solutions - you can special case everything that doesn't match your most used case.

Then profile. Profile, profile, profile. Look at memory usage, look at branching penalties, Look at function call overhead, look at pipeline utilisation. Work out what is slowing down your code. It's probably data access (I wrote an article called "The Latency Elephant" about the overhead of data access - google it. I can't post 2 links here as I don't have enough "reputation"), so closely examine that and then optimise your data layout (nice big flat homogeneous arrays are awesome) and data access (prefetch where possible).

Once you've minimised the overhead of the memory subsystem, try and determine if instructions are now the bottleneck (hopefully they are), then look at SIMD implementations of your algorithm - Structure-of-Arrays (SoA) implementations can be very data and instruction cache efficient. If SIMD isn't a good match for your problem then intrinsics and assembler level coding may be needed.

If you still need more speed then go parallel. If you have the benefit of running on a PS3 then the SPUs are your friends. Use them, love them. If you've already written a SIMD solution then you'll get a massive benefit moving to SPU.

And then, profile some more. Test in game scenarios - is this code still the bottleneck? Can you change the way this code is used at a higher level to minimise its usage (actually, this should be your first step)? Can you defer calculations over multiple frames?

Whatever platform you're on, learn as much as you can about the hardware and the profilers available. Don't assume that you know what the bottleneck is - find it with your profiler. And make sure you have a heuristic to determine if you have actually made your game go faster.

And then profile it again.

share|improve this answer

Const everything!

The more information you give the compiler about the data the better the optimizations are (at least in my experience).

void foo(Bar * x) {...;}

becomes;

void foo(const Bar * const x) {...;}

The compiler now knows that the pointer x is not going to change and that the data it is pointing to will not change either.

The other added benefit is that you can reduce the number of accidental bugs, stopping yourself (or others) modifying things that they shouldn't.

share|improve this answer
    
And your code buddy will love you! –  tenpn Jul 23 '10 at 14:13
4  
const does not improve compiler optimizations. True the compiler can generate better code if it knows a variable won't change, but const does not provide a strong enough guarantee. –  deft_code Jul 23 '10 at 15:04
3  
Nope. 'restrict' is far more useful than 'const'. See gamedev.stackexchange.com/questions/853/… –  Justicle Sep 14 '10 at 22:19
    
+1 ppl saying const cant help are wrong... infoq.com/presentations/kixeye-scalability –  NoSenseEtAl Aug 1 at 0:21

Most often, the best way to gain performance is to change your algorithm. The less general the implementation the closer you can get to the metal.

Assuming that has been done....

If it's really critical code indeed, try to avoid memory reads, try to avoid calculating stuff that can be precalculated (though no lookup tables as they violate rule number 1). Know what your algorithm does and write it in a way that the compiler knows it too. Check the assembly to be sure it does.

Avoid cache misses. Batch process as much as you can. Avoid virtual functions and other indirections.

Ultimately, measure everything. The rules change all the time. What used to speed up code 3 years ago now slows it down. A nice example is 'use double math functions instead of float versions'. I wouldn't have realized that one if I hadn't read it.

I forgot - don't have default constructors intialize your variables, or if you insist, at least also create constructors that don't. Be aware of the things that don't show up in the profiles. When you lose one unnecessary cycle per line of code nothing will show up in your profiler, but you'll lose a whole lot of cycles overall. Again, know what your code is doing. Make your core function lean instead of foolproof. Foolproof versions can be called if needed, but are not always needed. Versatility comes at a price - performance being one.

Edited to explain why no default initialization: A lot of code says: Vector3 bla; bla = DoSomething();

The intialization in the constructor is wasted time. Also, in this case the wasted time is small (probably clearing the vector), however if your programmers do this habitually it adds up. Also, a lot of function create a temporary (think overloaded operators), that gets initialized to zero and assigned after straight away. Hidden lost cycles that are too small to see a spike in your profiler, but bleed cycles all over your code base. Also, some people do a lot more in constructors (which is obviously a no-no). I've seen multi-millisecond gains from an unused variable where the constructor happened to be a bit on the heavy side. As soon as the constructor causes side effects the compiler won't be able to optmize it out, so unless you never use above code, I prefer either a non-initializing constructor, or, as I said, a version of the constructor that doesn't initialize.

Vector3 bla(noInit); bla = doSomething();

share|improve this answer
    
/Don't/ initialise your members in constructors? How does that help? –  tenpn Jul 24 '10 at 9:39
    
See edited post. Didn't fit in the comment box. –  Kaj Jul 24 '10 at 16:25
    
const Vector3 = doSomething()? Then the return-value optimisation can kick in and probably elise an assignment or two. –  tenpn Aug 23 '10 at 15:22

The restrict keyword is potentially handy, especially in cases where you need to manipulate objects with pointers. It allows the compiler to assume the pointed-to object is not going to get modified in any other way which in turn allows it to perform more aggressive optimisation such as keeping parts of the object in registers or reordering reads and writes more effectively.

One good thing about the keyword is that it's a hint which you can apply once and see benefits from without rearranging your algorithm. The bad side is that if you use it in the wrong place, you might see data corruption. But usually it's quite easy to spot where it's legitimate to use it - it's one of the few examples where the programmer can reasonably be expected to know more than the compiler can safely assume, which is why the keyword has been introduced.

Technically 'restrict' doesn't exist in standard C++, but platform-specific equivalents are available for most C++ compilers, so it's worth considering.

See also: http://cellperformance.beyond3d.com/articles/2006/05/demystifying-the-restrict-keyword.html

share|improve this answer

Minimize dependency chains to make better use of the CPU pipleline.

In simple cases the compiler may do this for you if you enable loop unrolling. However it often won't do it, especially when there's floats involved as reordering the expressions changes the result.

Example:

float *data = ...;
int length = ...;

// Slow version
float total = 0.0f;
int i;
for (i=0; i < length; i++)
{
  total += data[i]
}

// Fast version
float total1, total2, total3, total4;
for (i=0; i < length-3; i += 4)
{
  total1 += data[i];
  total2 += data[i+1];
  total3 += data[i+2];
  total4 += data[i+3];
}
for (; i < length; i++)
{
  total += data[i]
}
total += (total1 + total2) + (total3 + total4);
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.