前言

最近重读 CSAPP 第五章，这一章的主题是优化程序性能。

首先，在开始着手优化程序性能之前，需要考虑现有程序的算法和数据结构，先优化算法。这种优化获得的提升是数量级的提升，比如从 \(O(N^2)\) 复杂度到 \(O(N)\) 复杂度，这种理论上复杂度的优化，在数据量上去之后，效果明显。

接下来就是要相信编译器是很聪明的，它帮助你做很多性能优化，gcc 开启 -O 选项进行优化。但是呢，我们需要认识到编译器的界限在哪里，编译器不会帮你做哪些优化。对于编译器，它要考虑的是如何保证优化后程序的行为一致。因为一些问题的存在，编译器无法确定是否可以优化。最典型的问题是 memory aliasing，出现的场景是两个指针指向同一块内存地址。函数可能有 side effect，所以函数调用不会被轻易的优化，除非是 inline。知道了编译器能与不能，就可以写出编译器比较好优化的代码了。

最后是基于对现有处理器结构的理解，对内存层级的理解进行优化。现代处理器中处理指令和执行指令一般是分开的，处理指令的地方我们称之为 ICU(Instruction control unit)，执行指令的地方我们称之为 EU(Execution unit)。ICU 负责取指令，将指令解码成更小的可执行单元。EU 负责接收这些更小的可执行单元，这些分解的操作可以并行执行，因此可以利用这一点对程序进行优化。这章提到了三个优化的技巧：Loop Unrolling, Multiple Accumulators, Reassociation Transformation。此外，现代处理器还提供了 SIMD(Single Instruction Multiple Data)，单条指令，多个数据，使用这些指令可以获取更好的并行度，从而进一步提高程序性能。

这一章很重要的一个知识点是数据流图的分析，借助数据流图的分析，我们找到并定位程序的性能瓶颈。在分析数据流图的时候，需要意识到处理器的流水线特性。一个指令可以分解为多个小操作，这些小操作可以流水并行。因此在使用数据流图分析的时候，要考虑这一点。

优化技巧总结

• Eliminating Loop Inefficiencies，减少循环时低效调用，比如 for 循环当中检查边界，如果每次都调用一个方法获取长度，这将大大增加时间消耗，更坏的情况是导致了算法复杂度的改变。
• Reducing Procedure Calls，减少程序调用。
• Eliminating Unneeded Memory References，减少不必要的内存引用。使用一个寄存器变量做临时读写，将最后的结果写入到内存中。如果每次都写入内存，那么会很低效。
• Loop Unrolling，循环展开。for 循环每次步进 2 或者更多，提供指令级别并行。
• Multiple Accumulators，使用多个累积变量。从数据流图的角度去分析，使用多个累积变量可以获得更好的指令并行。
• Reassociation Transformation。算术运算的时候，可以先计算某些部分来获得更好的指令并行。
• SIMD，从指令级别的角度看，使用单条指令多条数据去加速并行。
• Register Spilling。如果使用了太多累积变量，超过了寄存器的数量，那么会开始使用放在内存中的栈变量，这样将会导致访存，使性能下降。
• 现代处理器采用了乱序执行的策略，对于分支执行，它会选择一个分支直接执行，如果分支预测错误了，那么将会清理环境，重新取指令，重新执行。为了减少这种分支预测错误带来的代价，可以使用 Conditional Moves 类别的指令来减少分支预测错误的代价。
• Do Not Be Overly Concerned about Predictable Branches。不用过多担心分支预测。因为很多情况下，分支预测的结果往往是正确的，只有最后一个元素预测错误，比如判断 index 是否已经在数组的边界等操作。不过对于一些比较随机的判断，分支预测的性能却不会很好，所以这些随机的分支判断可以使用 Conditional Moves 进行优化。

CPE

这一章让我觉得非常优雅的一个地方是 CPE，使用 Cycles Per Element 来评估性能。这有助于从理论层面上分析一段代码的性能边界究竟在哪里。Cycle 是处理器执行周期，比如一个 4GHz 的处理器，它每秒进行 \(4 \times 10^9\) 个操作，每个周期 \(0.25 ns\)。评估一段程序的性能，可以看看每个元素处理了多少个周期，即使用 CPE 来评估性能。

5.12 给出了处理器上操作的时间， Latency 是操作执行的时间，Issue 是两个操作之间需要的时间，Capacity 表示可以同时执行多少个这样的操作。后面的表中的 Throughput 分析了每个操作对每个元素执行时间 CPE 的理论上界。比如浮点数乘法，Capacity 为 2，Issue 为 1，在流水执行的情况下，平均下来一个浮点数需要 0.5 个 CPE，同理加法浮点数为 1.0 个 CPE。不过这里有个特别的例子，证书加法的 CPE 为什么是 0.5 而不是 0.25 呢？其实因为程序的瓶颈在别处，因为处理器上只有两个 load 单元，每次只能读取两个元素，所以不能同时 4 个元素都在进行。

CPE 的估计

计时的方法如下。我实现了一个最简单的求和，每个元素执行时间 2 ns。\(2 \times 1\) 循环展开、\(2 \times 2\) 循环展开、Reassociation Transformation 循环展开 的结果都是 1。看了一下服务器上的频率是 2.3GHz，每个周期大概是 0.5 ns。所以简单求和的 CPE 为 4，优化后的 CPE 为 2。如果要分析理论上界，我们还需要知道这个处理器的结构才行。(ps. 处理器是 Intel(R) Xeon(R) Gold 5218 CPU @ 2.30GHz)

#include <chrono>
using namespace std::chrono;

auto start = high_resolution_clock::now();
int ans = sum(x, N);
auto stop = high_resolution_clock::now();
auto duration = duration_cast<nanoseconds>(stop - start);
cout << duration.count() / N << endl;
cout << ans << endl;

多项式求和

书上有两个问题(5.5 和 5.6)讲的是多项式求和。多年前读到这个反直觉的例子，让我印象深刻至今。这两道题画个数据流图分析一下就清楚了。

• 在 5.5 中我们需要计算 n 次加法，2n 次乘法。在 5.6 中，我们需要计算 n 次加法，n 次减法。所以 5.6 计算次数更少，是不是应该算的更快呢？

• 直观来看，5.6 执行的运算数量少，应该有更快一点才对。不过画个数据流图，分析一下就知道 5.6 存在依赖关系，不能指令级别并行，而 5.5 不存在这种依赖关系，所以可以指令级别并行，速度比 5.5 要快！

对于 5.5 的数据流图分析，需要知道“流水线执行”。在计算 result 的 add 节点的时候，需要 3 个 CPE，但是因为不存在依赖关系，下一个 xpwr 可以并行执行，所以这个 add 节点的运算开销会被 xpwr 节点的乘法运行给掩盖。决定整个程序性能瓶颈的是 xpwr 的乘法计算。

对于 5.6 的数据流图，我们可以看到整个计算过程的 critical path 需要经过一个乘法，一个加法。因为存在依赖关系，所以乘法和加法不能并行，所以这注定了 5.6 比 5.5 慢。

总结

这篇博客挺短的，将书上的优化技巧提炼总结出来。在阅读第五章的时候，最好关注两个层面。第一，编译器能干什么、不能干什么，它的局限在哪里。第二，需要了解现代处理器的结构设计，了解内存层级读写性能，优化是建立在对于这些结构的理解之上的。