概述
编写高效程序需要注意
1、选择适当的算法和数据结构。
2、编写出编译器能够有效优化以转换成高效可执行代码的源代码。这一点需要理解优化编译器的能力和局限性。
3、处理运算量特别大的计算，需要在多核和多处理器的组合上并行运算。
程序优化第一步
消除不必要的工作，让代码尽可能有效地执行所期望的任务。这里包括了消除不必要的函数调用、条件测试和内存引用。这些优化不依赖于目标机器的任何具体属性，主要是针对代码的。
程序优化第二步
在此之前，我们需要一个目标机器的模型，致命如何处理指令以及各个操作的时序特性。比方说，编译器必须知道时序信息，才能确定使用一条乘法指令还是移位和加法的某种组合。目前计算机使用复杂的技术来处理机器级程序，并行的执行许多指令，执行顺序还可能不同于它们在程序中出现的顺序。程序员必须要理解这些机器如何工作，从而调整他们的程序来获取最大速度。
在了解了处理器的运作后，我们即可进行第二步，利用处理器提供的指令级并行(instruction-level parallelism)能力，同时执行多条指令。
优化编译器的能力和局限性
现代编译器运用复杂精细的算法来确定一个程序中计算的是什么值，以及它们是如何被使用的，之后会利用一些机会来简化表达式，在几个不同的地方使用同一个计算，以及降低一个给定的计算必须被执行的次数。一些编译器向用户提供了一些对它们使用的优化的控制，例如在GCC中最简单的控制便是指定优化级别。”-Og”是基本优化，而”-O1”,”-O2”,”-O3”则是让GCC使用更大量的优化，这样可以提高程序性能，但相应的也可能会增加程序的规模。对于大多数使用GCC的软件项目来说，优化级别-O2被定义为了可以被接受的标准，但还是主要考虑-O1级别编译出的代码。
第一个妨碍优化的因素
编译器必须很小心地对程序只使用安全的优化，这里的安全是指在程序可能遇到的所有可能情况下，在C语言标准提供的保证之下，优化后得到的程序和未优化版本有一样的行为。
我们用两个函数举一个栗子：
void twiddle1(long *xp, long *yp)
{
*xp += *yp;
*xp += *yp;
}
void twiddle1(long *xp, long *yp)
{
*xp += 2* *yp;
}乍一看的话，两程序好像是有相同的行为，都是将储存在由指针yp指示的位置处的值两次加到xp指针指示的位置出的值。另一方面，函数twiddle2效率要高些。因为它只要求了3此内存引用(读 xp，读yp，写xp)，而twiddle1则需要六次(两次读 xp，两次读yp，两次写xp)，因此我们会认为基于第二个函数执行的计算能产生更有效的代码。
不过如果考虑到xp等于yp的情况的话，此时函数twiddle1会执行下列运算：
*xp += *xp; /* Double value at xp */
*xp += *xp; /* Double value at xp */
其结果便是xp的值增加四倍，而twiddle2会执行下列运算：
*xp += 2* *xp; /* Trible value at xp */
现在就不一样了，程序二让xp的值增加了3倍，是不是很神奇。
编译器是不知道twiddle1会被如何调用的，因此他必须考虑到参数xp和yp相等的情况，所以他不会产生twiddle2风格代码作为twiddle1的优化版本。
这中两个指针可能指向同一内存位置的情况称为内存别名使用（memory aliasing）。在只执行安全的优化中，编译器必须假设不同的指针可能会指向内存中的同一位置。
第二个妨碍优化的因素
我们先举一个栗子：
long f();
long func1() {
return f() + f() + f() + f();
}
long func2() {
return 4*f();
}
同样的，这个例子看上去两个过程计算的都是一样的结果，但是func2只调用了f一次，而func1调用了f四次。要是你写了func1风格的代码，你可能会想要改成func2的样子。
不过考虑一下下面的f代码：
long counter = 0;
long f() {
return counter++;
}
这个函数有个副作用，——它修改了全局程序状态的一部分，改变调用它的次数会改变程序的行为，我们假设一种情况，在开始时全局变量counter都设置为0，对于func1的调用会返回0+1+2+3=6，而对func2的调用呢，则会返回4*0=0。
大多数编译器不会试图判断一个函数有没有副作用，如果没有，可能会被优化成func2的样子，相反，编译器会假设最糟糕的情况，并保持所有函数调用不变。
表示程序性能
我们引入度量标准每元素的周期数(Cycles Per Element),简称为CPE作为一种表示程序性能并指导我们改进代码的方法。CPE可以帮我们在更细节的级别上理解迭代程序的循环性能。很适合度量执行重复计算的程序。
处理器活动的顺序是由时钟来控制的，时钟提供了某个频率的规律信号，通常用GHz即千兆赫兹（1000000000周期/s）来表示。如果一个系统是4GHz的处理器，那就表示处理器时钟运行赫兹是每秒4*10^9个周期。每个时钟周期的时间就是时钟赫兹的倒数。那么一个4GHz的时钟周期就是0.25纳秒或者250皮秒，从程序员的角度来理解，用时钟周期来度量标准还是要比纳秒皮秒好的多，用时钟周期，度量值表示的是执行了多少条指令。
举个栗子表示下我们对CPE度量的使用：
下面两个函数都是用来计算长度为n的向量的前置和，对于向量a和前置和p的定义为
p0 = a0
pi = pi-1 + ai，1≤i＜n
void psum1(float a[], float p[], long n)
{
long 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 n)
{
long 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];
}
我们可以看到，函数psum1每次迭代计算结果的一个元素。第二个函数则使用循环展开的技术，每次迭代计算了两个元素。
这样一个过程所需时间可以用一个常数加上一个与被处理元素个数成正比的因子来描述。使用最小二乘法拟合后，psum1个psum2的运行时间约为368+9.0n和368+6.0n，这两个式子表示了对代码的计时和初始化过程、准备循环以及完成过程的开销为368个周期加上每个元素6.0或9.0周期的线性因子。对于较大的n值，运行时间主要就由线性因子来决定。这些项的系数称为每元素的周期数(CPE)的有效值。在这个例子中，psum2的CPE为6.0，优于9.0的psum1。
未完待续…
