CSAPP-优化程序性能

写程序的最主要的目的就是使它在所有的可能情况下都可以正确的工作。一个运行的很快但是给出错误的结果的程序没有任何用处。我们必须要写出清晰可以被维护的代码。

但是从另外一个方面讲，让程序运行的很快也是一个重要的考虑因素。这里将讨论如何使用几种不同类型的程序优化技术，使得程序运行的更快。

编写高效的程序需要做到下面几点：

  1. 我们必须选择一组适当的算法和数据结构。
  2. 我们必须编写出编译器能够有效优化以转换成高效可执行代码的源代码。对于这一点，理解优化编译器的能力和局限性十分重要。
  3. 针对处理运算中特别大的计算，将一个任务分成多个部分，这些部分可以在多核和多处理器的某种组合上并行地计算。

C语言的一些特性，例如执行指针运算和强制类型转换的能力，使得编译器很难对他进行优化。

在程序的开发和优化的过程中，我们必须考虑代码使用的方式，以及影响它的关键因素。通常，程序员必须在实现和维护程序的简单性与它的运行速度之间做出权衡。在算法级上，几分钟就能编写一个简单的插入排序，而一个高效的排序算法可能需要一天或者更长的时间去优化，在代码级上，许多低级别的优化往往会降低程序的可读性和模块性，使程序容易出错，并且难以修改或扩展。对于在性能重要的环境中反复执行的代码，进行大量的优化会比较合适。这里的一个挑战是在进行优化后任然保证代码的简洁性和可读性。

现代编译器采用了复杂的分析和优化形式，而且变得越来越好。然而即使最好的编译器也受到妨碍优化的因素(optimization blocker)的阻碍，妨碍优化的因素就是程序行为中那些严重依赖执行环境的方面，程序员必须编写容易优化的代码，以帮助编译器。

程序优化的第一步就是消除不必要的工作，让代码尽可能有效的执行所期望的任务。这包括消除不必要的函数调用、条件测试和内存引用。这些优化不依赖目标机器的任何具体属性。

这里为了使程序的性能最大化，通常需要一个目标机器的模型，指明如何处理指令，以及各个操作的时序特性。例如编译器必须知道时序信息才能确定是使用一条乘法指令，还是使用加法和移位操作的某种组合。

了解了处理器的运作，我们就可以进行程序优化的第二步，利用处理器提供的指令级并行能力，同时执行多条指令。

在这一篇的最后一部分我们讨论对大型程序的优化问题。通过代码剖析程序（profiler）的使用，分析测量程序各个部分性能。这种分析能够帮助找到代码中低效的地方，并确定程序中我们应该优化的部分。

研究程序的汇编代码表示是理解编译器以及产生的代码如何运行的最有效的手段之一。

1. 优化编译器的能力和局限性

现代编译器通过复杂精细的算法来确定一个程序中计算的是什么值，以及它们是如何被使用的。然后会利用一些机会来简化表达式，如在几个不同的地方使用同一个计算，以及降低一个给定计算必须被执行的次数。

对于大多数编译器，包括GCC，向用户提供一些对他们所使用的优化的控制。如，以命令行选项-Og制定GCC使用一组基本的优化使用选项-O1或者更高-Os/-O2/-O3，使得GCC使用更大规模的优化。这种做法可以进一步提高程序性能，但是也可能增加程序的规模，或者使得标准的调试工具更难对程序进行调试。

编译器需要很小心的对程序进行安全的优化。也就是说对于程序可能遇到的所有情况下，在C语言提供的标准下，优化后的程序和未优化的程序需要有一样的行为。例如下面两段代码：

1
2
3
4
5
void twiddle1(long *xp, long *yp)
{
  *xp += *yp;
  *xp += *yp;
}
1
2
3
4
void twiddle2(long *xp, long *yp)
{
  *xp += 2* *yp;
}

这里在大部分的情况下，这两个函数有着相同的行为，它们都是将存储在指针yp位置处的值两次加到xp指示的位置。同时后一种方式有着更快的执行效率，但是当xp指针和yp指针指向同一块地址空间的时候函数会出现不一致的结果。

这种两个指针指向同一个内存位置的情况被称为内存的别名使用(memory aliasing)。在只执行安全的优化中，编译器必须假设不同的指针可能会指向内存中的同一个位置。

另外一种妨碍优化的因素是函数的调用，例如下面两段代码：

1
2
3
4
5
6
7
8
9
10
11
long f();

