1. Choose Appropriate Algorithms and Data Structures
Selecting a suitable data structure is crucial. If there are many insertions and deletions in a collection of randomly stored numbers, using a linked list is much faster. Arrays and pointer statements are closely related; generally, pointers are more flexible and concise, while arrays are more intuitive and easier to understand. For most compilers, the code generated using pointers is shorter and more efficient than that generated using arrays.
In many cases, pointer arithmetic can replace array indexing, which often results in faster and shorter code. Compared to array indexing, pointers generally make the code faster and occupy less space. The difference is even more pronounced when using multi-dimensional arrays. The following code (incomplete for example analysis) serves the same purpose but differs in efficiency.
// Example Code 1: Array Indexing
for(;;){
a = array[t++];
}
// Example Code 2: Pointer Arithmetic
p = array;
for(;;){
a = *(p++);
}The advantage of the pointer method is that after loading the address of the array into address p, only an increment operation on p is needed in each loop. In the array indexing method, a complex calculation to determine the array index based on the value of t must be performed in each loop.2. Reduce the Intensity of Calculations(1) Lookup Tables (A Must for Game Programmers)
A savvy game developer will generally avoid performing calculations in their main loop; they will calculate values beforehand and then reference them in the loop. See the example below:
Old Code:
long factorial(int i){
if (i == 0)
return 1;
else
return i * factorial(i - 1);
}New Code:
static long factorial_table[] = {1, 1, 2, 6, 24, 120, 720 /* etc */};
long factorial(int i){
return factorial_table[i];
}If the table is large and difficult to write, create an init function to generate the table temporarily outside the loop.
(2) Modulus Operations
a = a % 8;Can be changed to:
a = a & 7;Explanation: Bitwise operations can be completed in one instruction cycle, while most C compilers implement the “%” operation by calling a subroutine, resulting in longer code and slower execution. Typically, for modulus operations of 2^n, bitwise operations can be used instead.
(3) Square Operations
a = pow(a, 2.0);Can be changed to:
a = a * a;Explanation: In microcontrollers with built-in hardware multipliers (like the 51 series), multiplication is much faster than calculating squares, as floating-point square calculations are implemented via subroutine calls. In AVR microcontrollers with built-in hardware multipliers, such as ATMega163, multiplication can be completed in just 2 clock cycles. Even in AVR microcontrollers without built-in hardware multipliers, the subroutine for multiplication is shorter and faster than that for square calculations.
If calculating cubes, such as:
a = pow(a, 3.0);Change to:
a = a * a * a;The efficiency improvement is even more significant.
(4) Use Shifts for Multiplication and Division
a = a * 4;
b = b / 4;Can be changed to:
a = a << 2;
b = b >> 2;Generally, if multiplication or division by 2^n is needed, shifts can be used instead. In ICCAVR, if multiplying by 2^n, left shift code can be generated, while multiplication by other integers or division by any number calls multiplication/division subroutines. Using shifts results in more efficient code than calling multiplication/division subroutines. In fact, any multiplication or division by an integer can be achieved using shifts, such as:
a = a * 9;Can be changed to:
a = (a << 3) + a;Replacing original expressions with expressions that require less computation is a classic example:
Old Code:
x = w % 8;
y = pow(x, 2.0);
z = y * 33;
for (i = 0; i < MAX; i++){
h = 14 * i;
printf("%d", h);
}New Code:
x = w & 7; /* Bitwise operation is faster than modulus operation */
y = x * x; /* Multiplication is faster than square operation */
z = (y << 5) + y; /* Bitwise shift multiplication is faster than multiplication */
for (i = h = 0; i < MAX; i++){
h += 14; /* Addition is faster than multiplication */
printf("%d", h);
}(5) Avoid Unnecessary Integer Division
Integer division is the slowest among integer operations, so it should be avoided whenever possible. One way to reduce integer division is through chained division, where division can be replaced by multiplication. The downside of this replacement is that it may cause overflow when calculating products, so it should only be used for division within a certain range.
Bad Code:
int i, j, k, m;
m = i / j / k;Recommended Code:
int i, j, k, m;
m = i / (j * k);(6) Use Increment and Decrement Operators
When using increment and decrement operations, try to use the increment and decrement operators, as increment statements are faster than assignment statements. This is because, for most CPUs, incrementing or decrementing memory words does not require explicit load and store instructions, as shown in the following statement:
x = x + 1;Mimicking most microcomputer assembly languages, the generated code is similar to:
move A, x ; Load x from memory into accumulator A
add A, 1 ; Increment accumulator A by 1
store x ; Store the new value back to xIf using the increment operator, the generated code would be:
incr x ; Increment x by 1Clearly, without the need for load and store instructions, increment and decrement operations execute faster and are shorter in length.
(7) Use Compound Assignment Expressions
Compound assignment expressions (such as a -= 1 and a += 1) can generate high-quality program code.
(8) Extract Common Sub-expressions
In some cases, C++ compilers cannot extract common sub-expressions from floating-point expressions, as this would mean reordering the expressions. It is important to note that compilers cannot rearrange expressions according to algebraic equivalence before extracting common sub-expressions. In such cases, programmers must manually extract common sub-expressions (in VC.NET, there is a “global optimization” option that can accomplish this, but the effectiveness is uncertain). Bad Code:
float a, b, c, d, e, f;
// ...
e = b * c / d;
f = b / d * a;Recommended Code:
float a, b, c, d, e, f;
// ...
const float t(b / d);
e = c * t;
f = a * t;Bad Code:
float a, b, c, e, f;
// ...
e = a / c;
f = b / c;Recommended Code:
float a, b, c, e, f;
// ...
const float t(1.0f / c);
e = a * t;
f = b * t;3. Struct Member Layout Many compilers have options for “aligning struct members to word, double word, or quad word boundaries.” However, it is still necessary to improve the alignment of struct members, as some compilers may allocate space for struct members in an order different from their declaration. Some compilers do not provide these features or do not do so effectively. Therefore, to achieve the best struct and struct member alignment with minimal cost, the following methods are recommended:
(1) Sort by Data Type Length
Sort the members of the struct by their type length, placing longer types before shorter ones when declaring members. Compilers require long data types to be stored at even address boundaries. When declaring a complex data type (which includes both multi-byte and single-byte data), multi-byte data should be stored first, followed by single-byte data, to avoid memory holes.Compilers automatically align instances of structures at even memory boundaries.
(2) Pad Structs to the Longest Type Length Multiple
Pad structs to the nearest multiple of the longest type length. By doing this, if the first member is aligned, the entire struct will naturally be aligned. The following example demonstrates how to reorder struct members:
Bad Code, Normal Order:
struct{ char a[5]; long k; double x;} baz;Recommended Code, New Order with Manual Padding:
struct{ double x; long k; char a[5]; char pad[7];} baz;This rule also applies to the layout of class members.
(3) Sort Local Variables by Data Type Length
When compilers allocate space for local variables, their order is the same as their declaration order in the source code. Similar to the previous rule, longer variables should be placed before shorter ones. If the first variable is aligned, other variables will be stored consecutively without needing padding bytes for natural alignment. Some compilers do not automatically change the order of variables when allocating space, and some compilers cannot produce 4-byte aligned stacks, so 4-byte variables may not be aligned. The following example demonstrates the reordering of local variable declarations:
Bad Code, Normal Order:
short ga, gu, gi; long foo, bar; double x, y, z[3]; char a, b; float baz;Recommended Code, Improved Order:
double z[3]; double x, y; long foo, bar; float baz; short ga, gu, gi;(4) Copy Frequently Used Pointer Parameters to Local Variables
Avoid frequently using values pointed to by pointer parameters within functions. Since compilers do not know if there are conflicts between pointers, pointer parameters often cannot be optimized by the compiler. This means that data cannot be stored in registers and clearly occupies memory bandwidth. Note that many compilers have a “no conflict” optimization switch (in VC, you must manually add the compiler command line /Oa or /Ow), which allows the compiler to assume that two different pointers always have different contents, thus avoiding the need to save pointer parameters to local variables. Otherwise, save the data pointed to by the pointer to local variables at the beginning of the function and copy it back before the function ends if necessary.
Bad Code:
// Assume q != r
void isqrt(unsigned long a, unsigned long* q, unsigned long* r){
*q = a;
if (a > 0) {
while (*q > (*r = a / *q)) {
*q = (*q + *r) >> 1;
}
}
*r = a - *q * *q;
}Recommended Code:
// Assume q != r
void isqrt(unsigned long a, unsigned long* q, unsigned long* r){
unsigned long qq, rr;
qq = a;
if (a > 0) {
while (qq > (rr = a / qq)) {
qq = (qq + rr) >> 1;
}
}
rr = a - qq * qq;
*q = qq;
*r = rr;
}4. Loop Optimization(1) Fully Decompose Small Loops
To fully utilize the CPU’s instruction cache, small loops should be fully decomposed. Especially when the loop body itself is small, decomposing the loop can improve performance. Note: Many compilers cannot automatically decompose loops.
Bad Code:
// 3D Transformation: Multiply vector V by 4x4 matrix M
for (i = 0; i < 4; i++) {
r[i] = 0;
for (j = 0; j < 4; j++) {
r[i] += M[j][i] * V[j];
}
}Recommended Code:
r[0] = M[0][0] * V[0] + M[1][0] * V[1] + M[2][0] * V[2] + M[3][0] * V[3];
r[1] = M[0][1] * V[0] + M[1][1] * V[1] + M[2][1] * V[2] + M[3][1] * V[3];
r[2] = M[0][2] * V[0] + M[1][2] * V[1] + M[2][2] * V[2] + M[3][2] * V[3];
r[3] = M[0][3] * V[0] + M[1][3] * V[1] + M[2][3] * V[2] + M[3][3] * V[3];(2) Extract Common Parts For tasks that do not require the loop variable to participate in calculations, they can be placed outside the loop. These tasks include expressions, function calls, pointer arithmetic, array access, etc. All operations that do not need to be executed multiple times should be gathered together and performed in an init function.(3) Delay Functions Commonly used delay functions typically use incrementing forms:
void delay(void){
unsigned int i;
for (i = 0; i < 1000; i++);
}Change it to a decrementing delay function:
void delay(void){
unsigned int i;
for (i = 1000; i > 0; i--);
}Both functions have similar delay effects, but almost all C compilers generate code for the latter that is 1-3 bytes shorter, as almost all MCUs have instructions for zero jumps, and using the latter method can generate such instructions. The same applies when using while loops; using decrement instructions to control the loop will generate 1-3 fewer bytes of code than using increment instructions. However, if there are instructions in the loop that read/write arrays using the loop variable “i,” using a pre-decrement loop may cause array out-of-bounds issues, which should be noted.(4) While Loops and Do…While Loops
There are two forms of while loops:
unsigned int i = 0;
while(i < 1000){
i++;
// User program
}Or:
unsigned int i = 1000;
do{
i--;
// User program
}while(i > 0);
In these two loops, the code generated by the do…while loop is shorter than that of the while loop after compilation.(5) Loop Unrolling
This is a classic speed optimization, but many compilers (like gcc -funroll-loops) can automatically accomplish this, so optimizing it yourself may not yield significant results.
Old Code:
for (i = 0; i < 100; i++) {
do_stuff(i);
}New Code:
for (i = 0; i < 100;) {
do_stuff(i);
i++;
do_stuff(i);
i++;
do_stuff(i);
i++;
do_stuff(i);
i++;
do_stuff(i);
i++;
do_stuff(i);
i++;
do_stuff(i);
i++;
do_stuff(i);
i++;
}As can be seen, the comparison instruction (i < 100) is reduced from 100 times to 10 times in the new code, saving 90% of the loop time. However, note that for loops where intermediate variables or results are modified, compilers often refuse to unroll (to avoid liability), so you may need to do the unrolling yourself.
One more point to note is that on CPUs with internal instruction caches (like MMX chips), because the code for loop unrolling is large, it often causes cache overflow, leading to frequent swapping of unrolled code between the CPU’s cache and memory. Since cache speed is very high, this can actually slow down loop unrolling. Additionally, loop unrolling can affect vector operation optimization.
(6) Sort Cases in Switch Statements by Frequency of Occurrence
Switch statements can be converted into various algorithms. The most common are jump tables and comparison chains/trees. When a switch is converted using a comparison chain, the compiler generates nested if-else-if code and performs comparisons in order, jumping to the statement that meets the condition when matched. Therefore, case values can be sorted according to their likelihood of occurrence, placing the most likely first to improve performance. Additionally, it is recommended to use small consecutive integers in cases, as in such cases, all compilers can convert the switch into a jump table.
Bad Code:
int days_in_month, short_months, normal_months, long_months;
switch (days_in_month) {
case 28:
case 29:
short_months++;
break;
case 30:
normal_months++;
break;
case 31:
long_months++;
break;
default:
cout << "month has fewer than 28 or more than 31 days" << endl;
break;
}Recommended Code:
int days_in_month, short_months, normal_months, long_months;
switch (days_in_month) {
case 31:
long_months++;
break;
case 30:
normal_months++;
break;
case 28:
case 29:
short_months++;
break;
default:
cout << "month has fewer than 28 or more than 31 days" << endl;
break;
}(7) Convert Large Switch Statements to Nested Switch Statements
When a switch statement has many case labels, a wise approach to reduce the number of comparisons is to convert the large switch statement into nested switch statements. Place the frequently occurring case labels in one switch statement, which is the outermost of the nested switch statements, and place the relatively infrequent case labels in another switch statement. For example, the following code segment places the relatively infrequent cases in the default case label.
pMsg = ReceiveMessage();
switch (pMsg->type) {
case FREQUENT_MSG1:
handleFrequentMsg();
break;
case FREQUENT_MSG2:
handleFrequentMsg2();
break;
case FREQUENT_MSGn:
handleFrequentMsgn();
break;
default: // Nested part to handle infrequent messages
switch (pMsg->type) {
case INFREQUENT_MSG1:
handleInfrequentMsg1();
break;
case INFREQUENT_MSG2:
handleInfrequentMsg2();
break;
case INFREQUENT_MSGm:
handleInfrequentMsgm();
break;
}
}If there is a lot of work to be done in each case of the switch, replacing the entire switch statement with a table of function pointers would be more effective. For example, the following switch statement has three cases:
enum MsgType {Msg1, Msg2, Msg3}
switch (ReceiveMessage()) {
case Msg1:
// ...
case Msg2:
// ...
case Msg3:
// ...
}To improve execution speed, replace the above switch statement with the following code.
/* Preparation */
int handleMsg1(void);
int handleMsg2(void);
int handleMsg3(void);
/* Create an array of function pointers */
int (*MsgFunction[])() = {handleMsg1, handleMsg2, handleMsg3};
/* Replace the switch statement with the following more efficient code */
status = MsgFunction[ReceiveMessage()]();(8) Loop Transposition
Some machines have special instruction handling for JNZ (jump if not zero), which is very fast. If your loop is direction-insensitive, you can loop from large to small.
Old Code:
for (i = 1; i <= MAX; i++) {
// ...
}New Code:
i = MAX + 1;
while (--i) {
// ...
}However, be careful; if pointer operations use the value of i, this method may cause serious pointer out-of-bounds errors (i = MAX + 1;). Of course, you can correct this by performing addition or subtraction on i, but this would negate the speedup unless in cases like the following:
Old Code:
char a[MAX + 5];
for (i = 1; i <= MAX; i++) {
*(a + i + 4) = 0;
}New Code:
i = MAX + 1;
while (--i) {
*(a + i + 4) = 0;
}(9) Common Code Blocks
Some common processing modules often use a lot of if-then-else structures to meet various calling needs, which is not ideal. If the judgment statements are too complex, they will consume a lot of time, so the use of common code blocks should be minimized. (In any case, space optimization and time optimization are opposing forces — Dong Lou). Of course, if it is just a simple judgment like (3 == x), it is still permissible to use it appropriately. Remember, optimization is always about pursuing a balance, not going to extremes.
(10) Improve Loop Performance
To improve loop performance, it is very useful to reduce unnecessary constant calculations (such as calculations that do not change with the loop).
Bad Code (including invariant if() in for()):
for (i ... ) // Custom condition {
if (CONSTANT0) {
DoWork0(i); // Assume CONSTANT0 does not change
} else {
DoWork1(i); // Assume CONSTANT0 does not change
}
}Recommended Code:
if (CONSTANT0) {
for (i ... ) {
DoWork0(i);
}
} else {
for (i ... ) {
DoWork1(i);
}
}If the value of if() is already known, this can avoid repeated calculations. Although the branches in the bad code can be easily predicted, since the recommended code determines the branch before entering the loop, it can reduce reliance on branch prediction.(11) Choose Good Infinite Loops In programming, we often need to use infinite loops, and the two common methods are while(1) and for (;;). These two methods are completely equivalent, but which one is better? Let’s look at the compiled code:
Before Compilation:
while(1);
After Compilation:
mov eax, 1
test eax, eax
je foo + 23h
jmp foo + 18h
Before Compilation:
for (;;);
After Compilation:
jmp foo + 23h
Clearly, the for(;;) instruction is shorter, does not occupy registers, and has no checks or jumps, making it better than while(1).5. Enhance CPU Parallelism
(1) Use Parallel Code
Try to decompose long dependent code chains into several independent code chains that can be executed in parallel in pipeline execution units. Many high-level languages, including C++, do not reorder generated floating-point expressions, as this is a rather complex process. It is important to note that reordered code being consistent with the original code does not equate to consistent computational results, as floating-point operations lack precision. In some cases, these optimizations may lead to unexpected results. Fortunately, in most cases, the final result may only have the least significant bits (i.e., the lowest bits) incorrect.
Bad Code:
double a[100], sum;
int i;
sum = 0.0f;
for (i = 0; i < 100; i++) sum += a[i];
Recommended Code:
double a[100], sum1, sum2, sum3, sum4, sum;
int i;
sum1 = sum2 = sum3 = sum4 = 0.0;
for (i = 0; i < 100; i += 4) {
sum1 += a[i];
sum2 += a[i + 1];
sum3 += a[i + 2];
sum4 += a[i + 3];
}
sum = (sum4 + sum3) + (sum1 + sum2);
Note: The use of 4-way decomposition is because it utilizes 4 pipeline floating-point additions, with each segment occupying one clock cycle, ensuring maximum resource utilization.(2) Avoid Unnecessary Read/Write Dependencies
When data is saved to memory, read/write dependencies exist, meaning data must be read after it has been correctly written. Although CPUs like AMD Athlon have hardware that accelerates read/write dependency delays, allowing data to be read before it is written to memory, avoiding read/write dependencies and storing data in internal registers will be faster. In a long chain of mutually dependent code, avoiding read/write dependencies is particularly important. If read/write dependencies occur when operating on arrays, many compilers cannot automatically optimize the code to avoid them. Therefore, programmers are recommended to manually eliminate read/write dependencies. For example, introducing a temporary variable that can be stored in a register can lead to significant performance improvements. The following code is an example:
Bad Code:
float x[VECLEN], y[VECLEN], z[VECLEN];
// ...
for(unsigned int k = 1; k < VECLEN; k++) {
x[k] = x[k - 1] + y[k];
}
for(k = 1; k < VECLEN; k++) {
x[k] = z[k] * (y[k] - x[k - 1]);
}Recommended Code:
float x[VECLEN], y[VECLEN], z[VECLEN];
// ...
float t(x[0]);
for(unsigned int k = 1; k < VECLEN; k++) {
t = t + y[k];
x[k] = t;
}
t = x[0];
for (k = 1; k < VECLEN; k++) {
t = z[k] * (y[k] - t);
x[k] = t;
}6. Loop Invariant Computation For some calculations that do not require loop variables, they can be placed outside the loop. Many compilers can still do this, but they are hesitant to touch expressions that use intermediate variables. In many cases, you will need to do this yourself. For functions called within loops, any operations that do not need to be executed multiple times should be extracted and placed in an init function, called before the loop. Additionally, try to minimize feeding times; if parameters are not necessary, avoid passing them. If loop variables are needed, let them create a static loop variable that accumulates themselves, which will be faster.
Also, regarding struct access, based on Dong Lou’s experience, if two or more elements of a struct are accessed within a loop, it is necessary to establish an intermediate variable (this applies to C++ objects as well). See the example below:
Old Code:
total = a->b->c[4]->aardvark + a->b->c[4]->baboon + a->b->c[4]->cheetah + a->b->c[4]->dog;New Code:
struct animals * temp = a->b->c[4];
total = temp->aardvark + temp->baboon + temp->cheetah + temp->dog;Some older C compilers do not perform aggregation optimizations, while newer compilers that comply with ANSI standards can automatically complete this optimization. See the example:
float a, b, c, d, f, g;
// ...
a = b / c * d;
f = b * g / c;This writing is certainly acceptable, but without optimization:
float a, b, c, d, f, g;
// ...
a = b / c * d;
f = b / c * g;If written this way, a new compiler that complies with ANSI standards can calculate b/c only once and substitute the result into the second expression, saving one division operation.7. Explanation This strategy mainly considers the high demands for program execution speed in embedded development, so it is primarily aimed at optimizing program execution speed.
Note: Optimization has its focus; it is an art of balance, often at the cost of program readability or increased code length.