优化程序性能·五

第5章 优化程序性能 关键词：程序优化，循环开销，并行性，投机执行，Amdahl定律 编写高效程序需要两类活动：第一，我们必须选择一组最好的算法和数据结构；第二，我们必须编写出编译器能够有效优化以转换成高校可执行代码的源程序。 研究汇编代码是理解编译器以及产生的代码会如何运行的最有效的手段之一。 5.1优化编译器的能力和局限性 对许多程序都很有用的度量标准是每元素的周期数（cycle per element，CPE）。这种度量标准帮助我们在更详细的级别上理解迭代程序的循环性能。 1 降低过程调用开销 消除循环的低效率。移动代码优化，这类优化包括识别出要执行多次（例如，在循环里）但是计算结果不会改变的计算，因而我们可以将计算移动到代码前面的、不会被多次求值的部分。 减少过程调用。过程调用会带来相当大的开销，而且妨碍大多数形式的程序优化。因此减少过程调用，可以优化程序代码。对于性能至关重要的程序来说，为了速度，经常必须要损害一些模块性和抽象性。如果以后要修改代码，添加一些对所采用的变换进行文档的记录是很明智的。 消除不必要的存储器引用。换句话说，就是减少程序读入和写入的次数，数据量少的时候可能用处不明显，但是一旦数据量变大，少读取一次就会使得程序性能大大优化。 2 针对目标处理器进行的程序优化 P6微体系结构，在工业上称为超标量（superscalar），意思是它可以在每个时钟周期执行多个操作，而且是乱序的（out-of-order），意思就是指令执行的顺序不一定要与它们在汇编程序中的顺序一致。整个设计有两个主要部分：ICU（instruction control unit，指令控制单元）和EU（execution unit，执行单元）。前者负责从存储器中读取指令序列，并根据指令序列生成一组针对程序数据的基本操作；而后者执行这些操作。 功能单元的性能。每个操作数都是由两个周期计数值来刻画的：一个是执行时间（latency），它指明功能单元完成操作所需要的总周期数；另一个是发射时间（issue time），它指明连续的、独立操作数之间的周期数。 通常处理器性能是受三类约束闲置的。第一，程序中的数据相关性迫使一些操作延迟直到它们的操作数被计算出来。因为功能单元有一个或多个周期的执行时间，这就设置了一个给定的操作序列执行周期数的下界。第二，资源约束限制了在任意给定时刻能够执行多少个操作。最后，转移预测逻辑的成功约束了处理器能够在指令流中超前工作以保持执行单元繁忙的程度。每次发生预测错误时，处理器从正确位置重新开始都会引起很大的延迟。 5.2 降低循环开销 我们可以在每次迭代中执行更多的数据操作来减小循环开销的影响，使用的是称为循环展开（loop unrolling）技术。其思想是在一次迭代中对多个数组元素进行访问和合并操作。这样使得到的程序需要更少的迭代，从而降低循环的开销。 循环展开的两个缺点：第一，使用循环展开时，我们引入了一种新的开销——当向量长度不能被展开整除时，需要完成所有剩下的元素（如for循环，原本循环变量为i+1,现在为i+3）。第二，就是它增加了生成的目标代码的数量。 将数组代买转换到指针代码，可以优化程序性能，但是这是以程序的可读性为代价的。通常数组代码更可取一些。编译器中，他们对数组代码应用非常高级的优化，而对指针代码只应用最小限度的优化。 5.3 提高并行性 处理器的几个功能单元是流水线化的，这意味着它们可以在前一个操作完成之前开始一个新的操作。我们的代码不能利用这种能力，即使使用循环展开也不能，这是因为我们将累积值放在一个单独的变量中。直到前面的计算完成之前，我们都不能计算x的新值。因此，处理器会暂停（stall），等待开始新的操作，直到当前操作完成。 1 循环分割（loop splitting） 对于一个可结合和可交换的合并操作来说，比如说整数加法或乘法，我们可以通过将一组合并操作分割成两个或更多的部分，并在最后合并结果来提高性能（但是，循环分割后的寄存器存放如果发生溢出，则会出现性能急剧下降，如2所示）。 2 寄存器溢出（register spilling） 循环并行性的好处是受描述计算的汇编代码的能力闲置的。特别地，IA32指令集中有很少量的寄存器来存放累积的值。如果我们有并行度p超过了可用的寄存器数量，编译器会诉诸于溢出，将某些临时值存放到栈中。一旦出现这种情况，性能会急剧下降。 对于整数数据类型的情况，总共只有八个整数寄存器可用。其中有两个（%ebp和%esp）指向栈中的区域。 5.4 综合：优化合并代码的效果小结 1 浮点性能异常：可能是提前溢出报错，从而降低了运行时间。 2 变换平台。 3 转移预测和预测错误惩罚。 正如我们前面提到过的，现代处理器在执行当前指令之前能工作的得很好，从存储器读取新指令，并译码指令，已确定在什么操作数上执行什么操作。只要指令遵循的是一种简单的顺序，那么这种指令流水线化（instruction pipelining）就能很好地工作。不过，当遇到转移的时候，处理器必须猜测转移该往哪个方向走。对于条件跳转的情况，这意味着要预测是否会选择转移。对于间接跳转（就像我们在代码中看到的，跳转到由一个跳转条目指定的地址）或过程返回这样的指令，这意味着预测目标地址。 在一个说投机执行（speculative execution）的处理器中，处理器会开始执行预测的转移目标处的指令。它这样做的方式是，避免修改任何实际的寄存器或存储器位置，直到确定了实际的结果。如果预测是正确的，处理器就简单地“提交”投机执行的指令的结果，把他们存储到寄存器或存储器中。如果预测是错误的，处理器必须丢掉所有投机执行的结果，在正确的位置，重新开始取指令的过程。这样做会引起很大的转移处罚（branch penalty），因为在产生有用的结果之前，必须重新填充指令流水线。 直到最近，支持投机执行所需的技术都被认为是开销太大，对除了最高级的超级计算机以外的所有机器来说都是异乎寻常的。不过大约从1998年开始，集成电路技术使得可以在一块芯片上放置如此之多的电路，以至于有些电路可以专门用来支持转移预测和投机执行。到目前，台式机或服务器中几乎每个处理器都支持投机执行。 不幸的是，C程序员对改进一个程序的转移性能是无能为力的，除了意识到数据相关的转一会引起性能上更高的花费。除此之外，程序员对编译器产生的详细的转移结构几乎没有什么控制，很难使转移更容易预测一些。最终，我们必须依靠两种因素的结合，一是编译器生成好的代码，尽量减少条件转移的使用；另一个是处理器有效地颛臾预测，降低转移预测错误的数量。 5.5 现实生活：性能提高技术 优化程序的基本策略： 1 高级设计。为手边的问题选择适当的算法和数据结构。要特别警觉，避免使用渐进地产生遭高性能的算法或编码技术。 2 基本编码原则。避免限制优化的因素，这样编译器就能产生高效的代码。 （1）消除连续的函数调用。在可能时，将计算移到循环外。考虑有选择的妥协程序的模块性以获得更大的效率。 （2）消除不必要的存储器引用。引入临时变量来保存中间结果。只有在最后的值计算出来时，才将结果存放到数组或全局变量中。 3 低级优化 （1）尝试各种与数组代码相关的指针形式。 （2）通过展开循环降低循环开销。 （3）通过诸如迭代分割之类的技术，找到使用流水线化的功能单元的方法。 要给读者的忠告是，要小心避免花费精力在令人误解的结果上。一项有用的技术是，在优化代码时使用检查代码（checking code）来测试代码的每个版本，以确保在这一过程中没有引入错误。检查代码将一系列测试应用到程序上，确保它得到期望的结果。当引入新的变量，改变循环边界，以及使代码整体更复杂时，很容易出错。此外，注意到性能上任何不同寻常的或出乎意料的变化是很重要的。 5.6 确认和消除性能瓶颈 代码剖析程序（code profiles），这是在程序执行时手机性能数据的分析工具。 系统优化的通用原则，成为Amdahl定律（Amdahl's law）。 程序剖析包括运行程序的这样一个版本，其中插入了工具代码，以确定程序的各个部分需要多少时间。确认出程序中我们需要集中注意力优化的部分是很有用的。剖析的一个有力之处在于可以一边在现实的基准数据（benchmark data）上运行的程序，一边进行剖析。 Amdahl定律，其主要思想是当我们加快系统一个部分的速度时，对系统整体性能的影响依赖于这个部分有多重要和速度提高了多少。考虑一个系统，在其中执行某个应用程序所用的时间T1，假设系统的某个部分需要这个时间的百分比为a，而我们将它的性能提高了k倍，也就是这个部分原来需要时间aT1，而现在需要时间（aT1/k），因此整个执行时间位T2： T2=（1-a）T1+（aT1）/k。 据此，我们可以计算加速S=T2/T1为 S=1/((1-a)+a/k)。 Amdahl定律提供了对通过只改进系统的一部分所获得性能收益的一个简单但是很有力的看法。收益既依赖于我们对这个部分的提高程度，也依赖于这个部分原来在整个时间中所占的比例。 参考文献 布赖恩特, O'Hallaron D, et al. 深入理解计算机系统[M]. 中国电力出版社, 2004.