每个程序员都应该了解的内存知识-Part5

程序员可以干什么——缓存优化

注：本文使用 Kimi AI 进行翻译

6 程序员可以做什么

在前面部分的描述之后，显然程序员有很多机会影响程序的性能，无论是正面还是负面。这仅针对内存相关操作。我们将从底层开始，从物理RAM访问和L1缓存开始，一直到影响内存处理的操作系统功能。

6.1 绕过缓存

当数据被产生并没有立即被再次使用时，内存存储操作首先读取整个缓存行，然后修改缓存数据的事实对性能是不利的。这个操作会将可能很快再次需要的数据推出缓存，以便于那些不久将不会被使用的数据。这特别是对于大型数据结构，如矩阵，它们被填充后稍后使用。在矩阵的最后一个元素被填充之前，其庞大的大小就会将第一个元素挤出，使缓存写入无效。

对于这种情况，处理器提供了对非临时写操作的支持。在这里，非临时意味着数据将不会被很快重用，因此没有必要缓存它。这些非临时写操作不会读取缓存行然后修改它；相反，新内容直接写入内存。

这听起来可能很昂贵，但并不一定如此。处理器将尝试使用写入合并（见第3.3.3节）来填充整个缓存行。如果成功，则根本不需要执行内存读取操作。对于x86和x86-64架构，gcc提供了一些内建函数：

#include <emmintrin.h>
void _mm_stream_si32(int *p, int a);
void _mm_stream_si128(int *p, __m128i a);
void _mm_stream_pd(double *p, __m128d a);

#include <xmmintrin.h>
void _mm_stream_pi(__m64 *p, __m64 a);
void _mm_stream_ps(float *p, __m128 a);

#include <ammintrin.h>
void _mm_stream_sd(double *p, __m128d a);
void _mm_stream_ss(float *p, __m128 a);

这些指令最有效地用于一次性处理大量数据。数据从内存加载，在一个或多个步骤中处理，然后重新写回内存。数据“流”通过处理器，因此得名内建函数。

内存地址必须分别对齐到8或16字节。在使用多媒体扩展的代码中，可以将正常的 _mm_store_* 内建函数替换为这些非临时版本。在第9.1节中的矩阵乘法代码中，我们没有这样做，因为写入的值很快就会被重用。这是一个使用流指令并不有用的示例。关于这段代码的更多内容将在6.2.1节中讨论。

处理器的写入合并缓冲区只能暂时存储对单个缓存行的部分写入请求。通常有必要将修改单个缓存行的所有指令一个接一个地连续发出，以便写入合并实际上可以发生。下面是一个如何做到这一点的示例：

#include <emmintrin.h>
void setbytes(char *p, int c)
{
   __m128i i = _mm_set_epi8(c, c, c, c,
                            c, c, c, c,
                            c, c, c, c,
                            c, c, c, c);
   _mm_stream_si128((__m128i *)&p[0], i);
   _mm_stream_si128((__m128i *)&p[16], i);
   _mm_stream_si128((__m128i *)&p[32], i);
   _mm_stream_si128((__m128i *)&p[48], i);
}

假设指针 p 适当对齐，调用此函数将把地址的缓存行中的所有字节设置为 c。写入合并逻辑将看到四个生成的 movntdq 指令，并且只有在执行最后一个指令后才发出写入命令。总之，这个代码序列不仅避免了在写入之前读取缓存行，还避免了用可能不久后不需要的数据污染缓存。在某些情况下，这可以带来巨大的好处。使用此技术的常见代码示例是 C 运行时中的 memset 函数，对于大块，应该使用类似上述的代码序列。

一些架构提供了专门的解决方案。PowerPC 架构定义了 dcbz 指令，可以用来清除整个缓存行。该指令并不真正绕过缓存，因为为结果分配了一个缓存行，但不会从内存中读取数据。与非临时存储指令相比，它的限制更多，因为缓存行只能设置为全零，并且如果数据不是临时的，它会污染缓存，但不需要写入合并逻辑就可以实现结果。

为了看到非临时指令的实际效果，我们将看一个新的测试，用于测量写入矩阵的时间，矩阵组织为二维数组。编译器将矩阵在内存中布局，使得最左边的（第一个）索引寻址行为，所有元素在内存中顺序排列。右边的（第二个）索引寻址行中的元素。测试程序以两种方式迭代矩阵：首先在内部循环中增加列号，然后增加行索引。这意味着我们得到了图 6.1 所示的行为。

图 6.1：矩阵访问模式

我们测量初始化一个 3000×3000 矩阵所需的时间。为了了解内存的行为，我们使用不使用缓存的存储指令。在 IA-32 处理器上，使用“非临时提示”进行此操作。为了比较，我们还测量了普通的存储操作。结果可以在表 6.1 中看到。

	内部循环增量
正常	0.048s
非临时	0.048s
表 6.1：定时矩阵初始化

对于使用缓存的正常写入，我们看到预期的结果：如果内存被顺序使用，我们得到了更好的结果，整个操作大约为 0.048s，转换为大约 750MB/s，与更或多或少随机访问所需的 0.127s（大约 280MB/s）相比。矩阵足够大，以至于缓存基本上无效。

我们在这里主要感兴趣的是绕过缓存的写入。它可能令人惊讶的是，顺序访问在这里和使用缓存的情况一样快。这种行为的原因是处理器执行了如上所述的写入合并。此外，非临时写入的内存排序规则是放宽的：程序需要显式地插入内存屏障（对于 x86 和 x86-64 处理器是 sfence 指令）。这意味着处理器有更多的自由度来写回数据，从而尽可能好地使用可用的带宽。

在内部循环中按列访问的情况下，情况是不同的。结果明显比缓存访问（0.16s，大约 225MB/s）慢。在这里，我们可以看到没有写入合并的可能性，每个内存单元格都必须单独寻址。这就需要不断地选择 RAM 芯片中的新行，以及所有相关的延迟。结果是比缓存运行结果差 25%。

在读取方面，直到最近，处理器除了使用非临时访问（NTA）预取指令的弱提示外，缺乏支持。对于读取，没有与写入合并等效的操作，这对于无法缓存的内存（如内存映射 I/O）尤其不利。英特尔在 SSE4.1 扩展中引入了 NTA 加载。它们使用少量的流式加载缓冲区实现；每个缓冲区包含一个缓存行。给定缓存行的第一个 movntdqa 指令将一个缓存行加载到缓冲区中，可能会替换另一个缓存行。对同一缓存行的后续 16 字节对齐访问将以极小的代价由加载缓冲区提供服务。除非有其他原因这样做，否则缓存行不会被加载到缓存中，从而使得在不污染缓存的情况下加载大量内存成为可能。编译器为此指令提供了一个内建函数：

#include <smmintrin.h>
__m128i _mm_stream_load_si128 (__m128i *p);

这个内建函数应该多次使用，将 16 字节块的地址作为参数传递，直到每个缓存行被读取。只有在那时才应该开始下一个缓存行。由于有几个流式读取缓冲区，可能可以同时从两个内存位置读取。

我们应该从这个实验中得到的是，现代 CPU 非常好地优化了未缓存的写入和（更近期的）读取访问，只要它们是顺序的。只要它们是顺序的，这些知识可以在处理只使用一次的大型数据结构时非常有用。第二，缓存可以帮助掩盖一些——但不是全部——随机内存访问的成本。在这个例子中，由于 RAM 访问的实现，随机访问要慢 70%。在实现方式改变之前，应该尽可能避免随机访问。

在关于预取的一节中，我们将再次看到非临时标志。

6.2 缓存访问

程序员可以对缓存做出的最重要的改进是那些影响第1级缓存的。我们将首先讨论它，然后再包括其他级别。显然，对第1级缓存的所有优化也影响其他缓存。所有内存访问的主题都是一样的：提高局部性（空间和时间）并对齐代码和数据。

6.2.1 优化第1级数据缓存访问

在第3.3节中，我们已经看到了有效使用 L1d 缓存可以如何提高性能。在本节中，我们将展示哪些类型的代码更改可以帮助提高该性能。继续上一节，我们首先专注于优化顺序访问内存。正如第3.3节的数字所示，当内存被顺序访问时，处理器会自动预取数据。

使用的示例代码是矩阵乘法。我们使用两个 1000×1000 的 double 元素的正方形矩阵。对于那些忘记了数学的人来说，给定两个矩阵 A 和 B，其元素 aij 和 bij，其中 0 ≤ i,j < N，乘积是：

一个简单的 C 实现如下所示：