long func1()
{
  return f()+f()+f()+f();
}

long func2()
{
  return 4*f();
}

这里func2 func1 两个函数在大多数的情况下都能得到相同的结果，所以可以看作func2是func1的代码优化，但是考虑到下面的f函数，会导致两个函数出现计算结果不一致的情况。

1
2
3
4
5
6
long temp = 0;

long f() {
  return temp++;
}

使用全局变量会对程序优化带来上面的副作用。修改全局程序状态的一部分。改变调用它的次数会改变程序的行为。

大多数的编译器不会试图判断一个函数是否有副作用，只会假设最糟糕的情况，保持所有的函数调用关系不变。

使用内联函数inline是将函数调用直接转化为函数实体。允许编译器对展开的代码作进一步的优化。在GCC中使用编译选项-finline。同时使用GDB调试代码的时候如果使用编译器的相关优化会导致调试或者设置断点的行为失败。

2. 表示程序的性能

对于程序的性能我们引入度量标准每元素的周期数（Cycles Per Element， CPE），作为一种表示程序性能并指导我们改进代码的方式。

同时从程序员的角度来讲通常使用时钟周期来作为标准，度量值的表示是执行了多少条指令，而不是时钟运行得有多快。

例如对于一个for循环所需要的时间可以通过一个线性方程t=a*n+b描述，其中n表述循环的次数，a表示这个for循环函数的CPE。通常这里使用最小二乘法来拟合。

最小二乘拟合：对于一个数据点(x_1,y_1)，…，(x_n,:y_n)的集合，我们常常试图画一条线，它能最接近于这些数据代表的X—Y趋势。使用最小二乘拟合，寻找一条形如:y=ax+b的直线。使得累计误差最小。

3. 程序示例

参考机器：指明测试函数运行的机器硬件环境。

更具简单的测量，简单使用命令项-O1，就可以进行一些简单的基本优化。可以显著的提高程序的性能。通常，养成至少使用这个级别的优化的习惯是很好的。

4. 消除循环的低效率

这里主要介绍通过代码移动消除循环中低效的部分。这类优化包括识别要执行多次（例如循环中的某些计算）但是计算结果不会改变的计算。因此可以将计算移动到代码前面不会被多次求值的部分。

5. 减少过程调用

过程的调用会带来开销，而且妨碍大多数形式的程序优化。

但是有的时候消除循环中函数的调用，代码的性能并没有出现显示的提升。原因可能使内循环中其他的操作形成了瓶颈。

6. 消除不必要的内存引用

使用指针会带来程序进行访存的动作，在循环中选择使用变量而不是指针可以消除不必要的内存引用。

7. 理解现代处理器

到这一节之前，我们运用的优化都没有依赖目标机器的任何特性。这些优化只是简单的降低过程调用的开销，以及消除一些重大的“妨碍优化的因素”。当我们试图进一步提高程序性能的时候，就必须考虑利用处理器的微体系结构来进行优化，也就是处理器用来执行指令的底层系统设计。

延迟界限(latency bound)和吞吐界限(throughput bound)是程序性能的终极限制。

7.1 整体操作

对于大多数的现代处理器在工业界被称为超标量(superscalar)，意思是它可以在每个时钟周期执行多个操作，而且是乱序的(out-of-order)，意思就是指令执行顺序不一定要和它们在机器级程序中的顺序一致。整个设计有两个主要部分：

  • 指令控制单元(Instruction Control Unit, ICU)。负责从内存中读取指令序列，并根据这些指令序列生成一组针对程序数据的基本操作。
  • 执行单元(Execution Unit, EU)。复制执行ICU生成的程序数据的基本操作。

ICU从*指令高速缓存(instruction cache)*中读取指令，指令高速缓存是一个特殊的高速存储器，它包含最近的访问指令。通常，ICU会在当前正在执行的指令很早之前取值，这样它才有足够的时间对指令译码，并把操作发送到EU。

现代处理器会采用一种被称为是*分支预测(branch prediction)的技术来处理选择分支的问题，处理器通过这一项技术来猜测是否会选择分支，同时预测分支的目标地址。使用投机执行(speculative execution)*的技术，处理器会开始取出位于他们预测分支会跳转到的地方的指令，并对指令译码，甚至在它确定分支预测是否正确之前就开始执行这些操作。如果分支预测错误，会将状态重新设置到分支点的状态，并开始取出和执行另一个方向上的指令。

