第 129 / 187 篇

12.1. 代码优化的第一步:代码剖析

说明

本文是个人学习用的非官方中英对照译文,原文: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 main function:

1
2
3
4
5
6
7
8
9
10
11
int main(int argc, char **argv) {
// error-handling and timing code omitted for brevity

int limit = strtol(argv[1], NULL, 10);
int length = limit;
int *array = allocateArray(length); //allocates array of specified length

genPrimeSequence(array, limit, &length); //generates sequence of primes

return 0;
}

main 函数包含对两个函数的调用:allocateArray 初始化一个由用户指定长度(即上限)的数组;genPrimeSequence 生成指定上限内的素数序列(注意,对于 2 到 n 之间的任何序列,素数不可能超过 n 个,而且通常要少得多)。该 C 文件中的 main 函数包含为上述两个函数分别计时的代码。在 limit 设为 5,000,000 时编译并运行这段代码,得到下面的结果:

The main function contains calls to two functions: allocateArray, which initializes an array of a user-specified length (or limit), and genPrimeSequence, 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). The main function in the C file contains code that times each of the two functions above. Compiling and running the code with limit set to 5,000,000 reveals the following:

1
2
3
4
5
6
7
8
$ gcc -o optExample optExample.c -lm
$ time -p ./optExample 5000000
Time to allocate: 5.5e-05
Time to generate primes: 3.85525
348513 primes found.
real 3.85
user 3.86
sys 0.00

optExample 程序大约需要 3.86 秒才能完成,几乎所有时间都花在 genPrimeSequence 函数上。花时间去优化 allocateArray 没有意义,因为任何改进对整个程序的运行时间来说都微不足道。在接下来的例子中,我们更仔细地关注 genPrimeSequence 函数及其相关的函数。为方便起见,这里再把这些函数列出来:

The optExample program takes approximately 3.86 seconds to complete, with nearly all of the time in the genPrimeSequence function. There is no point in spending time optimizing allocateArray, because any improvements will be negligible to the runtime of the overall program. In the examples that follow, we focus more closely on the genPrimeSequence function and its associated functions. The functions are reproduced here for convenience:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// helper function: checks to see if a number is prime
int isPrime(int x) {
int i;
for (i = 2; i < sqrt(x) + 1; i++) { //no prime number is less than 2
if (x % i == 0) { //if the number is divisible by i
return 0; //it is not prime
}
}
return 1; //otherwise it is prime
}

// finds the next prime
int getNextPrime(int prev) {
int next = prev + 1;
while (!isPrime(next)) { //while the number is not prime
next++; //increment and check again
}
return next;
}

// generates a sequence of primes
int genPrimeSequence(int *array, int limit) {
int i;
int len = limit;
if (len == 0) return 0;
array[0] = 2; //initialize the first number to 2
for (i = 1; i < len; i++) {
array[i] = getNextPrime(array[i-1]); //fill in the array
if (array[i] > limit) {
len = i;
return len;
}
}
return len;
}