for (i = 0; i < N; ++i)
  for (j = 0; j < N; ++j)
    for (k = 0; k < N; ++k)
      res[i][j] += mul1[i][k] * mul2[k][j];

两个输入矩阵是 mul1 和 mul2。假定结果矩阵 res 已初始化为全零。这是一个很好且简单的实现。但是，显然我们有刚刚在图 6.1 中解释的问题。虽然 mul1 被顺序访问，但内循环提高了 mul2 的行号。这意味着 mul1 被处理得像图 6.1 中的左矩阵，而 mul2 被处理得像右矩阵。这可不好。

有一种可能的补救措施可以很容易尝试。由于矩阵中的每个元素都被多次访问，因此可能值得在之前重新排列（用数学术语来说就是“转置”）第二个矩阵 mul2。

转置后（通常用上标“T”表示），我们现在顺序迭代两个矩阵。就 C 代码而言，现在看起来像这样：

double tmp[N][N];
for (i = 0; i < N; ++i)
  for (j = 0; j < N; ++j)
    tmp[i][j] = mul2[j][i];
for (i = 0; i < N; ++i)
  for (j = 0; j < N; ++j)
    for (k = 0; k < N; ++k)
      res[i][j] += mul1[i][k] * tmp[j][k];

我们创建了一个临时变量来包含转置矩阵。这需要触摸更多的内存，但这个成本，希望，可以通过以下方式收回：每列的 1000 个非顺序访问更昂贵（至少在现代硬件上）。是时候进行一些性能测试了。在 Intel Core 2 2666MHz 时钟速度上的结果是（以时钟周期为单位）：

	原始	转置
周期	16,765,297,870	3,922,373,010
相对	100%	23.4%

通过简单的矩阵转换，我们可以实现 76.6% 的加速！复制操作是值得的。1000 个非顺序访问真的很伤。下一个问题是，这是否是我们能做的最好。我们当然需要一个不需要额外复制的替代方法。我们并不总是有奢侈去执行复制：矩阵可能太大，或者可用内存太小。

寻找替代实现的搜索应该从仔细检查原始实现所涉及的数学和执行的操作开始。简单的数学知识使我们能够看到，只要每个加数恰好出现一次，每个结果矩阵元素的加法执行的顺序是无关紧要的。{这里我们忽略了可能改变溢出、下溢或舍入发生次数的算术效应。} 这种理解使我们能够寻找重新排序原始代码内循环中执行的加法的解决方案。

现在让我们检查一下执行原始代码时 mul2 元素访问的实际问题。mul2 的元素访问顺序是：(0,0)，(1,0)，…，(N-1,0)，(0,1)，(1,1)，….。元素 (0,0) 和 (0,1) 在同一个缓存行中，但是，当内循环完成一轮时，这个缓存行早已被逐出。对于这个例子，内循环的每一轮都需要，对于这三个矩阵中的每一个，1000 个缓存行（对于 Core 2 处理器是 64 字节）。这加起来远远超过了 32k 的 L1d 可用。

但如果我们在执行内循环时同时处理中间循环的两个迭代呢？在这种情况下，我们使用缓存行中保证在 L1d 中的两个 double 值。我们将 L1d 未命中率减半。这当然是一个改进，但是，根据缓存行大小，它可能仍然不是我们能够实现的最好结果。Core 2 处理器的 L1d 缓存行大小为 64 字节。这个实际值可以使用以下代码在运行时查询：

sysconf (_SC_LEVEL1_DCACHE_LINESIZE)

或者使用命令行工具 getconf，以便程序可以为特定的缓存行大小编译。由于 sizeof(double) 是 8，这意味着要充分利用缓存行，我们应该将中间循环展开 8 次。继续这个思路，为了有效地使用 res 矩阵，即同时写入 8 个结果，我们应该也将外循环展开 8 次。我们假设这里缓存行大小为 64，但代码在系统上也有 32 字节缓存行大小时运行良好，因为两个缓存行也得到了 100% 的利用。一般来说，最好在编译时使用 getconf 实用程序硬编码缓存行大小，如：

gcc -DCLS=$(getconf LEVEL1_DCACHE_LINESIZE) ...

如果二进制文件应该通用，应该使用最大的缓存行大小。对于非常小的 L1ds，这可能意味着不是所有的数据都适合缓存，但这样的处理器不适合高性能程序。我们得到的代码看起来像这样：

#define SM (CLS / sizeof (double))

for (i = 0; i < N; i += SM)
    for (j = 0; j < N; j += SM)
        for (k = 0; k < N; k += SM)
            for (i2 = 0, rres = &res[i][j],
                     rmul1 = &mul1[i][k]; i2 < SM;
                     ++i2, rres += N, rmul1 += N)
                for (k2 = 0, rmul2 = &mul2[k][j];
                     k2 < SM; ++k2, rmul2 += N)
                    for (j2 = 0; j2 < SM; ++j2)
                        rres[j2] += rmul1[k2] * rmul2[j2];

这看起来相当可怕。在某种程度上，它之所以可怕，是因为它包含了一些技巧。最明显的变化是我们现在有六个嵌套循环。外循环以 SM（缓存行大小除以 sizeof(double)）的间隔迭代。这将乘法分成几个可以具有更多缓存局部性的小问题。内部循环遍历外循环的缺失索引。再次，有三个循环。唯一的棘手部分是 k2 和 j2 循环的顺序不同。这是因为在实际计算中，只有一个表达式依赖于 k2，但有两个依赖于 j2。

这里的其余复杂性来自于 gcc 在优化数组索引方面并不是很聪明。引入额外的变量 rres、rmul1 和 rmul2 通过尽可能地将公共表达式从内部循环中提取出来来优化代码。C 和 C++ 语言的默认别名规则并不帮助编译器做出这些决定（除非使用 restrict，所有指针访问都是潜在的别名来源）。这就是为什么 Fortran 仍然是数值编程的首选语言：它使编写快速代码更容易。{理论上，1999 年修订版中引入到 C 语言中的 restrict 关键字应该解决这个问题。编译器还没有赶上，尽管。主要原因是存在太多错误的代码，这将误导编译器并导致它生成错误的目标代码。}

我们所有的工作都得到了回报，可以在表 6.2 中看到。

	原始	转置	子矩阵	向量化
周期	16,765,297,870	3,922,373,010	2,895,041,480	1,588,711,750
相对	100%	23.4%	17.3%	9.47%

通过避免复制，我们又获得了 6.1% 的性能提升。另外，我们不需要任何额外的内存。输入矩阵可以任意大，只要结果矩阵也适合内存。这是我们现在实现的通用解决方案的要求。

表 6.2 中还有一列没有解释。大多数现代处理器现在包括对向量化的特殊支持。通常被品牌化为多媒体扩展，这些特殊指令允许同时处理 2、4、8 或更多值。这些通常是 SIMD（单指令，多数据）操作，通过其他操作获得正确形式的数据。英特尔处理器提供的 SSE2 指令可以同时处理两个 double 值。指令参考手册列出了提供这些 SSE2 指令访问的内建函数。如果使用这些内建函数，程序将比原始代码再快 7.3%（相对）。结果是程序运行时间为原始代码的 10%。换算成人们认识的数字，我们从 318 MFLOPS 提升到 3.35 GFLOPS。由于我们在这里只对内存效应感兴趣，程序代码被推到了第 9.1 节。

应该指出，在代码的最后一个版本中，我们仍然存在一些 mul2 的缓存问题；预取仍然不起作用。但这不能解决，除非转置矩阵。也许缓存预取单元会变得更聪明，以识别模式，那么不需要额外的更改。在 2.66 GHz 处理器上，单线程代码达到 3.19 GFLOPS 并不坏。

我们在矩阵乘法的示例中优化的是加载缓存行的使用。缓存行的所有字节总是被使用。我们只是确保在缓存行被清空之前使用它们。这当然是特例。

更常见的是，数据结构填满了一个或多个缓存行，程序在任何时候只使用几个成员。在图 3.11 中，我们已经看到了大型结构大小的影响，如果只使用少数成员。

图 6.2：分布在多个缓存行上

图 6.2 显示了使用现在众所周知的程序执行的另一组基准测试的结果。这次两个相同列表元素的值被添加。在一种情况下，两个元素在同一个缓存行中；在另一种情况下，一个元素在列表元素的第一个缓存行中，第二个元素在最后一个缓存行中。图表显示了我们正在经历的减速。

毫不奇怪，在所有情况下，如果工作集适合 L1d，就没有负面影响。一旦 L1d 不再足够，就会因为使用两个缓存行而不是一个而受到惩罚。红线显示了数据，当列表在内存中顺序布局时。我们看到通常的两步模式：当 L2 缓存足够时，大约有 17% 的惩罚，当必须使用主内存时，大约有 27% 的惩罚。

