编写高效程序需要做到以下几点：
① 必须选择一组适当的算法和数据结构
② 必须编写出编译器能够有效优化以转换成高效可执行代码的源代码。理解优化编译器的能力和局限性是很重要的，编写程序方式中只是一点小小的变动，都会引起编译器优化方式很大的变化。
③ 技术针对处理运算量特别大的计算，将任务分成多个部分，这些部分可以在多核和多处理器的某种组合上并行地计算。
描述许多提高代码性能的技术，理想情况：编译器能够接受我们编写的任何代码，并产生尽可能高效的，具有指定行为的机器级程序。现代编译器采用了复杂的分析和优化形式，而且变得越来越好。
程序优化的第一步：消除不必要的工作，让代码尽可能有效地执行所期望的任务。第二步，利用处理器提供的指令级并行能力，同时执行多条指令。
5.1 优化编译器的能力和局限性
现代编译器运用复杂精细的算法来确定一个程序中计算的是什么值，以及它们是被如何使用的。然后会利用一些机会来简化表达式，在几个不同的地方使用同一个计算，以及降低一个给定的计算必须被执行的次数。大多数编译器，包括GCC，向用户提供了一些对它们所使用的优化的控制。
就像在第3章中的，最简单的控制就是指定优化级别。例如，以命令行选项“-Og”调用GCC 是让 GCC 使用一组基本的优化。以选项“ -O1 ”或高（如“ -O2 ”或“ -O3 ”）调用GCC会让它使用更大量的优化。这样做可以进一步提高程序的性能，但是也可能增加程序的规模，也可能使标准的调试工具更难对程序进行调试。虽然对于大多数使用 GCC 的软件项目来说，优化级别 -O2 已经成为了被接受的标准，但还是主要考虑以优化级别 -O1 编译出的代码。
特意限制了优化级别，以展示写C语言函数的不同方法如何影响编译器产生代码的效率。发现可以写出的C代码，即使用-O1选项编译得到的性能，也比用可能的最高的优化等级编译一个更原始的版本得到的性能好。
编译器必须很小心地对程序只使用安全的优化，也就是说对于程序可能遇到的所有可能的情况，在C语言标准提供的保证之下，优化后得到的程序和未优化的版本有一样的行为。限制编译器只进行安全的优化，消除了造成不希望的运行时行为的一些可能的原因，但是这也意味着程序员必须花费更大的力气写出编译器能够将之转换成有效机器代码的程序。为了理解决定一种程序转换是否安全的难度,让我们来看看下面两个过程：
乍一看，这两个过程似乎有相同的行为。它们都是将存储在由指针 yp 指示的位置处的值两次加到指针 xp 指示的位置处的值。另一方面，函数 twiddle2 效率更高一些。它只要求 3 次内存引用（读 *xp 读 *yp 写 *xp），而 twiddle1 需要 6 次（2次读 *xp 两次读 *yp 两次写 *xp）。因此，如果要编译器编译过程 twiddle1，会认为基于 twiddle2 执行的计算能产生更有效的代码。
这种两个指针可能指向同一个内存位置的情况称为内存别名使用。 在只执行安全的优化中，编译器必须假设不同的指针可能会指向内存中同一位置。 这就造成了一个妨碍优化的因素，这也是可能严重限制编译器产生优化代码机会的程序的一个方面。 如果编译器不能确定两个指针是否指向同一个位置，就必须假设什么情况都有可能，这就限制了可能的优化策略。
5.2 程序性能
引入度量标准每元素的周期数（Cycles Per Element,CPE）作为一种表示程序性能并指导改进代码的方法。CPE 这种度量标准在更细节的级别上理解迭代程序的循环性能。这样的度量标准对执行重复计算的程序来说是很适当的，例如处理图像中的像素，或是计算矩阵乘积中的元素。
处理器活动的顺序是由时钟控制的，时钟提供了某个频率的规律信号，通常用千兆赫兹（GHz），即十亿周期每秒来表示。例如，当表明一个系统有“ 4GHz ” 处理器，这表示处理器时钟运行频率为每秒 4*10^9 个周期。 每个时钟周期的时间是时钟频率的倒数。通常以纳秒（10^-9s）或皮秒（10^-12秒）为单位的。例如,一个4GHz 的时钟 其周期为 0.25 纳秒，或者 250 皮秒。从程序员的角度，用时钟周期来表示度量标准要比用纳秒或皮秒来表示有帮助得多。用时钟周期来表
示，度量值表示的是执行了多少条指令，而不是时钟运行得有多快。
许多过程含有在一组元素上迭代的循环。例如，图5-1 中的函数 psum1 和 psum2 计算的都是一个长度为 n 的向量的前置和（prefix sum）。对于向量 ，前置和
定义为
函数 psum1 每次迭代计算结果向量的一个元素。第二个函数使用循环展开（loop un-rolling）的技术，每次迭代计算两个元素。本章后面我们会探讨循环展开的好处。（关于分析和优化前置和计算的内容）
这样一个过程所需要的时间可以用一个常数加上一个与被处理元素个数成正比的因子来描述。例如，图5-2 是这两个函数需要的周期数关于 n 的取值范围图。使用最小二乘拟合。
发现，psum1 和 psum2 的运行时间（以时钟周期为单位）分别近似于等式 368+9.0n 和 368+6.0n。这两个等式表明对代码计时和初始化的过程，准备循环以及完成过程的开销为 368 个周期加上每个元素 6.0 或 9.0 周期的线性因子。对于较大的 n 的值（比如 200），运行时间就会主要由线性因子来决定。这些项中的系数称为每元素的周期数（CPE）的有效值。
注意，我们更愿意用每个元素的周期数而不是每次循环的周期数来度量，这是因为像循环展开这样的技术使得我们能够用较少的循环完成计算，而最终关心的是，对于给定的向量长度，程序运行的速度如何。将精力集中在减小计算的CPE上。根据这种度量标准，psum2 的CPE为6.0，优于CPE为9.0的psum1。
5.3 程序示例
为了说明一个抽象的程序是如何被系统地转换成更有效的代码的，将使用一个基于 图5-3 所示向量数据结构的运行示例。向量由两个内存块表示：头部和数据数组。头部是一个声明如下的结构：
typedef long data_t;
还会分配一个 len 个 data_t 类型对象的数组，用来存放实际的向量元素。
图 5-4 给出的是一些生成向量，访问向量元素以及确定向量长度的基本过程。一个值得注意的重要特性是向量访问程序 get_vec_element，它会对每个向量引用进行边界检查。 这段代码类似于许多其他语言（包括java）所使用的数组表示法。边界检查降低了程序出错的机会，但是它也会减缓程序的执行。
作为一个优化示例，考虑图 5-5 中所示代码，它用某种运算，将一个向量中所有的元素合并成一个值。通过使用编译时常数 IDENT 和 OP 的不同定义，这段代码可以重编译成对数据执行不同的运算。特别的，使用声明：
对这段代码进行一系列的变化，写出这个合并函数的不同版本，为了评估性能变化，会在一个具有 Intel Core i7 Haswell 处理器的机器上测量这些函数的CPE性能，这个机器称为参考机。这些测量值刻画的是程序在某个特定的机器上的性能，所以在其他机器和编译器组合中不保证有同等的性能。不过，我们把这些结果与许多不同编译器/处理器组合上的结果做了比较，发现也非常相似。
作为一个起点，下表给出的是 combine1 的 CPE度量值 ，它运行在我们的参考机上，尝试了操作（加法或乘法）和数据类型（长整数和双精度浮点数）的不同组合。使用多个不同的程序，实验显示 32位整数操作 和 64位整数操作 有相同的性能，除了涉及除法操作的代码之外。同样，对于操作单精度和双精度浮点数据的程序，其性能也是相同的。因此在表中，将只给出整数数据和浮点数据各自的结果。
未经优化的代码是从 C语言代码 到 机器代码的直接翻译，通常效率明显较低。简单地使用命令行选项“ -O1 ”，就会进行一些基本的优化。正如看到的，不需要做什么就能显著地提高程序性能——超过两个数量级。通常，养成至少使用这个级别优化的习惯是很好的（使用 -Og 优化级别能得到相似的性能结果） 在剩下的测试中，使用 -O1 和 -O2 级别的优化来生成和测量程序。
5.4 消除循环的低效率
可以观察到，过程 combine1 调用函数 vec_length 作为 for 循环的测试条件，如图 5-5 ，回想如何将含有循环的代码翻译成机器级程序的讨论，每次循环迭代时都必须对测试条件求值。另一方面，向量的长度并不会随着循环的进行而改变。因此，只需计算一次向量的长度，然后在后面的测试条件中都是用这个值。
这个优化是一类常见的优化例子，称为 代码移动 。这类优化包括识别要执行多次（例如在循环里）但是计算结果不会改变的计算。因而可以将计算移动到代码前面不会被多次求值的部分。本例中，对 vec_length 的调用从循环内部移动到循环的前面。
优化编译器会试着进行代码移动。不幸的是，就像前面讨论过，对于会改变在哪里调用函数或调用多少次的变换，编译器通常会非常小心。它们不能可靠地发现一个函数是否会有副作用，因而假设函数会有副作用。例如，如果 vec_length 有某种副作用那么 combine1 和 combine2 可能就会有不同的行为。为了改进代码，程序员必须经常帮助编译器显式地完成代码的移动。
举一个 combine1 中循环低效率的极端例子，图5-7 lower1。过程模仿几个学生的函数设计，函数是作为一个网络编程项目的一部分交上来的。这个过程的目的是将一个字符串中所有大写字母转换成小写字母。这个大小写转换涉及将“ A” 到“ Z ”范围内的字符转换成“ a ”到“ z”范围内的字符。
对库函数 strlen 的调用是 lower1 的循环测试的一部分。虽然 strlen 通常是用特殊的 x86 字符串处理指令来实现的，但是它的整体执行也类似于 图5-7 中给出的简单版本。因为 C 语言中的字符串是以 null 结尾的字符序列，strlen 必须一步一步地检查这个序列，直到遇到 null 字符。对于一个长度为 n 的字符串，strlen 所用的时间与 n 成正比。因为对 lower1 的 n 次迭代的每一次都会调用 strlen，所以 lower1 的整体运行时间是字符串长度的二次项，正比于 n^2
除了把对 strlen 的调用移出了循环以外，图5-7中所示的 lower2 与 lower1 是一样的。做了这样的变化之后，性能有了显著改善。对于一个长度为1048576的字符串，这个函数只需要 2.0毫秒--比 lower1快了500000 多倍。字符串长度每增加一倍，运行时间也会增加一倍--很显然运行时间是线性的。对于更长的字符串，运行时间的改进会更大。
在理想的世界里，编译器会认出循环测试中对 strlen 的每次调用都会返回相同的结果，因此应该能够把这个调用移出循环。这需要非常成熟完善的分析，因为 strlen 会检查字符串的元素，而随着 lower1 的进行，这些值会改变。编译器需要探查，即使字符串中的字符发生了改变，但是没有字符会从非零变为零，或是反过来，从零变为非零。即使是使用内联函数，这样的分析也远远超出了最成熟完善的编译器的能力，所以程序员必须自己进行这样的变换。
这个示例说明了编程时一个常见的问题，一个看上去无足轻重的代码片断有隐藏的渐近低效率(asymptotic inefficiency)。人们可不希望一个小写字母转换函数成为程序性能的限制因素。通常，会在小数据集上测试和分析程序，对此，lower1 的性能是足够的。不过，当程序最终部署好以后，过程完全可能被应用到一个有100万个字符的串上。突然， 这段无危险的代码变成了一个主要的性能瓶颈。相比较而言，lower2 的性能对于任意长度的字符串来说都是足够的。
5.5 减少过程调用
过程调用会带来开销，而且妨碍大多数形式的程序优化。combine2 的代码（图5-6）中看出，每次循环迭代都会调用 get_vec_element 获取下一个向量元素。对每个向量引用，这个函数要把向量索引 i 与循环边界做比较，很明显会造成低效率。在处理任意的数组访问时，边界检查可能是个很有用的特性，但是对 combine2 代码的简单分析表明所有的引用都是合法的。
作为替代，假设抽象数据类型增加一个函数 get_vec_start。这个函数返回数组的起始地址，如 图5-9。然后写出此图中 combine3 所示的过程，其内循环里没有函数调用。它没有用函数调用来获取每个向量元素，而是直接访问数组。一个纯粹主义者可能认为这种变换严重损害了程序的模块性。原则上来说，向量抽象数据类型的使用者甚至不应该需要知道向量的内容是作为数组来存储的，而不是作为诸如链表之类的某种其他数据结构来存储的。比较实际的程序员会争论说这种变换是获得高性能结果的必要步骤。
然而，性能没有明显的提升。事实上，整数求和的性能还略有下降。显然，内循环中的其他操作形成了瓶颈，限制性能超过调用 get_vec_element 。还会再回到函数，为什么 combine2 中反复的边界检查不会让性能更差。而现在，将这个转换视为一系列步骤中的一步，这些步骤将最终产生显著的性能提升。
5.6 消除不必要的内存引用
combine3 的代码将合并运算计算的值累积在指针 dest 指定的位置。通过检查编译出来的为内循环产生的汇编代码，可以看出这个属性。在给出的数据类型为 double，合并运算为乘法的 x86-64代码：
在这段循环代码中，指针 dest 的地址存放在 寄存器 rbx 中，它还改变了代码，将第 i 个数据元素的指针保存在 寄存器rdx 中，注释中显示为data+i。每次迭代，这个指针都加8。循环终止操作通过比较 该指针 与 保存在寄存器 rax 中的数值来判断。每次迭代时，累积变量的数值都要从内存读出再写入到内存。这样的读写很浪费，因为每次迭代开始时从 dest 读出的值就是上次迭代最后写入的值。
消除这种不必要的内存读写，按照 图5-10 中 combine4 的方式重写代码。引入一个临时变量 acc，它在循环中用来累计计算出来的值。只有在循环完成之后结果才存放在 dest 中。正如下面汇编代码所示，编译器可以用 寄存器 %xmm0 来保存累积值。与 combine3 中的循环相比，每次迭代的内存操作从两次读，一次写减少到只需一次读。
程序性能有了显著的提高：
可能有人认为编译器应该能够自动将 图5-9 所示的 combine3 的代码转换为在寄存器中累积的那个值，就像图 5-10 中所示的 combine4 的代码所做的那样。然而实际上，由于内存别名使用，两个函数可能会有不同的行为。例如，考虑整数数据，运算为乘法，标识元素为 1 的情况。设 v=[2,3,5] 是一个由 3 个元素组成的向量，考虑下面两个函数调用：
正如前面，combine3 将它的结果累积在目标位置中，在本例中，目标位置是向量的最后一个元素。因此，这个值首先设置为 1 ，然后设为 2*1=2，然后设为 2*3=6。 最后一次迭代中，这个值会乘以它自己，得到 6*6=36. 对于 combine4 情况，直到最后向量都保持不变，结束之前，最后一个元素会被设置为计算出来的值 1*2*3*5=30.
当然，说明 combine3 和 combine4 之间差别的例子是人为设计的。有人认为 combine4 的行为更加符合函数描述的意图。不幸的是，编译器不能判断函数会在什么情况下被调用，以及程序员的本意可能是什么。取而代之，在编译 combine3 时，保守的方法是不断地读和写内存，即使这样做效率不太高。
5.7 理解现代处理器
目前为止，运用的优化都不依赖于目标机器的任何特性。这些优化只是简单地降低了过程调用的开销，以及消除了一些重大的“ 妨碍优化的因素 ”，这些因素会给优化编译器造成困难。随着试图进一步提高性能，必须考虑利用处理器微体系结构的优化，也就是处理器用来执行指令的底层系统设计。要想充分提高性能，需要仔细分析程序，同时代码的生成也要针对目标处理器进行调整。尽管如此，我们还是能够运用一些基本的优化，在很大一类处理器上产生整体的性能提高。
为了理解改进性能的方法，我们需要理解现代处理器的微体系结构。由于大量的晶体管可以被集成到一块芯片上，现代微处理器采用了复杂的硬件，试图使程序性能最大化。带来的后果就是处理器的实际操作与通过观察机器级程序所察觉到的大相径庭。在代码级上，看上去似乎是一次执行一条指令，每条指令都包括从寄存器或内存取值，执行一个操作，并把结果存回到一个寄存器或内存位置。在实际的处理器中，是同时对多条指令求值的，这个现象称为指令级并行。在某些设计中，可以有100或更多条指令在处理中。采用一些精细的机制来确保这种并行执行的行为，正好能获得机器级程序要求的顺序语义模型的效果。现代微处理器取得的了不起的功绩之一是：它们采用复杂而奇异的微处理器结构，其中，多条指令可以并行地执行，同时又呈现出一种简单的顺序执行指令的表象。
对这些微处理器运行的原则有一般性的了解就足够能够理解它们如何实现指令级并行。发现两种下界描述了程序的最大性能。当一系列操作必须按照严格顺序执行时，就会遇到延迟界限(latencybound)，因为在下一条指令开始之前，这条指令必须结束。当代码中的数据相关限制了处理器利用指令级并行的能力时，延迟界限能够限制程序性能。吞吐量界限(throughpubound)刻画了处理器功能单元的原始计算能力。这个界限是程序性能的终极限制。
5.7.1 整体操作
图 5-11 是现代微处理器的一个非常简单化的示意图。假想的处理器设计是不太严格地基于近期的 Intel 处理器的结构。这些处理器在工业界称为超标量（superscalar），意思是可以在每个时钟周期执行多个操作，而且是乱序的，意思是指令执行的顺序不一定要与它们在机器级程序中的顺序一致。 整个设计由两个主要部分：指令控制单元 和 执行单元。前者负责从内存中读出指令序列，并根据这些指令序列生成一组针对程序数据的基本操作；后者执行这些操作。 与按序流水线相比，乱序处理器需要更大，更复杂的硬件，但是它们能更好地达到更高的指令集并行度。
ICU 从指令高速缓存(instruction cache)中读取指令，指令高速缓存是一个特殊的高速存储器，它包含最近访问的指令。通常，ICU 会在当前正在执行的指令很早之前取指，这样它才有足够的时间对指令译码，并把操作发送到 EU。不过，一个问题是当程序遇到分支时，程序有两个可能的前进方向。一种可能会选择分支，控制被传递到分支目标；另一种可能是不选择分支，控制被传递到指令序列的下一条指令。现代处理器采用了一种称为分支预测的技术，处理器会猜测是否会选择分支，同时还预测分支的目标地址。使用投机执行的技术，处理器会开始取出位于它预测的分支会跳到的地方的指令，并对指令译码，甚至在它确定分支预测是否正确之前就开始执行这些操作。如果过后确定分支预测错误，会将状态重新设置到分支点的状态，并开始取出和执行另一个方向上的指令。标记为取指控制的块包括分支预测，以完成确定取哪些指令的任务。
指令译码逻辑接收实际的程序指令，并将它们转换成一组基本操作（有时称为微操作）。每个这样的操作都完成某个简单的计算任务，例如两个数相加，从内存中读数据，或是向内存写数据。对于具有复杂指令的机器，比如 x86 处理器，一条指令可以被译码成多个操作关于指令如何被译码成操作序列的细节，不同的机器都会不同，这个信息可谓是高度机密，幸运的是，不需要知道某台机器实现的底层细节，我们也能优化自己的程序。
在一个典型的 x86 实现中，一条只对寄存器操作的指令，例如： addq %rax,%rdx
会被转化成一个操作。另一方面 一条包括一个或者多个内存引用的指令，例如 add %rax,8(%rdx)会产生多个操作，把内存引用和算术运算分开。这条指令会被译码成三个操作：一个操作从内存中加载一个值到处理器中，一个操作将加载进来的值加上寄存器 %rax 中的值，而一个操作将结果存回内存中。 这种译码逻辑对指令进行分解，允许任务在一组专门的硬件单元之间分割。这些单元可以并行地执行多条指令的不同部分。
EU接收来自取指单元的操作。通常，每个时钟周期会接收多个操作。这些操作会被分派到一组功能单元中，它们会执行实际的操作。这些功能单元专门用来处理不同类型的操作。
读写内存是由加载和存储单元实现的。加载单元处理从内存读数据到处理器的操作，这个单元有一个加法器来完成地址计算。类似，存储单元处理从处理器写数据到内存的操作。它也有一个加法器来完成地址计算。如图中所示，加载和存储单元通过数据高速缓存(data cache)来访问内存。数据高速缓存是一个高速存储器，存放着最近访问的数据值。
使用投机执行技术对操作求值，但是最终结果不会存放在 程序寄存器 或 数据内存 中，直到处理器能确定应该实际执行这些指令。分支操作被送到 EU，不是确定分支该往哪里去，而是确定分支预测是否正确。如果预测错误，EU会丢弃分支点之后计算出来的结果，它还会发信号给分支单元，说预测是错误的，并指出正确的分支目的。在这种情况中，分支单元开始在新的位置取指。如在3.6.6节中看到的，这样的预测错误会导致很大的性能开销。在可以取出新指令、译码和发送到执行单元之前，要花费一点时间。
图5-11说明不同的功能单元被设计来执行不同的操作。标记为执行“ 算术运算 ”的单元通常是专门用来执行 整数 和 浮点数 操作的不同组合。随着时间的推移，在单个微处理器芯片上能够集成的晶体管数量越来越多，后续的微处理器型号都增加了功能单元的数量以及每个单元能执行的操作组合，还提升了每个单元的性能。由于不同程序间所要求的操作变化很大，因此，算术运算单元被特意设计成能够执行各种不同的操作。比如，有些程序也许会涉及整数操作，而其他则要求许多浮点操作。如果一个功能单元专门执行整数操作，而另一个只能执行浮点操作，那么，这些程序就没有一个能够完全得到多个功能单元带来的好处了。
和除法需要更多的专用资源。 存储操作要两个功能单元——一个计算存储地址，一个实际保存数据。 5.12 节将讨论存储（和加载）操作的机制。
在ICU中，退役单元记录正在进行的处理，并确保它遵守机器级程序的顺序语义。图中展示了一个寄存器文件，它包含整数、浮点数和最近的SSE和AVX寄存器，是退役单元的一部分，因为退役单元控制这些寄存器的更新。 指令译码时，关于指令的信息被放置在一个先进先出的队列中。这个信息会一直保持在队列中，直到发生以下两个结果中的一个。首先，一旦一条指令的操作完成了，而且所有引起这条指令的分支点也都被确认为预测正确，那么这条指令就可以退役了，所有对程序寄存器的更新都可以被实际执行了。另一方面，如果引起该指令的某个分支点预测错误，这条指令会被清空，丢弃所有计算出来的结果。通过这种方法，预测错误就不会改变程序的状态了。
任何对程序寄存器的更新都只会在指令退役时才会发生，只有在处理器能够确信导致这条指令的所有分支都预测正确了，才会这样做。为了加速一条指令到另一条指令的结果的传送，许多此类信息是在执行单元之间交换的，即图中的“ 操作结果 ”。如图中的箭头所示，执行单元可以直接将结果发送给彼此。这是4.5.5节中简单处理器设计中采用的数据转发技术的更复杂精细版本。
控制操作数在执行单元间传送的最常见的机制称为寄存器重命名(register renaming)。当一条更新寄存器 r 的指令译码时，产生标记 t ，得到一个指向该操作结果的唯一的标识符。条目(r，t)被加入到一张表中，该表维护着每个程序寄存器 r 与 会更新该寄存器的操作的标记 t 之间的关联。当随后以寄存器 r 作为操作数的指令译码时，发送到执行单元的操作会包含 t 作为操作数源的值。当某个执行单元完成第一个操作时，会生成一个结果(v，t)，指明标记为 t 的操作产生值 v 。所有等待 t 作为源的操作都能使用 v 作为源值，这就是一种形式的数据转发。通过这种机制，值可以从一个操作直接转发到另一个操作，而不是写到寄存器文件再读出来，使得第二个操作能够在第一个操作完成后尽快开始。重命名表只包含关于有未进行写操作的寄存器条目。当一条被译码的指令需要寄存器 r ，而又没有标记与这个寄存器相关联，那么可以直接从寄存器文件中获取这个操作数。有了寄存器重命名，即使只有在处理器确定了分支结果之后才能更新寄存器，也可以预测着执行操作的整个序列。