http://stackoverflow.com/questions/2074099/coding-practices-which-enable-the-compiler-optimizer-to-make-a-faster-program
http://andr0meda.com/plunge/?p=95
http://assemblyrequired.crashworks.org/2008/07/08/load-hit-stores-and-the-__restrict-keyword
They are my notes all in one place
.I have not yet tried any of the code snippets myself. I take them at
face value, to be tried as and when I'm called upon to do so. Memory Pools
Algorithms used to manage the heap are notoriously slow in some platforms (e.g., vxworks). Even worse, the time that it takes to return from a call to malloc is highly dependent on the current state of the heap. Therefore, any function that calls malloc is going to take a performance hit that cannot be easily accounted for. That performance hit may be minimal if the heap is still clean but after that device runs for a while the heap can become fragmented. The calls are going to take longer and you cannot easily calculate how performance will degrade over time. You cannot really produce a worse case estimate. The optimizer cannot provide you with any help in this case either. To make matters even worse, if the heap becomes too heavily fragmented, the calls will start failing altogether. The solution is to use memory pools (e.g., glib slices ) instead of the heap. The allocation calls are going to be much faster and deterministic if you do it right.For C++, may be writing or using custom allocators that employ pooling will work well.
Avoid Aliasing related slowdowns
Write to local variables and not output arguments! This can be a huge help for getting around aliasing slowdowns. For example, if your code looks likeBad void DoSomething(const Foo& foo1, const Foo* foo2, int numFoo, Foo& barOut)
{ for (int i=0; i<numFoo, i++)
{
barOut.munge(foo1, foo2[i]); }
} the compiler doesn't know that foo1 != barOut, and thus has to reload foo1 each time through the loop. It also can't read foo2[i] until the write to barOut is finished. You could start messing around with restrict'ed pointers, but it's just as effective (and much clearer) to do this:
GoodIt sounds silly, but the compiler can be much smarter dealing with the local variable, since it can't possible overlap in memory with any of the arguments. This can help you avoid the dreaded load-hit-store (mentioned by Francis Boivin in this thread).void DoSomethingFaster(const Foo& foo1, const Foo* foo2, int numFoo, Foo& barOut) { Foo barTemp = barOut; for (int i=0; i<numFoo, i++) { barTemp.munge(foo1, foo2[i]); } barOut = barTemp; }
Load Hit Store issues
- read a from memory A into register X
- do something with a in X -> becomes b
- write b from register X to memory B
- read c from memory C into register Y There is nothing wrong with the code, nor with the reasoning behind it. But the CPU does have a problem when it has to execute it. The reason is that C and B can be equal in value, pointing effectively to the same address in memory. This means that c is in fact intended to be b (or a part of b – instructions sometimes chop binary values into lower and upper word fragments).
This dependency is recognized in the L1 cache, since all write instructions to memory temporarily block the CPU from reading from that cache until the value is written. So before the CPU can start reading from ‘C’, it has to wait until b is written to ‘B’, which could be at the very same memory address. [If the CPU would not wait, the value used as c is potentially not the one written by the previous instruction to memory at address B, and any further program flow / calculation might be off.] This waiting can take up quite some time, from 40 to 80 cycles, depending on your CPU. Despite advances in bus-logic and increased Front-Side-Bus performance, writing into memory is usually one of the slowest operations in the instruction set.
int CauseLHS(int *ptrA) { int a, b; int *ptrB = ptrA; // B and A point to the same address *ptrA = 5; // write data to address ptrA b = *ptrB; // read that data back in again (won't be // available for 80 cycles) a = b + 10; // stalls! the data isn't available yet. }
Use __restrict keyword for pointers
Use pointer parameters only if necessary, and mark them restrict if possible. This helps alias analysis a lot because the programmer guarantees there is no alias (the interprocedural alias analysis is usually very primitive). Very small struct objects should be passed by value, not by reference.int slow(int *a, int *b) { *a = 5; *b = 7; return *a + *b; // LHS stall: the compiler doesn't // know whether a == b, so it has to // reload both before the add }
int fast(int * __restrict a, int * __restrict b) { *a = 5; *b = 7; // RESTRICT promises that a != b return *a + *b; // no stall; the compiler hangs onto // 5 and 7 in the registers. }
It bears repeating that __restrict is a promise you make to your compiler. If you break your promise, you can get incorrect results. If pointers pA and pB are __restrict, and pA == pB, that will cause mysterious bugs.For example, in the
fast() function above, if a does equal b, then the correct return value would be 14. However, the compiler won’t know that *b = 7 has changed the value of *a, and so you might actually get a return value of 12.Pay attention to order in which memory is accessed
#define N 1000000;
int matrix[N][N] = { ... };
//awesomely fast
long sum = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
sum += matrix[i][j];
}
}
//painfully slow
long sum = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
sum += matrix[j][i];
}
}Do IO in blocks
For example :-static const char Menu_Text[] = "\n"
"1) Print\n"
"2) Insert new customer\n"
"3) Destroy\n"
"4) Launch Nasal Demons\n"
"Enter selection: ";
static const size_t Menu_Text_Length = sizeof(Menu_Text) - sizeof('\0');
//...
std::cout.write(Menu_Text, Menu_Text_Length); Don't use printf family for constant data
Constant data can be output using a block write. Formatted write will waste time scanning the text for formatting characters or processing formatting commands. See above code example.Declare small functions as inline or macros
Loop Unrolling
Each loop has an overhead of incrementing and termination checking. To get an estimate of the performance factor, count the number of instructions in the overhead (minimum 3: increment, check, goto start of loop) and divide by the number of statements inside the loop. The lower the number the better.unsigned int sum = 0;
for (size_t i; i < BYTES_TO_CHECKSUM; ++i)
{
sum += *buffer++;
}unsigned int sum = 0;
size_t i = 0;
**const size_t STATEMENTS_PER_LOOP = 8;**
for (i = 0; i < BYTES_TO_CHECKSUM; **i = i / STATEMENTS_PER_LOOP**)
{
sum += *buffer++; // 1
sum += *buffer++; // 2
sum += *buffer++; // 3
sum += *buffer++; // 4
sum += *buffer++; // 5
sum += *buffer++; // 6
sum += *buffer++; // 7
sum += *buffer++; // 8
}
// Handle the remainder:
for (; i < BYTES_TO_CHECKSUM; ++i)
{
sum += *buffer++;
}Use boolean arithmetic instead of if statements.
Basically reduce if blocks.For example:-
bool status = true;
status = status && /* first test */;
status = status && /* second test */; Factor out variable allocation outside of loops
Declare static text (const literals) as static const
When variables are declared without thestatic, some
compilers may allocate space on the stack and copy the data from ROM.
These are two unnecessary operations. This can be fixed by using the static prefix.Avoid too many floating point to int conversions and vice versa.
They use different registers and converting from one type to another means calling the actual conversion instruction, writing the value to memory and reading it back in the proper register set.
Use const correctness as much as possible in your code.
It allows the compiler to optimize much better.In this document are loads of other optimization tips: CPP optimizations (a bit old document though)
Highlights:
- use constructor initialization lists
- use prefix operators (++i instead of i++)
- use explicit constructors
- inline functions
- avoid temporary objects
- be aware of the cost of virtual functions
- return objects via reference parameters
- consider per class allocation
- consider stl container allocators
- the 'empty member' optimization
- etc
Put functions that are used together in close physical proximity in source.
This increases the likelihood that they will be near each other in object files and near each other in your executable. This improved locality of instructions can help avoid instruction cache misses while running.Make most functions static.
If global variables are used, mark them static and constant if possible.
If they are initialized once (read-only), it's better to use an initializer list like static const int VAL[] = {1,2,3,4}, otherwise the compiler might not discover that the variables are actually initialized constants and will fail to replace loads from the variable with the constants.When writing tests with multiple conditions place the most likely one first.
if(a || b || c) should be if(b || a || c) if b is more likely to be true than the others. Compilers usually don't know anything about the possible values of the conditions and which branches are taken more (they could be known by using profile information, but few programmers use it).Using a switch is faster than doing a test like if(a || b || ... || z).
Check first if your compiler does this automatically, some do and it's more readable to have the if though.Data structure alignment
It is the way data is arranged and accessed in computer memory. It consists of two separate but related issues: data alignment and data structure padding. When a modern computer reads from or writes to a memory address, it will do this in word sized chunks (e.g. 4 byte chunks on a 32-bit system). Data alignment means putting the data at a memory offset equal to some multiple of the word size, which increases the system's performance due to the way the CPU handles memory. To align the data, it may be necessary to insert some meaningless bytes between the end of the last data structure and the start of the next, which is data structure padding.Profile, Profile, Profile
Then, and only then, you might want to start investigating the effects of telling the compiler how to use memory. Make 1 change at a time and measure its impact. Focus only on the hotspots.Yes, compiler writers are not from a race of coding giants and compilers contain mistakes and what should, according to the manual and according to compiler theory, make things faster sometimes makes things slower. That's why you have to take one step at a time and measure before- and after-tweak performance.
And yes, ultimately, you might be faced with a combinatorial explosion of compiler flags so you need to have a script or two to run make with various compiler flags, queue the jobs on the large cluster and gather the run time statistics. If it's just you and Visual Studio on a PC you will run out of interest long before you have tried enough combinations of enough compiler flags.