指令译码逻辑接收实际的程序指令，并将它们转换成一组基本操作/微操作。每个这样的操作都完成某个简单的计算任务，例如两个数相加，从内存中读取数据，或者向内存中写数据。对于X86处理器，一条指令通常被译码为多个操作。

EU接收来自取指单元的操作。通常每个时钟周期会接收多个操作。这些操作分派到一组功能单元中，它们会执行实际的操作。这些功能单元专门用来处理不同类型的操作。

读写内存是由加载和存储单元实现的。加载单元从内存中读取数据到处理器的操作。存储单元处理从处理器写数据到内存的操作。这两个都有一个单独的加法器来完成地址计算。

举个例子，我们的Intel Core i7 Haswell参考机有8个功能单元，编号为0-7。下面部分列出每个单元的功能：

  • 0：整数运算、浮点乘，整数和浮点除法、分支；
  • 1：整数运算、浮点加法、整数乘法、浮点乘法；
  • 2：加载、地址计算；
  • 3：加载、地址计算；
  • 4：存储；
  • 5：整数运算；
  • 6：整数运算、分支；
  • 7：存储、地址计算；

在ICU中，*退役单元(retirement unit)*记录正在进行的处理，并确保它遵循机器级程序的顺序语义。指令译码时，关于指令的信息被放置在一个FIFO的队列中。这个信息可以一直保持在队列中，直到发生以下两个结果中的一个。1）一但一条指令的操作完成了而且所有引起这条指令的分支点也都被确认预测正确，那么这条指令就可以退役（retired）了，所有对程序寄存器的状态都可以被实际执行了。2）如果引起该指令的分支节点预测错误，这条指令会被清空（flushed），丢弃所有计算出来的结果。通过这种方法，预测错误就不会改变程序状态了。

所有对程序寄存器的更新都只在指令退役的时候才会发生。

7.2 功能单元的性能

对于功能单元的性能，我们通常采用下面的数值来刻画：

  • 延迟(latency) : 表示完成运算所需要的总时间
  • 发射时间(issue time) : 表示两个连续的同类型的运算之间需要的最小时钟周期
  • 容量(capacity) : 表示能够执行该运算功能单元的数量

表达发射时间的一种常见的方法是指明这个功能单元的最大吞吐量，定义为发射时间的倒数。

7.3 处理器操作的抽象模型

通常我们使用程序*数据流(date-flow)来分析在现代处理器上执行机器级程序性能，可以展现不同操作之间的数据相关是如何限制它们的执行顺序的。谢谢限制形成了图形中的关键路径(critical path)*，这是执行一组机器指令所需要的时间的下边界。

对于循环的代码片段，我们通常将可以访问的寄存器分为4类：

  • 只读：这些寄存器只作为源值。可以作为数据，也可以用来计算内存地址，但是在循环中它们是不会被修改的。
  • 只写：这些寄存器作为数据传送操作的目的。
  • 局部：这些寄存器在循环内部被修改和使用，迭代与迭代之间不相关。
  • 循环：对于循环来说，这些寄存器即作为源值，又作为目的，一次迭代中产生的值会在另一次迭代中使用。

数据流表示中的关键路径提供的只是程序需要周期数的下限。还有其他的一些因素会限制性能。

8. 循环展开

循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。

循环展开能够从两个方面改进程序的性能。首先，它减少了不直接有助于程序结果的操作的数量，例如循环索引计算和条件分支。第二，它提供了一些方法，可以进一步变化代码，减少整个计算中关键路径上的操作数量。

编译器可以很容易地执行循环展开。只要优化级别设置得足够高，许多编译器都能例行公事地做到这一点。用优化等级3或者更高级调用GCC，它就会执行循环展开。

9. 提高并行性

程序的性能是受运算单元的延迟限制的。但是执行加法和乘法的功能单元是完全流水线化的，表明每个时钟周期可以开始一个新的操作，并且有些操作可以被多个功能单元执行。

  • 多个累积变量。对于一个可以结合和可以交换的合并运算来说，可以通过将一组合并运算分割成多个部分，并在最后合并结果来提升性能。
  • 重新结合变换。简单的通过代码描述为将acc = (acc OP data[i]) OP data[i+1]变换为acc = acc OP (data[i] OP data[i+1])的形式。

Intel中的SSE指令是采用向量指令达到更高的并行度。

10. 一些限制因素