要找出程序中的热点,应关注循环最多的区域。人工检查代码有助于定位热点,不过在尝试优化之前,总应该用基准测试工具加以验证。人工检查 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 optExample program yields the following observations.

  • genPrimeSequence 函数试图生成 2 到某个整数 n 之间的所有素数。由于 2 到 n 之间的素数个数不会超过 n,genPrimeSequence 中的 for 循环最多运行 n 次。for 循环的每次迭代都调用一次 getNextPrime 函数。因此,getNextPrime 最多运行 n 次。
  • The genPrimeSequence function 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, the for loop in genPrimeSequence runs no more than n times. Every iteration of the for loop calls the getNextPrime function once. Thus, getNextPrime runs no more than n times.
  • getNextPrime 函数中的 while 循环会一直运行,直到发现一个素数为止。尽管很难预先把 getNextPrime 函数中 while 循环的执行次数表示为 n 的函数(相邻素数之间的间隔可以任意大),但可以肯定的是,while 循环的每次迭代都会执行 isPrime。
  • The while loop in the getNextPrime function will continue running until a prime is discovered. Although it is difficult to determine the number of times the while loop in the getNextPrime function will execute ahead of time as a function of n (the gap between consecutive prime numbers can be arbitrarily large), it is certain that isPrime executes on every iteration of the while loop.
  • isPrime 函数恰好包含一个 for 循环。假设这个循环总共运行 k 次迭代,那么循环体中的代码总共运行 k 次。回想一下,for 循环的结构由一个初始化语句(把循环变量初始化为某个值)、一个布尔表达式(决定何时终止循环)和一个步进表达式(每次迭代更新循环变量)组成。表 1 描述了一个运行 k 次迭代的 for 循环中各组成部分的执行次数。在每个 for 循环中,初始化恰好发生一次。对于 k 次迭代,布尔表达式执行 k + 1 次,因为它必须再做最后一次检查来终止循环。循环体和步进表达式各执行 k 次。
  • The isPrime function contains exactly one for loop. 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 a for loop that runs for k iterations. In every for loop, 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 isPrime function, and that the sqrt function 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 sqrt function 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 the callgrind tool to inspect the OptExample program’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 the optExample program with the -g flag and running callgrind on a smaller range (2 to 100,000). Like other Valgrind applications, callgrind runs 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, the optExample program will take longer to execute when run in conjunction with callgrind.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
$ gcc -g -o optExample optExample.c -lm
$ valgrind --tool=callgrind ./optExample 100000
==32590== Callgrind, a call-graph generating cache profiler
==32590== Copyright (C) 2002-2015, and GNU GPL'd, by Josef Weidendorfer et al.
==32590== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==32590== Command: ./optExample 100000
==32590==
==32590== For interactive control, run 'callgrind_control -h'.
Time to allocate: 0.003869
Time to generate primes: 0.644743
9592 primes found.
==32590==
==32590== Events : Ir
==32590== Collected : 68338759
==32590==
==32590== I refs: 68,338,759

在终端输入 ls,会看到一个名为 callgrind.out.xxxxx 的新文件,其中 xxxxx 是一个唯一的 id。在这里,这个文件是 callgrind.out.32590(即上面输出左侧一栏显示的数字)。对这个文件运行 callgrind_annotate,可以得到关于我们关心的三个函数的更多信息:

Typing ls at the terminal reveals a new file called callgrind.out.xxxxx, where xxxxx is a unique id. In this case, the file is callgrind.out.32590 (i.e., the number shown along the left-hand column in the preceding output). Running callgrind_annotate on this file yields additional information on the three functions of interest:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
$ callgrind_annotate --auto=yes callgrind.out.32590
----------------------------------------------------------------
Profile data file 'callgrind.out.32393' (creator: callgrind-3.11.0)
----------------------------------------------------------------
...
. //helper function: checks to see if a number is prime
400,004 int isPrime(int x) {
. int i;
36,047,657 for (i = 2; i < sqrt(x)+1; i++) { //no prime is less than 2
13,826,015 => ???:sqrt (2765204x)
16,533,672 if (x % i == 0) { //if the number is divisible by i
180,818 return 0; //it is not prime
. }
. }
9,592 return 1; //otherwise it is prime
200,002 }
.
. // finds the next prime
38,368 int getNextPrime(int prev) {
28,776 int next = prev + 1;
509,597 while (!isPrime(next)) { //while the number is not prime
67,198,556 => optExample.c:isPrime (100001x)
90,409 next++; //increment and check again
. }
9,592 return next;
19,184 }
.
. // generates a sequence of primes
6 int genPrimeSequence(int * array, int limit) {
. int i;
2 int len = limit;
2 if (len == 0) return 0;
2 array[0]=2; //initialize the first number to 2
38,369 for (i = 1; i < len; i++) {
143,880 array[i] = getNextPrime(array[i-1]); //fill in the array
67,894,482 => optExample.c:getNextPrime (9592x)
76,736 if (array[i] > limit){
2 len = i;
2 return len;
. }
. }
. return len;
4 }

