CSAPP第五章 - 优化程序性能

本章我们主要以优化一个求前缀和的函数为例子进行

自己实现了一个 vector

然后我们会通过修改宏定义，对不同的数据类型进行前缀积和前缀和。

如求前缀和就可以定义 IDENT 为 1，OP 为 *

1. 编译器优化

1.1 调整优化等级

通过设置 -O1 的优化等级就可以带来很大的提升

1.2 妨碍编译器优化

编译器为了保证优化的正确性，一些可能看似正确的，但是会导致前后程序行为发生变化的优化是不会应用的

1.2.1 内存别名使用

比如上述的 twiddle1 和 twiddle2 看似行为是一样的，但是我们考虑，如果 xp 和 yp 两个指针指向的地址一样的话，twiddle1 会使得数据变为原来的 4 倍，而 twiddle2 会使得数据变为原来的 3 倍

所以编译器在考虑代码优化时，总会假定不同的指针可能会指向内存的同一个位置。

当然，如果我们自己知道一些情况不会发生，那么我们就可以通过一些关键字去提示编译器：

• restrict：告诉编译器，被修饰的指针指向的内存只有自己这一个指针指向，没有别的指针指向。
• const：告诉编译器，指针指向的内存只会读不会写。

比如：

上述代码，编译器就会认为 x 和 y 数组之间没有重叠，因此可以直接进行向量化的优化。

当然有时候即使可能出现内存别名的情况，编译器也会尽力处理。比如上述代码如果不加 restrict 和 const 的话，编译器会生成如下的代码：判断 x 数组访问的范围和 y 数组访问的范围有无重合，有重合的话就不优化，否则进行向量化优化。

1.2.2 函数调用副作用

上述的 func1 和 func2 也看似行为是一样的。但有可能 f 函数有副作用：

那么调用一次函数和调用四次函数，造成的结果是肯定不一样的。

类似的例子还有：

编译器不好说 norm 函数会不会有副作用，因此不会将其提出循环体。

我们可以使用 __attribute__((const)) 来提示编译器：

1.2.3 Unsigned 溢出

如下的代码虽然已经加了 restrict 关键字，但是还是没有进行向量化优化：

原因之一在于，i 和 n 都是无符号整数，并且 i 每次加 4，那么编译器就认为有可能出现无符号整数的溢出情况。无符号溢出会使得该整数变为 0，于是上述这个循环就会循环无穷多次。

解决办法是把 i 和 n 改成有符号整数。这是因为在不同的架构上有符号整数溢出的行为不一样，于是编译器就假设有符号溢出永远不会发生，于是就进行了向量化优化。

所以一般而言 for 循环的变量最好就用有符号整数，除非要进行位运算。

2. 编码优化

2.1 代码移动

上面的 combine1 每次循环后都会调用 vec_length。而我们已经确定了 vec_length 是一个固定的值，所以我们可以写成这样：

这样的话我们只会调用一次 vec_length，提升如下：

像这种，会计算多次，但是每次计算的结果不变，于是我们可以把计算结果移动到不会多次求值的代码前，这种优化就叫做代码移动

还有一个更能说明问题的例子。strlen 函数求一个字符串是 $O(n)$ 的，如果遍历一个字符串时，循环的条件中写了 strlen 的话，那么整个循环的复杂度就会增加到 $O(n^2)$，对代码效率的影响远不是 CPE 可以衡量的了

编译器不会自动进行这种优化，原因是可能函数调用有副作用

2.2 减少函数调用

由于我们的 vector 本质上就是包裹了一下数组，所以 get_vec_element 可以被替换为先在循环外通过 get_vec_start 获得数组首地址之后然后再使用当前循环枚举的 i 来进行寻址：

这个改动减少了函数调用的次数。但是优化却很有限：

2.3 减少内存引用

进行内存读写需要消耗多个时钟周期，对性能影响较大。上面的 combine3 中，我们发现代码的第 10 行，首先将会从 dest 对应的内存中读数据，然后计算完成之后会把结果写回 dest 对应的内存中。这实际上是没有必要的，我们可以写成下面这样：

这样的话会先把计算结果积累在一个局部变量中，而这个局部变量应该是放在寄存器上的，对于寄存器的读写消耗的时钟周期较小。

优化的结果如下：

编译器不会自动进行这个优化，如果 dest 指向的内存也是 vector 的一部分的话（内存别名引用）就会使得优化前后的行为不同。所以我们手动进行这个的优化的前提是我们确信使用函数时 dest 不会指向 vector 所在的区域

3. 利用处理器架构优化

3.1 现代处理器架构

现代处理器是超标量的，特点是同一个周期内有多个指令在并行执行，并且是乱序执行的。

整个设计大概是有两部分，ICU（指令控制单元）和 EU（执行单元）