在一个程序的数据流表示中，关键路径指明了执行该程序所需时间的一个基本下界。也就是说，如果程序中有某条数据相关链，这条链上的所有延迟之和等于T，那么这个程序至少需要T个周期才能执行完成。

同时功能单元的吞吐量界限也是程序执行时间的一个下界。也就是说，假设一个程序一共需要N个某种运算的计算，而微处理器只有C个能执行这个操作的功能单元，并且这些单元的发射时间为I。那么，这个程序的执行至少需要N*i/C个周期。

10.1 寄存器溢出

循环并行性的好处受汇编代码描述计算的能力限制。如果我们的并行度P超过了可用的寄存器数量，那么编译器就会诉诸溢出(spilling)，将某些临时值存放到内存中，通常是在运行时堆栈上分配空间。这会导致维护多个累积变量的优势消失。

10.2 分支预测和预测错误处罚

根据前面章节的描述，当分支预测逻辑不能正确预测一个分支是否需要跳转的时候，条件分支可能会导致很大的分支预测错误处罚。

现代处理器对于条件分支，处理器必须猜测分支该往那个方向走。对于条件转移的情况，这意味着需要预测是否会选择分支。对于像间接跳转（跳转到由一个跳转表条目指定的地址）或者返回这样的指令，这意味着要预测目标地址。

对于使用*投机执行(speculative execution)*的处理器，处理器会开始执行预测的分支目标处的指令。他会避免修改任何实际的寄存器或者内存位置，直到确定了实际的结果。如果预测正确，那么处理器就会提交投机执行的结果。如果预测错误，处理器就必须丢弃掉所有投机执行的结果。在正确的位置上重新开始取指令的过程。

对于C语言程序员，可以通过下面的通用原则来保证分支预测处罚不会阻碍程序的效率：

  1. 不要过分关心可预测的分支。
  2. 书写适合用条件传送实现的代码。例如C语言中的goto和?:表达式都是这种适合条件传送的实现代码。

11. 理解内存性能

到目前为止我们运行的所有代码，以及测试，都只访问了相对比较少量的内存。对于现代处理器这样的操作都是被*高速缓存(cache)*提供的快速访问。这里会进一步研究涉及加载（从内存读到寄存器中）和存储（从寄存器写到内存中）操作的程序的性能，只考虑所有的数据都存放在高速缓存中的情况。

11.1 加载的性能

一个包含加载操作的程序性能即依赖于流水线的能力，也依赖于加载单元的延迟。

可以通过下面的方法确定一台机器上的延迟：通过建立一系列加载操作组成的一个计算，一条加载操作的结果决定下一条操作的地址。

11.2 存储的性能

与前面加载操作对应的是*存储(store)*操作。它将一个寄存器的值写入到内存中。

与其他操作不同的是存储操作并不会影响任何寄存器的值。因此，就其本质来说，一系列存储操作不会产生数据相关。只有加载操作会受到存储操作结果的影响。

写/读相关（write/read dependency）：一个内存读的结果依赖于一个最近的内存写。

12. 应用： 性能提高技术

对于如何编写高效的代码基本上遵循下面的基本策略：

  1. 高级的设计。为遇到的问题选择合适的数据结构和算法。
  2. 遵循基本的编码原则。避免限制优化的因素，帮助编译器产生高效的代码。a）消除连续的函数调用。b）消除不必要的内存引用。
  3. 低级别优化。优化代码结构以利用硬件功能。

13. 确认和消除性能瓶颈

对于处理大程序的时候，知道优化什么地方是十分重要的前提条件。这里将描述如何使用*代码分析程序(code profiler)*。同时还描述一个系统优化的通用原则，amdahl定律。

程序剖析（profiling）运行程序的一个版本，在其中插入工具代码，以确定程序的各个部分需要多少时间。

Unix系统提供一个剖析程序GPROF。这个程序可以得出每个函数被调用的次数，以执行调用的函数来分类。同时还可以确定每个函数花费了多少CPU时间。

在linux上运行分析程序过程如下：

1
2
3
linux> gcc -0g -pg prog.c -o prog #使用-0g优化确保程序能够被正常跟踪。使用-pg 让编译的程序可被剖析
linux> ./prog file.txt # 程序运行后会生成一个分析文件gmon.out
linux> gprof prog # 调用gprof分析gmon.txt中的数据

剖析程序帮助我们把注意力集中在程序最耗时的部分上，同时还提供了关于过程调用结构的有用信息。