左侧一栏的数字表示与每一行相关的执行指令总数。括号中的数字表示某个函数运行的次数。利用左侧一栏的数字,我们能够验证人工检查的结果。在 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 genPrimeSequence function, the getNextPrime function 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). Inspecting getNextPrime reveals that the majority of those instructions (67.1 million, or 99%) result from the call to isPrime, which is called a total of 100,001 times. Lastly, inspecting isPrime reveals that 13 million of the total instructions (20.5%) result from the sqrt function, 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 isPrime function, with the sqrt function 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 the isPrime function, and potentially reducing the number of times sqrt executes.

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-invariants compiler 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 input x, GCC will not always make that assumption. Consider the case where the sqrt function updates a secret global variable, g. In that case, calling sqrt once outside of the function (one update to g) is not the same as calling it every iteration of the loop (n updates to g). If a compiler cannot determine that a function always returns the same result, it will not automatically move the sqrt function outside the loop.

然而,程序员知道,把计算 sqrt(x) + 1 移到 for 循环之外不会影响循环的行为。更新后的函数如下,也可以在这个文件中获取:

However, the programmer knows that moving the computation sqrt(x) + 1 outside the for loop does not effect the loop’s behavior. The updated function is shown here and is available in the following file:

1
2
3
4
5
6
7
8
9
10
11
//helper function: checks to see if a number is prime
int isPrime(int x) {
int i;
int max = sqrt(x)+1;
for (i = 2; i < max; i++) { //no prime number is less than 2
if (x % i == 0) { //if the number is divisible by i
return 0; //it is not prime
}
}
return 1; //otherwise it 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 optimizing optExample2.

译注

按表中数据,未优化时运行时间从 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 -O3
Original 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 callgrind on the optExample2 executable reveals why such a large improvement in runtime was observed. The following code snippet assumes that the file callgrind.out.30086 contains the annotations of running callgrind on the optExample2 executable:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
$ gcc -g -o optExample2 optExample2.c -lm
$ valgrind --tool=callgrind ./optExample2 100000
$ callgrind_annotate --auto=yes callgrind.out.30086
------------------------------------------------------------------
Profile data file 'callgrind.out.30086' (creator: callgrind-3.11.0)
------------------------------------------------------------------
...
400,004 int isPrime(int x) {
. int i;
900,013 int max = sqrt(x)+1;
500,000 => ???:sqrt (100001x)
11,122,449 for (i = 2; i < max; i++) { //no prime number is less than 2
16,476,120 if (x % i == 0) { //if the number is divisible by i
180,818 return 0; //it is not prime
. }
. }
9,592 return 1; //otherwise it is prime
200,002 }
.
. // finds the next prime
38,368 int getNextPrime(int prev) {
28,776 int next = prev + 1;
509,597 while (!isPrime(next)) { //while the number is not prime
29,789,794 => optExample2.c:isPrime (100001x)
90,409 next++; //increment and check again
. }
9,592 return next;
19,184 }

把对 sqrt 的调用移到 for 循环之外,使程序中 sqrt 函数的调用次数从 270 万次减少到 100,000 次(减少了 96%)。这个数字与 isPrime 函数的调用次数相符,证实了每次调用 isPrime 时 sqrt 函数只执行一次。

Moving the call to sqrt outside of the for loop reduces the number of times the sqrt function is called in the program from 2.7 million to 100,000 (96% reduction). This number corresponds to the number of times the isPrime function is called, confirming that the sqrt function executes only once with every invocation of the isPrime function.

注意,在指定了优化选项时,即使程序员没有手动外提代码,编译器也能进行相当程度的优化。在这个例子中,原因是 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 fsqrt that is specified by the x86 ISA. When optimization flags are turned on, the compiler replaces all instances of the sqrt function with the fsqrt instruction. This process is known as inlining, and we cover it greater detail in the following section. Because fsqrt is 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)。