第五章 优化程序性能
0. 优化之路咋走？
首先需要知道优化之路可以怎么走，下面摘自 CMU 的公开课 slides。主要有两方面因素：
代码风格：良好的数据结构与算法思想，循环、变量等人为因素； 编译器与操作系统：了解编译器优化，从汇编、profile 等角度分析性能瓶颈，了解操作系统层面因素；
1. 量化程序性能
使用 CPE（Cycles Per Element）来量化程序性能。其表示每个循环执行了多少个时钟周期（可以预估执行了多少个指令）。
对于一个“4GHz”的处理器而言，时钟运行的频率是每秒 4x10^9 个周期，即一个时钟周期 = 0.25ns。
例如，将程序的循环的 CPE 从 9 优化到 6，表示我们将程序中的每个循环，从消耗 9 个时钟周期，优化到 6 个时钟周期，节省了 3 个时钟周期。
CPE 其实就是右图中的斜率，我们的优化目标是尽可能让直线躺平。
为什么要用 CPE？
其实就是比较直观，而且容易跟运算单元的速度进行关联，可以很方便地估计出优化的幅度。
下面是常见操作的CPE：
下面是对 capacity、latency、issue 的图形化描述：
- capacity：描述处理器单位时间能过处理的指令数量
- latency：描述单位指令执行时间
- issue：描述相同指令之间的执行间隔（可以翻译为发射时间）
通过各个模块的 CPE，快速估算出优化的幅度：
对于某台机器 load=2, mul=3, add=1
- 左图：关键路径消耗 (load+mul)n=(2+3)n=5n 个时钟周期
- 右图：关键路径消耗 (load+mul+mul)n/2=(2+3+3)n/2=4n 个时钟周期，速度提高 20%
当然，这个 CPE 在实际工作中计算出来是比较麻烦的，但是对于了解常见汇编指令的速度还是有一定帮助。
2. 编译器优化的能力和局限性
编译器能做啥？
这里介绍几个编译器能做的优化。
优化计算表达式：将复杂表达式转换为简单表达式，例如用位操作来代替乘法；
使用公共变量：使用临时变量等方式来避免重复几计算；
编译器挫在哪？
挫一：处理函数调用
为什么编译器不能够发现，并将 strlen 提取到循环外？
- 函数可能有副作用，例如修改某个全局变量
- 函数不一定是幂等的，例如依赖某个全局变量
编译器倾向于把函数调用当作黑盒，因为无法知道其副作用，所以不会对此进行优化。 —— 鲁迅
挫二：内存别名引用
编译器不能优化这点吗？
看上去编译器似乎能够优化这点，但是编译器会假设两个指针地址可能相同，因此必须非常谨慎，躺平不动。
程序员要养成使用局部变量的习惯，显式地告诉编译器，这里没有内存别名。 —— 鲁迅
3. 现代微处理器
到目前为止，我们提及到的优化技巧，都不依赖于目标机器的任何特性。我们目前的优化，只是简单的降低了过程调用的开销、避开了编译器的挫。如果要进一步进行优化，必须考虑利用现代微处理器的优化，也就是处理器用来执行指令的底层系统设计。
这样的处理器，在工业界称为超标量（Superscalar），即每个时钟周期可以执行多个指令，且是乱序执行。整个处理器分为两大部分，指令控制单元（ICU）和执行单元（EU）。
- 指令控制单元：从高速缓存中取指、译码，生成一组 low level 的基本操作；
- 执行单元：执行上述基本操作；包括多个功能单元，比如 arith（算术运算）、load（内存读）、store（内存写）等等，分别负责各自独立的计算和存取内存操作。
当程序遇到分支的时候，程序可能有两个前进的方向。现代处理器使用了分支预测技术（Branch Prediction），会猜测是否选择分支，且会预测分支跳转的目标地址。然后使用投机执行（Speculative Execution）技术对目标分支跳转到的指令进行取指和译码（甚至在分支预测之前就开始投机执行）。如果之后确定分支预测错误，则会将寄存器状态重置为分支点的状态，并开始取出和执行另一个分支上的指令。所以可以看到，分支预测错误会导致很大的性能开销。
4. 让处理器助你一臂之力吧！
循环展开
优化前后的关键路径对比，可以看到每 2 个 Element，节省了一个 load 操作，速度提高 20%：
提高并行性
分治法
优化前后的关键路径对比，可以看到每个 2 个 Element，节省了 mul 操作，速度提高 1x 多：
- 左边关键路径：load+2*mul=8
- 右边关键路径：load+mul=5
重新结合运算
优化前后的关键路径对比，可以看到每个 4 个 Element，节省了 2mul+2load 操作，速度提高 2x 多：
- 左边关键路径：(load+2mul)2=16
- 右边关键路径：2*mul=6
小结
本质：解除数据依赖
- 分治法：利用每个子问题的并行执行提高速度
- 重新结合变换：解除多项式操作中，项之间的关键依赖
分支
书写容易预测的代码
Why is processing a sorted array faster than processing an unsorted array? - Stack Overflow
现代处理器可以很好预测分支指令的有规律模式。
if (data[c] >= 128)
sum += data[c];
T = branch taken
N = branch not taken
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (easy to predict)
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, ...
branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T ...
= TTNTTTTNTNNTTT ... (completely random - impossible to predict)
书写适合条件传送的代码
- 条件跳转
- 条件传送
为什么条件传送更快？
先计算，再选择结果。且这些计算没有数据依赖，可以充分利用处理器的指令流水。
SIMD
SIMD（Single Instruction Multiple Data）即单指令流多数据流，是一种采用一个控制器来控制多个执行器，同时对一组数据（又称“数据向量”）中的每一个分别执行相同的操作从而实现空间上的并行性的技术。简单来说就是一个指令能够同时处理多个数据。
Achieving Greater Parallelism with SIMD Instructions
5. 小结
- 良好的编码习惯
- 数据结构与算法
- 消除编译器优化障碍
- 过程调用
- 内存别名引用
- 优化循环
- 帮助机器更好地优化
- 利用指令并行
- 避免不可预测的分支
- 提高指令缓存命中率
本文所讲的这些优化方法，在大部分编译器中都已经实现了。但是它们有可能不会实行这些优化，或需要我们手动设置更高级别的优化选项才行。所以，作为一个程序员，我们应该做的是尽量引导编译器执行这些优化，或者说排除阻碍编译器优化的障碍。这样可以使我们的代码在保持简洁的情况下获得更高的性能。迫不得已时，我们才去手动做这些优化。
另外，循环展开、多路并行并不是越多越好。因为寄存器的个数是有限的，x86-64 最多只能有 12 个寄存器用于累加，如果局部变量的个数多于 12 个，就会被放进存储器，反倒严重拉低程序性能。
6. 身边活生生的例子
数据依赖
组内有同学反馈，跑 pprof 的时候，发现一个简单的函数调用占用了 20% 左右的 CPU 时间，这个函数只是取了一个对象里面的列表元素做简单计算。只不过对象潜套了多个指针，于是怀疑是指针嵌套的问题。
我把对应的代码抽出来，对比了直接引用（左）与指针嵌套引用（右）的汇编代码区别：
可以发现，右侧代码中，红圈中的 5 行指令都是在 DX 寄存器中进行操作，形成了数据依赖，无法充分利用指令流水。
指令缓存
摘自内部 infra 组同学的一篇文章，描述的是 RPC 框架一个小改动带来的性能问题。
事故现场：Mergely - Diff online, merge documents
可以看到，相比旧版本的生成代码，该 commit 在返回错误的时候会额外包装一下：
if err := ...; err != nil {
return thrift.PrependError(fmt.Sprintf("%T read field x 'xxx' error: ", p), err)
}
而旧版本的生成代码是直接返回的错误：
if err := ...; err != nil {
return err
}
虽然这些只是在发生错误的时候才会调用到，在正常流程中不会用到，但是生成的汇编代码中这段逻辑占了相当大的比例：
而 Go 的编译器并没有帮我们重排这些指令，导致在真正运行的时候，L1 cache miss 大大提高，极大地降低了性能。
拓展阅读
以下是 golang 一些性能分析的拓展阅读，有兴趣可以看。
Reference
- CMU 课件 10-optimization
-
CMU 电子书、课程等资料地址 wangmu89/Book-CSAPP: 深入理解计算机系统
- https://github.com/wangmu89/Book-CSAPP)