在随机内存访问的情况下，相对数据看起来有点不同。适合 L2 的工作集的减速在 25% 到 35% 之间。超出这个范围后，它下降到大约 10%。这不是因为惩罚变小了，而是因为实际的内存访问变得不成比例地更昂贵。数据还表明，在某些情况下，元素之间的距离很重要。随机 4 CLs 曲线显示了更高的惩罚，因为使用了第一和第四个缓存行。

使用 pahole 程序（见 [dwarves]）可以很容易地看到数据结构与缓存行的布局比较。这个程序检查二进制文件中定义的数据结构。假设一个程序包含这个定义：

struct foo {
   int a;
   long fill[7];
   int b;
};

在 64 位机器上编译，pahole 的输出包含（除其他内容外）图 6.3 所示的信息。

这个输出告诉我们很多。首先，它显示数据结构使用了一个以上的缓存行。该工具假设当前使用的处理器的缓存行大小，但这个值可以通过命令行参数覆盖。特别是在结构的大小刚好超过缓存行限制的情况下，并且分配了许多这种类型的对象，压缩该结构是有意义的。也许一些元素可以有更小的类型，或者某些字段实际上是可以用单独的位表示的标志。

在示例中，压缩很容易，程序本身就暗示了这一点。输出显示第一个元素之后有一个四字节的空洞。这个空洞是由结构和 fill 元素的对齐要求引起的。很容易看出，元素 b，大小为四个字节（由行尾的 4 表示），完全适合这个间隙。在这种情况下的结果是，间隙不再存在，数据结构适合一个缓存行。pahole 工具可以自己执行此优化。如果使用 —reorganize 参数，并将结构名称添加到命令行的末尾，工具的输出是优化后的结构和缓存行使用情况。

除了移动元素以填补空白外，该工具还可以优化位字段和组合填充和空洞。有关更多详细信息，请参见 [dwarves]。

拥有一个刚好足够容纳尾随元素的空洞当然是理想情况。要使这种优化有用，需要对象本身对齐到缓存行。我们将在下面讨论这个问题。

pahole 输出还有助于更容易地确定是否需要重新排序元素，以便一起使用的元素也一起存储。使用 pahole 工具，可以很容易地确定哪些元素在同一个缓存行中，以及何时需要重新洗牌元素以实现这一点。这不是一个自动化的过程，但该工具可以提供很大的帮助。

个体结构元素的位置和它们的使用方式也很重要。正如我们在第 3.5.2 节中看到的，具有关键字的代码的性能在缓存行后期更差。这意味着程序员应该始终遵循以下两条规则：

1. 始终将最有可能是关键字的结构元素移动到结构的开头。
2. 在访问数据结构时，如果访问顺序不是由情况决定的，则按照结构中定义的顺序访问元素。

对于小结构，这意味着程序员应该按照它们可能被访问的顺序排列元素。这必须以灵活的方式处理，以允许其他优化，如填补空白，也能适用。对于更大的数据结构，每个缓存行大小的块应该遵循规则进行排列。

如果对象本身没有对齐，那么重新排序元素是不值得花费时间的。对象的对齐由数据类型的对齐要求确定。每种基本类型都有自己的对齐要求。对于结构化类型，其元素中最大的对齐要求决定了结构的对齐。这几乎总是小于缓存行大小。这意味着即使结构的成员被排列以适应同一个缓存行，分配的对象可能没有匹配缓存行大小的对齐。

确保对象具有设计结构布局时使用的对齐的两种方法：

• 对象可以具有显式的对齐要求进行分配。对于动态分配，调用 malloc 只会分配与最苛刻的标准类型（通常是 long double）匹配的对齐的对象。可以使用 posix_memalign 来请求更高的对齐。

  #include <cstdlib.h>
  int posix_memalign(void **memptr,
                      size_t align,
                      size_t size);

  这个函数将新分配的内存的指针存储在 memptr 指向的指针变量中。内存块大小为 size 字节，并在 align 字节边界上对齐。

  对于编译器分配的对象（在 .data、.bss 等和栈上），可以使用变量属性：

  struct strtype variable
        __attribute__((aligned(64)));

  在这种情况下，无论 strtype 结构的对齐要求如何，variable 都在 64 字节边界上对齐。这对于全局变量和自动变量都有效。

  这种方法对数组不起作用，除非数组的每个元素的大小是对齐值的倍数。它也意味着必须适当注释每个单独的变量。使用 posix_memalign 也不是完全免费的，因为对齐要求通常会导致碎片化和/或更高的内存消耗。

• 类型的对齐要求可以使用类型属性更改：

  struct strtype {
     ...members...
  } __attribute__((aligned(64)));

  这将导致编译器分配所有对象的适当对齐，包括数组。程序员必须确保为动态分配的对象请求适当的对齐。这里再次使用 posix_memalign。使用 gcc 提供的 alignof 运算符并将其值作为第二个参数传递给 posix_memalign 是很容易的。

  多媒体扩展在本节中提到，几乎总是要求内存访问对齐。也就是说，对于 16 字节的内存访问，地址应该在 16 字节对齐。x86 和 x86-64 处理器有特殊变体的内存操作可以处理未对齐的访问，但这些操作较慢。这种硬对齐要求对于大多数 RISC 架构来说并不新鲜，它们要求所有内存访问完全对齐。即使架构支持未对齐的访问，这有时也比使用适当的对齐慢，特别是如果错位导致加载或存储使用两个缓存行而不是一个。

图 6.4：未对齐访问的开销

图 6.4 显示了未对齐内存访问的影响。现在众所周知的测试在访问内存时（顺序或随机）增加一个数据元素，一次使用对齐的列表元素，一次使用故意错位的元素。图表显示了程序因未对齐访问而产生的减速。顺序访问情况下的影响比随机访问情况更显著，因为在后一种情况下，未对齐访问的成本部分被通常更高的内存访问成本掩盖了。在顺序情况下，工作集大小适合 L2 缓存，减速约为 300%。这可以通过 L1 缓存的有效性降低来解释。一些增量操作现在触及两个缓存行，开始处理列表元素现在通常需要读取两个缓存行。L1 和 L2 之间的连接太拥挤了。

对于非常大的工作集大小，未对齐访问的影响仍然是 20% 到 30%——鉴于对齐访问时间已经很长了，这是很多。这张图应该表明对齐必须被认真对待。即使架构支持未对齐访问，也不能认为“它们和对齐访问一样好”。

这些对齐要求有一些副作用。如果一个自动变量有一个对齐要求，编译器必须确保在所有情况下都满足它。这不是微不足道的，因为编译器无法控制调用站点以及它们如何处理栈。这个问题可以通过两种方式处理：

1. 生成的代码积极对齐栈，必要时插入间隙。这需要代码来检查对齐，创建对齐，并稍后撤销对齐。

2. 要求所有调用者都有对齐的栈。

所有常用的应用程序二进制接口（ABIs）都遵循第二条路线。如果调用者违反了规则并且被调用者需要对齐，程序很可能会失败。保持对齐无损并不免费。

栈帧的大小在函数中使用不一定是对齐的倍数。这意味着如果从这个栈帧调用其他函数，则需要填充。编译器在大多数情况下知道栈帧的大小，因此它知道如何调整栈指针以确保任何从该栈帧调用的函数的对齐。事实上，大多数编译器会简单地将栈帧大小四舍五入并完成。

这种处理对齐的简单方法在变量长度数组（VLAs）或 alloca 使用时是不可能的。在这种情况下，栈帧的总大小只在运行时知道。可能需要主动对齐控制，使生成的代码（略微）变慢。

在某些架构上，只有多媒体扩展需要严格的对齐；这些架构上的栈对正常数据类型总是最小对齐，通常是 32 和 64 位架构的 4 或 8 字节对齐。在这些系统上，强制对齐会产生不必要的成本。这意味着，在这种情况下，我们可能想要消除严格的对齐要求，如果我们知道它永远不会依赖于它。尾部函数（不调用其他函数的函数）不需要对齐。同样，只调用不需要对齐的函数的函数也不需要对齐。如果能识别足够多的函数集，程序可能想要放宽对齐要求。对于 x86 二进制文件，gcc 支持放宽的栈对齐要求：

-mpreferred-stack-boundary=2

