说明
本文是个人学习用的非官方中英对照译文,原文:https://diveintosystems.org/book/C12-CodeOpt/index.html。
原书采用 CC BY-NC-ND 4.0 许可(禁止演绎),请勿公开传播本译文。
标为「译注」「现代更新」的内容是译者补充,不代表原书作者观点;代码与原文逐字一致,未作改动。
12. Code Optimization
代码优化(code optimization)是在不改变程序固有功能的前提下,通过减小代码规模、降低复杂度、减少内存使用或缩短运行时间(或它们的某种组合)来改进程序的过程。许多编译系统都把代码优化器作为中间步骤。具体来说,优化编译器(optimizing compiler)在编译过程中应用改进代码的变换。几乎所有现代编译器(包括 GCC)都是优化编译器。GCC 的 C 编译器实现了各种各样的优化选项(optimization flag),让程序员可以直接使用其中一部分已实现的优化。编译器优化选项以增加编译时间和降低调试便利性为代价来优化代码。为简单起见,GCC 把这些优化选项中的一部分打包成不同的优化级别(optimization level),程序员可以直接调用。例如,下面的命令以 1 级优化编译一个示例程序:
Code optimization is the process by which a program is improved by reducing its code size, complexity, memory use, or runtime (or some combination thereof) without changing the program’s inherent function. Many compilation systems include a code optimizer as an intermediate step. Specifically, an optimizing compiler applies code-improving transformations as part of the compilation process. Virtually all modern compilers (including GCC) are optimizing compilers. The GCC C compiler implements a wide variety of optimization flags that give programmers direct access to a subset of the implemented optimizations. Compiler optimization flags optimize code at the expense of compile time and ease of debugging. For simplicity, GCC wraps up a subset of these optimization flags into different optimization levels that the programmer can directly invoke. For example, the following command compiles a sample program with level 1 optimizations:
1 | $ gcc -O1 -o program program.c |
GCC 的 1 级优化(-O1 或 -O)执行基本的优化,以减小代码规模和执行时间,同时尽量把编译时间控制在最低。2 级优化(-O2)包括 GCC 已实现的、不涉及空间与性能权衡的大部分优化。最后,3 级优化(-O3)执行额外的优化(例如本章后面讨论的函数内联),可能会使程序的编译时间显著变长。GCC 文档详细描述了已实现的各种优化选项。
The level 1 (
-O1or-O) optimizations in GCC perform basic optimizations to reduce code size and execution time while attempting to keep compile time to a minimum. Level 2 (-O2) optimizations include most of GCC’s implemented optimizations that do not involve a space-performance trade-off. Lastly, level 3 (-O3) performs additional optimizations (such as function inlining, discussed later in this chapter), and may cause the program to take significantly longer to compile. The GCC documentation describes the implemented optimization flags in detail.
现代更新(截至 2026-11)· 现在的 GCC 优化级别
原文说函数内联属于 -O3 的「额外优化」。按当前的 GCC 手册,-O2 已经开启了 -finline-functions 和 -finline-small-functions 等内联相关选项;手册对 -O2 的描述是「执行几乎所有不涉及空间与速度权衡的已支持优化」。调试时,手册建议在不使用其他优化选项时用 -Og 配合 -g:不加任何 -O 时,一些收集调试有用信息的编译遍根本不会运行,因此 -Og 可能带来更好的调试体验。GCC 手册:Optimize Options;GCC 手册:Debugging Options
关于优化编译器及其构造和工作原理的详细讨论超出了本教材的范围;我们鼓励感兴趣的读者阅读 Aho、Sethi 和 Ulman 的经典著作 Compilers: Principles, Techniques, and Tools。本章的目的在于指出大多数编译器能做(和不能做)的一些事情,以及程序员如何与编译器和剖析工具配合来改进代码。
A detailed discussion of optimizing compilers and their construction and operation is beyond the scope of this textbook; we encourage interested readers to check out the seminal text, Compilers: Principles, Techniques, and Tools, by Aho, Sethi, and Ulman. Rather, the purpose of the chapter is to highlight some things that most compilers can (and cannot) do, and how programmers can partner with their compilers and profiling tools to help improve their code.
译注
第三位作者的名字应为 Ullman(Jeffrey D. Ullman)。这本书因封面上画着一条龙而被称为「龙书」,中译本名为《编译原理》;第 2 版增加了作者 Monica S. Lam。
编译器已经在做的事
What Compilers Already Do
接下来的几个小节简要介绍几乎每个编译器都会执行的几种常见优化。学生绝不应该手动实现这些优化,因为编译器已经实现了它们。
Several of the common optimizations performed by virtually every compiler are described briefly in the upcoming sections. Students should never manually implement these optimizations, because they are already implemented by the compiler.
常量折叠(constant folding)
代码中的常量在编译时求值,以减少生成的指令数。例如,在下面的代码片段中,宏展开(macro expansion)把语句
int debug = N-5替换为int debug = 5-5,然后常量折叠把这条语句更新为int debug = 0。
Constant Folding
Constants in the code are evaluated at compile time to reduce the number of resulting instructions. For example, in the code snippet that follows, macro expansion replaces the statement
int debug = N-5withint debug = 5-5. Constant folding then updates this statement toint debug = 0.
1 | #define N 5 |
常量传播(constant propagation)
如果在编译时就知道某个变量的值是常量,常量传播就用这个常量值替换该变量。考虑下面的代码段:
Constant Propagation
Constant propagation replaces variables with a constant value if such a value is known at compile time. Consider the following code segment:
1 | int debug = 0; |
采用常量传播的编译器会把 if (debug) 改为 if (0)。
A compiler employing constant propagation will change
if (debug)toif (0).
译注 · 这个例子其实不成立
debug 是一个普通的(外部链接、非 const)全局变量,其他源文件可以声明 extern int debug; 并在调用 doubleSum 之前修改它,所以编译器不能假定它在函数里一定是 0。译者用 clang -O2 -target x86_64-linux-gnu -S 编译原文的 doubleSum,生成的汇编里仍保留了对 printf 的调用;把声明改成 static int debug = 0;(本文件内从未修改)之后,printf 调用才被完全删掉。要让编译器做这种优化,变量应声明为 static、const,或者干脆用宏。
死代码消除(dead code elimination)
程序中散落着用不到的变量、赋值或语句并不罕见。尽管这些多余的语句很少是有意引入的,但它们往往是软件开发周期中不断迭代和完善的自然副产品。如果不加检测,这些所谓的死代码(dead code)序列会让编译器输出不必要的汇编指令,进而浪费处理时间。大多数编译器使用数据流分析等技术来识别不可达的代码段并将其删除。死代码消除通过减小代码规模及相应的指令集合,常常能让程序更快。举个例子,我们再来看
doubleSum函数,编译器已用常量传播把if语句中的debug替换成了0:
Dead Code Elimination
It is not uncommon for a program to be littered with unused variables, assignments, or statements. Even though these unneeded statements are rarely introduced intentionally, they are often a natural by-product of the constant iteration and refinement of the software development cycle. If left undetected, these so-called dead code sequences can cause compilers to output unnecessary assembly instructions that in turn waste processing time. Most compilers employ techniques such as dataflow analysis to identify unreachable code segments and thereby remove them. Dead code elimination often makes a program faster by shrinking code size and the associated set of instructions. As an example, let’s revisit the
doubleSumfunction in which the compiler employed constant propagation to replacedebugwith0in theifstatement:
1 | int debug = 0; |
采用数据流分析的编译器能认识到 if 语句总是求值为假,printf 语句永远不会执行。因此,编译器会在编译出的可执行文件中删除这个 if 语句和对 printf 的调用。另一遍处理还会删除语句 debug = 0。
A compiler employing dataflow analysis recognizes that the
ifstatement always evaluates to false and that theprintfstatement never executes. The compiler therefore eliminates theifstatement and the call toprintfin the compiled executable. Another pass also eliminates the statementdebug = 0.
简化表达式
有些指令比其他指令代价更高。例如,汇编中的
imul和idiv算术指令需要很长时间才能执行完。编译器通常会尽可能简化数学运算,以减少代价高的指令的数量。例如,在doubleSum函数中,编译器可能会把表达式2 * total替换为total + total,因为加法指令比乘法代价低:
Simplifying expressions
Some instructions are more expensive than others. For example, the
imulandidivarithmetic instructions in assembly take a long time to execute. Compilers commonly attempt to reduce the number of expensive instructions by simplifying mathematical operations whenever possible. For example, in thedoubleSumfunction, the compiler may replace the expression2 * totalwithtotal + totalbecause the addition instruction is less expensive than multiplication:
1 | //declaration of debug removed through dead-code elimination |
同样,编译器会用移位和其他位运算符来变换代码序列,以简化表达式。例如,编译器可能会把表达式 total * 8 替换为 total << 3,或把表达式 total % 8 替换为 total & 7,因为位运算只需一条很快的指令就能完成。
Likewise, the compiler will transform code sequences with bit-shifting and other bitwise operators to simplify expressions. For example, the compiler may replace the expression
total * 8withtotal << 3, or the expressiontotal % 8withtotal & 7given that bitwise operations are performed with a single fast instruction.
译注
对 int 这样可能为负的有符号数,total % 8 不能直接换成 total & 7:C 中 -1 % 8 等于 -1,而 -1 & 7 等于 7。编译器只会在能证明 total 非负,或者类型是无符号数时才做这种替换,否则要加修正指令(同理见 9.3 节关于有符号除法的译注)。
编译器并不总能做到的事:学习代码优化的好处
What Compilers Cannot Always Do: Benefits of Learning Code Optimization
既然优化编译器有这么多好处,学习代码优化有什么用,可能并不是一眼就能看清的。人们很容易把编译器想象成一个「聪明」的神奇黑盒。但归根结底,编译器只是一个为了加速代码而执行一系列代码变换的软件。编译器能执行的优化类型也是有限的。
Given the benefits of optimizing compilers, it may not be immediately obvious why learning code optimization is useful. It may be tempting to think of the compiler as a magical black box that is “smart.” At the end of the day, the compiler is a piece of software that performs a series of code transformations in an effort to speed up code. Compilers are also limited in the types of optimizations they can perform.
算法上的强度削弱是不可能的
代码性能差的首要原因是选错了数据结构和算法。编译器无法神奇地修正这些错误的决定。例如,编译器永远不会把实现冒泡排序的程序优化成实现快速排序的程序。尽管编译器及其优化的复杂程度在不断提高,但任何一个编译器的优化质量在不同平台上都有差异。因此,确保代码使用最佳算法和数据结构的责任在于程序员。
Algorithmic Strength Reduction Is Impossible
The top reason for poor code performance is bad choices of data structures and algorithms. Compilers cannot magically fix these bad decisions. For example, a compiler will never optimize a program implementing bubble sort into one that implements quick sort. While the sophistication of compilers and their optimizations continues to improve, the quality of any individual compiler’s optimizations varies between platforms. The onus is therefore on the programmer to ensure that their code leverages the best algorithms and data structures.
编译器优化选项不能保证让代码「最优」(或行为一致)
提高编译器的优化级别(例如从
-O2提高到-O3)并不总能缩短程序的运行时间。有时,程序员可能会发现把优化选项从-O2提高到-O3反而拖慢了程序,或者根本没有提升性能。在另一些情况下,程序员可能会发现,不加优化选项编译的程序看似没有错误,而用-O2或-O3编译却出现段错误或其他错误。这类编程错误特别难以调试,因为 GCC 的调试选项(-g)与优化选项(-O)不兼容:-O级别的编译器优化所做的变换,会干扰调试器分析底层代码的能力。许多常用的剖析工具(例如 GDB 和 Valgrind)都需要-g选项。
Compiler Optimization Flags Are Not Guaranteed to Make Code “Optimal” (or Consistent)
Increasing the level of compiler optimizations (e.g., from
-O2to-O3) may not always decrease the runtime of a program. Sometimes, the programmer may discover that updating the optimization flags from-O2to-O3slows down a program, or yields no performance increase at all. In other cases, a programmer may discover that a program compiled without the optimization flags seemingly yields no errors, whereas compiling it with-O2or-O3results in segmentation faults or other errors. These types of programming errors are especially difficult to debug, because GCC’s debug (-g) flag is incompatible with its optimization (-O) flags, as the transformations performed by compiler optimizations at the-Olevels interfere with the debugger’s ability to analyze the underlying code. The-gflag is required by many common profiling tools, such as GDB and Valgrind.
译注 · -g 与 -O 可以同时使用
说两者「不兼容」并不准确。GCC 手册明确写道:「GCC 允许你把 -g 和 -O 一起使用」,只是优化后的代码可能出人意料:有些声明的变量可能根本不存在,控制流可能短暂地跑到意想不到的地方,等等。手册还建议,如果不使用其他优化选项,可以把 -Og 与 -g 一起使用,以获得更好的调试体验。GCC 手册:Debugging Options
行为不一致的一个重要原因是,C/C++ 标准没有为如何处理未定义行为提供明确的指导。因此,如何解决这种模糊性往往由编译器决定。不同优化级别对未定义行为的处理方式不一致,可能导致结果发生变化。考虑下面这个来自 John Regehr1 的例子:
One large reason for inconsistent behavior is that the C/C++ standard does not provide clear guidance for resolving undefined behavior. As a result, it is often up to the compiler to decide how to resolve ambiguity. Inconsistencies on how different optimization levels handle undefined behavior can cause answers to change. Consider the following example from John Regehr1:
1 | int silly(int a) { |
假设以 a = INT_MAX 运行 silly。在这种情况下,计算 a + 1 会导致整数溢出。然而,C/C++ 标准并没有规定编译器应当如何处理整数溢出。事实上,不加优化编译这个程序时,函数返回 0;而用 -O3 优化编译时,函数返回 1。
Suppose that
sillywas run witha = INT_MAX. In this case, the computationa1results in integer overflow. However, the C/C++ standard does not define how integer overflow should be handled by the compiler. In fact, compiling the program with no optimizations causes the function to return 0, while compiling it with-O3optimizations results in the function returning 1.
译注
原书网页此处的 a + 1 排版出错,显示成了 a、反斜杠和换行后的 1。译者在 Apple M1 Pro 上用 Clang 复现了这个现象:把 silly 标为 noinline 后以 INT_MAX 调用,-O0 编译输出 0,-O3 编译输出 1。-O3 下编译器依据「有符号溢出是未定义行为」直接把 (a + 1) > a 化简成了 1。
简而言之,使用优化选项时应当谨慎、深思熟虑,并且只在必要时使用。了解应当使用哪些优化选项,也能帮助程序员与编译器协作,而不是与之对抗。
In short, optimization flags should be used with caution, thoughtfully, and when necessary. Learning which optimization flags to employ can also help the programmer work with their compiler instead of against it.
原书注 · 编译器无须处理未定义行为(The compiler is not required to handle undefined behavior)
以 a = INT_MAX 运行 silly 函数,就是未定义行为的一个例子。注意,编译器产生不一致的输出,并不是编译器设计上的缺陷,也不是使用优化选项的后果。编译器被专门设计为遵循语言规范。C 语言标准没有规定编译器遇到未定义行为时应当做什么;程序可能崩溃、无法编译,或者产生不一致或不正确的结果。归根结底,识别并消除代码中的未定义行为是程序员的责任。silly 应当返回 0、1 还是其他某个值,最终是程序员必须做出的决定。要进一步了解 C 程序中的未定义行为及相关问题,请访问 C FAQ2 或 John Regehr 的博客1。
The
sillyfunction when run witha = INT_MAXis an example of undefined behavior. Note that the inconsistent output produced by the compiler is not a flaw in the compiler’s design or a consequence of using optimization flags. Compilers are specifically designed to follow a language’s specification. The C Language standard does not specify what a compiler should do when it encounters undefined behavior; the program may crash, fail to compile, or generate inconsistent or incorrect results. Ultimately, the programmer is responsible for identifying and eliminating undefined behavior in code. Whethersillyshould return 0, 1, or some other value is ultimately a decision the programmer must make. To learn more about undefined behavior and related issues in C programs, visit the C FAQ2 or John Regehr’s blog1.
指针可能带来问题
回想一下,编译器所做的变换不会改变源程序的基本行为。如果某个变换有改变程序行为的风险,编译器就不会做这个变换。在内存别名(memory aliasing)的情况下尤其如此,即两个不同的指针指向内存中的同一个地址。举个例子,考虑下面的函数
shiftAdd,它以两个整型指针作为参数。这个函数把第一个数乘以 10,再加上第二个数。所以,如果给shiftAdd函数传入整数 5 和 6,结果将是 56。
Pointers Can Prove Problematic
Recall that the compiler makes transformations that leave the fundamental behavior of the source program unchanged. If a transformation risks changing the behavior of the program, the compiler will not make the transformation. This is especially true in the case of memory aliasing where two different pointers point to the same address in memory. As an example, consider the following function
shiftAddthat takes two integer pointers as its two parameters. The function multiplies the first number by 10 and adds the second number to it. So, if theshiftAddfunction were passed the integers 5 and 6, the result will be 56.
表 1. 两个把第一个数乘以 10 再加上第二个数的函数的比较。可在这个链接获取。
Table 1. Comparison of two functions that multiplies the first number by 10 and adds the second to it. Available at this link.
未优化版本
Unoptimized Version
1 | void shiftAdd(int *a, int *b){ |
优化版本
Optimized Version
1 | void shiftAddOpt(int *a, int *b){ |
shiftAddOpt 函数对 shiftAdd 函数进行了优化,去掉了一次对 a 的额外内存引用,使编译出的汇编指令更少。然而,由于存在内存别名的风险,编译器永远不会做这个优化。要理解其中的原因,考虑下面的 main 函数:
The
shiftAddOptfunction optimizes theshiftAddfunction by removing an additional memory reference toa, resulting in a smaller set of instructions in the compiled assembly. However, the compiler will never make this optimization due to the risk of memory aliasing. To understand why, consider the followingmainfunction:
1 | int main(void){ |
编译并运行这个程序,得到预期的输出:
Compiling and running this program gives the expected output:
1 | $ gcc -o shiftadd shiftadd.c |
假设改写程序,让 shiftAdd 的两个参数都是指向 x 的指针:
Suppose, instead, that the program were modified so that
shiftAddnow takes a pointer toxas its two parameters:
1 | int main(void){ |
预期的输出是 55。然而,重新编译并运行改写后的代码,得到两个不同的输出:
The expected output is 55. However, recompiling and rerunning the updated code gives two different outputs:
1 | $ gcc -o shiftadd shiftadd.c |
假设 a 和 b 指向同一个内存位置,重新跟踪一遍 shiftAdd 函数,就会发现问题所在。shiftAdd 中把 a 乘以 10,使 x 更新为 50。接着,shiftAdd 中把 b 加到 a 上,使 x 翻倍为 100。内存别名的风险表明,shiftAdd 和 shiftAddOpt 实际上并不等价,尽管程序员的本意可能是让它们等价。要解决这个问题,要认识到 shiftAdd 的第二个参数并不需要以指针形式传入。用整数替换第二个参数,就消除了别名的风险,让编译器能把一个函数优化成另一个:
Retracing through the
shiftAddfunctions with the assumption thataandbare pointing to the same memory location reveals the issue. The multiplication ofaby 10 inshiftAddupdatesxto 50. Next, addingatobinshiftAddresults inxdoubling to 100. The risk of memory aliasing reveals thatshiftAddandshiftAddOptare not in fact equivalent, though the programmer may have intended them to be. To fix this issue, recognize that the second parameter ofshiftAdddoes not need to be passed in as a pointer. Replacing the second parameter with an integer eliminates the risk of aliasing and allows the compiler to optimize one function into the other:
表 2. 改进后的、把第一个数乘以 10 再加上第二个数的函数。可在这个链接获取。
Table 2. Improved functions that multiply the first number by 10 and adds the second to it. Available at this link.
未优化版本(修正后)
Unoptimized (Fixed) Version
1 | void shiftAdd(int *a, int b){ |
优化版本(修正后)
Optimized Version (Fixed)
1 | void shiftAddOpt(int *a, int b){ |
去掉不必要的内存引用,既能让程序员保持原来 shiftAdd 函数的可读性,又能让编译器优化这个函数。
Removing the unneeded memory reference allows the programmer to maintain the readability of the original
shiftAddfunction while enabling the compiler to optimize the function.
译注
如果第二个参数确实需要是指针,C99 起还可以用 restrict 限定符(如 int *restrict a, int *restrict b)向编译器承诺两个指针不会指向同一对象,编译器据此可以做同样的优化;但若调用者违背承诺(像上面那样传 &x, &x),结果就是未定义行为。译者用 clang -O2 -target x86_64-linux-gnu -S 对比:原版 shiftAdd 要两次写回 *a(先存 *a * 10,读 *b 后再存一次),加了 restrict 的版本只在最后写一次。顺便可以看到,乘以 10 被编译成了 lea (%rax,%rax,4) 加一次加法,这正是前面说的「简化表达式」。
与编译器合作:一个示例程序
Partnering with Your Compiler: A Sample Program
在接下来的几节中,我们将集中学习常见的优化类型,并讨论一些编程和剖析策略,让编译器更容易优化我们的代码。为了引导讨论,我们将努力优化下面这个(写得不够好的)程序,它试图找出 2 到 n 之间的所有素数(源代码可在这个链接获取):
In the following sections, we concentrate on learning more about popular types of optimizations and discuss programming and profiling strategies to help make it easier for compilers to optimize our code. To guide our discussion, we will work to optimize the following (suboptimally written) program that attempts to find all the prime numbers between 2 and n (source code available at this link):
1 | //helper function: checks to see if a number is prime |
表 3 展示了用下面的基本编译命令,在不同优化级别下生成 2 到 5,000,000 之间素数的计时结果:
Table 3 shows the timing results for producing the primes between 2 and 5,000,000 with the different optimization level flags using the following basic compilation command:
1 | $ gcc -o optExample optExample.c -lm |
表 3. 生成 2 到 5,000,000 之间的素数所用的时间(秒)
Table 3. Time in Seconds to Produce Prime numbers between 2 and 5,000,000
| 未优化 | -O1 |
-O2 |
-O3 |
|---|---|---|---|
| 3.86 | 2.32 | 2.14 | 2.15 |
Unoptimized -O1-O2-O33.86 2.32 2.14 2.15
使用优化选项时观察到的最快时间约为 2.14 秒。尽管使用优化选项确实让这个程序的运行时间减少了一秒多,但继续提高优化级别带来的改进微乎其微。在接下来的几节中,我们将讨论如何修改程序,让编译器更容易优化它。
The fastest observed time with optimization flags is approximately 2.14 seconds. Although using optimization flags does shave off more than a second from the runtime of this program, upping the optimization flags provides minimal improvement. In the next sections, we will discuss how we can modify our program to make it easier for the compiler to optimize.
参考文献
References
John Regehr. “A Guide to Undefined Behavior in C and C++, Part 1”. https://blog.regehr.org/archives/213
C FAQ. “comp.lang.c FAQ list: Question 11.33”. http://c-faq.com/ansi/undef.html