第2章 串行代码基本优化技术
在千核级并行计算机时代，有些观点认为编写高效串行代码在许多领域已经有些过时了。因为增加更多CPU以获得大规模并行能力要比投入大量精力优化串行代码简单得多。这似乎是一个合理的理论，5.3.8节的论述中也体现了对这种观点的支持。然而，本书认为程序在单处理器上的性能优化毫无疑问是最重要的，如果通过一些简单的优化方法就可以实现两倍加速比，那么用户会更倾向于使用较少的CPU。这样不仅可把宝贵的计算资源释放给其他用户或项目，而且还可以使投入大量资金购买的硬件获得更加有效的利用。因此，并行代码性能优化的第一步应该是在单处理器上的优化，使其运行速度加快。本章总结了串行代码剖析和优化的基本工具和策略。第3章会进行更深入的讨论，特别是数据传输优化的相关内容。
2.1 标量剖析
收集程序行为的相关信息，特别是程序对资源的使用信息，这个过程称为程序剖析。其中，在高性能计算方向最重要的“资源”是运行时间。因此，常见的剖析策略是评估程序中不同函数，甚至某几行关键代码的运行时间，并以此确定热点（hot spot，运行时间占主导地位的代码段）。这些热点随后会被剖析，并尽可能地进行优化。2.1.1节分别介绍了基于函数和基于代码行的程序剖析方法。
然而，即使已经确定热点，但在很多情况（特别是这些函数或者代码块包含多行代码）下，造成性能瓶颈的原因却并不明确。这时，确定程序性能限制因素（如主存数据访问或流水线阻塞）的愿望就会非常迫切。如果数据访问是主要限制因素，则最直接的方法是确定导致程序性能降低的数据访存操作。解决这个问题的有效途径是使用硬件性能计数器，可提供当前系统使用的所有处理器信息，并提供芯片和系统内资源使用情况的深入分析。2.1.2节对此会有详细讨论。
应该指出，在很多情况下，我们对串行代码的性能提升无能为力。因此，使用户能够确定优化工作的有效性至关重要。3.1节提供了此类常见情况的指导。
2.1.1 基于函数和代码行的程序剖析
一般情况下，基于函数和代码行的剖析主要有两种技术：代码插入和采样。代码插入的工作原理是让编译器修改每个函数的调用，并插入代码以记录这些调用、调用者（或者完整调用栈）以及可能需要的时间信息。显然，这个技术会导致明显的额外开销（特别是当代码执行时间非常短时）。虽然代码插入技术会试图弥补这些开销，但仍然存在很多不确定性。相对这些额外开销，代码采样有着明显优势：程序在一定的时间间隔（如10ms）内被周期性中断，并且记录程序计数器（或当前调用栈）信息。这个过程本质上是统计，代码运行的时间越长，产生的结果就越精确。结合目标代码相关信息，代码抽样还可以在源代码行甚至机器代码行级别产生运行时间信息。由于效率的原因，限制了代码插入在很多函数或者代码块（只有一个入口和出口，代码块间又没有相互调用和跳转）上的使用。
1．函数剖析
GNU binutils包提供的gprof是使用最广泛的函数剖析工具。gprof使用代码抽样和插入技术，收集函数剖析和调用图（也称为蝴蝶图）文件。为激活剖析功能，代码编译时必须指定合适的编译选项（许多现代编译器都能够产生与gprof兼容的指令：如GCC，使用-pg编译选项）并运行一次。这将产生一个人工不可读、但可被gprof理解的输出文件：gmon.out。这个文件包含了程序中所有函数的执行时间以及它们的调用频次信息：
https://yqfile.alicdn.com/386eae9e91da48b9960355b81dbde1ec8bad7ae3.png" >
每一行代表一个函数，各列解释如下：
%time：函数独立运行时间（不包含被该函数调用的其他函数的运行时间）占总运行时间的百分比。
cumulative seconds：所有函数的累积运行时间（包括自身）。
self seconds：函数的独立运行时间（单位：秒）。默认情况下，表单会根据这一列信息进行排序。
calls：函数被调用的次数。
self ms/call：函数每次调用的平均独立运行时间（单位：ms）。
total ms/call：函数每次调用的平均整体运行时间（包括被它调用的其他函数的运行时间，单位：ms）。
根据gmon.out，上面实例的优化工作应该从intersect()函数开始，同时也要关注shade()函数的优化。函数的独立运行时间暗示了优化该函数所能获得的最大性能提升。例如，如果能将shade()函数的性能提高两倍，那么整个应用程序的运行时间为7.3?-?0.95?=?6.35s，大约得到了15%的性能提升。
注意，程序剖析结果关键取决于编译器执行内联函数的能力。内联是一种使用函数体本身替代函数调用接口，以减少函数调用开销的优化方法（更加深入的讨论见2.4.2节）。如果编译器支持内联功能，那么剖析结果可能会被严重曲解（当热点函数被内联执行时，其运行时间会作为调用函数运行时间的一部分输出）。当内联函数对程序性能有明显影响，而编译器/剖析器不支持对内联函数的正确剖析时，需要禁止内联功能。当然，这样可能会对程序性能产生明显影响。
虽然剖析文件已经包含了大量信息。然而，它并没有说明当一个函数被几个不同函数调用时，对运行时间的贡献是怎么样的；这个函数又调用了哪几个子函数，当这些子函数依次调用时，对运行时间又贡献了多少。蝴蝶图（函数调用图）提供了这些信息。
调用图的每一部分代表一个函数，最左边显示了该函数的运行索引。位于该索引之上的函数是当前函数的调用者函数（调用当前函数的函数），之下的是被调用者函数（被当前函数调用的函数）。同时，调用图也说明了函数的递归调用（见shade()函数）情况。调用图各个字段的含义如下：
%time对应函数运行时间（包括被调用者函数的运行时间）占总运行时间的百分比。这应该等于剖析文件中该函数的“调用次数”与“每次调用整体运行时间”的乘积。
self对应函数的独立运行时间（与剖析文件一样，不包括被调用者函数的运行时间）。对于调用者函数（被调用者函数）行，该列值说明了对应函数（被调用者函数）对其调用者函数（对应函数）的整体运行时间贡献。
children：对应函数的整体运行时间减去独立运行时间（对应函数的被调用者函数的总运行时间）。对于调用者函数行，其列值为对应函数的被调用者函数对其调用者函数运行的时间贡献。对于被调用者函数行，其列值为对应函数的被调用者函数的被调用者函数对该函数的运行时间贡献。
called：对应函数的调用次数（可分为递归调用次数+非递归调用次数，如shade()函数）。对于调用者函数行，其列值为该函数被调用者函数的调用次数。对于被调用者函数行，其列值为被调用者函数被该函数调用的次数。
目前有很多工具实现了蝴蝶图的可视化。借助可视化蝴蝶图，可浏览整个调用树并快速找到关“键路径”，即对整体运行时间起主导作用的函数序列：从根节点到某些叶子节点。
2.基于行的剖析
如果待剖析程序中有大函数（代码行作为计量单位），这个函数的运行时间又在整体运行时间中占很大比例时，基于函数的剖析就显得力不从心了：
如上表所示，Fortran程序的main函数大约有1700行代码，运行时间占总体运行时间的73%。如果使用简单方法不能确定这类函数的热点，就需要借助基于行的剖析工具。目前，有许多这种开源或者商业工具，可在不同层面上完成基于行的代码剖析工作。本节以开源工具OProfile[T19]为例说明基于行的程序剖析过程。需要说明的是，OProfile也具有基于函数的程序剖析功能，在某种程度上可代替gprof。使用OProfile的唯一前提是程序必须进行可调式编译（通常通过添加编译选项-g实现），不需要其他特殊指令。然后启动后台剖析程序（通常由系统超级管理员启动），以监控整个计算机系统并收集正在运行的所有二进制文件信息。最后，用户可提取一个特定二进制文件的相关信息。除其他事项外，这个信息可以看作带注释的源代码：每一行源代码都添加了相应的采样命中次数（第一列）和占全部程序采样的相对百分比（第二列）信息：
然而，对这些数据的使用必须要特别小心。为使机器指令在内存中的地址能够和源代码行正确匹配，编译器生成的符号表必须保持一致性。如果开启高级优化，现代编译器会大量重组代码（比如，循环的融合与拆分、代码行的重新排列以及变量的优化消除等）。所以，实际执行的代码可能和原始代码差异很大。更进一步讲，由于现代处理器的流水线架构，查看特定源代码甚至机器指令在特定时刻的状态是不可能的。然而，采用基于循环的方法（取样自各个循环体）查看基于代码行的剖析数据还是相对安全的。如果对剖析信息有疑问，可对代码进行基于低级别优化的重新编译（禁用内联），这样可能会提供更加有意义的信息。
上述基于代码行的剖析数据可非常方便地放入表单中，以确定程序热点。如果某一行代码产生了较多的采样，所有样本的累积总和会在该行号上产生一个陡峭的斜坡（如图2-1所示）。
2.1.2 硬件性能计数器
确定热点（如根据时钟周期）是程序性能剖析的第一步。然而，要确定程序性能低的原因或者确定限制程序性能的资源，仅有时钟周期信息是远远不够的。幸运的是，现代处理器都采用了少量性能计数器（通常远小于10）。性能计数器是一种专用片上寄存器，当特定事件发生时，其值会依次递增。在它可以监控的几百个事件中，下面几个信息是对程序性能剖析最有用的：
- 总线事务（即cache行数据传输）次数。一般情况下，会用“cache 未命中”来替代总线事务。然而，由于预取机制（硬件或者软件实现）会干扰cache命中率的统计。使用“总线事务次数”统计内存总线传输的数据量是比较稳妥的方式。如果处理器实际使用的访存带宽接近理论峰值（更高或者接近STREAM（访存带宽标准测试集）[W119,134]能达到的访存带宽，具体见3.1节），再继续优化访存带宽利用率对性能提升就没有意义了。此外，“总线事务次数”还可用于验证一些理论模型（比如一个为应用程序评估数据传输量的模型）的正确性（3.1节对这个模型进行了详细讨论）。
- 访存次数。结合总线事务次数可指导cache行的效利用。例如，如果从一个cache行中加载或者存储的DP数据小于DP字中cache行的大小，说明这是一个非连续访存。非连续访存一般会造成程序性能的降低。然而，我们必须要对数据的使用方式非常清楚。例如，由于某些原因，处理器流水线在绝大部分时间内阻塞或寄存器数据进行了大量算术运算，非连续访存可能就不是应用程序的性能瓶颈。
- 浮点数运算次数。这个基准的重要性经常被高估（正如第3章讨论，科学应用程序的主要性能限制因素是数据传输）。如果每个CPU时钟周期所能进行的浮点数运算次数接近理论峰值（给定CPU的峰值性能，或者当乘法和加法操作不对称时相对较低的性能）时，基本的代码优化方法不太可能提升程序性能，这时可能要考虑算法上的改进。
- 分支预测失误。当CPU对条件分支预测错误时，该计数器递增。分支预测的时间消耗与具体的硬件架构相关，大约是数十个时钟周期（见2.3.2节的讨论）。科学应用程序往往是基于循环的，因此分支会被很好地预测。然而，“指针链接”和计算性分支增加了预测失误的可能性。
- 流水线阻塞。由于处理器流水线（见1.2.3节）不同阶段执行的操作间存在相互依赖，导致流水线某一阶段处于等待空闲状态，称为流水线阻塞，或者流水线气泡。通常情况下，流水线阻塞是不能避免的。例如，当访存带宽是程序性能的限制因素时，算术单元将耗费大量的时间等待操作数据。当有“太多”气泡时，确定优化方法是非常困难的。如果没有让具备执行条件的指令首先执行的机制，单纯依靠硬件是无法有效修正气泡现象的，因此阻塞周期分析在有序架构（如Intel IA64）上非常重要。
- 执行指令条数。结合钟周期可成为判断如何有效利用具有多执行单元的超标量硬件架构（拥有多个执行单元）的准则。经验表明，即使有设计良好的流水线，并且有紧凑内循环代码，编译器生成代码的执行性能也很难达到每时钟周期2～3条指令。
使用硬件性能计数器进行程序剖析的方法基本有两种。我们常借助于工具快速了解应用程序的性能属性。这个工具不仅能够检测全部计数器信息，而且还可能计算生成许多派生计数器信息，如“每时钟周期指令数”和“每访存cache未命中数”。在这个工具中运行某些应用程序可能会产生类似的输出（这些例子都是在SGI Altix系统上根据lipfpm工具生成的输出进行编译的）：
通常使用的性能计数器数目非常少（一般为2～4个）。如需使用大量计数器（如上例）可能需要运行应用程序多次，或者剖析工具本身支持不同矩阵组的多路复用（如多个不同计数器组在一定时间间隔内可进行切换如100ms）。后者会引入一个统计错误，这个错误必须密切关注（特别是涉及的计数非常小或者应用程序运行时间非常短的情况）。
上例中，每个时钟周期完成的指令数目（较多）、对cache和主存带宽需求（较小）、已完成的存取指令数目与L2 cache未命中数目的关系，都说明了这个硬件已经得到了很好的利用。流水线气泡占总CPU时钟周期的40%，如果没有其他参照，很难说明这个值到底是高还是低。为了便于比较，下面是运行在相同硬件架构上的向量代码（采用较长的向量长度）的剖析结果：
https://yqfile.alicdn.com/e3815aff7d6ff9de58ad1d88176d7558da943136.png" >
上例的带宽需求（较高）、每个时钟周期完成的指令数（较少）、存取指令数与L2 cache未命中数的关系，都表明这是一个访存受限应用。与前面的例子相比，阻塞指令所占比例增加了一倍以上。只有基于多个计数器、精心设计的阻塞指令周期分析，才能够解释这些气泡产生的原因。
尽管提供了一些重要信息，但收集“全局”硬件计数器信息在很多情况下还是过于简单。比如，如果将应用程序的性能剖析信息根据性能属性的较大差异（如cache受限与访存受限）分成许多子段，结合计数器信息可能会导致错误的结论。将计数器的增长限制到特定的代码段，可实现计数器剖析文件的分解并获得更具体的数据。最简单的工具是一个至少允许控制计数器的开启和禁用的API库。包含在LIKWID[T20,W120]包中的开源工具就可以做到这一点，更重要的是，这个工具和目前绝大多数x86架构的处理器兼容。
使用硬件性能计数器的更高级方式（OProfile和Intel VTune[T21]等工具都支持）是将采样机制应用于应用程序的代码行或函数事件上，这和基于代码行的程序剖析非常类似。与简单的定期获取指令指针或者调用栈的快照不同，这个方法对每个计数器（或者更精确些是metric）定义了溢出值。当计数器增加到这个值时会产生一个中断，并进行IP或者调用栈采样。一个特定计数器的采样累积自然会发生在该计数器增加最频繁的地方。注意，以上方法不是基于整个程序而是基于函数，甚至是基于代码行的。然而，对硬件事件计数结果的正确理解需要相当多的经验。
2.1.3 手工代码插入
如果基于编译器的代码插入开销相对于应用程序太大，或者只想对程序的部分代码段进行剖析以获得相对简单的性能属性视图，手工代码插入是非常好的方法。程序员可在程序中插入计时函数如gettimeofday()（见代码清单1-2，wrapper函数），或者插入剖析库加PAPI（T22）（如果需要硬件计数器信息）。像在2.1.1和2.1.2节讨论的那样，许多剖析库都允许应用程序控制标准剖析机制的启动和停止[T20]。在C++代码中，如果由于模板和运算符重载技术的应用而使程序剖析文件变得非常混乱，这种方法将非常有用。
理解计时函数返回结果时要非常小心。当测试时间和计时器的最小计时单位是同一数量级（如用最小的时间间隔就可以完成）时，最容易发生对计时函数返回结果的错误解释。