如果给定的选项值为 N，则栈对齐要求将设置为 2N 字节。因此，如果使用值为 2，则栈对齐要求从默认值（16 字节）降低到仅 4 字节。在大多数情况下，这意味着不需要额外的对齐操作，因为正常的栈推送和弹出操作本来就在四字节边界上工作。这个特定于机器的选项可以帮助减少代码大小，也可以提高执行速度。但它不能适用于许多其他架构。即使对于 x86-64，它通常也不适用，因为 x86-64 ABI 要求将浮点参数传递到 SSE 寄存器中，而 SSE 指令需要完整的 16 字节对齐。尽管如此，只要这个选项可用，它就可以产生显著的差异。

高效放置结构元素和对齐并不是影响缓存效率的唯一数据结构方面。如果使用结构数组，则整个结构定义都会影响性能。记住图 3.11 中的结果：在这种情况下，数组元素中的未使用数据量不断增加。结果是预取越来越无效，对于大型数据集，程序变得效率越来越低。

对于大型工作集，尽可能使用可用的缓存非常重要。为了实现这一点，可能需要重新排列数据结构。虽然将概念上属于同一组的所有数据放在同一个数据结构中对程序员来说更容易，但这可能不是获得最大性能的最佳方法。假设我们有如下数据结构：

struct order {
  double price;
  bool paid;
  const char *buyer[5];
  long buyer_id;
};

进一步假设这些记录存储在一个大数组中，并且一个经常运行的工作将所有未结账单的预期付款总额加起来。在这种情况下，buyer 和 buyer_id 字段所使用的内存被不必要地加载到缓存中。根据图 3.11 中的数据，程序的性能可能比它可能的性能差 5 倍。

将 order 数据结构分成两个会更好，将前两个字段存储在一个结构中，将其他字段存储在其他地方。这个改变当然会增加程序的复杂性，但性能提升可能证明这种成本是合理的。

最后，让我们考虑另一种缓存使用优化，虽然它也适用于其他缓存，但主要是在 L1d 访问中感受到。如在图 3.8 中所见，缓存的关联度增加对正常操作有益。缓存越大，通常关联度越高。L1d 缓存太大，不能是完全关联的，但又不够大，不能像 L2 缓存那样具有相同的关联度。如果工作集中的许多对象落入同一个缓存集，这可能是一个问题。如果由于集的过度使用导致驱逐，程序可能会经历延迟，即使缓存的大部分未使用也是如此。有时称这些缓存未命中为冲突未命中。由于 L1d 寻址使用虚拟地址，这实际上是程序员可以控制的。如果一起使用的变量也存储在一起，那么它们落入同一组的可能性就最小化了。图 6.5 显示了问题可能有多快出现。

图 6.5：缓存关联度效应

在图中，现在熟悉的 Follow {测试是在 32 位机器上执行的，因此 NPAD =15 意味着每个列表元素一个 64 字节的缓存行。} 与 NPAD =15 测试是在使用特殊设置进行测量的。X 轴是两个列表元素之间的距离，以空列表元素为单位。换句话说，距离为 2 意味着下一个元素的地址在前一个之后 128 字节。所有元素都以相同的距离在虚拟地址空间中布局。Y 轴显示列表的总长度。只使用一到 16 个元素，这意味着总工作集大小为 64 到 1024 字节。Z 轴显示遍历每个列表元素所需的平均周期数。

图中显示的结果不应令人惊讶。如果使用较少的元素，所有数据都适合 L1d，每个列表元素的访问时间仅为 3 个周期。对于列表元素的几乎所有排列：虚拟地址很好地映射到 L1d 插槽，几乎没有冲突。在这两个（在此图中）特殊的距离值中，情况是不同的。如果距离是 4096 字节（即距离 64 个元素）的倍数，并且列表的长度大于 8，则每个列表元素所需的平均周期数急剧增加。在这些情况下，所有条目都在同一组中，一旦列表长度超过关联度，条目就从 L1d 中被冲出，并且下一轮必须从 L2 中重新读取。这导致每个列表元素大约 10 个周期的成本。

有了这张图，我们可以确定使用的处理器具有 8 路关联和 32kB 总大小的 L1d 缓存。这意味着，如果必要，可以使用测试来确定这些值。相同的效应也可以在 L2 缓存上测量，但这里更复杂，因为 L2 缓存使用物理地址进行索引，而且它要大得多。

对于程序员来说，这意味着关联度是值得关注的。在现实世界中，以 2 的幂的边界布局数据的情况经常发生，但这正是可能导致上述效应和性能下降的情况。未对齐的访问可能会增加冲突未命中的概率，因为每次访问可能需要额外的缓存行。

图 6.6：AMD 上的 L1d 银行地址

如果执行此优化，则还可以执行另一个相关的优化。至少，AMD 的处理器将 L1d 实现为几个单独的银行。L1d 每个周期可以接收两个数据字，但前提是这两个字存储在不同的银行中，或者存储在具有相同索引的银行中。银行地址编码在虚拟地址的低位中，如图 6.6 所示。如果一起使用的变量也存储在一起，则它们位于不同的银行或具有相同索引的相同银行的可能性很高。

6.2.2 优化第1级指令缓存访问

为良好的 L1i 使用做准备需要类似于良好 L1d 使用的技术。然而，问题是，除非程序员编写汇编代码，否则通常不会直接影响 L1i 的使用方式。如果使用编译器，程序员可以通过指导编译器创建更好的代码布局来间接确定 L1i 的使用。

代码的优势在于它在跳转之间是线性的。在这些时期，处理器可以有效地预取内存。跳转会扰乱这个美好的画面，因为

• 跳转目标可能不是静态确定的；
• 即使它是静态的，如果它错过了所有缓存，内存获取可能需要很长时间。

这些问题会在执行中造成停顿，可能严重影响性能。这就是为什么今天的处理器在分支预测（BP）上投入了大量资源。高度专业化的 BP 单元尽可能提前确定跳转的目标，以便处理器可以开始将新位置的指令加载到缓存中。它们使用静态和动态规则，并且越来越擅长在执行中确定模式。

将数据尽快放入缓存对于指令缓存更为重要。如第 3.1 节所述，指令必须在执行之前进行解码，为了加快这个速度（在 x86 和 x86-64 上很重要），指令实际上是以解码形式缓存的，而不是从内存中读取的字节/字形式。

为了实现最佳的 L1i 使用，程序员应该至少注意以下代码生成方面的考虑：

1. 尽可能减少代码占用的内存。这必须与循环展开和内联等优化相平衡。

2. 代码执行应该是线性的，没有气泡。{气泡在图形上描述了处理器管道中执行必须等待资源时出现的空缺。有关更多详细信息，请参阅有关处理器设计的文献。}

3. 在有意义的情况下对齐代码。

我们现在将看看一些编译器技术，这些技术可用于帮助根据这些方面优化程序。

编译器有选项启用优化级别；也可以单独启用特定优化。在高优化级别（gcc 的 -O2 和 -O3）启用的许多优化都涉及循环优化和函数内联。总的来说，这些是好的优化。如果通过这些方式优化的代码占程序总执行时间的很大一部分，则整体性能可以提高。特别是内联函数允许编译器一次性优化更大的代码块，这反过来又使得生成更好地利用处理器流水线架构的机器代码成为可能。通过死代码消除或值范围传播等方式处理代码和数据，在能够将程序的更大部分视为单个单元时，工作得更好。

更大的代码大小意味着对 L1i（以及 L2 和更高级别）缓存的压力更大。这可能导致性能降低。更小的代码可以更快。幸运的是，gcc 有一个优化选项可以指定这一点。如果使用 -Os，编译器将优化代码大小。已知会增加代码大小的优化被禁用。使用此选项通常会产生令人惊讶的结果。特别是如果编译器不能真正利用循环展开和内联，这个选项是一个大胜利。

内联也可以单独控制。编译器有启发式和限制来指导内联；这些限制可以由程序员控制。-finline-limit 选项指定函数必须有多大才能被认为太大而不适合内联。如果一个函数在多个地方被调用，在所有地方内联它会导致代码大小爆炸。但还有更多。假设函数 inlcand 在两个函数 f1 和 f2 中被调用。函数 f1 和 f2 本身是顺序调用的。

内联	无内联
start f1 code f1 inlined inlcand more code f1 end f1 start f2 code f2 inlined inlcand more code f2 end f2	start inlcand code inlcand end inlcand start f1 code f1 end f1 start f2 code f2 end f2

表 6.3 显示了没有内联和在两个函数中都内联时生成的代码可能是什么样子。如果函数 inlcand 在 f1 和 f2 中都内联，生成的代码的总大小是：

size f1 + size f2 + 2 × size inlcand

