说明
本文是个人学习用的非官方中英对照译文,原文:https://diveintosystems.org/book/C12-CodeOpt/memory_considerations.html。
原书采用 CC BY-NC-ND 4.0 许可(禁止演绎),请勿公开传播本译文。
标为「译注」「现代更新」的内容是译者补充,不代表原书作者观点;代码与原文逐字一致,未作改动。
12.3. Memory Considerations
程序员应当特别注意内存的使用,尤其是在使用矩阵和数组这类占用大量内存的数据结构时。尽管编译器提供了强大的优化功能,但编译器并不总能做出改善程序内存使用的优化。在本节中,我们用一个矩阵-向量程序的实现(matrixVector.c)来引导对改善内存使用的技术和工具的讨论。
Programmers should pay special attention to memory use, especially when employing memory-intensive data structures such as matrices and arrays. Although compilers offer powerful optimization features, the compiler cannot always make optimizations that improve a program’s memory use. In this section, we use an implementation of a matrix-vector program (matrixVector.c) to guide discussion of techniques and tools for improving memory use.
这个程序的 main 函数执行两个步骤。首先,它分配并初始化输入矩阵、输入向量和输出矩阵。然后,它执行矩阵-向量乘法。在 10,000 × 10,000 的矩阵-向量规模上运行代码,可以看到 matrixVectorMultiply 函数占用了大部分时间:
The
mainfunction of the program performs two steps. First, it allocates and initializes the input matrix, the input vector, and the output matrix. Next, it performs matrix-vector multiplication. Running the code on matrix-vector dimensions of 10,000 × 10,000 reveals that thematrixVectorMultiplyfunction takes up the majority of the time:
1 | $ gcc -o matrixVector matrixVector.c |
因此,我们的讨论将集中在 matrixVectorMultiply 函数上。
Our discussion will thus focus on the
matrixVectorMultiplyfunction.
12.3.1. 循环交换
12.3.1. Loop Interchange
循环交换(loop interchange)优化交换嵌套循环中内外层循环的顺序,以最大化缓存局部性。编译器很难自动完成这项任务。GCC 中虽然有 -floop-interchange 编译选项,但目前默认不开启。因此,程序员最好留意自己的代码是如何访问数组和矩阵这类复合内存数据结构的。举个例子,我们来仔细看看 matrixVector.c 中的 matrixVectorMultiply 函数:
Loop interchange optimizations switch the order of inner and outer loops in nested loops in order to maximize cache locality. Automatically performing this task is difficult for compilers to do. In GCC, the
-floop-interchangecompiler flag exists but is currently not available by default. Therefore, it is a good idea for programmers to pay attention to how their code is accessing memory-composite data structures like arrays and matrices. As an example, let’s take a closer look at thematrixVectorMultiplyfunction in matrixVector.c:
现代更新(截至 2026-11)· GCC 的循环交换
按当前的 GCC 手册,-O3 会开启 -floop-interchange(手册的描述是:在 graphite 框架之外执行循环交换,可以改善循环嵌套的缓存性能,并让向量化等进一步的循环优化得以进行),-O3 同时还开启 -floop-unroll-and-jam、-ftree-loop-distribution(即本节后面讲的循环分裂)等相关的循环变换。不过,表 2 的数据说明,对本节这种由指针数组构成的「数组的数组」矩阵,编译器并没有替你把循环换过来,手动调整循环顺序依然必要。GCC 手册:Optimize Options
表 1. 对 matrixVectorMultiply() 函数进行循环交换
Table 1. Loop interchange on the matrixVectorMultiply() function.
原始版本(matrixVector.c)
Original Version (matrixVector.c)
1 | void matrixVectorMultiply(int **m, |
循环交换版本(matrixVector2.c)
Loop interchange version (matrixVector2.c)
1 | void matrixVectorMultiply(int **m, |
输入矩阵和输出矩阵是动态分配的(C 语言章节讨论的第二种方法)。因此,矩阵的各行彼此不连续,而每一行中的元素是连续的。当前的循环顺序使程序逐列而不是逐行地遍历矩阵。回想一下,数据是以块而不是元素为单位加载到缓存中的。因此,当访问 res 或 m 中某个数组的元素 x 时,与 x 相邻的元素也会被加载到缓存中。逐「列」遍历矩阵会导致更多的缓存未命中,因为每次访问都迫使缓存加载新的块。表 2 显示,加上优化选项并没有缩短这个函数的运行时间。然而,只要交换一下循环的顺序(如前面的代码示例以及 matrixVector2.c 所示),函数就能快将近八倍,并让编译器能够进行更多的优化。
The input and output matrices are dynamically allocated (second method discussed in C chapter). As a result, the rows in the matrices are not contiguous to one another, whereas the elements in every row are contiguous. The current ordering of the loops causes the program to cycle through each column instead of every row. Recall that data is loaded into cache in blocks not elements. As a result, when an element x in an array in either
resormis accessed, the elements adjacent to x are also loaded into cache. Cycling through every “column” of the matrix causes more cache misses, as the cache is forced to load new blocks with every access. Table 2 shows that adding optimization flags does not decrease the runtime of the function. However, simply switching the order of the loops (as shown in the previous code examples and in matrixVector2.c) makes the function nearly eight times faster and allows the compiler to perform additional optimizations.
表 2. 在 10,000 × 10,000 个元素上执行矩阵乘法所用的时间(秒)
Table 2. Time in Seconds to Perform Matrix Multiplication on 10,000 × 10,000 Elements
| 版本 | 程序 | 未优化 | -O1 |
-O2 |
-O3 |
|---|---|---|---|---|---|
| 原始版本 | matrixVector |
2.01 | 2.05 | 2.07 | 2.08 |
| 循环交换后 | matrixVector2 |
0.27 | 0.08 | 0.06 | 0.06 |
Version Program Unoptimized -O1-O2-O3Original matrixVector2.01 2.05 2.07 2.08 With Loop Interchange matrixVector20.27 0.08 0.06 0.06
Valgrind 的 cachegrind 工具(在第 11 章中讨论过)是识别数据局部性问题的好方法,它能揭示前面例子中 matrixVectorMultiply 函数两个版本在缓存访问上的差异。
The Valgrind tool
cachegrind(discussed in Chapter 11) is a great way to identify data locality issues, and reveals the cache access differences in the two versions of thematrixVectorMultiplyfunction shown in the previous example.
其他几种改善局部性的编译器优化:循环分裂与循环融合
12.3.2. Some Other Compiler Optimizations for Improving Locality: Fission and Fusion
在 10,000 × 10,000 个元素上重新运行改进后的程序,得到下面的运行时间:
Rerunning the improved program on 10,000 × 10,000 elements yields the following runtime numbers:
1 | $ gcc -o matrixVector2 matrixVector2.c |
现在,分配和填充矩阵所花的时间最多。进一步的计时表明,实际上最耗时的是填充矩阵。我们来仔细看看那段代码:
Now, matrix allocation and filling takes the most time. Additional timing reveals that it is the filling of the matrices that in fact takes the most time. Let’s take a closer look at that code:
1 | //fill matrices |
为了填充输入矩阵和输出矩阵,一个 for 循环遍历所有行,并对每个矩阵调用 fillArrayRandom 和 fillArrayZeros 函数。在某些情况下,编译器把单个循环拆成两个独立的循环可能会更有利(称为循环分裂,loop fission),如表 3 所示。
To fill the input and output matrices, a
forloop cycles through all the rows, and calls thefillArrayRandomandfillArrayZerosfunctions on each matrix. In some scenarios, it may be advantageous for the compiler to split the single loop into two separate loops (known as loop fission), as shown in Table 3.
表 3. 对 main 中填充矩阵的 for 循环进行循环分裂的示例
Table 3. Loop fission example on fill matrices for loop in main.
原始版本
Original Version
1 | for (i = 0; i < rows; i++) { |
循环分裂后
With loop fission
1 | for (i = 0; i < rows; i++) { |
把在同一范围上运行的两个循环的内容合并到一个循环中(即循环分裂的逆过程),称为循环融合(loop fusion)。循环分裂和循环融合都是编译器为改善数据局部性而可能执行的优化。面向多核处理器的编译器也可能利用循环分裂或融合,让循环能在多个核心上高效执行。例如,编译器可能用循环分裂把两个循环分配给不同的核心。同样,编译器可能用循环融合把相互依赖的操作合并到循环体中,再把循环迭代的一个子集分配给每个核心(假设各次迭代之间的数据是独立的)。
The process of taking two loops that operate over the same range and combining their contents into a single loop (i.e., the opposite of loop fission) is called loop fusion. Loop fission and fusion are examples of optimizations a compiler might perform to try to improve data locality. Compilers for multicore processors may also use loop fission or fusion to enable loops to execute efficiently on multiple cores. For example, a compiler may use loop fission to assign two loops to different cores. Likewise, a compiler may use loop fusion to combine together dependent operations into the body of the loop and distribute to each core a subset of the loop iterations (assuming data between iterations are independent).
在我们的例子中,手动应用循环分裂并不能直接提高程序性能;填充数组所需的时间几乎没有变化。不过,它可能会让一个更隐蔽的优化显现出来:包含 fillArrayZeros 的那个循环是不必要的。matrixVectorMultiply 函数会给 result 数组中的每个元素赋值,事先把它们全部初始化为零是多余的。
In our case, applying loop fission manually does not directly improve program performance; there is virtually no change in the amount of time required to fill the array. However, it may make clear a more subtle optimization: the loop containing
fillArrayZerosis not necessary. ThematrixVectorMultiplyfunction assigns values to each element in theresultarray; a prior initialization to all zeros is unnecessary.
表 4. 去掉对 fillArrayZeros 的多余调用
Table 4. Removing unneeded call to fillArrayZeros.
之前的版本(matrixVector2.c)
Previous version (matrixVector2.c)
1 | for (i = 0; i < rows; i++) { |
用 calloc() 更新后的版本(matrixVector3.c)
Updated version with calloc() (matrixVector3.c)
译注
标题提到了 calloc(),但下面列出的代码只是把 fillArrayZeros 那一行注释掉了;由于 matrixVectorMultiply 用 = 给每个元素赋值,结果矩阵本来就不需要预先清零。
1 | for (i = 0; i < rows; i++) { |
12.3.3. 用 Massif 进行内存剖析
12.3.3. Memory Profiling with Massif
做了上面的改动之后,运行时间只略有下降。尽管它省去了把结果矩阵所有元素填充为零的步骤,但用随机数填充输入矩阵仍需要相当多的时间:
Making the previous change results in only a slight decrease in runtime. Although it eliminates the step of filling in all elements in the result matrix with zeros, a significant amount of time is still required to fill the input matrix with random numbers:
1 | $ gcc -o matrixVector3 matrixVector3.c |
尽管各个数组在内存中并不连续存放,但每个数组都占 10,000 × sizeof(int) 字节,即 40,000 字节。由于总共分配了 20,000 个数组(初始矩阵和结果矩阵各 10,000 个),这相当于 8 亿字节,即大约 762 MB 的空间。用随机数填满 762 MB 的空间,花很多时间也就不难理解了。对于矩阵,内存使用量随输入规模呈平方增长,可能对性能产生很大影响。
Even though each array is stored noncontiguously in memory, each one takes up 10,000 ×
sizeof(int)bytes, or 40,000 bytes. Because there is a total of 20,000 (10,000 each for the initial matrix and the result matrix) arrays allocated, this corresponds to 800 million bytes, or roughly 762 MB of space. Filling 762 MB with random numbers understandably takes a lot of time. With matrices, memory use increases quadratically with the input size, and can play a large role in performance.
Valgrind 的 massif 工具可以帮助你剖析内存使用情况。与本书介绍过的其他 Valgrind 工具(memcheck、cachegrind 和 callgrind)一样,massif 作为程序可执行文件的包装器运行。具体来说,massif 在程序运行过程中给程序的内存使用拍快照,剖析内存使用量如何波动。程序员可能会发现 massif 工具很适合用来跟踪程序如何使用堆内存,以及找出改善内存使用的机会。我们在 matrixVector3 可执行文件上运行 massif 工具:
Valgrind’s
massiftool can help you profile memory use. Like the other Valgrind tools we covered in this book (memcheck, cachegrind, and callgrind),massifruns as a wrapper around a program’s executable. Specifically,massiftakes snapshots of program memory use throughout the program, and profiles how memory usage fluctuates. Programmers may find themassiftool useful for tracking how their programs use heap memory, and for identifying opportunities to improve memory use. Let’s run themassiftool on thematrixVector3executable:
1 | $ valgrind --tool=massif ./matrixVector3 10000 10000 |
运行 massif 会生成一个 massif.out.xxxx 文件,其中 xxxx 是一个唯一的 id 号。如果你在跟着输入,输入 ls 就能看到对应的 massif 文件。在下面的例子中,对应的文件是 massif.out.7030。用 ms_print 命令查看 massif 的输出:
Running
massifproduces amassif.out.xxxxfile, wherexxxxis a unique id number. If you are typing along, typelsto reveal your corresponding massif file. In the example that follows, the corresponding file ismassif.out.7030. Use thems_printcommand to view themassifoutput:
1 | $ ms_print massif.out.7030 |
输出的顶部是内存使用图。x 轴表示执行的指令数,y 轴表示内存使用量。上图表明,在我们运行 matrixVector3 的过程中,总共执行了 97.78 亿条(Gi)指令。在执行期间,massif 总共拍了 80 张快照来测量堆的使用情况。内存使用在最后一张快照(79)处达到峰值。程序的峰值内存使用为 763.3 MB,并且在整个程序运行期间保持相对稳定。
At the top of the output is the memory use graph. The x-axis shows the number of instructions executed. The y-axis shows memory use. The graph above indicates that a total of 9.778 billion (Gi) instructions executed during our run of
matrixVector3. During execution,massiftook a total of 80 snapshots to measure use on the heap. Memory use peaked in the last snapshot (79). Peak memory use for the program was 763.3 MB, and stayed relatively constant throughout the program.
图之后是所有快照的摘要。例如,下面的表对应于快照 79 附近的几张快照:
Summaries of all the snapshots occur after the graph. For example, the following table corresponds to the snapshots around snapshot 79:
1 | .... |
每一行对应一张特定的快照,内容依次是:拍摄的时间、此时堆内存的总消耗量(以字节为单位)、此时程序请求的字节数(「useful-heap」,有效堆)、超出程序请求而额外分配的字节数,以及栈的大小。默认情况下,栈剖析是关闭的(它会显著拖慢 massif)。要启用栈剖析,在运行 massif 时使用 --stacks=yes 选项。
Each row corresponds to a particular snapshot, the time it was taken, the total heap memory consumption (in bytes) at that point, the number of bytes requested by the program (“useful-heap”) at that point, the number of bytes allocated in excess of what the program asked for, and the size of the stack. By default, stack profiling is off (it slows
massifdown significantly). To enable stack profiling, use the--stacks=yesoption when runningmassif.
massif 工具揭示出,程序 99.96% 的堆内存使用发生在 allocateArray 函数中,总共分配了 8 亿字节,与我们前面粗略估算的结果一致。读者可能会发现,massif 是识别程序中高堆内存使用区域的有用工具,而高堆内存使用往往会拖慢程序。例如,当程序员频繁调用 malloc 而没有在第一个恰当的时机调用 free 时,程序中就会发生内存泄漏(memory leak)。massif 工具对检测这类泄漏非常有用。
The
massiftool reveals that 99.96% of the program’s heap memory use occurred in theallocateArrayfunction and that a total of 800 million bytes were allocated, consistent with the back-of-the-envelope calculation we performed earlier. Readers will likely findmassifa useful tool for identifying areas of high heap memory use in their programs, which often slows a program down. For example, memory leaks can occur in programs when programmers frequently callmallocwithout callingfreeat the first correct opportunity. Themassiftool is incredibly useful for detecting such leaks.