第 124 / 187 篇

11.5. 缓存分析与 Valgrind

说明

本文是个人学习用的非官方中英对照译文,原文:https://diveintosystems.org/book/C11-MemHierarchy/cachegrind.html。
原书采用 CC BY-NC-ND 4.0 许可(禁止演绎),请勿公开传播本译文。
标为「译注」「现代更新」的内容是译者补充,不代表原书作者观点;代码与原文逐字一致,未作改动。

11.5. Cache Analysis and Valgrind

由于缓存对程序性能有显著的影响,大多数系统都提供了测量程序缓存使用情况的剖析工具。Valgrind 的 cachegrind 模式就是这样一种工具,本节用它来评估缓存性能。

Because caches significantly influence program performance, most systems provide profiling tools to measure a program’s use of the cache. One such tool is Valgrind’s cachegrind mode, which this section uses to evaluate cache performance.

译注

Valgrind 不能在 Apple Silicon Mac 上运行(见第 3 章的现代更新)。要跟做本节,可以在 ARM64 或 x86-64 的 Linux 虚拟机、容器里安装 Valgrind。

考虑下面这个生成随机 N×N 矩阵的程序:

Consider the following program that generates a random N×N matrix:

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
44
45
46
47
48
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>

int **genRandomMatrix(int n, int max) {
int i, j;
int **mat = malloc(n * sizeof(int *));

for (i = 0; i < n; i++) {
mat[i] = malloc(n * sizeof(int));

for (j = 0; j < n; j++) {
mat[i][j] = 1 + rand() % max;
}
}

return mat;
}

void free_all(int **mat, int n) {
int i;

for (i = 0; i < n; i++) {
free(mat[i]);
}

free(mat);
}

int main(int argc, char **argv) {
int i, n;
int **matrix;

if (argc != 2) {
fprintf(stderr, "usage: %s <n>\n", argv[0]);
fprintf(stderr, "where <n> is the dimension of the matrix\n");
return 1;
}

n = strtol(argv[1], NULL, 10);
srand(time(NULL));

matrix = genRandomMatrix(n, 100);

free_all(matrix, n);
return 0;
}

本章前面几节介绍了两个求矩阵所有元素平均值的函数。它们的唯一区别是对矩阵的下标方式:

Prior sections in this chapter introduced two functions for averaging every element of a matrix. They differ only in the way they index into the matrix:

1
2
3
4
5
6
7
8
9
10
11
12
float averageMat_v1(int **mat, int n) {
int i, j, total = 0;

for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
// Note indexing: [i][j]
total += mat[i][j];
}
}

return (float) total / (n * n);
}
1
2
3
4
5
6
7
8
9
10
11
12
float averageMat_v2(int **mat, int n) {
int i, j, total = 0;

for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
// Note indexing: [j][i]
total += mat[j][i];
}
}

return (float) total / (n * n);
}

本节使用缓存剖析工具来量化它们之间的差异。

This section uses cache profiling tools to quantify the differences between them.

11.5.1. 初步分析:理论分析与基准测试

11.5.1. A First Cut: Theoretical Analysis and Benchmarking

基于局部性和存储器层次结构的理论分析表明,由于 mat 在内存中按行优先顺序存放,第一个版本(对矩阵 mat)表现出更好的空间局部性。第二种解法的空间局部性很差,因为矩阵中的每个元素是按列优先顺序被访问的。回想一下,数据是以块为单位加载到缓存中的。按列优先顺序遍历矩阵很可能导致更多的缓存未命中,从而性能更差。

A theoretical analysis based on locality and the memory hierarchy suggests that the first version exhibits better spatial locality (on matrix mat) due to the fact that mat is stored in row-major order in memory. The second solution has poor spatial locality because each element in the matrix is visited in column-major order. Recall that data is loaded into a cache in blocks. Traversing the matrix in column-major order will likely lead to more cache misses, resulting in poorer performance.

我们修改 main 函数,加入对 gettimeofday 函数的调用,以准确测量两个版本之间的性能差异:

Let’s modify the main function to include calls to the gettimeofday function to accurately measure the difference in performance between the two versions:

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
int main(int argc, char** argv) {
/* Validate command line parameters. */
if (argc != 2) {
fprintf(stderr, "usage: %s <n>\n", argv[0]);
fprintf(stderr, "where <n> is the dimension of the matrix\n");
return 1;
}

/* Declare and initialize variables. */
int i;
float res;
double timer;
int n = strtol(argv[1], NULL, 10);
srand(time(NULL));
struct timeval tstart, tend;
int ** matrix = genRandomMatrix(n, 100);

/* Time version 1. */
gettimeofday(&tstart, NULL);
res = averageMat_v1(matrix, n);
gettimeofday(&tend, NULL);
timer = tend.tv_sec - tstart.tv_sec + (tend.tv_usec - tstart.tv_usec)/1.e6;
printf("v1 average is: %.2f; time is %g\n", res, timer);

/* Time version 2. */
gettimeofday(&tstart, NULL);
res = averageMat_v2(matrix, n);
gettimeofday(&tend, NULL);
timer = tend.tv_sec - tstart.tv_sec + (tend.tv_usec - tstart.tv_usec)/1.e6;
printf("v2 average is: %.2f; time is %g\n", res, timer);

/* Clean up. */
free_all(matrix, n);
return 0;
}