如果没有发生内联，总大小就小了 size inlcand。这是 f1 和 f2 紧随其后被调用时需要的 L1i 和 L2 缓存的大小。另外：如果 inlcand 没有被内联，代码可能仍然在 L1i 中，并且不需要再次解码。另外：分支预测单元可能因为已经看过代码而做出更好的跳跃预测。如果编译器默认的内联函数大小上限对程序不是最好的，它应该被降低。

然而，有些情况下，内联总是有意义的。如果一个函数只被调用一次，它最好被内联。这给了编译器执行更多优化的机会（比如值范围传播，这可能显著改善代码）。内联可能因选择限制而受到挫败。gcc 对于这种情况有一个选项，总是内联一个函数。添加 always_inline 函数属性指示编译器做正如其名的事情。

在同样的情况下，如果一个函数不应该被内联，尽管它足够小，noinline 函数属性可以被使用。即使对于小函数，如果它们经常从不同的地方被调用，使用这个属性也是有意义的。如果 L1i 内容可以被重用，并且整体占用空间减少，这通常可以弥补额外的函数调用成本。分支预测单元现在非常好。如果内联可以导致更积极的优化，情况就不同了。这必须根据具体情况决定。

always_inline 属性在内联代码总是被使用时效果很好。但如果这不是情况呢？如果内联函数只偶尔被调用：

void fct(void) {
  ... code block A ...
  if (condition)
    inlfct()
  ... code block C ...
}

通常，这样的代码序列生成的代码与源代码的结构相匹配。这意味着首先是代码块 A，然后是一个条件跳转，如果条件评估为 false，则跳过它。接下来是内联的 inlfct 生成的代码，最后是代码块 C。这看起来都是合理的，但它有一个问题。

如果 condition 经常为 false，执行就不是线性的。中间有一块大块未使用的代码，它不仅因为预取而污染了 L1i，还可能引起分支预测问题。如果分支预测错误，条件表达式可能会非常低效。

这是一般问题，不是特定于内联函数。无论何时使用条件执行，并且它是不平衡的（即，表达式远比另一个结果更频繁地导致一个结果），都可能存在错误的静态分支预测和因此管道中的气泡的风险。这可以通过告诉编译器将执行频率较低的代码移出主代码路径来防止。在这种情况下，if 语句生成的条件分支将跳转到一个顺序之外的地方，如下所示。

上面的部分表示简单的代码布局。如果区域 B（例如，上面内联的函数 inlfct）经常不被执行，因为条件 I 跳过了它，处理器的预取将拉入包含块 B 的缓存行，这些缓存行很少被使用。使用块重排序，这可以改变，结果可以在下图的下半部分看到。经常执行的代码在内存中是线性的，而很少执行的代码被移动到不会影响预取和 L1i 效率的地方。

gcc 提供了两种方法来实现这一点。首先，编译器可以在重新编译代码时考虑分析输出，并根据配置布局代码块。我们将在第 7 节中看到这是如何工作的。第二种方法是通过显式分支预测。gcc 识别 __builtin_expect：

long __builtin_expect(long EXP, long C);

这个构造告诉编译器表达式 EXP 最有可能具有值 C。返回值是 EXP。__builtin_expect 旨在在条件表达式中使用。在几乎所有情况下，它将用于布尔表达式的上下文中，在这种情况下，定义两个辅助宏更方便：

#define unlikely(expr) __builtin_expect(!!(expr), 0)
#define likely(expr) __builtin_expect(!!(expr), 1)

然后，这些宏可以像这样使用：

if (likely(a > 1))

如果程序员使用这些宏，然后使用 -freorder-blocks 优化选项，gcc 将像上图所示重排序块。这个选项在 -O2 下启用，但在 -Os 下禁用。还有另一个选项来重排序块（-freorder-blocks-and-partition），但它的用途有限，因为它不能与异常处理一起使用。

小循环的另一个巨大优势，至少在某些处理器上是这样。Intel Core 2 前端有一个称为循环流检测器（LSD）的特殊功能。如果循环不超过 18 条指令（其中没有一条是对子程序的调用），只需要最多 4 次解码器获取 16 字节，最多有 4 条分支指令，并且执行次数超过 64 次，那么循环有时会被锁定在指令队列中，因此当循环再次使用时更快可用。这适用于通过外循环多次进入的小内部循环。

即使没有这样的专用硬件，紧凑的循环也有优势。内联不是关于 L1i 的唯一优化方面。另一个方面是对齐，就像数据一样。有明显差异：代码主要是线性的，不能在地址空间中任意放置，它不能由程序员直接通过编译器生成的代码来影响。有一些程序员可以控制的方面。

对齐每个单独的指令没有任何意义。目标是使指令流顺序。因此，只有在战略位置上对齐才有意义。为了决定在哪里添加对齐，需要了解对齐的优势。在缓存行的开头有一个指令意味着该缓存行的预取最大化了。对于指令，这也意味着解码器更有效。很容易看出，如果执行到缓存行末尾的指令，处理器必须准备好读取一个新的缓存行并解码指令。可能会出现问题（例如缓存行未命中），这意味着缓存行末尾的指令平均而言不如在开头的指令有效。

结合以下推论，如果控制刚刚转移到指令上（因此预取不有效），我们得出结论，代码对齐最有用的地点：

• 在函数的开头；
• 在仅通过跳转到达的基本块的开头；
• 在某种程度上，在循环的开头。

在前两种情况下，对齐几乎没有成本。执行在新位置继续，如果我们选择在缓存行的开头，我们优化了预取和解码。{对于指令解码处理器，通常使用比缓存行更小的单元，x86 和 x86-64 的情况下是 16 字节。} 编译器通过插入一系列无操作指令来填充对齐创建的间隙来实现这种对齐。这个“死代码”占用了一点空间，但通常不会影响性能。

第三种情况略有不同：对齐每个循环的开头可能会造成性能问题。问题是循环的开头通常紧跟着其他代码顺序执行。如果情况不是很幸运，上一条指令和对齐的循环开始之间将有一个间隙。与前两种情况不同，这个间隙不能完全是死的。执行完上一条指令后，循环中的第一个指令必须执行。这意味着，在执行完上一条指令后，必须执行一系列无操作指令来填补间隙，或者必须有一个无条件跳转到循环开始的指令。两种可能性都不是免费的。特别是如果循环本身执行得不频繁，无操作指令或跳转可能比通过对齐节省的成本更多。

程序员可以通过以下三种方式影响代码的对齐。显然，如果代码是用汇编器编写的，可以显式地对函数和其中的所有指令进行对齐。汇编器为所有架构提供了 .align 伪操作来执行此操作。对于高级语言，编译器必须了解对齐要求。与数据类型和变量不同，这在源代码中不可能。相反，使用编译器选项：

-falign-functions=N

这个选项指示编译器将所有函数对齐到大于 N 的下一个幂次方二的边界。这意味着最多会创建 N 字节的间隙。对于小函数，使用大的 N 值是浪费。同样对于只执行很少的代码。后者可能在库中经常发生，这些库可能包含受欢迎和不受欢迎的接口。选择选项值的明智选择可以加速事情或通过避免对齐来节省内存。通过将 N 的值设置为 1 或使用 -fno-align-functions 选项，可以关闭所有对齐。

第二种情况——仅通过跳转到达的基本块的开头——可以通过不同的选项控制：

-falign-jumps=N

所有其他细节都是等效的，同样的内存浪费警告适用。

第三种情况也有自己的选项：

-falign-loops=N

同样，同样的细节和警告适用。除了这里，正如之前解释的，对齐在运行时有成本，因为如果顺序到达对齐地址，必须执行无操作指令或跳转指令。

gcc 知道另一个控制对齐的选项，这里只提一下以供完整性。-falign-labels 对代码中每个单独的标签（基本上是每个基本块的开头）进行对齐。这在几乎所有情况下都会减慢代码速度，因此不应该使用。

6.2.3 优化第2级和更高级别缓存访问

对于第1级缓存使用所说的一切都适用于第2级和更高级别的缓存访问。还有两个额外的方面适用于最后一级缓存：

• 缓存未命中总是非常昂贵的。虽然 L1 未命中（希望如此）经常命中 L2 和更高级别的缓存，从而限制了惩罚，但显然没有回退到最后一级缓存。
• L2 缓存和更高的缓存通常由多个核心和/或超线程共享。因此，每个执行单元可用的有效缓存大小通常小于总缓存大小。

