前言
我们常常关注程序的性能，而程序性能的一个重要参考就是:运行时间，同时，我们都知道，这也是衡量一个算法好坏的重要标准。在一个程序保证正确的前提下，其运行得快慢往往决定了其性能的好坏。当然，并不是所有的程序都有很严格的性能要求，往往这些程序更加倾向于保证程序的正确性及稳定性，性能是其次需要考虑的。但对于某些实时性要求比较高的程序，性能成为影响其功能和用户体验的重要因素。因此，优化和提高程序的性能的方法对我们每个编码者尤为重要。
我所知道的可以提高程序的三种方法是：一、在程序中使用一组合适的数据结构、高效算法二、编写出编译器能够有效优化而转换成高效可执行代码的源代码三、将程序划分成多个部分，这些部分可以得到并行计算和处理。而本篇所讲的内容只跟方法二有关，即如何写出编译器能够有效优化的源代码。后面我们会介绍多个可能的方法做到这点。
1. 优化编译器的能力和局限性
编译器本身就具有优化代码的能力，并且分类有严格的等级，例如，在使用GCC编译器时可以在命令中使用-O1命令开启最基本的优化，同样在MS下的CL编译工具也具有类似的优化命令。当然，编译器对程序进行优化的前提都是一样，即必须保证优化后和优化之前的程序行为一样。即所谓优化是一种安全的优化，这就意味着程序员必须花费更大的力气写出程序使编译器能够将之转换成有效机器代码。下面我们就看下对编译器来说，程序转换是否安全的难度：
Void twiddle1(int * xp ,int *yp)
{
*xp+=*yp;
*xp+=*yp;
}
Void twiddle2(int* xp,int *yp)
{
*xp+=2**yp;
}
咋一看，这两个过程似乎有相同的行为。不过，函数twiddle2效率更高一些。它只需要3次存储器引用(读*xp,读*yp，写*xp)，而twiddle1需要6次(2次读*xp,2次读*yp,2次*xp)。我们对比编译器产生也可以明显看的出。
不过，既然两个程序的行为相同，而读写效率又有这么大的差异，那为什么编译器不把twiddle2风格的代码作为twiddle1的优化版本呢？
因为，这里存在一个安全的隐患，我们忽略了xp等于yp的情况。此时，函数twiddl1会执行下面的计算:
*xp+=*xp;
*xp+=*xp;
结果是xp的值会增加4倍，而twiddle2会执行：
*xp+=2*xp;
结果是xp的值会增加3倍。而这显然是不能被允许的，这与前面所提的编译器优化原则即优化前后必须保证行为一致相背离。这种两个指针可能指向同一个存储位置的情况被称为存储器别名使用。在只执行安全的优化中，编译器必须假设不同的指针可能会指向存储器中同一个位置。从而限制了可能的优化策略。
第二个妨碍优化的因素是函数调用。我们先看下面的例子：
Int f();
Int fun1()
{
Return f()+f()+f()+f();
}
Int fun2()
{
Return 4*f();
}
最初看上去两个过程计算的都是相同结果，但是func2只调用f 一次，而fun1只调用4次，以func1作为源时，会很想产生fun2风格的代码。
不过，考虑下面的f代码：
Int counter = 0;
Int f()
{
Return counter++;
}
假设开始时全局变量为0，对func1的调用会返回0+1+2+3=6,而对fun2的调用会返回4*0=0。大多数编译器不会试图判断一个函数u是否没有副作用，相反，编译器会假设最糟的情况，并保持所有的函数调用不变。
2.表示程序性能
传统的我们会用类似gettickcount,gettime等获取时间的方法来计算程序段的运行时间从而估算其行能。在这里我们一个更加准确的标准度量每元素的周期数(CyclesPer Element,CPE)，作为一种表示程序性能并指导我们改进代码的方法。
许多过程含有一组元素上迭代的循环，如下面的函数psum1和psum2计算的都是一个长度为n的向量的前置和。函数psum1每次迭代计算结果向量的一个元素。第二个函数使用循环展开的技术，每次迭代计算两个元素。
Void psum1(float a[],float p[],long int n)
{
Long int I;
P[0]=a[0];
For(I =1;i<n;i++){
P[i]=p[i-1]+a[i];
}
}
Void psum2(float a[],float p[],long int n)
{
Long int I ;
P[0]=a[0];
For(i=1;i<n-1;i+=2){
Float mid_val = p[i-1]+a[i];
P[i]=mid_val;
P[i+1]=mid_val+a[i+1];
}
If(i<n)
P[i]=p[i-1]+a[i];
}
我们取一定返回内的n值分别计算两个函数的运行周期数。使用最小二乘拟合我们发现psum1和psum2的运行时间分别近似等式496+10.0n和500+6.5n.。这两个等式表明代码计时和初始化过程、准备循环以及完成过程的开销为496~500个周期加上每个元素6.5或者10.0的线性因子，对于较大的n值，显然其运行时间是由线性因子来决定的。这些项中的系数就称为每元素的周期数(CPE)。在这里我们更愿意用每个元素的周期数而不是每次循环的周期数来度量，是因为像循环展开这样的技术使得我们能够用较少的循环完成计算，而我们最终关心的是，对于给定的n，程序运行得速度如何。
根据这个度量标准。Psum2的CPE为6.5，由于CPE为10.0的psum1。
3.未优化的原始程序
这是一个简单的数据结构，其用数据类型data_t作为基本元素的数据类型。
typedef struct {
Long int len;
Data_t *data;
}vec_rec,*vec_ptr;
然后定义两个宏变量INENT 和OP分别对应不同运算时所应取的值。
#define INENT 0
# define OP +
和
#defineINENT 1
#define OP*
//创建一个新的结构对象
Vec_ptrnew_vec(long int len)
{
Vec_ptr result = (vec_ptr)malloc(szieof(vec_rec));
If(!result){
Return Null;
}
Result->len = len;
If(len>0){
Data_t*data=(data_t*)calloc(len,sizeof(data_t));
If(!data){
Free(result);
Return NULL;
}
Result->data=data;
}else{
Result->data =NULL;
}
Return result;
}
//取值
Intget_vec_element(vec_ptr v,long int index,data_t *dest)
{
If(index<0|| index>=v->len)
Return0;
*dest=v->data[index];
Return 1;
}
//取长度Long int vec_length(vec_ptr v){ Return v->len;} //合并运算Void combine1(vec_ptr v,data_t *dest){ Long int I; *dest =IDENT; For(i=0;i<vec_length(v);i++){ Data_vval; Get_vec_element(v,I,&val); *dest=*destOP val; }}
我们下面的数据都是在一个拥有Inter core i7处理器的机器上测试得到的CPE值。首先等到的一组数据是combine1和其优化版本的比较，我们发现简单实用命令行选项-O1进行一些基本优化就能显著的提高程序性能。
4.消除循环的低效率
可以看到，过程combine1调用函数vec_length作为for循环的测试条件。而每次调用vec_length的值都是相同的。为此，我们只计算一次向量的长度，然后在for循环的中使用这个值，这样避免多次对同一个方法进行调用。下面是上个版本的修订版Combine2：
Void combine2(vec_ptr v,data_t *dest)
{
Long int I;
Long intlength =vec_length(v);
*dest =IDENT;
For(i=0;i<length;i++){
Data_tval;
Get_vec_elemen(v,I,&val);
*dest= *dest OP val;
}
}
这是改进后的性能提升：
这是一种称为“代码移动”的优化方法，这类优化将循环中多次执行，但是结果不会改变的值，因此可以将其移动到多次执行的代码前面先进行计算。优化编译器可能会尝试进行代码移动，但是通常会非常小心，因为它们不能可靠的发现一个函数是否会有副作用(像之前介绍的)，因而会假设会有副作用。因此时需要我们帮助其显示地完成代码移动。
5.减少过程调用
过程调用会带来相当大的开销，而且妨碍了程序的优化。从combine2的代码可以看出，每次循环迭代都会调用get_vec_element来获取下一个向量元素。在该方法内部，会对每个向量索引i做越界比较，造成一定的低效率。然而对程序进行简单的分析后，发现每次调用并不一定需要这样的检查。作为替代，我们可以添加一个get_vec_start的函数，返回向量数组的其实地址这样我们就可以对其进一步优化，得到combine3:
Data_t*get_vec_start(vec_ptr v) {
Returnv->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 = IDENT;
For(i=0;i<length;i++){
*dest = *dest OP data[i];
}
}
不过从原则上来说，这种方法严重损害了程序的模块性，因为向量抽象数据类型的使用者不需要知道向量的内容是作为数组来存储的。不过，对于性能至关重要的应用来说，为了速度，必须经常牺牲和损害一些模块性和抽象性。
我们看下提升的性能CPE：
我们发现，只提高了整数求和的性能，也就是说combine2中的边界检查并没有我们预测的那么差。这个原因的分析后面再做说明。
6.减少不必要的存储器引用
Combine3将合并运算计算的值累计在指针dest指定的位置，通过查看其产生的汇编代码，我们看到在循环的迭代中存储器的读写主要发生在对于dest和data的一次读以及对dest的一次写操作。
对于我们combine3的优化版本，我们将而每次迭代计算的值放入一个临时变量，计算完成时再写入内存中。
Void combine4(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 = IDENT;
For(i=0;i<length;i++){
Acc=acc OP data[i];
}
*dest =acc;
}
这样产生的汇编代码如下,可以看到比上个版本的存储器访问少了两次，只有一次读操作。
最后，我们再看优化后的性能提升：
可以看到，消除循环内不必要的存储器引用可以显著的提高程序性能。而这个跟存储器系统的结构相关。在后面的篇节中我会对其进行介绍。
7.现代处理器
到目前为止，我们运用的优化都不依赖于目标机器的任何特性，这些优化只是简单的降低了过程调用，并消除了妨碍编译器优化的一些因素，如果想要充分的提高性能，我们需要考虑利用微处理器结构的优化。这将要求我们在特定机器上对程序进行性能优化，这里我不对处理器结构及其硬件结构多做说明，因为不同处理器的结构可能并不相同且难于理解。所以我们只对影响程序性能的关键要素做出简单说明，如果据此不能够充分理解，可以查看本书第四章<处理器体系结构>及本章的详细介绍。
在现代处理器中，大都具备了指令级并行的处理能力。比如有100条指令，采用一些精细的机制来确保并行执行的行为，它们采用复杂而奇异的微处理结构，其中，多条指令可以并行地执行，同时又呈现一种简单地顺序执行指令的表象。
现在处理器同时采用了一种分支预测的技术，当程序中出现分支时，处理器会猜测是否会选择分支，同时还预测分支的目标地址。使用投机执行的技术，处理器会开始取出位于它预测的分支会跳到的地方的指令，并对指令译码，甚至在它确定分支预测是否正确之前就开始执行这些操作。如果过后确定分支预测错误，会将状态重新设置到分支点的状态，并开始取出和执行另一个方向的指令。
延迟界限—当一系列擦偶偶必须按照严格顺序执行时，在下一条指令开始之前，这条指令必须结束。当代码中的数据相关限制了处理器利用指令级并行的能力时，延迟界限能够限定程序性能。
吞吐量界限—刻画处理器功能单元的原始计算能力,是程序性能的终极限制。
下面我们介绍的优化方法都跟现代处理器具有的这些特性相关，所以在不同机器上的表现并不相同，你需要经过多次的测试找到合适的值来对程序进行最充分的优化。
8.循环展开
循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。它主要从两方面提高程序的性能。首先，它减少了不直接有助于程序结果的操作的数量，例如循环索引计算和条件分治。其次，它提供了一些方法，可以进一步变化代码，减少整个计算中关键路径上的操作数量。
对于k次循环展开，上限设为n-k+1,在循环内对元素i到i+k-1应用合并计算。每次迭代，循环所以i加k。那么最大循环索引i+k-1<(n-k+1)+k-1=n;
因此，我们combine5的循环展开版本，这里k=2
Void combine5(vec_ptr v,data_t *dest)
{
Long int I;
Long int length = vec_length(v);
Long int limit = length-1;
Data_t *data = get_vec_start(v);
Data_t acc = IDENT;
For(i=0;i<limit;i+=2){
Acc = (acc OP data[i] ) OP data[i+1];
}
For(;i<length;i++){
Acc = acc OP data[i];
}
*dest =a cc;
}
下面我们看下相比上个版本的CPE值：
我们看到相对combine4整数运算的性能有所提升，但是并不是很好，无论对于2次还是3次展开，对于浮点运算没有帮助，但是对于整数加法合成法，CPE降至1.00.我们知道了这些优化的结果是依赖于处理器复杂的指令级并行能力。而对于浮点运算我们只需明白其CPE受限于延迟界限。
9.提高并行性
在此，程序是受限于运算单的延迟的。不过，还行加法和乘法的功能单元是完全流水化的，这意味着它们可以每个时钟周期开始一个新操作，而combine5的代码没能利用这种能力，这是因为我们将累积值放在一个单独的acc中。在一次流水线上的计算完成之前，都不能计算acc的新值。虽然功能单元能够每L个时钟周期开始一条新操作，这里L是合并的延迟。下面，我们将破这种顺序相关，得到比延迟界限更好的性能方法。
9.1多个累计变量
先看我们改进的Combine6方法：
Void combine6(vec_ptr v,data_t *dest)
{
Long int I;
Long int length = vec_length(v);
Long int limit =length-1;
Data_t * data = get_vec_start(v);
Data_t acc0 = IDENT;
Data_t acc1 = IDENT;
For(i=0;i<limit ;i+=2){
Acc0 = acc0 OP data[i];
Acc1 = acc1 OP data[i+1];
}
For(;i<length;i++){
Acc0 = acc0 OPdata[i];
}
*dest = acc0 OP acc1;
}
我们使用了一种带有多路并行的循环展开方法，来充分的利用处理器的并行能力。对于上述代码，可以对比combine5我们可以说，combine6在流出线的处理过程获得了两条关键路径。从而将利用率提高了2倍。
9.2 重新结合变换
这种方法也可以打破顺序相关从而使性能提升到延迟界限之外的方法。我们对combine5的代码做微小的改动，就可以做到这点。
Void combine5(vec_ptr v,data_t *dest)
{
Long int I;
Long int length = vec_length(v);
Long int limit = length-1;
Data_t *data = get_vec_start(v);
Data_t acc = IDENT;
For(i=0;i<limit;i+=2){
Acc = acc OP (data[i] OP data[i+1]);
}
For(;i<length;i++){
Acc = acc OP data[i];
}
*dest =a cc;
}
我们可以看到令人吃惊的结果，仅仅是改变一个计算时的结合顺序就能是性能提高这么大。这主要是因为每次迭代内的第一个乘法都不需要等待前一次迭代的累计值就可以执行，流水线的每个关键路径上都有1/2个操作，有点类似2路并行的情况。总得来说，重新结合变换减少了计算中关键路径上的操作的数量，能通过更好地利用功能单元的流水线能力得到更好的性能。
10.一些限制因素
可能我们了解了上面优化的方法，可能会有这样的疑问：是不是循环展开和多路并行的次数越大对于程序性能提升越有帮助？答案显然不是，我们知道循环展开和多路并行都以来了处理器的对于指令的并行处理能力。而这个能力受限于其对应汇编指令集的能力，简单来说，IA32指令集只有很少量的寄存器来存放累计的值。如果我们的并行度超过了可用的寄存器数量，那么编译器会诉诸溢出，将某些临时值存放在栈中。一旦出现这种情况，性能就会急剧下降。
同时，我们前面提到过现代处理器具有分支预测能力。在一个使用投机执行的处理器中，处理器会开始执行预测的分支目标处的指令。如果预测结果正确，那么处理器会根据预测的结果继续执行，否则，就必须丢弃所有投机执行的结果，在正确的位置，重新开始取指令的过程。对于这种预测错误，处理器会得到处罚，对于Inter Core i7 来说，有将近44个时钟周期。在这里，让我们回顾下combine2变化到combine3时的情况，我们把函数get_vec_element从函数内循环中拿了出来，我们发现对应于combine2，CPE并没有多大的变化，即使这个函数使用了两个条件语句来检查向量索引是否在界限内。这些检测总是确定索引是在界限之内的，所以是高度可预测的。像这种在合并函数中闭合循环的分支通常会被预测为选择分支，而只在最后一次会导致预测错误处罚。所以预测分支并没有我们想象的那么糟糕，现代处理器中的分支预测逻辑非常善于辨别不同的分支指令有规律的模式和长期的趋势。
11.Amdahl定律
Amdahl定律对于我们对于系统优化有一定的指导意义。其主要思想是当我们加快系统一个部分的速度时，对系统整体性能的影响依赖于这个部分有多重要和速度提高了多少。考虑一个系统，在其中执行某个应用程序需要Told.假设系统的某个部分需要这个时间的百分比为a,而我们将他的性能提高到了k倍。也就是，这部分原来需要时间aTold,而现在需要时间(aTold)/k,因此整个执行时间会是
例如系统原来被占用60%(a=0.6)的部分被提高到了3(k=3)倍。那么加速比为1[0.4+0.6/3]=1.67
因此，计时我们大幅度改进了系统的一个主要部分，净加速比还是很小。这就是Amdahl定律的主要观点——要想大幅度提高整个系统的速度，我们必须提高整个系统很大一部分的速度。根据Amdahl定律 ，我们知道要想提高整个系统的速度，必须对程序进行剖析，从而了解整个系统的最影响程序性能的部分。
如果想要知道程序中哪一部分占用了很大的比重，我们可以通过在Unix系统中，通过一个剖析程序GPROF来进行分析。首先，它去掉程序中每个函数花费了多少CPU时间，其次，它计算每个函数被调用的次数，以执行调用的函数进行分类。
用GPROF进行剖析需要3个步骤，比如我们要对程序test.c进行剖析
1> 程序必须为剖析而编译和链接。使用GCC，在命令行上简单地包括运行时标识‘-pg’
gcc –O1 –pg test.c – test
2>然后程序像往常一样执行：
./test file.txt
它会产生一个文件gmon.out
3>调用GPROF来分析gmon.out中的数据。
gprof ./test
分析的结果是以函数进行分类的，记录了每个函数花费的时间占总时间的百分比，函数被调用的次数等信息。