深入理解计算机系统学习笔记（2）之程序优化
序言
写程序最主要的目的是使程序在所有可能的情况下都能正确地运行。一个运行很快但是运行结果错误的程序是没有用处的。如何编写高效的程序？首先必须选择一组合适的算法和数据结构，其次才是编写初编译器能够有效优化使得程序能够高效可执行。
编译器优化
现在主要的一些编译器，比如GCC，都允许程序定制优化选项，比如说编译程序的时候添加“-O1”,”-O2”和”-O3”，其中“-O1”为基本的优化，”-O2”和”-O3”是更全面的优化，一般来说我们都会选取前两级优化就可以满足要求。看下下面的这个程序，看看没有添加优化选项和添加优化选项的程序运行时间的对比。这个例子不具有普遍性。程序来自(http://cenalulu.github.io/linux/about-denormalized-float-number/)这篇博文讨论的关于浮点方面的知识。
#include <iostream>
#include <string>
using namespace std;
int main() {
const float x=1.1;
const float z=1.123;
float y=x;
for(int j=0;j<90000000;j++)
{
y*=x;
y/=z;
y+=0;
y-=0;
}
return 0;
}首先我们用不带优化选项的GCC编译下
g++ -Wall float.cpp -o float 然后我们运行下，前缀加time可以查看运行时间
time ./float
real 0m9.943s
user 0m9.949s
sys 0m0.000s
居然接近10s，至于为什么运行那么慢，可以参考这篇博文(http://cenalulu.github.io/linux/about-denormalized-float-number/)，那么我们用-O1优化级别试试，看看程序运行时间有没缩短。
g++ -Wall -O1 float.cpp -o float
time ./float
real 0m0.067s
user 0m0.064s
sys 0m0.004s吓傻了，居然只需要67ms，这个运行速度跟上面博文把程序稍微改动下的运行速度更快。我们再试试-O2和-O3优化
g++ -Wall -O2 float.cpp -o float
real 0m0.002s
user 0m0.002s
sys 0m0.000s
2ms！！！这样就无须三级优化了。上面并没有验证程序正确性。一般来说，程序优化选择-O2即可满足。
消除循环的低效率
这类优化成为代码移动(code motion),这类优化就是把循环体内将需要被多次求值的部分移动到循环体外。比如下面这个程序，在for循环内调用了vec_length(v)函数，这样每次循环迭代，都要必须调用函数求值
typedef int data_t;
typedef struct {
long int len;
data_t *data;
}vec_rec, *vec_ptr;
void combine1(vec_ptr v, data_t *dest){
long int i;
*dest = 0;
for (i = 0; i < vec_length(v); ++i)
{
data_t val;
get_vec_element(v, i, &val);
*dest = *dest + val;
}
}下面的程序就是对上面的程序的优化，改进循环测试的效率。
void combine2(vec_ptr v, data_t *dest){
long int i;
*dest = 0;
long int length = vec_length(v);
for (i = 0; i < length; ++i)
{
data_t val;
get_vec_element(v, i, &val);
*dest = *dest + val;
}
}再看下下面的极端程序，程序功能将大写字母转换成小写。
void lower1(char *s){
for (int i = 0; i < strlen(s); ++i)
{
if(s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
}
}很简单的一个程序，但是算下时间复杂度，假如字符串的长度为n，乍一看好像是O(n)，其实是
void lower2(char *s){
long int length = strlen(s);
for (int i = 0; i < length; ++i)
{
if(s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
}
}下面这个图就是两个程序随着字符串的长度变化，程序运行时间的对比。
减少过程调用
过程调用会带来很大的开销，而且妨碍大多数形式的程序优化。下面的程序为例
int get_vec_element(vec_ptr v, long int index, data_t *dest){
if(index < 0 || index >= v->len)
return 0;
*dest = v->dada[index];
return 1;
}
void combine2(vec_ptr v, data_t *dest){
long int i;
*dest = 0;
long int length = vec_length(v);
for (i = 0; i < length; ++i)
{
data_t val;
get_vec_element(v, i, &val);
*dest = *dest + val;
}
}从combine2的代码可以看出，循环每次迭代都会调用get_vec_element来获取下一个向量的元素。而且函数内还需要对index做边界检查。改进的程序在循环体外获取数组的起始地址，在循环体内就是简单的直接操作数组即可。改进的程序如下：
data_t *get_vec_start(vec_ptr v)
{
return v->data;
}
void combine3(vec_ptr v, data_t *dest){
long int i;
*dest = 0;
long int length = vec_length(v);
data_t *data = get_vec_start(v);
for (i = 0; i < length; ++i)
{
*dest = *dest + data[i];
}
}消除不必要的存储器引用
同样是关注循环体内的代码，注意的是这里的代码是浮点格式的乘法运算
#include <stdio.h>
#include <stdlib.h>
typedef float data_t;
typedef struct {
long int len;
data_t *data;
}vec_rec, *vec_ptr;
long int vec_length(vec_ptr v){
return v->len;
}
data_t *get_vec_start(vec_ptr v)
{
return v->data;
}
void combine3(vec_ptr v, data_t *dest){
long int i;
long int length = vec_length(v);
data_t *data = get_vec_start(v);
*dest = 0;
for (i = 0; i < length; ++i)
{
*dest = *dest * data[i];
}
}
用gcc 将上述代码转换成汇编
gcc -O1 -S test.c汇编的代码为：
.file "test.c"
.text
.globl vec_length
.type vec_length, @function
vec_length:
.LFB39:
.cfi_startproc
movq (%rdi), %rax
ret
.cfi_endproc
.LFE39:
.size vec_length, .-vec_length
.globl get_vec_start
.type get_vec_start, @function
get_vec_start:
.LFB40:
.cfi_startproc
movq 8(%rdi), %rax
ret
.cfi_endproc
.LFE40:
.size get_vec_start, .-get_vec_start
.globl combine3
.type combine3, @function
combine3:
.LFB41:
.cfi_startproc
movq (%rdi), %rdx
movq 8(%rdi), %rcx
movl $0x00000000, (%rsi)
testq %rdx, %rdx
jle .L3
movq %rcx, %rax
leaq (%rcx,%rdx,4), %rdx
.L5:
movss (%rsi), %xmm0
mulss (%rax), %xmm0
movss %xmm0, (%rsi)
addq $4, %rax
cmpq %rdx, %rax
jne .L5
.L3:
rep ret
.cfi_endproc
.LFE41:
.size combine3, .-combine3
.ident "GCC: (Ubuntu 4.8.2-19ubuntu1) 4.8.2"
.section .note.GNU-stack,"",@progbits
感觉各种看不懂，不过如果学过汇编语言，上面的代码看懂还是没问题的。不过因为这里我只关注循环体内的代码，所以看看循环体内的汇编
.L5:
movss (%rsi), %xmm0 从%rsi寄存器读取数值放到寄存器%xmm0中
mulss (%rax), %xmm0 两个数相乘，结果写入%xmmo寄存器中
movss %xmm0, (%rsi) 把相乘的结果再写入%rsi寄存器
addq $4, %rax
cmpq %rdx, %rax
jne .L5上述的代码是X86-64的浮点代码上述的%rsi, %rax, %rdx 是64位汇编的寄存器，这里都是保存临时值。%xmm0~%xmm15为XMM寄存器，专为保存浮点数据，每个寄存器都是128位字长，也就是可以存放4个单精度（float）或2个双精度（double）浮点数。movss指令是复制一个单进度数，mulss是进行单精度乘法运算。从上述代码的注释可以看出，每次迭代开始从%xmm0读入的值就是上次迭代运算的结果最后写入%xmm0的值。每次迭代都有一次的浪费的存储器读写。总共有两次读和一次写。
改进上面的代码，引入临时变量acc，循环体内累计计算每次运算的结果，运算完成后再加结果存放在dest中。代码如下
void combine3(vec_ptr v, data_t *dest){
long int i;
long int length = vec_length(v);
data_t *data = get_vec_start(v);
data_t acc = 0;
for (i = 0; i < length; i++)
{
acc = acc * data[i];
}
*dest = acc;
}再看看循环体内的汇编代码，看有什么不同：
.L5:
mulss (%rax), %xmm0
addq $4, %rax
cmpq %rdx, %rax
jne .L5
jmp .L4
.L4:
movss %xmm0, (%rsi)
ret正如上面的汇编代码所示，循环体内%xmm0就是acc临时变量，不断地累乘，这里只有一次读，这样每次迭代从两次读一次写减少到只需要一次读。循环结束后再放入%rsi寄存器中。
另外有一篇写得不错程序优化的文章，可以参考阅读http://blog.csdn.net/zwhlxl/article/details/45092901