为了避免高昂的缓存未命中成本，工作集大小应该与缓存大小相匹配。如果数据只需要一次，这显然没有必要，因为缓存无论如何都是无效的。我们谈论的是数据集需要多次的工作负载。在这种情况下，使用一个太大而不适合放入缓存的工作集将创建大量的缓存未命中，即使预取成功执行，也会减慢程序速度。

程序必须执行其工作，即使数据集太大。这是程序员的工作，以最小化缓存未命中的方式完成工作。对于最后一级缓存，这是可能的——就像对 L1 缓存一样——通过在更小的部分上处理工作。这非常类似于表 6.2 中优化的矩阵乘法。一个区别是，对于最后一级缓存，要处理的数据块可以更大。如果 L1 优化也需要，代码变得更加复杂。想象一下矩阵乘法，其中数据集——两个输入矩阵和输出矩阵——不适合最后一级缓存一起。在这种情况下，可能适当的同时优化 L1 和最后一级缓存访问。

L1 缓存行大小在许多处理器代中通常是恒定的；即使不是，差异也将很小。假设更大的大小没有问题。在处理器上具有较小缓存大小的情况下，将使用两个或更多缓存行而不是一个。在任何情况下，为它硬编码缓存行大小并优化代码是合理的。

对于更高级别的缓存，如果程序应该是通用的，这不是这样。这些缓存的大小可以有很大的差异。八倍或更多的因素并不罕见。不可能将更大的缓存大小作为默认值，因为这将意味着代码在所有机器上的性能都很差，除了那些拥有最大缓存的机器。相反的选择也不好：假设最小的缓存意味着扔掉 87% 或更多的缓存。这是不好的；正如我们从图 3.14 看到的，使用大缓存可以对程序的速度产生巨大影响。

这意味着代码必须根据缓存行大小动态调整自己。这是特定于程序的优化。我们在这里只能说，程序员应该正确计算程序的要求。不仅需要数据集本身，更高级别的缓存也用于其他目的；例如，所有执行的指令都从缓存中加载。如果使用库函数，这种缓存使用可能会增加相当大的数量。这些库函数也可能需要它们自己的数据，进一步减少了可用的内存。

一旦我们有了内存需求的公式，我们就可以将其与缓存大小进行比较。如前所述，缓存可能与多个其他核心共享。目前 {肯定很快就会有更好的方法！} 获取正确信息的唯一方法，而不是硬编码知识，是通过 /sys 文件系统。在表 5.2 中，我们已经看到了内核对硬件发布的信息。程序必须找到目录：

/sys/devices/system/cpu/cpu*/cache

对于最后一级缓存。这可以通过该目录中 level 文件中最高的数值来识别。当目录被识别时，程序应该读取该目录中 size 文件的内容，并将数值除以文件 shared_cpu_map 中位掩码中设置的位数。

这样计算出的值是一个安全的下限。有时程序对其他线程或进程的行为了解更多。如果这些线程被安排在共享缓存的核心或超线程上，并且已知缓存使用不会耗尽其总缓存大小的一部分，则计算出的极限可能太低而无法最优。是否应该使用超过公平份额的缓存真的取决于情况。程序员必须做出选择，或者必须允许用户做出决定。

6.2.4 优化 TLB 使用

TLB 使用的优化有两种。第一种优化是减少程序必须使用的页面数量。这自然会导致更少的 TLB 未命中。第二种优化是通过减少必须分配的更高级别目录表的数量，使 TLB 查找更便宜。更少的表意味着更少的内存使用，这可能导致目录查找的缓存命中率更高。

第一种优化与最小化页面错误密切相关。我们将在第 7.5 节中详细涵盖该主题。虽然页面错误通常是一次性成本，但 TLB 未命中是持续的惩罚，因为 TLB 缓存通常很小，并且经常刷新。页面错误比 TLB 未命中昂贵得多，但是，如果程序运行时间足够长，并且某些程序部分频繁执行，TLB 未命中甚至可能超过页面错误成本。因此，重要的是从页面错误和 TLB 未命中的角度考虑页面优化。不同之处在于，虽然页面错误优化只需要将代码和数据分组到一页宽，但 TLB 优化要求在任何时候尽可能少地使用 TLB 条目。

第二种 TLB 优化更难控制。必须使用的页面目录的数量取决于进程的虚拟地址空间中使用的地址范围的分布。在地址空间中广泛变化的位置意味着更多的目录。一个复杂的问题是，地址空间布局随机化（ASLR）导致正是这些情况。为了防止机器的攻击者猜测函数或变量的地址，堆栈、DSO、堆和可能的可执行文件的加载地址在运行时随机化。

为了获得最大性能，ASLR 肯定应该被关闭。额外目录的成本足够低，以至于在几乎所有情况下都不需要这样做。内核可以随时执行的一种优化是确保单个映射不会跨越两个目录之间的地址空间边界。这将以最小的方式限制 ASLR，但不足以显著削弱它。

程序员直接受此影响的唯一方式是当显式请求地址空间区域时。这发生在使用 mmap 与 MAP_FIXED 时。以这种方式分配新的地址空间区域非常危险，几乎从不这样做。然而，这是可能的，如果使用它，程序员应该知道最后一级页面目录的边界，并适当选择请求的地址。

6.3 预取

预取的目的是隐藏内存访问的延迟。今天处理器的命令流水线和乱序执行（OOO）能力可以隐藏一些延迟，但充其量只能对缓存命中的访问隐藏延迟。要覆盖主内存访问的延迟，命令队列必须非常长。一些没有 OOO 的处理器试图通过增加核心数量来补偿，但这是一种糟糕的权衡，除非所有使用的代码都被并行化了。

预取可以进一步帮助隐藏延迟。处理器根据某些事件（硬件预取）或程序（软件预取）的显式请求执行预取。

6.3.1 硬件预取

硬件预取的触发器通常是两个或更多缓存未命中的特定模式。这些缓存未命中可以是对连续或前面的缓存行。在旧的实现中，只有对相邻缓存行的缓存未命中才被识别。在现代硬件中，步幅也被识别，这意味着跳过固定数量的缓存行被识别为一种模式，并得到适当的处理。

如果每个单独的缓存未命中都触发硬件预取，对性能来说是很糟糕的。例如，对全局变量的随机内存访问非常普遍，由此产生的预取大多会浪费 FSB 带宽。这就是为什么，要启动预取，至少需要两个缓存未命中。处理器今天都期望有超过一个的内存访问流。处理器尝试自动为每个缓存未命中分配这样的流，如果达到阈值，则开始硬件预取。当今的 CPU 可以跟踪八到十六个独立的流，用于更高级别的缓存。

负责模式识别的单元与相应的缓存相关联。可能有 L1d 和 L1i 缓存的预取单元。对于 L2 缓存和更高级别的缓存，很可能也有预取单元。L2 和更高级别的预取单元与使用相同缓存的所有其他核心和超线程共享。因此，八到十六个独立流的数量很快就会减少。

预取有一个大弱点：它不能跨越页面边界。原因应该是显而易见的，当一个人意识到 CPU 支持按需分页时。如果预取器被允许跨越页面边界，访问可能会触发操作系统事件以使页面可用。这本身就可能是糟糕的，特别是对于性能。更糟糕的是，预取器不了解程序或操作系统本身的语义。它因此可能会预取页面，这些页面在现实生活中永远不会被请求。这意味着预取器可能会在处理器以可识别的模式访问的内存区域之前，运行得更远。这不仅是可能的，而且是非常可能的。如果处理器作为预取的副作用触发了对这样一页的请求，操作系统甚至可能完全偏离其轨道，因为这样的请求在其他情况下永远不会发生。

因此，重要的是要意识到，无论预取器在预测模式方面有多好，程序将在页面边界处经历缓存未命中，除非它显式地预取或从新页面读取。这是另一个原因，要优化数据的布局，以最小化缓存污染，通过保持不相关数据的分离。

由于这个页面限制，处理器没有非常复杂的逻辑来识别预取模式。考虑到仍然普遍的 4k 页面大小，有意义的范围有限。在其中识别步幅的地址范围多年来已经增加，但今天超过通常使用的 512 字节窗口可能没有太多意义。当前的预取单元不识别非线性访问模式。更有可能的是，这样的模式确实是随机的，或者至少是足够非重复的，以至于尝试识别它们是没有意义的。

如果硬件预取意外被触发，可以做的事情只有那么多。一种可能性是尝试检测这个问题并稍微更改数据和/或代码布局。这可能会很困难。可能有一些特殊的本地解决方案，比如在 x86 和 x86-64 处理器上使用 ud2 指令 { _或非指令。这是推荐的未定义操作码。} 这个指令本身不能执行，它在间接跳转指令后使用；它用作指令获取器的信号，处理器不应该浪费努力解码以下内存，因为执行将在不同位置继续。这是一个非常特殊的情况。在大多数情况下，我们不得不接受这个问题。

