说明
本文是个人学习用的非官方中英对照译文,原文:https://diveintosystems.org/book/C12-CodeOpt/basic.html。
原书采用 CC BY-NC-ND 4.0 许可(禁止演绎),请勿公开传播本译文。
标为「译注」「现代更新」的内容是译者补充,不代表原书作者观点;代码与原文逐字一致,未作改动。
12.1. Code Optimization First Steps: Code Profiling
「真正的问题在于,程序员在错误的地方、错误的时间,为效率操心得太多了;过早优化是编程中一切罪恶(至少是大部分罪恶)的根源。」——高德纳(Don Knuth),《计算机程序设计艺术》(The Art of Computer Programming)
“The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.” - Don Knuth, The Art of Computer Programming
代码优化中最大的危险之一,是过早优化(premature optimization)的观念。所谓过早优化,是指程序员凭着对性能低效之处的「直觉」而不是数据来进行优化。只要有可能,在着手优化之前,就应当在不同的输入上测量代码不同部分的运行时间,以找出热点(hot spot),即程序中执行指令最多的区域。
One of the biggest dangers in code optimization is the concept of premature optimization. Premature optimization occurs when a programmer attempts to optimize based on “gut feelings” of where performance inefficiencies occur, and not on data. Whenever possible, it is important to measure the runtime of different portions of code on different inputs prior to starting optimization to identify hot spots or areas in the program in which the most instructions occur.
为了弄清如何优化 optExample.c,我们先仔细看看 main 函数:
To figure out how to optimize optExample.c, let’s start by taking a closer look at the
mainfunction:
1 | int main(int argc, char **argv) { |
main 函数包含对两个函数的调用:allocateArray 初始化一个由用户指定长度(即上限)的数组;genPrimeSequence 生成指定上限内的素数序列(注意,对于 2 到 n 之间的任何序列,素数不可能超过 n 个,而且通常要少得多)。该 C 文件中的 main 函数包含为上述两个函数分别计时的代码。在 limit 设为 5,000,000 时编译并运行这段代码,得到下面的结果:
The
mainfunction contains calls to two functions:allocateArray, which initializes an array of a user-specified length (or limit), andgenPrimeSequence, which generates a sequence of primes within the specified limit (note that for any sequence between 2 and n, there cannot be more than n primes, and frequently there are significantly less). Themainfunction in the C file contains code that times each of the two functions above. Compiling and running the code withlimitset to 5,000,000 reveals the following:
1 | $ gcc -o optExample optExample.c -lm |
optExample 程序大约需要 3.86 秒才能完成,几乎所有时间都花在 genPrimeSequence 函数上。花时间去优化 allocateArray 没有意义,因为任何改进对整个程序的运行时间来说都微不足道。在接下来的例子中,我们更仔细地关注 genPrimeSequence 函数及其相关的函数。为方便起见,这里再把这些函数列出来:
The
optExampleprogram takes approximately 3.86 seconds to complete, with nearly all of the time in thegenPrimeSequencefunction. There is no point in spending time optimizingallocateArray, because any improvements will be negligible to the runtime of the overall program. In the examples that follow, we focus more closely on thegenPrimeSequencefunction and its associated functions. The functions are reproduced here for convenience:
1 | // helper function: checks to see if a number is prime |
要找出程序中的热点,应关注循环最多的区域。人工检查代码有助于定位热点,不过在尝试优化之前,总应该用基准测试工具加以验证。人工检查 optExample 程序,可以得出以下观察结果。
To find hot spots in a program, focus on the areas with the most loops. Manual inspection of code can assist in locating hot spots, though it should always be verified with benchmarking tools prior to attempting optimization. A manual inspection of the
optExampleprogram yields the following observations.
genPrimeSequence函数试图生成 2 到某个整数 n 之间的所有素数。由于 2 到 n 之间的素数个数不会超过 n,genPrimeSequence中的for循环最多运行 n 次。for循环的每次迭代都调用一次getNextPrime函数。因此,getNextPrime最多运行 n 次。
- The
genPrimeSequencefunction attempts to generate all the prime numbers between 2 and some integer n. Since the number of primes between 2 and n cannot exceed n, theforloop ingenPrimeSequenceruns no more than n times. Every iteration of theforloop calls thegetNextPrimefunction once. Thus,getNextPrimeruns no more than n times.
getNextPrime函数中的while循环会一直运行,直到发现一个素数为止。尽管很难预先把getNextPrime函数中while循环的执行次数表示为 n 的函数(相邻素数之间的间隔可以任意大),但可以肯定的是,while循环的每次迭代都会执行isPrime。
- The
whileloop in thegetNextPrimefunction will continue running until a prime is discovered. Although it is difficult to determine the number of times thewhileloop in thegetNextPrimefunction will execute ahead of time as a function of n (the gap between consecutive prime numbers can be arbitrarily large), it is certain thatisPrimeexecutes on every iteration of thewhileloop.
isPrime函数恰好包含一个for循环。假设这个循环总共运行 k 次迭代,那么循环体中的代码总共运行 k 次。回想一下,for循环的结构由一个初始化语句(把循环变量初始化为某个值)、一个布尔表达式(决定何时终止循环)和一个步进表达式(每次迭代更新循环变量)组成。表 1 描述了一个运行 k 次迭代的for循环中各组成部分的执行次数。在每个for循环中,初始化恰好发生一次。对于 k 次迭代,布尔表达式执行 k + 1 次,因为它必须再做最后一次检查来终止循环。循环体和步进表达式各执行 k 次。
- The
isPrimefunction contains exactly oneforloop. Suppose that the loop runs for a total of k iterations. Then, the code in the loop body runs k times in total. Recall that the structure of a for loop consists of an initialization statement (which initializes the loop variable to a particular value), a Boolean expression (that determines when to terminate the loop), and a step expression (that updates the loop variable every iteration). Table 1 depicts the number of times each loop component executes in aforloop that runs for k iterations. In everyforloop, initialization happens exactly once. The Boolean expression executes k + 1 times for k iterations, since it must perform one final check to terminate the loop. The loop body and the step expression execute k times each.
表 1. 循环各组成部分的执行次数(假设 k 次迭代)
Table 1. Loop execution components (assuming k iterations)
| 初始化语句 | 布尔表达式 | 步进表达式 | 循环体 |
|---|---|---|---|
| 1 | k+1 | k | k |
Initialization statement Boolean expression Step expression Loop body 1 k+1 k k
我们对代码的人工检查表明,程序的大部分时间花在 isPrime 函数中,而 sqrt 函数执行得最频繁。接下来我们用代码剖析来验证这个假设。
Our manual inspection of the code suggests that the program spends most of its time in the
isPrimefunction, and that thesqrtfunction executes the most often. Let’s next use code profiling to verify this hypothesis.
12.1.1. 用 Callgrind 进行剖析
12.1.1. Using Callgrind to Profile
在我们这个小程序中,用人工检查得出「sqrt 函数位于代码的『热点』中」这一假设相对简单。然而,在较大的程序中识别热点会变得复杂得多。无论如何,用剖析来验证我们的假设都是个好主意。像 Valgrind 这样的代码剖析工具能提供大量关于程序执行的信息。在本节中,我们用 callgrind 工具来查看 OptExample 程序的调用图。
In our small program, it was relatively straightforward to use manual inspection to form the hypothesis that the
sqrtfunction occurs in a “hot spot” in the code. However, identifying hot spots can become more complex in larger programs. Regardless, it is a good idea to use profiling to verify our hypothesis. Code profiling tools like Valgrind provide a lot of information about program execution. In this section, we use thecallgrindtool to inspect theOptExampleprogram’s call graph.
译注
与第 11 章相同,Valgrind(包括 callgrind)不能在 Apple Silicon Mac 上运行,需要在 Linux 虚拟机或容器中跟做本节。
要使用 callgrind,我们先用 -g 选项重新编译 optExample 程序,并在一个较小的范围(2 到 100,000)上运行 callgrind。与其他 Valgrind 应用一样,callgrind 作为程序的包装器运行,添加诸如各函数的执行次数以及由此执行的指令总数之类的注解。因此,与 callgrind 一起运行时,optExample 程序要花更长的时间才能执行完。
To use
callgrind, let’s start by recompiling theoptExampleprogram with the-gflag and runningcallgrindon a smaller range (2 to 100,000). Like other Valgrind applications,callgrindruns as a wrapper around a program, adding annotations such as the number of times functions execute and the total number of instructions that are executed as a result. Consequently, theoptExampleprogram will take longer to execute when run in conjunction withcallgrind.
1 | $ gcc -g -o optExample optExample.c -lm |
在终端输入 ls,会看到一个名为 callgrind.out.xxxxx 的新文件,其中 xxxxx 是一个唯一的 id。在这里,这个文件是 callgrind.out.32590(即上面输出左侧一栏显示的数字)。对这个文件运行 callgrind_annotate,可以得到关于我们关心的三个函数的更多信息:
Typing
lsat the terminal reveals a new file calledcallgrind.out.xxxxx, wherexxxxxis a unique id. In this case, the file iscallgrind.out.32590(i.e., the number shown along the left-hand column in the preceding output). Runningcallgrind_annotateon this file yields additional information on the three functions of interest:
1 | $ callgrind_annotate --auto=yes callgrind.out.32590 |
左侧一栏的数字表示与每一行相关的执行指令总数。括号中的数字表示某个函数运行的次数。利用左侧一栏的数字,我们能够验证人工检查的结果。在 genPrimeSequence 函数中,getNextPrime 函数导致的执行指令数最多,为 6780 万条,对应 9,592 次函数调用(生成 2 到 100,000 之间的素数)。检查 getNextPrime 可以发现,其中大部分指令(6710 万条,即 99%)来自对 isPrime 的调用,isPrime 总共被调用了 100,001 次。最后,检查 isPrime 可以发现,总指令中有 1300 万条(20.5%)来自 sqrt 函数,它总共执行了 270 万次。
The numbers along the left-hand column represent the number of total executed instructions associated with each line. The numbers in parentheses indicate the number of times a particular function was run. Using the numbers along the left-hand column, we are able to verify the results of our manual inspection. In the
genPrimeSequencefunction, thegetNextPrimefunction resulted in the most number of executed instructions at 67.8 million instructions, corresponding to 9,592 function calls (to generate the primes between 2 and 100,000). InspectinggetNextPrimereveals that the majority of those instructions (67.1 million, or 99%) result from the call toisPrime, which is called a total of 100,001 times. Lastly, inspectingisPrimereveals that 13 million of the total instructions (20.5%) result from thesqrtfunction, which executes a total of 2.7 million times.
这些结果验证了我们最初的假设:程序的大部分时间花在 isPrime 函数中,而 sqrt 函数是所有函数中执行最频繁的。减少执行的指令总数会让程序更快;上面的分析表明,我们最初的努力应当集中在改进 isPrime 函数上,并尽可能减少 sqrt 的执行次数。
These results verify our original hypothesis that the program spends most of its time in the
isPrimefunction, with thesqrtfunction executing the most frequently of all the functions. Reducing the total number of executed instructions results in a faster program; the above analysis suggests that our initial efforts should concentrate on improving theisPrimefunction, and potentially reducing the number of timessqrtexecutes.
12.1.2. 循环不变量外提
12.1.2. Loop-Invariant Code Motion
循环不变量外提(loop-invariant code motion)是一种优化技术,它把循环内部发生的静态计算移到循环外部,而不影响循环的行为。优化编译器能够自动完成大多数循环不变量优化。具体来说,GCC 中的 -fmove-loop-invariants 编译选项(在 -O1 级别启用)会尝试识别可以外提的循环不变量代码,并把它们移到各自的循环之外。
Loop-invariant code motion is an optimization technique that moves static computations that occur inside a loop to outside the loop without affecting the loop’s behavior. Optimizing compilers are capable of making most loop-invariant code optimizations automatically. Specifically, the
-fmove-loop-invariantscompiler flag in GCC (enabled at level-O1) attempts to identify examples of loop-invariant code motion and move them outside their respective loop.
然而,编译器并不总能识别出循环不变量外提的机会,尤其是在涉及函数调用的情况下。由于函数调用可能无意中引起副作用(side effect,即非预期的行为),大多数编译器会避免去判断一个函数调用是否总是返回相同的结果。因此,尽管程序员知道 sqrt(x) 总是返回某个输入 x 的平方根,GCC 并不总会做出这样的假设。考虑 sqrt 函数会更新一个秘密的全局变量 g 的情形。在这种情况下,在循环外面调用一次 sqrt(对 g 更新一次),与在循环的每次迭代中都调用它(对 g 更新 n 次)是不一样的。如果编译器无法确定一个函数总是返回相同的结果,它就不会自动把 sqrt 函数移到循环之外。
However, the compiler cannot always identify cases of loop-invariant code motion, especially in the case of function calls. Since function calls can inadvertently cause side effects (unintended behavior), most compilers will avoid trying to determine whether a function call consistently returns the same result. Thus, even though the programmer knows that
sqrt(x)always returns the square root of some inputx, GCC will not always make that assumption. Consider the case where thesqrtfunction updates a secret global variable,g. In that case, callingsqrtonce outside of the function (one update tog) is not the same as calling it every iteration of the loop (n updates tog). If a compiler cannot determine that a function always returns the same result, it will not automatically move thesqrtfunction outside the loop.
然而,程序员知道,把计算 sqrt(x) + 1 移到 for 循环之外不会影响循环的行为。更新后的函数如下,也可以在这个文件中获取:
However, the programmer knows that moving the computation
sqrt(x) + 1outside theforloop does not effect the loop’s behavior. The updated function is shown here and is available in the following file:
1 | //helper function: checks to see if a number is prime |
表 2 显示,即使还没有使用编译选项,这个简单的改动就让 optExample2 的运行时间减少了整整两秒(47%)。此外,编译器优化 optExample2 似乎也稍微容易一些。
Table 2 shows that this simple change shaves off a full two seconds (47%) of the runtime of
optExample2, even before using compiler flags. Furthermore, the compiler seems to have a slightly easier time optimizingoptExample2.
译注
按表中数据,未优化时运行时间从 3.86 秒降到 1.83 秒,减少了约 2.03 秒,降幅约 53%;1.83 秒约为原来的 47%。原文的「47%」应理解为优化后所用时间占原时间的比例。
表 2. 生成 2 到 5,000,000 之间的素数所用的时间(秒)
Table 2. Time in Seconds to Produce the Prime Numbers Between 2 and 5,000,000
| 版本 | 未优化 | -O1 |
-O2 |
-O3 |
|---|---|---|---|---|
| 原始版本 | 3.86 | 2.32 | 2.14 | 2.15 |
| 循环不变量外提后 | 1.83 | 1.63 | 1.71 | 1.63 |
Version Unoptimized -O1-O2-O3Original 3.86 2.32 2.14 2.15 With loop-invariant code motion 1.83 1.63 1.71 1.63
在 optExample2 可执行文件上重新运行 callgrind,就能看出为什么运行时间有这么大的改进。下面的代码片段假设文件 callgrind.out.30086 中存放的是在 optExample2 可执行文件上运行 callgrind 得到的注解:
Rerunning
callgrindon theoptExample2executable reveals why such a large improvement in runtime was observed. The following code snippet assumes that the filecallgrind.out.30086contains the annotations of runningcallgrindon theoptExample2executable:
1 | $ gcc -g -o optExample2 optExample2.c -lm |
把对 sqrt 的调用移到 for 循环之外,使程序中 sqrt 函数的调用次数从 270 万次减少到 100,000 次(减少了 96%)。这个数字与 isPrime 函数的调用次数相符,证实了每次调用 isPrime 时 sqrt 函数只执行一次。
Moving the call to
sqrtoutside of theforloop reduces the number of times thesqrtfunction is called in the program from 2.7 million to 100,000 (96% reduction). This number corresponds to the number of times theisPrimefunction is called, confirming that thesqrtfunction executes only once with every invocation of theisPrimefunction.
注意,在指定了优化选项时,即使程序员没有手动外提代码,编译器也能进行相当程度的优化。在这个例子中,原因是 x86 ISA 规定了一条名为 fsqrt 的特殊指令。打开优化选项时,编译器会用 fsqrt 指令替换所有 sqrt 函数的实例。这个过程称为内联(inlining),我们会在下一节中更详细地介绍它。由于 fsqrt 不再是一个函数,编译器更容易识别出它的循环不变性质,并把它移到循环体之外。
Note that the compiler was able to perform significant levels of optimization when optimization flags were specified, even if the programmer does not manually perform code motion. In this case, the reason is due to a special instruction called
fsqrtthat is specified by the x86 ISA. When optimization flags are turned on, the compiler replaces all instances of thesqrtfunction with thefsqrtinstruction. This process is known as inlining, and we cover it greater detail in the following section. Becausefsqrtis no longer a function, it is easier for the compiler to identify its loop-invariant nature, and move it outside the body of the loop.
译注 · 实际用的是 sqrtsd
fsqrt 是老式 x87 浮点单元的指令;在 x86-64 上,编译器对 double 求平方根用的是 SSE2 的 sqrtsd。严格说来,把 sqrt 换成一条指令属于编译器对内建函数(builtin)的展开,与下一节讲的、把用户函数体复制到调用处的内联并不完全相同。译者用 clang -O2 -target x86_64-linux-gnu -S 编译原始的 isPrime,可以看到 sqrtsd 只在循环开始前执行一次(已被外提),旁边还保留了一个对 sqrt@PLT 的调用,只在参数为负时才走到那里(交给库函数处理定义域错误,例如设置 errno)。