ICU 中有一个指令高速缓存。通常 ICU 会提前进行取指，以留有足够的时间对指令进行译码。

指令译码单元完成的工作比我们第四章流水线的译码阶段要复杂得多，其会将原始的指令分解成一组基本操作，每个基本操作都完成一个最基本的任务（从内存加载数据，写入数据到内存，进行运算等，类似精简指令集），于是处理器就可以并行地执行一条指令的不同部分。

通常，EU 在每个周期会接收到来自 ICU 的多个操作，这些操作会被分派到相应的功能单元中，执行实际的操作。

面对分支预测，现代处理器会有更加灵活的分支预测策略，并使用投机执行技术，即处理器预测分支后会实际地去执行这些指令。不过由于后续可能会存在预测错误，所以提前执行的指令不会真的去写寄存器或者内存，而是先将执行的结果放到退役单元。如果后面处理器判定预测正确，那么退役单元里未应用的操作将会被应用到寄存器文件中。反之，则会丢弃掉之前提前执行的指令产生的数据。

由于只有判定预测正确之后才会将操作应用到寄存器文件，为了加快指令之间的数据交流，现代处理器还允许指令之间直接在 EU 中进行数据交换，其中一个技术是寄存器重命名。EU 中会维护一个重命名表，当有一个指令更新寄存器 r 时，就会产生一个标记 t，然后我们就把 (r,t) 放入这个表中，后续使用寄存器 r 的指令都会根据这个表转而使用 t。这有点类似于数据转发。

3.2 性能分析

现代处理器有多个功能单元，不同功能单元可以进行不同操作，一个功能单元也能整合不同的功能。Intel Core i7 Haswell 中有如下的 8 个功能单元，编号分别从 0 到 7：

根据 Intel 的数据，一些运算具有如下的性能参数（图中的单位为时钟周期）：

延迟表明完成单个运算需要的周期数，我们可以看到与浮点数相关的运算和除法运算是多周期指令。同时除法的延迟还是变化的，某些除数和被除数的组合可能比其他组合需要更多的步骤。

发射时间是发射两个相同类型的指令之间所需的时间间隔。大多数指令的发射时间为 1，因为我们可以考虑流水线设计，即使只有一个功能单元，我们也可以不断地将指令发射到流水线，相邻指令之间还是有时间间隔，不会同时占用一个功能单元，因此发射时间为 1 的功能单元被称为完全流水线化的。对于除法运算，发射时间和延迟时间一致，这意味着除法器不是流水线化的，开启一个新的运算之前，上一个运算必须完全执行完毕。

容量指的是有多少个可以进行特定运算的功能单元，也意味着我们可以同时发射多少个同类型的指令。

发射时间的倒数就表明一个功能单元的最大吞吐量。由于我们可以有多个功能单元，所以如果定义容量为 $C$，发射时间为 $I$，那么这个类型的指令的最大吞吐量就为 $\frac{C}{I}$

我们有（图中的单位为 CPE）：

上图的延迟表明延迟界限，即如果我的程序只利用了一个运算单元，且存在数据依赖（即上下一条指令要用到上一条指令的运算结果），能到达的最低 CPE 值。和延迟时间相同。

上图的吞吐量表明吞吐量界限，即如果我的程序充分利用了所有的运算单元，且不存在数据依赖，能到达的最低 CPE 值。值和最大吞吐量相同。但是我们发现加法的吞吐量界限为 0.5 并非 0.25，这是由于我们还需要考虑到数据加载的瓶颈，而处理器只有两个加载单元，因此加法计算单元只能同时用两个。

分析我们目前最快的 combine4，对比一下发现：

已经很接近延迟界限，但是仍有一段距离。

combine4 的循环部分对应的汇编代码如下：

将指令拆分成基本操作，然后我们可以画出下面这种数据流图：

重排一下：

其中蓝色部分是关键部分。我们省略掉白色部分，然后再多拼接几个蓝色部分，得到：

我们可以看到整个循环大概是需要左边 $n$ 次的乘法计算，右边 $n$ 次的加法计算。其中乘法计算的延迟时间较大，所以左侧形成的路径是关键路径，对我们程序的效率起主要作用。

上面 combine4 的 CPE 还未接近延迟界限（尤其是整数加法）的原因就在于右侧的非关键路径。而未接近吞吐量界限的原因就在于左边的关键路径。

3.3 循环展开

我们可以把原来的两次循环合并成一个循环，如：

我们管这种叫做 $2\times 1$ 循环展开

性能对比：

使用循环展开可以让我们减少非关键路径上的运算：

这使得我们可以接近延迟界限。但关键路径上的运算数量没有减少，因此还是达不到吞吐量界限。

3.4 提高并行性

3.4.1 多个累积变量