可以完全或部分禁用整个处理器的硬件预取。在 Intel 处理器上，使用模型特定寄存器（MSR）进行此操作（IA32_MISC_ENABLE，许多处理器上的位 9；位 19 仅禁用相邻缓存行预取）。这在大多数情况下必须在内核中发生，因为它是一个特权操作。如果分析显示在系统上运行的重要应用程序由于硬件预取而遭受带宽耗尽和过早缓存逐出，使用这个 MSR 是可能的。

6.3.2 软件预取

硬件预取的优势在于程序不需要调整。缺点，正如刚刚描述的那样，是访问模式必须是平凡的，预取不能在页面边界之外发生。由于这些原因，我们现在有更多的可能性，其中软件预取是最重要的。软件预取确实需要修改源代码，通过插入特殊指令。一些编译器支持 pragma 来或多或少地自动插入这些特殊指令。

在 x86 和 x86-64 上，Intel 的编译器内建函数约定通常用于插入这些特殊指令：

#include <xmmintrin.h>
enum _mm_hint {
   _MM_HINT_T0 = 3,
   _MM_HINT_T1 = 2,
   _MM_HINT_T2 = 1,
   _MM_HINT_NTA = 0
};
void _mm_prefetch(void *p,
                  enum _mm_hint h);

程序可以使用 _mm_prefetch 内建函数对程序中的任何指针进行操作。大多数处理器（包括所有 x86 和 x86-64 处理器）会忽略由于无效指针导致的错误，这使得程序员的生活大大简化。如果传递的指针引用了有效的内存，那么预取单元将被指令加载数据到缓存中，并在必要时逐出其他数据。不必要的预取应该绝对避免，因为这可能会降低缓存的有效性，并消耗内存带宽（可能在逐出的缓存行是脏的情况下是两个缓存行）。

与 _mm_prefetch 内建函数一起使用的不同的提示是实现定义的。这意味着每个处理器版本都可以略有不同地实现它们。通常可以说的是 _MM_HINT_T0 将数据获取到所有级别的缓存中，对于包容性缓存，以及对于排他性缓存到最低级别的缓存。如果数据项在更高级别的缓存中，它将被加载到 L1d 中。_MM_HINT_T1 提示将数据拉入 L2 而不是 L1d。如果有 L3 缓存，_MM_HINT_T2 提示可以对它做类似的事情。这些是细节，虽然弱指定，需要为实际使用的处理器进行验证。一般来说，如果数据将立即使用，使用 _MM_HINT_T0 是正确的选择。当然，这需要 L1d 缓存大小足以容纳所有预取的数据。如果立即使用的工作集大小太大，将所有内容预取到 L1d 是一个坏主意，应该使用其他两个提示。

第四个提示 _MM_HINT_NTA 是特殊的，因为它允许告诉处理器特别对待预取的缓存行。NTA 代表非临时对齐，我们在第 6.1 节中已经解释过了。程序告诉处理器应尽可能避免使用此数据污染缓存，因为数据只短时间使用。因此，处理器在加载时可以避免将数据读入较低级别的缓存，对于包容性缓存实现。当数据从 L1d 逐出时，数据不需要推入 L2 或更高，而是可以直接写入内存。处理器设计者可能部署其他技巧，如果给出了这个提示。程序员在使用这个提示时必须小心：如果即时工作集大小太大并强制逐出带有 NTA 提示加载的缓存行，将从内存重新加载。

图 6.7：平均值与预取，NPAD=31

图 6.7 显示了使用现在熟悉的指针追逐框架的测试结果。列表是随机的。与以前的测试不同的是，程序实际上在每个列表节点上花费了一些时间（大约 160 个周期）。正如我们从图 3.15 中的数据中学到的，一旦工作集大小大于最后一级缓存，程序的性能就会严重受损。

我们现在可以通过在计算之前发出预取请求来尝试改善这种情况。也就是说，在循环的每一轮中，我们预取一个新的元素。预取的节点在列表中与当前正在处理的节点之间的距离必须仔细选择。鉴于每个节点在 160 个周期内被处理，并且我们必须预取两个缓存行（NPAD =31），五个列表元素的距离就足够了。

图 6.7 的结果表明，预取确实有帮助。只要工作集大小不超过最后一级缓存的大小（机器有 512kB = 2^19B 的 L2），数字就是相同的。预取指令没有增加可测量的额外负担。一旦超过 L2 大小，预取节省了 50 到 60 个周期，高达 8%。预取不能隐藏所有的惩罚，但它确实有所帮助。

AMD 在其 Opteron 系列的 10h 家族中实现了另一个指令：prefetchw。这个指令到目前为止在 Intel 方面没有等效的指令，也不通过内建函数提供。prefetchw 指令像其他预取指令一样将缓存行预取到 L1，但不同之处在于缓存行立即被置于 ‘M’ 状态。如果后面没有写入到缓存行，这将是一个劣势。如果有一到多个写入，它们将被加速，因为写入不需要改变缓存状态——在缓存行被预取时已经发生了。预取可以带来比我们在这里实现的微不足道的 8% 更大的优势。但正确执行预取是出了名的困难，特别是如果同一个二进制文件应该在各种机器上表现良好。

CPU 提供的性能计数器可以帮助程序员分析预取。可以计数和采样的事件包括硬件预取、软件预取、有用的软件预取、各级缓存未命中等。在第 7.1 节中，我们将介绍这些事件中的一些。所有这些计数器都是特定于机器的。

在分析程序时，应该首先查看缓存未命中。当找到大量缓存未命中的源头时，应该尝试为有问题的内存访问添加预取指令。这应该一次在一个地方完成。每次修改的结果应该通过观察测量有用预取指令的性能计数器来检查。如果这些计数器没有增加，预取可能是错误的，它没有足够的时间从内存中加载，或者预取逐出了仍然需要的缓存中的内存。

gcc 现在能够在一种情况下自动发出预取指令。如果循环正在迭代数组，可以使用以下选项：

-fprefetch-loop-arrays

编译器将弄清楚是否进行预取有意义，如果有意义，应该提前多远。对于小数组，这可能是不利的，如果数组的大小在编译时未知，结果可能更糟。gcc 手册警告说，好处高度依赖于代码的形式，而且在某些情况下，代码实际上可能运行得更慢。程序员必须谨慎使用这个选项。

6.3.3 预取的特殊类型：推测

处理器的乱序执行能力允许在不相互冲突的情况下移动指令。例如（这次使用 IA-64 作为示例）：

st8        [r4] = 12
add        r5 = r6, r7;;
st8        [r18] = r5

这段代码将值 12 存储在由寄存器 r4 指定的地址，将寄存器 r6 和 r7 的内容相加并存储在寄存器 r5 中。最后，它将总和存储在由寄存器 r18 指定的地址。这里的关键是 add 指令可以在前面的 st8 指令之前或同时执行，因为它们之间没有数据依赖性。但如果其中一个加数需要加载呢？

st8        [r4] = 12
ld8        r6 = [r8];;
add        r5 = r6, r7;;
st8        [r18] = r5

额外的 ld8 指令从由寄存器 r8 指定的地址加载值。显然，这个加载指令和后面的 add 指令之间存在数据依赖性（这就是为什么在指令后面有 ;; 的原因，感谢询问）。关键是新的 ld8 指令——与 add 指令不同——不能在前面的 st8 之前移动。处理器在指令解码期间不能足够快地确定存储和加载是否冲突，即 r4 和 r8 是否可能有相同的值。如果它们有相同的值，st8 指令将决定加载到 r6 中的值。更糟糕的是，ld8 也可能由于缓存未命中而带来大量的延迟。

IA-64 架构支持这种情况的推测性加载：

ld8.a      r6 = [r8];;
[... other instructions ...]
st8        [r4] = 12
ld8.c.clr  r6 = [r8];;
add        r5 = r6, r7;;
st8        [r18] = r5

新的 ld8.a 和 ld8.c.clr 指令属于一起，它们替换了前面代码序列中的 ld8 指令。ld8.a 指令是推测性加载。它的值不能直接使用，但处理器可以开始工作。当到达 ld8.c.clr 指令时，内容可能已经被加载了（给定有足够的指令在间隙中）。这个指令的参数必须与 ld8.a 指令的参数匹配。如果前面的 st8 指令没有覆盖该值（即 r4 和 r8 是相同的），则什么都不需要做。推测性加载完成了它的工作，加载的延迟被隐藏了。如果存储和加载冲突，ld8.c.clr 重新从内存中加载值，我们最终得到了正常 ld8 指令的语义。

