优化程序性能
优化编译器的能力和局限性
编译器必须很小心地对程序只使用安全的优化，也就是说对于程序可能遇到的所有可能的情况，在C语言标准提供的保证之下，优化得到的程序和未优化的版本有一样的行为，限制编译器只进行安全的优化，消除了造成不希望的运行时行为的一些可能的原因。为理解决定一种程序转换是否安全的难度，考虑以下的代码：
1 void twiddle1(long *xp, long *yp) {
2 *xp += *yp;
3 *xp += *yp;
4 }
5
6 void twiddle2(long *xp, long *yp) {
7 *xp += 2 * *yp;
8 }
函数 twiddle2 的效率更高，因为它只要求 3 次内存引用（读 xp，读 *yp，写 *xp），而 twiddle1 需要 6 次（2 次读 *xp，2 次读 *yp，2 次写xp）。
不过，如果 xp = yp，那么函数 twiddle1 实际的操作是将 xp 的值增加 4 倍。
2 *xp += *xp; /* Double value at xp */
3 *xp += *xp; /* Double value at xp */
而函数twiddle2 则是将 xp 的值增加了 3 倍。
由于编译器不知道 xp 与 yp 是否可能相等，因此 twiddle2 不能作为 twiddle1 的优化版本。
这种两个指针可能指向同一个内存位置的情况称为 内存别名使用，在只执行安全的优化中，编译器必须假设不同的指针可能会指向内存中的同一位置， 这是一个主要妨碍优化的因素。
第二次妨碍优化的因素是函数调用
1 long f();
2
3 long func1() {
4 return f() + f() + f() + f();
5 }
6
7 long func2() {
8 return 4 * f();
9 }
先不考虑函数 f 的具体内容，可以看到，func2 只调用 f 一次，而 func1 调用 f 四次。但如果考虑函数 f 如下：
1 long counter = 0;
2
3 long f() {
4 return counter++;
5 }
显然，对于这样的 f，func1 会返回 6，而 func2 会返回 0。这种情况编译器也是无法判断的，因此编译器也无法做出这种优化。
表示程序性能
对于一个程序，如果我们记录该程序的数据规模以及对应的运行所需的时钟周期，并通过最小二乘法来拟合这些点，我们将得到形如 y = a + bx 的表达式，其中 y 是时钟周期，x 是数据规模。当数据规模较大时，运行时间就主要由线性因子 b 来决定。这时候，我们将 b 作为度量程序性能的标准，称为每元素的周期数（Cycles Per Element, CPE）。
程序示例
为了方便说明，先声明一个如下的结构：
1 typedef struct {
2 long len;
3 data_t *data;
4 } vec_rec, *vec_ptr
这个声明用 data_t 来表示基本元素的数据类型。
先考虑如下的代码：
1 void combine1(vec_ptr v, data_t *dest) {
2 long i;
3
4 *dest = IDENT;
5 for (i = 0; i < vec_length(v); i++) {
6 data_t val;
7 get_vec_element(v, i, &val);
8 *dest = *dest OP val;
9 }
10 }
上一页的代码中，循环体每执行一次，都会调用一次函数 vec_length，但数组的长度是不变的，那么可以考虑将 vec_length 移出循环体来提升效率：
消除循环的低效率
1 void combine2(vec_ptr v, data_t *dest) {
2 long i;
3 long length = vec_length(v);
4
5 *dest = IDENT;
6 for (i = 0; i < length; i++) {
7 data_t val;
8 get_vec_element(v, i, &val);
9 * dest = *dest OP val;
10 }
11 }
减少过程调用
1 data_t *get_vec_start(vec_ptr v) {
2 return v -> data;
3 }
4
5 void combine3(vec_ptr v, data_t *dest) {
6 long i;
7 long length = vec_length(v);
8 data_t *data = get_vec_start(v);
9
10 *dest = IDENT;
11 for (i = 0; i < length; i++)
12 *dest = *dest OP data[i];
13 }
我们消除了循环体中的所有调用。但实际上，这样的改变不会带来性能的提升，在整数求和的情况下还会造成性能下降。这是因为内循环中还有其他的操作形成了瓶颈。
消除不必要的内存引用
先看看 combine3 的 x86-64 汇编代码
1 .L17:
2 vmovsd (%rbx), %xmm0
3 vmulsd (%rdx), %xmm0, %xmm0
4 vmovsd %xmm0, (%rbx)
5 addq $8, %rdx
6 cmpq %rax, %rdx
7 jne .L17
通过上面的汇编代码可以看到，每次迭代时，累积变量的数值都要从内存中读出再写入到内存，这样的读写是很浪费的，而且是可以消除的：
理解现代处理器
整体操作
近期的 Intel 处理器是超标量（superscalar）的，意思是它可以在每个时钟周期执行多个操作。此外还是 乱序（out-of-order），意思是指令执行的顺序不一定与机器级程序中的顺序一致。
这样的设计使得处理器能够达到更高的并行度。例如，在执行分支结构的程序时，处理器会采用分支预测（branch prediction）技术，来预测是否需要选择分支，同时还预测分支的目标地址。
此外还有一种投机执行（speculative execution）技术，意思是处理器会在分支之前就执行分支之后的操作。如果预测错误，那么处理器就会将状态重置到分支点的状态。
功能单元的性能
算术运算的性能：
- 延迟：表示完成运算所需要的总时间
- 发射时间：表示两个连续的同类型的运算之间需要的最小时钟周期数
- 容量：表示能够执行该运算的功能单元的数量
循环展开
所谓循环展开，指的是通过增加每次迭代计算的元素数量来减少循环的迭代次数。 考虑如下的程序：
1 void psum1(float a[], float p[], long n) {
2 long i;
3 p[0] = a[0];
4 for (i = 1; i < n; i++)
5 p[i] = p[i-1] + a[i];
6 }
通过对 psum1 函数进行循环展开，能够使迭代次数减半：
1 void psum2(float a[], float p[], long n) {
2 long i;
3 p[0] = a[0];
4 for (i = 1; i < n - 1; i += 2) {
5 float mid_val = p[i-1] + a[i];
6 p[i] = mid_val;
7 p[i+1] = mid_val + a[i+1];
8 }
9 if (i < n)
10 p[i] = p[i-1] + a[i];
11 }
一些限制因素
寄存器溢出
对于循环展开，很自然地考虑如下问题：是否展开的次数越多，性能提升越大？实际上，循环展开需要维护多个变量，一旦展开的次数过多，没有足够的寄存器保存变量，那么就需要将变量保存到内存中，这就会导致访存时间消耗增加。即便是在x86-64 这样拥有足够多寄存器的架构中，循环也很可能在寄存器溢出之前就达到吞吐量限制，从而无法持续提升性能。
并行计算
同⼀个CPU内部可以有若⼲条指令同时"执⾏"，这是所谓的「指令级并⾏」（instruction-level parallelism，ILP）。指令级并⾏并不在⽤户的控制范围内，⽽是由编译器和CPU共同决定。另⼀种并⾏的概念为多个处理器同时处理⼀条以上的指令，每个处理 器都在⾃⼰所在的电路板上，这种并⾏可以由⽤户显式地调度
并⾏概念定义为：在程序的执⾏过程中寻找独⽴的操作。这些独⽴的操作往往其执⾏逻辑相同，只是⽤于不同的数据项。我们把这种情况称为「数据级并⾏」（data parallelism）：同⼀操作被并⾏地应⽤于许多数据元素，这在科学计算中是⼗分常⻅的。并⾏性往往源于这样⼀个事实：⼀个数据集（向量、矩阵、图……）被分散到许多处理器上，每个处理器都在处理其数据的⼀部分。
如果是单指令操作，传统上多采⽤数据级并⾏；如果是在⼦程序下处理，则通常称为「任务并⾏」（task parallelism）
我们⼀定可以找到这样⼀种场景，使得指令之间相互独⽴且⽆依赖关系。⼀般情况下，编译器根据指令级并⾏来分析、运⾏代码：⼀条独⽴的指令可以被赋予给⼀个独⽴的浮点单元，也可以在优化寄存器时被重新排列。
指令级并⾏是功能性并⾏的⼀种情况；功能并⾏可以通过连接相互独⽴的⼦程序来获得。在更⾼层次上，功能并⾏可以通过包含独⽴的⼦程序来获得，通常称为任务并⾏
功能性并⾏的⼀些例⼦是蒙特卡洛模拟，以及其他穿越参数化搜索空间的算法。⼀个参数化的搜索空间，如布尔可满⾜性问题