CSAPP 深入理解计算机系统（三）：优化程序性能

2024/07/08

CSAPP笔记系列（已完结）： CSAPP 课程笔记索引

怎么让程序运行的更快？

• 比如，去掉程序中不必要的工作，这个优化不依赖于目标机器。
• 让代码能够被编译器优化（编译器友好代码）。
• 针对特定的机器对程序进行优化（风险在于换一个处理器可能就效果较差，但也有一些通用性的做法）

要使程序运行高效，不一定要使用汇编编写（除非在一些资源特别小的机器上）。

1. 编译器的通用优化方法：Code Motion、 Reduction in Strength 、 Share Common Subexpressions
2. 编译器优化的局限Procedure Calls 、Memory Aliasing 及解决办法（编译器友好代码）
3. 指令级并行、流水线操作单元、SIMD向量操作：数十倍提高运行效率
4. 条件分支：避免不可预测的分支

Performance Realities

There’s more to performance than asymptotic complexity

Optimizing Compilers

gcc不是最好的编译器，但对于大部分人已经足够用。

Limitations of Optimizing Compilers 编译器的局限

• 编译器并不能真正理解你正在使用的数字。当你定义一个int，实际上它的取值范围是比int范围小很多的子集。编译器也很难理解内存引用模式和过程调用的影响。
• 大部分优化是基于静态分析。
• 编译器有一整套优化策略和方法。但是编译器只做确定的优化。如果发现编译器没有做预期中的优化，应该回去看代码。

Code Motion

一种编译器优化技术，通常在O1优化中使用。

Reduction in Strength

将耗时的操作转化为简单的操作，比如移位、加法替代乘法

Share Common Subexpressions

共享通用的表达式，在O1优化中使用。比如下面的例子中，计算一个像素矩阵上下左右的值之和。

#1 Procedure Calls

在过程间调用时，编译器经常无法自动实现一些优化。编译器将过程间调用视为一个黑盒。

补偿方法：

• 使用inline函数，gcc O1优化
• 手动code motion

比如一个将字符串改为小写的例子。错误写法中，将strlen（On复杂度）放到循环条件里。在汇编代码里，每一次循环，都会调用strlen。从而整体复杂度为O(n^2)。code motion优化之后的复杂度为O(n)。

性能对比：

为什么编译器不能自动优化的原因：在循环体中修改了字符串s。即使修改其中的字符并不会影响字符串的长度，但是strlen函数的实现在其他文件（或者系统库）中。编译器在链接之前，并不知道这个函数是怎么实现的。因此出于不确定原因，每次都会计算一次strlen。

#2 Memory Aliasing

内存别名，即内存中的一个位置可能被程序中的不同部分引用。所以编译器在使用该位置的值时，必须每次都读取最新值，因为可能被别的引用所修改。

注：这里 alias加与不加的计算结果不同

乱序执行（Out Of Order）：处理器可以打乱指令的执行顺序。

超标量（super scalar）：同时执行多个指令，实现指令级并行（ILP）。可以同时执行多个指令的CPU称为超标量指令处理器。

指令级并行（Instruction-Level Parallelism ）：可以认为程序是一个顺序执行的指令序列，CPU尽可能的读取多的指令序列。然后CPU把读入的指令拆开，发现有的指令之间不是相互依赖的，所以可以开始执行程序后面的代码。因为它们彼此独立。

几乎所有处理器都实现了这个特性，因此也是一种通用优化方法。

Modern CPU Design

基本思想：把程序的操作拆分、重组，使这些基本单元尽可能繁忙、执行代码的不同片段。

Pipelined Functional Units 流水线操作单元

以Haswell CPU 为例，流水线技术通常可以成倍缩小计算时间。（注意，除法无法被流水线拆分。因此在代码中避免使用除法）

Cycles Per Element (CPE) ：处理一个元素（OP）占用的时钟周期。这个指标可以很好地衡量程序运行的性能，和元素的数量无关。即下图中的Slope：

利用指令级并行的例子：

1没有指令集并行，因为每一次OP都需要前一次OP的计算结果。

2Loop Unrolling with Reassociation (2x1a) 一次循环执行2次操作，利用并行，将CPE缩小1/2。

注：浮点数运算不满足结合律。舍入可能会导致计算结果不同。但如果计算过程中不会发生舍入的情况，那么这种转换不会影响计算结果。即使发生舍入的情况比较少，也足够让大多数编译器不会造成结合性导致的差异。因为它们的浮点数计算的优化相当保守。

3Loop Unrolling with Separate Accumulators (2x2) 另一种方法，同样在一次循环执行2次操作，将CPE缩小1/2。

通过调整Unrolling & Accumulating 的参数组合，可以将int、float的CPE接近吞吐量界限。

Programming with AVX2

怎么突破硬件限制（吞吐量界限）？增加寄存器的数量。YMM寄存器是提供给浮点数计算的额外的一组寄存器（之前是XMM寄存器），一共16个，每一个32字节（XMM是8字节）。通过与SIMD Operations 的结合，还可以实现向量化操作。

SIMD Operations

其中一条矢量加法指令可以同时执行八次单精度浮点加法或者四次双精度浮点加法。如果这个硬件处于繁忙状态，可以大幅提高乘法性能。三个时钟周期，可以并行进行八次流水线的浮点数乘法。

Intel编译器会自动做一些这方面的优化，gcc也尝试去实现这种优化，但效果不好，可能gcc已经放弃这个优化了。因此只能手动实现向量化编程（参考：http://csapp.cs.cmu.edu/3e/waside/waside-simd.pdf）。

SIMD向量操作与标量操作的性能和吞吐量对比：

What About Branches?

Instruction Control Unit 指令控制单元必须在Execution Unit 执行单元之前产生足够多的操作（Fetch），以让Execution Unit 保持繁忙。当遇到条件分支时，不确定往哪条分支继续执行，需要等到Execution Unit执行到这里之后才知道。在等待的过程中，Execution Unit 的指令池变得很空。

Branch Prediction

分支预测技术，猜测可能的分支走向并执行指令。如果猜错，则回退到预测点，重新执行。回退过程会消耗大量时钟周期，可能成为性能瓶颈。

总结：Getng High Performance