推测性加载还没有（或许？）被广泛使用。但正如示例所示，它是一种非常简单但有效的方法来隐藏延迟。预取基本上是等效的，对于寄存器较少的处理器，推测性加载可能没有太多意义。推测性加载有（有时很大）的优势，它将值直接加载到寄存器中，而不是加载到缓存行中，在那里它可能再次被逐出（例如，当线程被取消调度时）。如果可用，应该使用推测。

6.3.4 助手线程

当尝试使用软件预取时，人们经常遇到代码复杂性的问题。如果代码必须迭代数据结构（我们的情况下是列表），则必须在同一个循环中实现两个独立的迭代：正常迭代执行工作和第二个迭代，它向前看，以使用预取。这很容易变得足够复杂，以至于可能会犯错误。

此外，还需要确定向前看多远。太少，内存将无法及时加载。太远，刚刚加载的数据可能再次被逐出。另一个问题是，尽管预取指令不阻塞并等待内存加载，但它们需要时间。指令必须被解码，如果解码器太忙，这可能是值得注意的，例如，由于编写得很好/生成的代码。最后，循环的代码大小增加了。这降低了 L1i 效率。如果尝试通过连续发出多个预取请求（因为第二个加载不依赖于第一个结果）来避免这部分成本，就会遇到未完成的预取请求数量的问题。

另一种方法是完全独立地执行正常操作和预取。这可以通过两个普通线程完成。显然，必须安排这些线程，以便预取线程正在填充由两个线程访问的缓存。有两种特殊的解决方案值得一提：

• 使用同一核心上的超线程（见图 3.22）。在这种情况下，预取可以进入 L2（甚至 L1d）。

• 使用比 SMT 线程“更笨”的线程，它们除了预取和其他简单操作外什么也不做。这是处理器制造商可能探索的一个选项。

使用超线程的方法特别有趣。正如我们在图 3.22 中看到的，如果超线程执行独立代码，缓存的共享是一个问题。如果一个线程被用作预取助手线程，这不是问题。相反，这是期望的效果，因为最低级别的缓存被预加载。此外，由于预取线程大部分时间处于空闲或等待内存状态，如果另一个超线程不必访问主内存，它的正常操作就不会受到太多干扰。后者正是预取助手线程防止的。

唯一的棘手部分是确保助手线程不要运行得太远。它不能完全污染缓存，以至于最旧的预取值再次被逐出。在 Linux 上，可以使用 futex 系统调用来轻松进行同步，或者使用稍微高一些的成本，使用 POSIX 线程同步原语。

图 6.8：平均值与助手线程，NPAD=31

这种方法的好处可以在图 6.8 中看到。这是与图 6.7 相同的测试，只是添加了额外的结果。新测试创建了一个额外的助手线程，该线程提前约 100 个列表项，并读取（不仅仅是预取）每个列表元素的所有缓存行。在这种情况下，我们每个列表元素有两个缓存行（在 32 位机器上，NPAD =31，缓存行大小为 64 字节）。

两个线程被安排在同一个核心的两个超线程上。测试机器只有一个核心，但如果有多个核心，结果应该大致相同。我们将在第 6.4.3 节中介绍的亲缘函数，用于将线程绑定到适当的超线程。NUMA_cpu_level_mask 接口从 libNUMA 可以用来确定操作系统知道是超线程的两个（或更多）处理器。

#include <libNUMA.h>
ssize_t NUMA_cpu_level_mask(size_t destsize,
                             cpu_set_t *dest,
                             size_t srcsize,
                             const cpu_set_t*src,
                             unsigned int level);

这个接口可以用来确定 CPU 通过缓存和内存连接的层次结构。这里感兴趣的是级别 1，它对应于超线程。要将两个线程安排在两个超线程上，可以使用 libNUMA 函数（错误处理为了简洁起见省略）：

cpu_set_t self;
NUMA_cpu_self_current_mask(sizeof(self),
                           &self);
cpu_set_t hts;
NUMA_cpu_level_mask(sizeof(hts), &hts,
                    sizeof(self), &self, 1);
CPU_XOR(&hts, &hts, &self);

执行此代码后，我们有两个 CPU 位集。self 可以用来设置当前线程的亲缘性，hts 中的掩码可以用来设置助手线程的亲缘性。这应该在创建线程之前理想地发生。我们将在第 6.4.3 节中介绍设置亲缘性的接口。如果没有超线程可用，NUMA_cpu_level_mask 函数将返回 1。这可以用作避免这种优化的信号。

这个基准测试的结果可能会令人惊讶（或者也许不会）。如果工作集适合 L2，则助手线程的开销将性能降低 10% 到 60%（再次忽略最小的工作集大小，噪音太高）。这是可以预期的，因为如果所有数据已经在 L2 缓存中，预取助手线程只使用系统资源而没有对执行做出贡献。

一旦 L2 大小耗尽，情况就改变了。预取助手线程有助于将运行时间减少约 25%。我们仍然看到一个上升的曲线，只是因为预取不能足够快地处理。主线程执行的算术运算和助手线程的内存加载操作相互补充，资源冲突最小，这导致了这种协同效应。

这些测试的结果应该可以转移到许多其他情况。由于缓存污染，超线程通常不太有用，但在这些情况下它们表现出色，应该被利用。sys 文件系统允许程序找到线程兄弟（见表 5.3 中的 thread_siblings 列）。一旦这些信息可用，程序只需定义线程的亲缘性，然后以两种模式运行循环：正常操作和预取。助手线程预取的内存量应该取决于共享缓存的大小。在这个例子中，L2 的大小是相关的，程序可以使用以下方式查询其大小：

sysconf(_SC_LEVEL2_CACHE_SIZE)

助手线程的进度是否必须受到限制取决于程序。通常最好确保有一些同步，因为调度细节否则可能导致显着的性能下降。

6.3.5 直接缓存访问

现代操作系统中的缓存未命中的一个来源是传入数据流量的处理。现代硬件，如网络接口卡（NIC）和磁盘控制器，具有将接收到的或读取的数据直接写入内存而无需涉及 CPU 的能力。这对于我们今天拥有的设备的性能至关重要，但也带来了问题。假设一个来自网络的传入数据包：操作系统必须通过查看数据包的头部来决定如何处理它。NIC 将数据包放入内存，然后通知处理器数据包的到来。处理器没有机会预取数据，因为它不知道数据何时到达，甚至可能不知道确切的存储位置。结果是在读取头部时发生缓存未命中。

英特尔在其芯片组和 CPU 中增加了技术来缓解这个问题 [directcacheaccess]。这个想法是用将被通知有关传入数据包的 CPU 的缓存填充数据包的数据。数据包的有效载荷在这里并不重要，这些数据通常由更高级别的函数处理，无论是在内核还是在用户级别。数据包的头部用于决定必须如何处理数据包，因此这些数据立即需要。

网络 I/O 硬件已经有 DMA 来写数据包。这意味着它直接与内存控制器通信，内存控制器可能集成在北桥中。内存控制器的另一侧是通过 FSB 与处理器的接口（假设内存控制器没有集成到 CPU 本身中）。

直接缓存访问（DCA）的背后思想是扩展 NIC 和内存控制器之间的协议。在图 6.9 中，第一个图显示了在具有南北桥的常规机器中开始 DMA 传输。

图 6.9：直接缓存访问

NIC 连接到（或是由）南桥。它启动 DMA 访问，但提供了有关应推入处理器缓存的数据包头部的新信息。

传统行为将是，在第二步中，简单地完成与内存的 DMA 传输。对于设置了 DCA 标志的 DMA 传输，北桥还会向 FSB 发送数据，并带有一个新的特殊 DCA 标志。处理器总是窥探 FSB，如果它识别出 DCA 标志，它就会尝试将定向到处理器的数据加载到最低级别的缓存中。实际上，DCA 标志是一个提示；处理器可以自由地忽略它。DMA 传输完成后，处理器被信号。

操作系统在处理数据包时，首先必须确定它是什么类型的数据包。如果 DCA 提示没有被忽略，操作系统必须执行的加载很可能击中缓存。将这个节省的数百个周期每个数据包乘以每秒可以处理的数万个数据包，节省的数量加起来就是非常显著的数字，特别是当涉及到延迟时。

没有集成 I/O 硬件（在这个例子中是 NIC）、芯片组和 CPU，这样的优化是不可能的。因此，如果需要这项技术，有必要明智地选择平台。

参考资料

• 原文