说明
本文是个人学习用的非官方中英对照译文,原文:https://diveintosystems.org/book/C12-CodeOpt/loops_functions.html。
原书采用 CC BY-NC-ND 4.0 许可(禁止演绎),请勿公开传播本译文。
标为「译注」「现代更新」的内容是译者补充,不代表原书作者观点;代码与原文逐字一致,未作改动。
12.2. Other Compiler Optimizations: Loop Unrolling and Function Inlining
上一节介绍的循环不变量外提优化是一个简单的改动,却大幅缩短了执行时间。然而,这类优化取决于具体情况,并不总能提高性能。在大多数情况下,循环不变量外提由编译器负责完成。
The loop-invariant code motion optimization described in the previous section was a simple change that resulted in a massive reduction in execution time. However, such optimizations are situationally dependent, and may not always result in improvements to performance. In most cases, loop-invariant code motion is taken care of by the compiler.
如今,代码被阅读的次数比被编写的次数多。在大多数情况下,为了微小的性能提升而损害代码的可读性是不值得的。一般来说,程序员应当尽可能让编译器去做优化。在本节中,我们介绍一些以前由程序员手动实现、如今通常由编译器实现的优化技术。
Code today is more often read than it is written. In most cases, fractional performance gains are not worth the hit to code readability. In general, a programmer should let the compiler optimize whenever possible. In this section, we cover some optimization techniques that were previously manually implemented by programmers but are today commonly implemented by compilers.
网上有一些资料提倡手动实现我们在接下来几节中描述的技术。不过,我们鼓励读者在尝试于代码中手动实现这些优化之前,先检查自己的编译器是否支持它们。本节描述的所有优化 GCC 都已实现,但较老的编译器中可能没有。
There are several sources online that advocate for the manual implementation of the techniques we describe in the following sections. However, we encourage readers to check whether their compilers support the following optimizations before attempting to manually implement them in their code. All the optimizations described in this section are implemented in GCC, but may not be available in older compilers.
12.2.1. 函数内联
12.2.1. Function Inlining
编译器试图执行的一个优化步骤是函数内联(function inlining),即用函数体替换对函数的调用。例如,在 main 函数中,对 allocateArray 函数进行内联的编译器,会把对 allocateArray 的调用替换为对 malloc 的直接调用:
One optimization step that compilers attempt to perform is function inlining, which replaces calls to a function with the body of the function. For example, in the
mainfunction, a compiler inlining theallocateArrayfunction will replace the call toallocateArraywith a direct call tomalloc:
表 1. 编译器内联 allocateArray 函数的示例
Table 1. Example of compiler inlining the allocateArray function.
原始版本
Original Version
1 | int main(int argc, char **argv) { |
内联了 allocateArray 的版本
Version with allocateArray in-lined
1 | int main(int argc, char **argv) { |
内联函数可以为程序节省一些运行时间。回想一下,程序每次调用函数时,都必然会生成许多与函数的建立和销毁相关的指令。内联函数让编译器能消除这些多余的调用,并让编译器更容易发现其他可能的改进,包括常量传播、常量折叠和死代码消除。在 optExample 程序的例子中,内联很可能让编译器得以用 fsqrt 指令替换对 sqrt 的调用,进而把它移到循环之外。
Inlining functions can result in some runtime savings for a program. Recall that every time a program calls a function, many instructions associated with function creation and destruction are necessarily generated. Inlining functions enables the compiler to eliminate these excessive calls, and makes it easier for the compiler to identify other potential improvements, including constant propagation, constant folding, and dead code elimination. In the case of the
optExampleprogram, inlining likely allows the compiler to replace the call tosqrtwith thefsqrtinstruction, and subsequently move it outside the loop.
-finline-functions 选项建议 GCC 对函数进行内联。这项优化在 3 级优化时开启。尽管 -finline-functions 可以独立于 -O3 选项使用,但它只是给编译器的一个建议,让编译器去寻找可以内联的函数。同样,可以用 static inline 关键字建议编译器内联某个特定的函数。记住,编译器不会内联所有函数,函数内联也不能保证让代码更快。
The
-finline-functionsflag suggests to GCC that functions should be inlined. This optimization is turned on at level 3. Even though-finline-functionscan be used independently of the-O3flag, it is a suggestion to the compiler to look for functions to inline. Likewise, thestatic inlinekeyword can be used to suggest to the compiler that a particular function should be inlined. Keep in mind that the compiler will not inline all functions, and that function inlining is not guaranteed to make code faster.
译注
按当前的 GCC 手册,-finline-functions 在 -O2 级别就已开启(见本章开头的现代更新)。另外,上一段提到的 fsqrt 在 x86-64 上实际是 SSE2 的 sqrtsd,见上一节的译注。
程序员一般应当避免手动内联函数。手动内联函数很可能会大大降低代码的可读性,增加出错的可能,并使函数更难更新和维护。例如,试图把 isPrime 函数内联到 getNextPrime 函数中,会大大降低 getNextPrime 的可读性。
Programmers should generally avoid inlining functions manually. Inlining functions carries a high risk of significantly reducing the readability of code, increasing the likelihood of errors, and making it harder to update and maintain functions. For example, trying to inline the
isPrimefunction in thegetNextPrimefunction will greatly reduce the readability ofgetNextPrime.
12.2.2. 循环展开
12.2.2. Loop Unrolling
本节讨论的最后一种编译器优化策略是循环展开。我们再来看 isPrime 函数:
The last compiler optimization strategy we discuss in this section is loop unrolling. Let’s revisit the
isPrimefunction:
1 | // helper function: checks to see if a number is prime |
for 循环总共执行 max 次,其中 max 比整数 x 的平方根大一。在汇编层面,循环的每次执行都要检查 i 是否小于 max。如果是,指令指针就跳到计算取模运算的循环体。如果取模运算的结果为 0,程序立即退出循环并返回 0;否则,循环继续执行。尽管分支预测器很擅长预测条件表达式的求值结果(尤其是在循环内部),但一旦猜错,就会打乱指令流水线,造成性能损失。
The
forloop executes a total ofmaxtimes, wheremaxis one more than the square root of integerx. At the assembly level, every execution of the loop checks to see whetheriis less thanmax. If so, the instruction pointer jumps to the body of the loop, which computes the modulo operation. If the modulo operation results in 0, the program immediately exits the loop and returns 0. Otherwise, the loop continues execution. While branch predictors are fairly good at predicting what a conditional expression evaluates to (especially inside loops), wrong guesses can result in a hit to performance, due to disruptions in the instruction pipeline.
循环展开(loop unrolling)是编译器为减少猜错的影响而进行的一种优化。循环展开的目标是把每次迭代完成的工作量增加到 n 倍,从而把循环的迭代次数减少到 1/n。当一个循环按 2 倍展开时,循环的迭代次数减为一半,而每次迭代完成的工作量翻倍。
Loop unrolling is an optimization that compilers perform to reduce the impact of wrong guesses. In loop unrolling, the goal is to reduce the number of iterations of a loop by a factor of n by increasing the workload that each iteration performs by a factor of n. When a loop is unrolled by a factor of 2, the number of iterations in the loop is cut by half, whereas the amount work performed per iteration is doubled.
我们来手动对 isPrime 函数应用 2 倍循环展开(见 optExample3.c):
Let’s manually apply 2-factor loop unrolling to our
isPrimefunction (available in optExample3.c):
1 | // helper function: checks to see if a number is prime |
注意,尽管我们把 for 循环的迭代次数减半了,但循环的每次迭代现在要做两次取模检查,每次迭代的工作量翻了一番。重新编译并运行程序,运行时间略有改善(见表 2)。代码的可读性也降低了。使用循环展开的更好方式,是调用 -funroll-loops 编译优化选项,它告诉编译器展开那些迭代次数可以在编译时确定的循环。-funroll-all-loops 编译选项是一个更激进的选项,无论编译器能否确定迭代次数,它都会展开所有循环。表 2 展示了手动 2 倍循环展开(见 optExample3.c)的运行时间,并与在前一个程序(optExample2.c)上加 -funroll-loops 和 -funroll-all-loops 编译优化选项的运行时间进行比较。
Notice that even though we have halved the number of iterations that the
forloop takes, each iteration of the loop now performs two modulo checks, doubling the amount of work per iteration. Recompiling and rerunning the program results in marginally improved times (see Table 2). The readability of the code is also reduced. A better way to utilize loop unrolling is to invoke the-funroll-loopscompiler optimization flag, which tells the compiler to unroll loops whose iterations can be determined at compile time. The-funroll-all-loopscompiler flag is a more aggressive option that unrolls all loops whether or not the compiler is certain of the number of iterations. Table 2 shows the runtimes of the manual 2-factor loop unrolling (available inoptExample3.c) compared to adding the-funroll-loopsand-funroll-all-loopscompiler optimization flags to the previous program (optExample2.c).
表 2. 生成 5,000,000 个素数所用的时间(秒)
Table 2. Time in Seconds to Produce 5,000,000 Prime Numbers
译注
表中前两行与 12.1 节表 2 完全相同,可见这里沿用的是同一个实验,即生成 2 到 5,000,000 之间的素数,而不是「5,000,000 个素数」。
| 版本 | 未优化 | -O1 |
-O2 |
-O3 |
|---|---|---|---|---|
| 原始版本(optExample.c) | 3.86 | 2.32 | 2.14 | 2.15 |
| 循环不变量外提后(optExample2.c) | 1.83 | 1.63 | 1.71 | 1.63 |
| 手动 2 倍循环展开(optExample3.c) | 1.65 | 1.53 | 1.45 | 1.45 |
加 -funroll-loops(optExample2.c) |
1.82 | 1.48 | 1.46 | 1.46 |
加 -funroll-all-loops(optExample2.c) |
1.81 | 1.47 | 1.47 | 1.46 |
Version Unoptimized -O1-O2-O3Original (optExample.c) 3.86 2.32 2.14 2.15 With loop-invariant code motion (optExample2.c) 1.83 1.63 1.71 1.63 With manual 2-factor loop unrolling (optExample3.c) 1.65 1.53 1.45 1.45 With -funroll-loops(optExample2.c)1.82 1.48 1.46 1.46 With -funroll-all-loops(optExample2.c)1.81 1.47 1.47 1.46
尽管手动循环展开确实带来了一些性能提升,但编译器内建的循环展开选项与其他优化选项结合使用时,能获得相当的性能。如果程序员想在代码中加入循环展开优化,默认应当使用相应的编译选项,而不是自己手动展开循环。
While manual loop unrolling does result in some performance improvement, the compiler’s built-in loop unrolling flags when combined with the other optimization flags yield comparable performance. If a programmer wants to incorporate loop unrolling optimizations into their code, they should default to using the appropriate compiler flags, and not manually unroll loops themselves.