编译并运行这段代码,得到下面的结果(注意,时间会因运行的机器而异):

Compiling the code and running it yields the following result (note that times will vary based on the on which machine it’s run):

1
2
3
4
$ gcc -o cachex cachex.c
$ ./cachex 5000
v1 average is: 50.49; time is 0.053641
v2 average is: 50.49; time is 0.247644

差别真大!基本上,使用行优先顺序的解法比第二种快 4.61 倍!

That’s a big difference! In essence, the solution using row-major order is 4.61 times faster than the second one!

11.5.2. 现实中的缓存分析:Cachegrind

11.5.2. Cache Analysis in the Real World: Cachegrind

对两种解法先做理论分析、再实际运行,验证了第一个版本比第二个快。然而,这并没有证实缓存分析的细节。幸运的是,Valgrind 工具套件可以帮上忙。在本书前面,我们讨论过 Valgrind 如何帮助查找程序中的内存泄漏。本节介绍 Valgrind 的缓存模拟器 Cachegrind。Cachegrind 让程序员能够研究程序或某个特定函数对缓存的影响。

Theoretically analyzing the two solutions and then running them verifies that the first version is faster than the second. However, it doesn’t confirm the details of the cache analysis. Fortunately, the Valgrind suite of tools can help. Earlier in the book, we discussed how Valgrind can help find memory leaks in a program. This section describes Cachegrind, Valgrind’s cache simulator. Cachegrind enables a programmer to study how a program or particular function affects the cache.

Cachegrind 模拟程序与计算机缓存层次结构之间的交互。在很多情况下,Cachegrind 能自动检测机器的缓存组织结构。在无法检测的情况下,Cachegrind 仍然会模拟第一级(L1)缓存和最后一级(LL)缓存。它假定第一级缓存有两个独立的部分:指令缓存和数据缓存。这样做的原因是,最后一级缓存对运行时间的影响最为重要。L1 缓存的相联度也最低,所以确保程序与它良好地交互很重要。这些假设符合大多数现代机器的结构。

Cachegrind simulates how a program interacts with the computer’s cache hierarchy. In many cases, Cachegrind can autodetect the cache organization of a machine. In the cases that it cannot, Cachegrind still simulates the first level (L1) cache and the last level (LL) cache. It assumes the first level cache has two independent components: the instruction cache and the data cache. The reason for this is that the last level cache has the most important implications for runtime. L1 caches also have the lowest level of associativity, so it’s important to ensure that programs interact well with it. These assumptions match the structure of most modern machines.

Cachegrind 收集并输出以下信息:

Cachegrind collects and outputs the following information:

  • 指令缓存读(Ir)
  • Instruction cache reads (Ir)
  • L1 指令缓存读未命中(I1mr)和 LL 缓存指令读未命中(ILmr)
  • L1 instruction cache read misses (I1mr) and LL cache instruction read misses (ILmr)
  • 数据缓存读(Dr)
  • Data cache reads (Dr)
  • D1 缓存读未命中(D1mr)和 LL 缓存数据读未命中(DLmr)
  • D1 cache read misses (D1mr) and LL cache data misses (DLmr)
  • 数据缓存写(Dw)
  • Data cache writes (Dw)
  • D1 缓存写未命中(D1mw)和 LL 缓存数据写未命中(DLmw)
  • D1 cache write misses (D1mw) and LL cache data write misses (DLmw)

注意,D1 的总访问数由 D1 = D1mr + D1mw 计算,LL 的总访问数由 ILmr + DLmr + DLmw 给出。

Note that D1 total access is computed by D1 = D1mr + D1mw and LL total access is given by ILmr + DLmr + DLmw.

译注

这两个公式算出的其实是未命中总数,而不是访问总数。对照下面的输出:D1 misses: 1,192,118 正好等于 1,129,099 rd + 63,019 wr;LL misses: 65,452 正好等于 1,053 + 1,543 + 62,856(即 ILmr + DLmr + DLmw)。

我们来看看第 1 个版本的代码在 Cachegrind 下的表现如何。要运行它,用下面的命令在编译好的代码上执行 Valgrind:

Let’s see how well version 1 of the code operates under Cachegrind. To run it, execute Valgrind on the compiled code with the following command:

1
$ valgrind --tool=cachegrind --cache-sim=yes ./cachex 1000

现代更新(截至 2026-11)· Cachegrind 默认不再模拟缓存

从 Valgrind 3.21.0(2023 年 4 月) 起,Cachegrind 的 --cache-sim=no 成为默认值:Valgrind 的发布说明解释说,这套缓存模拟已经很老,不太可能与任何真实的现代机器相符,因此默认只收集 Ir(执行的指令数)这一项最有用的事件。所以本节命令里显式写的 --cache-sim=yes 在新版本中是必需的,省略它就看不到 D1mr、DLmr 等未命中数据。同一版本中,cg_annotate、cg_diff 和 cg_merge 也用 Python 重写了。Valgrind NEWS(3.21.0 部分)

在这次调用中,Valgrind 的 cachegrind 工具充当 cachex 可执行文件的包装器。为 Cachegrind 选择较小的矩阵规模有助于加快执行速度。Cachegrind 输出关于整个程序缓存命中和未命中次数的信息:

In this invocation, Valgrind’s cachegrind tool acts as a wrapper around the cachex executable. Choosing a smaller matrix size for Cachegrind aids in the speed of execution. Cachegrind outputs information about the number of cache hits and misses in the overall program:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
==28657== Cachegrind, a cache and branch-prediction profiler
==28657== Copyright (C) 2002-2017, and GNU GPL'd by Nicholas Nethercote et al.
==28657== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==28657== Command: ./cachex 1000
==28657==
--28657-- warning: L3 cache found, using its data for the LL simulation.
average is: 50.49; time is 0.080304
average is: 50.49; time is 0.09733
==28657==
==28657== I refs: 122,626,329
==28657== I1 misses: 1,070
==28657== LLi misses: 1,053
==28657== I1 miss rate: 0.00%
==28657== LLi miss rate: 0.00%
==28657==
==28657== D refs: 75,292,076 (56,205,598 rd + 19,086,478 wr)
==28657== D1 misses: 1,192,118 ( 1,129,099 rd + 63,019 wr)
==28657== LLd misses: 64,399 ( 1,543 rd + 62,856 wr)
==28657== D1 miss rate: 1.6% ( 2.0% + 0.3% )
==28657== LLd miss rate: 0.1% ( 0.0% + 0.3% )
==28657==
==28657== LL refs: 1,193,188 ( 1,130,169 rd + 63,019 wr)
==28657== LL misses: 65,452 ( 2,596 rd + 62,856 wr)
==28657== LL miss rate: 0.0% ( 0.0% + 0.3% )

然而,本次分析特别关心的是两个求平均值函数各自的命中和未命中情况。要查看这些信息,使用 Cachegrind 的工具 cg_annotate。运行 Cachegrind 之后,当前工作目录下应该会生成一个类似 cachegrind.out.n 的文件,其中 n 是某个进程 ID 号。要运行 cg_annotate,输入下面的命令(把 cachegrind.out.28657 替换为你的输出文件名):

However, this analysis is interested specifically in the hits and misses for the two versions of this averaging function. To view that information, use the Cachegrind tool cg_annotate. Running Cachegrind should have produced a file in the current working directory that looks similar to cachegrind.out.n, where n is some process ID number. To run cg_annotate, type in the following command (replacing cachegrind.out.28657 with the name of the output file):

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
$ cg_annotate cachegrind.out.28657

I1 cache: 32768 B, 64 B, 8-way associative
D1 cache: 32768 B, 64 B, 8-way associative
LL cache: 8388608 B, 64 B, 16-way associative
Command: ./cachex 1000
Data file: cachegrind.out.28657
Events recorded: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Events shown: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Thresholds: 0.1 100 100 100 100 100 100 100 100
Include dirs:
User annotated:
Auto-annotation: off

----------------------------------------------------------------------------
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
----------------------------------------------------------------------------
122,626,329 1,070 1,053 56,205,598 1,129,099 1,543 19,086,478 63,019 62,856 PROGRAM TOTALS

----------------------------------------------------------------------------
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw file:function
----------------------------------------------------------------------------
14,009,017 3 3 9,005,008 62,688 0 1,004 0 0 averageMat_v1
14,009,017 0 0 9,005,008 1,062,996 0 1,004 0 0 averageMat_v2

我们对这条命令的输出做了少许编辑,以便集中关注求平均值函数的两个版本。输出显示,版本 2 产生了 1,062,996 次数据未命中,而版本 1 只有 62,688 次。Cachegrind 有力地证明了我们的分析是正确的!

We’ve edited the output from this command slightly to focus on the two versions of the average function. This output shows that version 2 yields 1,062,996 data misses, compared to only 62,688 misses in version 1. Cachegrind provides solid proof that our analysis is correct!