现在我们的代码的数据相关性比较强，因为计算新的 acc 时还依赖于上一个 acc。数据相关导致，即使我发射时间很快，但是前面的指令算不完，后面的指令也无法向前推进。所以强的数据相关性会使我们的 CPE 最低只能到延迟界限。

为了降低数据相关性，我们可以这么做，将奇数位置的数据积累到 acc1 上，偶数的积累到 acc0 上。由于更新 acc0 的时候不需要 acc1 更新完毕，反之亦然，因此我们就降低了数据相关性。

我们把这种两阶循环展开，积累到两路的变量，称为 $2\times 2$ 循环展开

比较一下性能：

此时我们终于突破了延迟界限

对于延迟为 L，容量为 C 的功能单元，使用 $k\times k$ 阶循环展开且达到吞吐量界限的话，需要让 $k$ 取 $L\cdot C$。感性理解是，虽然功能单元延迟是 $L$，但是如果功能单元是完全流水线化的话，我们需要一下发射 $L$ 条指令来填满流水线。如果有 $C$ 个相同的单元，我们就需要一下发射 $L\cdot C$ 条指令。

不过这种多路积累可能会有一些问题。比如给出的序列的奇数位置特别大，偶数位置接近于 0，那么在进行乘法的时候，acc1 可能会溢出，而正常进行循环的话一大一小相乘就会抵消。而且在第二章我们也说过，绝对值相差非常大的几个浮点数之间进行乘法操作，不同的乘法顺序会产生不同的结果。这些都会使得程序的行为发生变化。

3.4.2 重新结合变换

我们把 combine5 的代码中的 acc = (acc OP data[i]) OP data[i+1] 改为 acc = acc OP (data[i] OP data[i+1]) 的话，依然能够提高代码的并发性。只是改变了结合顺序，但是前者与 data[i] 计算完毕后才能继续与 data[i+1] 计算，下次循环与 data[i+2] 计算的时候还需要等等待前面与 data[i+1] 计算完毕。而后者则在 data[i] 与 data[i+1] 计算完毕之后可以立刻进行 data[i+2] 与 data[i+3] 的计算，由此消除了数据相关性，代码可以并行地执行。

书上有一个练习题能够帮助我们更好地去理解这个：

其中五个不同的结合顺序的数据流图如下：

显然其中 A1 的并行性极差，由于浮点乘法的延迟为 5，所以 A1 的 CPE 为 5。

A2 和 A5 我们发现，前者的 x*y 和后者的 y*z 是独立于关键路径的，因此可以和关键路径并行计算，也就是两路的并行。关键路径上只有两个操作，因此 CPE 为原来的 $\frac{2}{3}$，即 3.33

A3 和 A4 相较于 A2 和 A5，又将一个运算从关键路径上拿走，CPE 为原来的 $\frac{1}{3}$，即 1.67

3.4.3 内存相关

上面的数据之间的相关联是发生在寄存器中的，实际上也可以发生在内存上。我们之前的代码由于读内存都是根据循环枚举的 i 进行寻址，所以关于内存的数据相关比较小。

但我们考虑，如果现在，我们把原来的 vector 改为 list。list 的一个特点就是我们必须读到上一个元素才能获得下一个元素的地址然后读下一个元素，由此一来就产生了数据相关。这种情况下，代码的 CPE 会降到 4，因为 CPU 的 L1 cache 的访问速度是 4 周期

我们再看这个代码：

如果 dst 和 src 不同的话，那么读写内存就无相关性，可以并行地执行。反之，在读 src 的时候需要等待 dst 完成写入，这就带来了数据相关性，导致这个实例的 CPE 达到了 7.3

又比如：

A 的 CPE 小，因为读的位置永远比写的位置靠后。B 的 CPE 大，因为每次读的位置都已经被写了一遍，需要等待先前写入操作完成，并行程度较差

3.5 寄存器溢出

我们循环展开时，积累的变量不能太多，比如：

我们使用了更高阶的循环展开和更多的累积变量，但是反而 CPE 升高。这是因为变量太多的话，编译器无法将全部的变量都分配到寄存器上，这样的话就会使得一些变量必须开在栈上，增加了内存引用。

3.6 分支预测

现代处理器的分支预测能力已经足够强了，大多数有规律的代码都可以被成功预测。所以这一点不应该是我们过度关心的。不过对于一些比较随机的情况，分支预测容易失败，且我们在第三章中提到如果分支预测错误的话需要撤销当前预测分支，这将会带来巨大的惩罚。所以我们需要考虑条件传送。

这里我们是从 C 语言角度考虑优化的，而具体汇编代码是由编译器产生的。所以我们只能尽可能诱导编译器产生条件传送代码。一个比较好的办法是使用三目运算符：

变为：