对程序性能优化的小结
对程序性能优化的总结
1. 重中之重 - 算法优化：
程序性能优化最显著的优化方法是算法上的优化，算法的优化对性能的提升往往是一个数量级的，例如排序，冒泡的时间复杂度为O(N^2)，而快速排序的时间复杂度为O(Nlog(N))，这种性能的提供是非常明显的。
2. 消除冗余的循环：
我们先看一下for循环生成的汇编代码for (int N = 4， i = 0; i < N; ++i){}
15 movl $4, -4(%ebp) // N = 4
16 movl $0, -8(%ebp) // i = 0
17 jmp .L2
18 .L3:
19 addl $1, -8(%ebp) // ++i
20 .L2:
21 movl -8(%ebp), %eax
22 cmpl -4(%ebp), %eax // i - N
23 setl %al
24 testb %al, %al
25 jne .L3
从上面的汇编代码中可以看出每次执行循环的时候都要执行19到25行这6汇编指令，因此减少循环可以提高程序性能。
例如上面的代码可以写成如下开形式：
for(int N = 4, i = 0; i < N; i += 2)
{
operate (i);
operate (i + 1);
}
3. 减少过程函数调用：
我们知道程序中函数调用的开销是非常大的，我们看一下简单的函数调用的开销：
int add ( int a , int b)
{
return a + b;
}
其汇编代码如下：
5 _Z3addii:
6 .LFB0:
7 .cfi_startproc
8 .cfi_personality 0x0,__gxx_personality_v0
9 pushl %ebp
10 .cfi_def_cfa_offset 8
11 movl %esp, %ebp
12 .cfi_offset 5, -8
13 .cfi_def_cfa_register 5
14 movl 12(%ebp), %eax //取b
15 addl %eax, 8(%ebp) // a += b
16 popl %ebp
17 ret
从汇编代码中可以看出函数调用的开销是非常大的。
假设有一个程序
const int NUM = 100;
int GetNum()
{
return NUM;
}
for (int i = 0; i < GetNum(); ++i)
{
//TODO...
}
最优化的写法是
int iNum = GetNum();
for (int i = 0; i < iNum; ++i)
{
//TODO...
}
当然这种写法的前提是GetNum()的数值在执行for的时候是没有变化的。
4. 消除不必要的存储器引用 ：
void add(int * array , int len , int * res)
{
* res = 0;
for (int i = 0; i < len; ++i)
{
*res += array[i];
}
}
其汇编代码（去掉for)
19 movl 12(%ebp), %ebx // %ebx，存len的地址
20 movl 16(%ebp), %edx // %edx, 存*res的地址
21 movl $0, (%edx) // 写mem
22 testl %ebx, %ebx
23 jle .L4
24 movl $0, %eax // i = 0;
25 .L3:
26 movl (%esi,%eax,4), %ecx // 取array[i]
27 addl %ecx, (%edx) // +=，写mem
28 addl $1, %eax //
29 cmpl %ebx, %eax
30 jne .L3
从上面的汇编代码分析中可以看出，每次for循环都进行了写内存。我们知道读写内存是非常耗时的，因此可以对其进行优化。
void add(int * array , int len , int * res)
{
int sum = 0;
for (int i = 0; i < len; ++i)
{
sum += array[i];
}
*res = sum;
}
//汇编
53 movl 12(%ebp), %ecx
54 movl $0, %eax
55 movl $0, %edx // sum = 0
56 testl %ecx, %ecx
57 jle .L8
58 .L11:
59 addl (%ebx,%eax,4), %edx // sum += array[i];， 只写寄存器
60 addl $1, %eax
61 cmpl %ecx, %eax
62 jne .L11
63 .L8:
64 movl 16(%ebp), %eax
优化后的代码在循环中少了一次寄存器的读写。
注意上面的代码是经过了-O选项优化的。
5. 增强流水线处理能力。
现在的处理器，每个核心在会有多个执行单元，相互之间采用流水线的执行方式，如果前后两个操作没有依赖关系，可以并行执行。
考虑一个求和的for循环
int Array[N]; 假设N为偶数
int sum = 0
for (int i = 0; i < N; ++i)
{
sum += Array[i];
}
将其流水线化可以表示如下：
int sum1 = 0;
int sum2 = 0;
for (int i = 0; i < N; i += 2)
{
sum1 += Array[i];
sum2 += Array[i + 1];
}
sum1 += sum2;
由于
sum1 += Array[i];
sum2 += Array[i + 1];
是没有相互依赖的，因此可以流水线执行。
6. cache对程序性能的影响
参看本人关于“矩阵乘积的并行”算法的讨论 http://blog.csdn.net/realxie/article/details/7260072
7. 性能调试工具：
gprof .
$ g++ program.cpp -o program -pg
$ ./program
$ gprof program;
注意一定要带-pg参数
1. 重中之重 - 算法优化：
程序性能优化最显著的优化方法是算法上的优化，算法的优化对性能的提升往往是一个数量级的，例如排序，冒泡的时间复杂度为O(N^2)，而快速排序的时间复杂度为O(Nlog(N))，这种性能的提供是非常明显的。
2. 消除冗余的循环：
我们先看一下for循环生成的汇编代码for (int N = 4， i = 0; i < N; ++i){}
15 movl $4, -4(%ebp) // N = 4
16 movl $0, -8(%ebp) // i = 0
17 jmp .L2
18 .L3:
19 addl $1, -8(%ebp) // ++i
20 .L2:
21 movl -8(%ebp), %eax
22 cmpl -4(%ebp), %eax // i - N
23 setl %al
24 testb %al, %al
25 jne .L3
从上面的汇编代码中可以看出每次执行循环的时候都要执行19到25行这6汇编指令，因此减少循环可以提高程序性能。
例如上面的代码可以写成如下开形式：
for(int N = 4, i = 0; i < N; i += 2)
{
operate (i);
operate (i + 1);
}
3. 减少过程函数调用：
我们知道程序中函数调用的开销是非常大的，我们看一下简单的函数调用的开销：
int add ( int a , int b)
{
return a + b;
}
其汇编代码如下：
5 _Z3addii:
6 .LFB0:
7 .cfi_startproc
8 .cfi_personality 0x0,__gxx_personality_v0
9 pushl %ebp
10 .cfi_def_cfa_offset 8
11 movl %esp, %ebp
12 .cfi_offset 5, -8
13 .cfi_def_cfa_register 5
14 movl 12(%ebp), %eax //取b
15 addl %eax, 8(%ebp) // a += b
16 popl %ebp
17 ret
从汇编代码中可以看出函数调用的开销是非常大的。
假设有一个程序
const int NUM = 100;
int GetNum()
{
return NUM;
}
for (int i = 0; i < GetNum(); ++i)
{
//TODO...
}
最优化的写法是
int iNum = GetNum();
for (int i = 0; i < iNum; ++i)
{
//TODO...
}
当然这种写法的前提是GetNum()的数值在执行for的时候是没有变化的。
4. 消除不必要的存储器引用 ：
void add(int * array , int len , int * res)
{
* res = 0;
for (int i = 0; i < len; ++i)
{
*res += array[i];
}
}
其汇编代码（去掉for)
19 movl 12(%ebp), %ebx // %ebx，存len的地址
20 movl 16(%ebp), %edx // %edx, 存*res的地址
21 movl $0, (%edx) // 写mem
22 testl %ebx, %ebx
23 jle .L4
24 movl $0, %eax // i = 0;
25 .L3:
26 movl (%esi,%eax,4), %ecx // 取array[i]
27 addl %ecx, (%edx) // +=，写mem
28 addl $1, %eax //
29 cmpl %ebx, %eax
30 jne .L3
从上面的汇编代码分析中可以看出，每次for循环都进行了写内存。我们知道读写内存是非常耗时的，因此可以对其进行优化。
void add(int * array , int len , int * res)
{
int sum = 0;
for (int i = 0; i < len; ++i)
{
sum += array[i];
}
*res = sum;
}
//汇编
53 movl 12(%ebp), %ecx
54 movl $0, %eax
55 movl $0, %edx // sum = 0
56 testl %ecx, %ecx
57 jle .L8
58 .L11:
59 addl (%ebx,%eax,4), %edx // sum += array[i];， 只写寄存器
60 addl $1, %eax
61 cmpl %ecx, %eax
62 jne .L11
63 .L8:
64 movl 16(%ebp), %eax
优化后的代码在循环中少了一次寄存器的读写。
注意上面的代码是经过了-O选项优化的。
5. 增强流水线处理能力。
现在的处理器，每个核心在会有多个执行单元，相互之间采用流水线的执行方式，如果前后两个操作没有依赖关系，可以并行执行。
考虑一个求和的for循环
int Array[N]; 假设N为偶数
int sum = 0
for (int i = 0; i < N; ++i)
{
sum += Array[i];
}
将其流水线化可以表示如下：
int sum1 = 0;
int sum2 = 0;
for (int i = 0; i < N; i += 2)
{
sum1 += Array[i];
sum2 += Array[i + 1];
}
sum1 += sum2;
由于
sum1 += Array[i];
sum2 += Array[i + 1];
是没有相互依赖的，因此可以流水线执行。
6. cache对程序性能的影响
参看本人关于“矩阵乘积的并行”算法的讨论 http://blog.csdn.net/realxie/article/details/7260072
7. 性能调试工具：
gprof .
$ g++ program.cpp -o program -pg
$ ./program
$ gprof program;
注意一定要带-pg参数