第五章 优化程序性能
优化程序性能
编写高效程序需要做到以下几点：第一，我们必须选择一组适当的算法和数据结构。第二，我们必须编写出编译器能够有效优化以转换成高效可执行代码的源代码。
程序优化的第一步就是消除不必要的工作，让代码尽可能有效地执行所期望的任务。
程序优化的第二步，利用处理器提供的指令级并行(instruction-level parallelism)能力，同时执行多条指令。
5.1 优化编译器的能力和局限性
编译器必须很小心地对程序只使用安全的优化，也就是说对于程序可能到的所有可能的情况，在 C 语言标准提供的保证之下，优化后得到的程序和未优的版本有一样的行为。限制编译器只进行安全的优化，消除了造成不希望的运行时行为的些可能的原因，但是这也意味着程序员必须花费更大的力气写出编译器能够将之转换成效机器代码的程序。
两个指针可能指向同一个内存位置的情况称为内存别 名使用（memory aliasing），在只执行安全的优化中，编译器必须假设不同的指针可能会指向内存中一个位置。
如果编译器不能确定两个指针是否指向同一个位置，就必须假设什么情况都有可能，这就限制了可能的优化策略。
5.2 表示程序性能
我们引人度量标准每元素的周期数（Cycles Per Element, CPE）, 作为一种表示程序性能并指导我们改进代码的方法。
处理器活动的顺序是由时钟控制的，时钟提供了某个频率的规律信号，通常用千兆赫兹(GHz), 即十亿周期每秒来表示。
5.4 消除循环的低效率
优化是一类常见的优化的一个例子，称为代码移动（code motion）这优化包括识别要执行多次（例如在循环里）但是计算结果不会改变的计算。因而以将计算移动到代码前面不会被多次求值的部分。
5.5 减少过程调用
过程调用会带来开销，而且妨碍大多数形式的程序优化。
5.6 消除不必要的内存引用
减少对内存的引用次数
5.7 理解现代处理器
5.7. 1 整体操作
图 5-11 —个乱序处理器的框图。指令控制单元负责从内存中读出指令, 弁产生一系列基本操作。然后执行单雜聋成这些操作 及指出分支预测是否正确
5.7.2 功能单元的性能
图 5-12 提供了 Intel Core i7 Haswell 参考机的一些算术运算的性能，有的是测量出来的，有的是引用 Intel 的文献[49]。这些时间对于其他处理器来说也是具有代表性的。每个运算都是由以下这些数值来刻画的：一个是延迟（latency）, 它表示完成运算所需要的总时间；另一个是发射时间（issue time）, 它表示两个连续的同类型的运算之间需要的最小时钟周期数；还有一个是容量（capacity），它表示能够执行该运算的功能单元的数量。
图 5-12 参考机的操作的延迟、发射时间和容量特性。延迟表明执行实际运算所需要的时钟周期总数，而发射时间表明两次运算之间间隔的最小周期数。容量表明同时能发射多少个这样的操作。除法需要的时间依赖于数据值
5.7.3 处理器操作的抽象模型
- 从机器级代码到数据流图
图 5-13 combine4的内循环代码的图形化表示。指令动态地被翻译成一个或两个操作，每个_操作从其他操作或寄存器接收值，并且为其他操作和寄存器产生值。我们给出最后条指令的目标为标号 loop 它跳转到给出的第一条指令
图 5-14 是对图 5-13 的图形化表示的进一步改进，目标是只给出影响程序执行时间的操作和数据相关。在图 5-14a 中看到，我们重新排列了操作符，更清晰地表明了从顶部源寄存器(只读寄存器和循环寄存器)到底部目的寄存器(只写寄存器和循环寄存器)的数据流。
图 5-14 将 combine4 的操作抽象成数据流图
- 其他性能因素
数据流表示中的关键路径提供的只是程序需要周期数的下界。还有其他一些因素会限制性能，包括可用的功能单元的数量和任何一步中功能单元之间能够传递数据值的数量。
5.8 循环展开
循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。
5.9 提局并行性
在此，程序的性能是受运算单元的延迟限制的。不过，正如我们表明的，执行加法和乘法的功能单元是完全流水线化的，这意味着它们可以每个时钟周期开始一个新操作，并且有些操作可以被多个功能单元执行。硬件具有以更高速率执行乘法和加法的潜力，但是代码不能利用这种能力，即使是使用循环展开也不能，这是因为我们将累积值放在一个单独的变量acc 中。在前面的计算完成之前，都不能计算 acc 的新值。虽然计算 acc 新值的功能单元能够每个时钟周期开始一个新的操作，但是它只会每 L 个周期开始一条新操作，这里 L 是合并操作的延迟。现在我们要考察打破这种顺序相关，得到比延迟界限更好性能的方法。
5.9.1 多个累积变量
对于一个可结合和可交换的合并运算来说，比如说整数加法或乘法，我们可以通过将一组合并运算分割成两个或更多的部分，并在最后合并结果来提高性能。
图 5-21 展示的是使用这种方法的代码。它既使用了两次循环展开，以使每次迭代合并更多的元素，也使用了两路并行，将索引值为偶数的元素累积在变量 OCGD 中，而索引值为奇数的元素累积在变量 accl 中。因此，我们将其称为 2x2循环展开”。同前面一样，我们还包括了第二个循环，对于向量长度不为 2的倍数时，这个循环要累积所有剩下的数组元素。然后，我们对 accO 和 accl 应用合并运算，计算最终的结果。
图 5-21 运用 2X2 循环展开。通过维护多个累积变量，这种方法利用了多个功能单元以及它们的流水线能力
要理解 combines 的性能，我们从图 5-22 所示的代码和操作序列开始。通过图 5-23 所示的过程，可以推导出一个模板，给出迭代之间的数据相关。同 combines —样，这个内循环包括两个 vmulsd 运算，但是这些指令被翻译成读写不同寄存器的 mul 操作，它们之间没有数据相关（图 5-23b）然后，把这个模板复制 n/2 次（图 5-24）, 就是在一个长度为n的向量上执行这个函数的模型。可以看到，现在有两条关键路径，一条对应于计算索引为偶数的元素的乘积(程序值 accO)另一条对应于计算索引为奇数的元素的乘积（程序值 accl）每条关键路径只包含n/2 个操作，因此导致 CPE 大约为 5.00/2=2.50。相似的分析可以解释我们观察到的对于不同的数据类型和合并运算的组合，延迟为 L 的操作的CPE 等于 L/2 实际上，程序正在利用功能单元的流水线能力，将利用率提髙到 2 倍。唯一的例外是整数加。我们已将将 CPE 降低到 1.0 以下，但是还是有太多的循环开销，而无法达到理论界限 0.50。
图 5-22 combines内循环代码的图形化表示。每次循环有两条 vmulsd 指令，每条指令被翻译成一个 load 和一个 mul 操作
图 5-23 将 combine6的运算抽象成数据流图
图5-24 combine6 对一个长度为 的向量进行操作的数据流表示。现在有两条关键路径，每条关键路径包含 n/2 个操作
5.9.2 重新结合变换
图 5-2_6 给出了 函数 combine7 它与 combine5 的展开代码（图 5-16）的唯一区别在于内循环中元素合并的方式。在 combines 中，合并是以下面这条语句来实现的
acc= (acc OP data[i]) OP data[i+l];
而在 combine? 中，合并是以这条语句来实现的
acc= acc OP (data[i] OP data[i+1]);
差别仅在于两个括号是如何放置的。我们称之为 重新结合变换。
图 5-26 运用 2x1a 循环展开，重新结合合并操作。这种方法增加了可以并行执行的操作数量
图 5-27 说明了 combine7内循环的代码（对于合并操作为乘法，数据类型为 double的情况）是如何被译码成操作，以及由此得到的数据相关。我们看到，来自于 vmovsd 和第一个 vmulsd 指令的 load 操作从内存中加载向量元素 i 和 i+1, 第一个 mul 操作把它们乘起来。然后，第二个 mul 操作把这个结果乘以累积值acc。图 5-28a 给出了我们如何对图 5-27 的操作进行重新排列、优化和抽象，得到表示一次迭代中数据相关的模板（图 5-28b）对于 combine5 和 combine7 的模板，有两个 load 和两个 mul 操作但是只有一个mul 操作形成了循环寄存器间的数据相关链。然后，把这个模板复制 n/2 次，给出了 n 个向量元素相乘所执行的计算（图 5-21），我们可以看到关键路径上只有 n/2 个操作。每次迭代内的第一个乘法都不需要等待前一次迭代的累积值就可以执行。因此，最小可能的 CPE减少了 2 倍。
图 5-27 combine7 内循环代码的图形化表示。每次迭代被译码成与 combines5 或 combines6 类似的操作，但是数据相关不同
图 5-28 将 combine7 的操作抽象成数据流图
图 5-29 combine7 对一个长度为 w 的向量进行操作的数据流表示。我们只有一条关键路径，它只包含n/2 个操作
5.11 —些限制因素
5.11.1 寄存器溢出
现代X86-64 处理器有 16 个寄存器，并可以使用 16 个 YMM 寄存器来保存浮点数。一旦循环变
量的数量超过了可用寄存器的数量，程序就必须在栈上分配一些变量。
5.11.2 分支预测和预测错误处罚
- 不要过分关心可预测的分支
- 书写适合用条件传送实现的代码
5.12 理解内存性能
5.12. 1 加载的性能
一个包含加载操作的程序的性能既依赖于流水线的能力，也依赖于加载单元的延迟。在参考机上运行合并操作的实验中，我们看到除了使用 SIMD 操作时以外，对任何数据类型组合和合并操作来说，CPE 从没有到过 0.50 以下。一个制约示例的 CPE 的因素是，对于每个被计算的元素，所有的示例都需要从内存读一个值。对两个加载单元而言，其每个时钟周期只能启动一条加载操作，所以 CPE 不可能小于 0.50。对于每个被计算的元素必须加载k个值的应用，我们不可能获得低于k/2 的 CPE。
5.12.2 存储的性能
存储单元包含一个存储缓冲区,它包含已经被发射到存储单元而又还没有完成的存储操作的地址和数据，这里的完成包括更新数据高速缓存。提供这样一个缓冲区，使得一系列存储操作不必等待每个操作都更新高速缓存就能够执行。当一个加载操作发生时，它必须检查存储缓冲区中的条目，看有没有地址相匹配。如果有地址相匹配（意味着在写的字节与在读的字节有相同的地址）， 它就取出相应的数据条目作为加载操作的结果。
与到目前为止我们已经考虑过的其他操作不同，存储操作并不影响任何寄存器值。因此，就其本性来说，一系列存储操作不会产生数据相关。只有加载操作会受存储操作结果的影响，因为只有加载操作能从由存储操作写的那个位置读回值。图 5-33 所示的函数Write_read 说明了加载和存储操作之间可能的相互影响。这幅图也展示了该函数的两个示例执行，是对两元素数组 a 调用的，该数组的初始内容为一10 和 17, 参数 cnt 等于 3。这些执行说明了加载和存储操作的一些细微之处。
图 5-33 写和读内存位置的代码，以及示例执行- 这个函数突出的是当参数 src 和 dest 相等时，存储和加载之间的相互影响
图 5-34 加载和存储单元的细节。存储单元包含一个未执行的写的缓冲区。加载单元必须检查它的地址是否与存储单元中的地址相符，以发现写/读相关
图 5-35 给出了这个循环代码的数据流表示。指令 movq % rax,(%rsi)被翻译成两个操作：s_addr 指令计算存储操作的地址，在存储缓冲区创建一个条目，并且设置该条目的地址字段。s_data 操作设置该条目的数据字段。正如我们会看到的，两个计算是独立执行的，这对程序的性能来说很重要。这使得参考机中不同的功能单元来执行这些操作。
图 5-3S write_read 内循环代码的图形化表示。第一个 movl 指令被译码两个独立的操作，计算存储地址和将数据存储到内存
除了由于写和读寄存器造成的操作之间的数据相关，操作符右边的弧线表示这些操作隐含的相关。特别地 s_addr 操作的地址计算必须在s_data操作之前。此外，对指令 movq (%rdi),rdx 译码得到的 load 操作必须检查所有未完成的存储操作的地址，在这个操作和 s_addr 操作之间创建一个数据相关。这张图中 s_data 和 load 操作之间有虚弧线。这个数据相关是有条件的：如果两个地址相同，操作必须等待直到 s_data 将它逋结果存放到存储缓冲区中，但是如果两个地址不同，两个操作就可以独立地进行。
图 5-36 说明了 write_read 内循环操作之间的数据相关。在图 5-36a 中，重新排列了操作，让相关显得更清楚。我们标出了三个涉及加载和存储操作的相关，希望引起大家特别的注意。标号为（1）的弧线表示存储地址必须在数据被存储之前计算出来。标号为（2）的弧线表示需要 load 操作将它的地址与所有未完成的存储操作的地址进行比较。最后，标号为（3）的虚弧线表示条件数据相关，当加载和存储地址相同时会出现。
图 5-36 抽象 write_read 的操作。我们首先重新排列图 5-35 的操作(a), 然后只显示那些使用一次迭代中的值为下一次迭代产生新值的操作（b）
图 5-37 函数 write_read 的数据流表示。当两个地址不同时，唯一的关键路径是减少 cnt(示例A)，当两个地址相同时，存储、加载和增加数据的链形成了关键路径(示例 B)
5.13 应用：性能提高技术
要警惕，在为了提高效率重写程序时避免引入错误。在引人新变量、改变循环边界和使得代码整体上更复杂时，很容易犯错误。一项有用的技术是在优化函数时，用检查代码来测试函数的每个版本，以确保在这个过程没有引人错误。检查代码对函数的新版本实施一系列的测试，确保它们产生与原来一样的结果。对于高度优化的代码，这组测试情况必须变得更加广泛，因为要考虑的情况也更多。
5.14 确认和消除性能瓶颈
至此，我们只考虑了优化小的程序，在这样的小程序中有一些很明显限制性能的地方，因此应该是集中注意力对它们进行优化。在处理大程序时，连知道应该优化什么地方都是很难的。本节会描述如何使用代码剖析程序（code profiler）, 这是在程序执行时收集性能数据的分析工具。我们还展示了一个系统优化的通用原则，称为 Amdahl 定律。
5.14.1 程序剖析
程序剖析(profiling)运行程序的一个版本，其中插人了工具代码，以确定程序的各个部分需要多少时间。这对于确认程序中我们需要集中注意力优化的部分是很有用的。剖析的一个有力之处在于可以在现实的基准数据（benchmark data}上运行实际程序的同时，进行剖析。
Unix 系统提供了一个剖析程序 GPROF。这个程序产生两种形式的信息。首先，它确定程序中每个函数花费了多少 CPU 时间。其次，它计算每个函数被调用的次数，以执行调用的函数来分类。这两种形式的信息都非常有用。这些计时给出了不同函数在确定整体运行时间中的相对重要性。调用信息使得我们能理解程序的动态行为。
GPR0F 有些属性值得注意：
- 计时不是很准确
- 假设没有执行内联替换
- 默认情况下，不会显示对库函数的计时
5.14.2 使用剖析程序来指导优化
5.15 小结
虽然关于代码优化的大多数论述都描述了编译器是如何能生成髙效代码的，但是应用程序员有很多方法来协助编译器完成这项任务。没有任何编译器能用一个好的算法或数据结构代替低效率的算法或数据结构，因此程序设计的这些方面仍然应该是程序员主要关心的。我们还看到妨碍优化的因素，例如内存别名使用和过程调用，严重限制了编译器执行大量优化的能力。同样，程序员必须对消除这些妨碍优化的因素负主要的责任。这些应该被看作好的编程习惯的一部分，因为它们可以用来消除不必要的工作。