Tip

本文翻译自Ulrich Drepper所著《What Every Programmer Should Know About Memory》1的第六章，也是其文中最核心的一章，如有疏漏还请留言斧正。

✳本文较长，约25, 000余词，但耐心看下去你必将能收获非常多底层优化相关的原理性知识。

  通过前面几节的描述可知，程序员有相当多的机会可以影响程序的性能，无论是正面的亦或是负面的。本文只关注内存相关操作，我们将从自下而上的阐述那些会影响内存处理的时机，从最底层的物理内存访问，到L1缓存，再到操作系统相关功能。

1. 缓存绕过

   当数据被产出后并不会立即被消费，而实际上却需要先读一个完整的缓存行进缓存再修改缓存数据，这有损性能。这个操作会将那些本可能即将被用到的数据赶出缓存，而用那些不会被立即用到的数据取而代之。这对于一些大型数据结构而言尤其如此，比如说矩阵，一般是先填充而后再使用。在矩阵的最后一个元素被填充前，其庞大的体积会驱逐（缓存中）的那些先前的元素，这会让缓存写变得低效。

对于这类问题，处理器提供了称为非时域2写操作的支持。非时域写操作在当前语境下意味着数据将不会被很快用到，所以没有理由缓存它们。这类非时域写操作不会先读一个缓存行再写进缓存，取而代之的是，新内容将会直接被写入内存。

这可能听起来有点代价高昂但也并不一定非得如此。处理器会尝试使用写合并（译注：参见第三章3.3.3节）的方式来填充整个缓存行，如果这个合并操作成功，它将能消除任何读取内存的需要。对于x86和x86_64架构gcc提供如下内置函数：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#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);

这些内置指令用于一次性处理大量数据时最为高效。从内存中加载数据，经过一步或多步的处理，然后写回内存。这些数据“流过”处理器，所以这也为什么称之为内置函数（intrinsics）。

根据指令版本不同，内存也地址必须相应的8或者16字节对齐。那些使用多媒体指令集中_mm_store_* 系列内置函数的代码，亦能替换成这些非时域版本的内置函数。在矩阵乘法的代码（译注：参见附录代码6.1）中我们没有使用它因为写入的值很快便会被再次用到。这是一个流指令集没用的一个示例，详见2.1节。

处理器的写合并缓冲区仅能暂存部分针对缓存行的写请求，它通常需要一并发出能修改一个缓存行的所有指令以让写合并真的生效，示例如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

#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已正确对齐，调用这个函数将会把p指向的内存区设置为c。通过生成4个movntdq指令组成实现写合并逻辑，且仅当最后一条指令执行后才会触发写合并。总的来说，这段代码不仅能避免在写操作之前读缓存行，也能避免缓存被那些可能不会立马用到的数据污染。在某些情况下这能获得巨大的收益。举例而言，针对大区块使用常见的C运行时函数memset就会用到类似上面的代码片段。

某些架构提供了特殊解决方案。PowerPC架构定义了一条dcbz指令用于清理整条缓存行。由于目标缓存行是为结果而存在的，所以这条指令并不会真的绕过缓存，但它不会从从内存中读取数据。相比于非时域存储指令这条指令更为受限，因为它只能清零缓存行，且会污染缓存（在数据是非时域的情况下），但是同样也不需要写组合来达成目标。

我们将使用一个 新的测试来观察非时域指令的实际表现，这个测试将会测量针对二维数组组成的矩阵的写操作。编译器会将矩阵在内存进行布局，使得最左侧的（二维数组的第一个）索引用于寻址内存中连续的一行，右侧的（二维数组的第二个）索引用于索引行内的每个元素。测试程序有两种方法遍历矩阵，其一是在内层循环中递增列索引，其二是在内层循环中递增行索引，所以我们便有如图6.2所示的行为（译者注：注意分别看i和j的位置，i意味着外层循环，j意味着内层循环）：

图6.1 矩阵访问模式

我们会测量初始化一个3000 x 3000矩阵所需时间。为了观察内存行为，我们使用了不适用缓存的存储指令。在IA-32处理器可以使用“非时域提示”。作为对比，我们也会测量使用常规储存操作的情况。结果参见表6.1：

内循环行递增 内循环列递增
普通 0.048s 0.127s
非时域 0.048s 0.160s

表6.1 矩阵初始化耗时

对于使用缓存的普通写而言，我们得到了预期的结果：如果线性访问内存会得到好得多的结果，全部操作耗时0.048s约合750MB/s，相对而言随机访问的版本耗时0.127s（约合280MB/s）。矩阵已经大到足以让缓存变得根本性的低效。

这里我们主要感兴趣的还是绕缓存写操作。 在线性访问内存的情况下它和使用缓存一样快，这点可能令人惊讶。其原因正是我们前面所述的写合并。另外，对于非时域写操作而言内存序规则被放宽：程序需要显式插入内存屏障（对于x86和x86_64处理来说是sfence指令）。这就意味着处理器有更大的自由来回写内存从而尽可能的利用有效内存带宽。

对于那个在内循环中基于列的访问模式则情况有所不同。不使用缓存的访问明显慢于使用缓存访问的情况（0.16s，约225MB/s）。我们可以发现此时没法使用写合并，每个内存单元都必须单独寻址。这也持续要求内存芯片选择新行，并带来相应的延迟。结果就是比使用缓存的版本差25%。

对于读取而言，直到最近处理器都还缺乏除了基于非时域访问预取（Non-temporal access NTA）指令的弱提示外的其他支持。对读取来说现还没有等价于写合并的东西，这对于诸如内存映射I/O这类没法缓存的内存来说尤为糟糕。Intel在SSE4.1扩展指令集中引入了NTA载入。它们基于少量的流式加载缓冲区实现，每个缓冲区内含一个缓存行。对于给定缓冲行，第一条movntdqa指令会将它加载到缓冲区里，可能会替换其他缓存行。后续针对那个缓冲行进行16字节对齐的访问将会变得廉价。除非存在其他原因，那个缓存行将不会被装载进缓存中，如此便能做到加载大量数据而不污染缓存。编译器为此提供了一个内置函数：

1
2

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

这个内置函数理应被以16字节为一组的进行多次传参调用，直到一个缓存行被读完。此时才应该开始读下一缓存行。由于存在多个流式缓冲区，所以同时读两个内存位置也是可能的。

我们从这个实验中能得到的是，针对线性内存访问，现代CPU对非缓存写，以及近来（译注：指2007年）对非缓存读，都优化得相当好。这个信息在进行一次性大数据结构处理时非常有帮助。其次，缓存可以帮助隐藏部分随机内存访问（所造成的延迟）。由于内存访问的实现方式，此例中随机访问慢了70%。所以直到其实现方式发生改变，那么在此之前都应该尽量避免产生随机访问。

2. 缓存访问

  希望提升程序性能的程序员会发现最好专注于能影响L1缓存的的改动，因为这样能产出最好的结果。在扩展到其他层级缓存之前，我们将先讨论L1缓存。显而易见的是，所有针对L1缓存的优化也同样会对其他层级有效。所有针对内存访问的主题都无外乎：提升时间和空间的局部性，以及对齐代码和数据。

2.1. 优化L1数据缓存的访问

  在第3.2节中我们已经见识过了L1数据缓存能多大程度的提升性能。本节中我们将展示何种代码改动能帮助性能提升。紧接上节，我们先专注于优化数据的线性访问。正如3.3节中看到的数据那样，当线性访问内存时处理器会自动预取数据。

我们使用矩阵乘法作为示例代码。我们使用1000 x 1000，使用double元素的方块矩阵（下简称方阵）。对于那些已经把线性代数还给老师的同学，给定两个矩阵A和B，其元素分别为aij和bij，且 0 <= i,j <= N，其积为：

$$ (AB)_{ij} = \sum_{k=0}^{N-1} a_{ik} b_{kj} = a_{i1} b_{1j} + a_{i2} b_{2j} + \cdots + a_{i(N-1)} b_{(N-1)j} $$

一个简单的C实现如下：

1
2
3
4

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假定已初始化为全0。这是一个又好又简单的实现。但是它显然同样也存在我们在图6.1中所展示的问题。虽然mul1是线性访问的，然而内循环递增的是mul2的行索引。这就意味着mul1是像图6.1中的左图那样处理，而mul2则是右图。这显然不太好。

有一个补救措施可以一试。由于矩阵中的每个元素都会被多次访问，所以也许值得在使用mul2矩阵前重组它（转置，数学意义上）。

$$ (AB)_{ij} = \sum_{k=0}^{N-1} a_{ik} b_{jk}^{T} = a_{i1} b_{j1}^{T} + a_{i2} b_{j2}^{T} + \cdots + a_{i(N-1)} b_{j(N-1)}^{T} $$

转置后（一般表示为"T"上标）我们便能同时线性遍历两个矩阵。就C代码而言现如下：

1
2
3
4
5
6
7
8

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次非线性访问真的影响很大。

接下来的问题是这是否我们的最优解了。毫无疑问我们需要一个不需要额外内存的替代方案。我们不会每次都有进行如此拷贝的奢侈机会：矩阵可能太大或者可用内存太少。

调查替代实现应该从仔细检视原视实现的相关数学和操作开始。通过基础数学知识可知，结果矩阵的每个元素其相加顺序并不重要，只要其加数确切的只使用了一次3。这个认识能让我们去寻找能重排原始代码中内层循环相加顺序的解决方案。

现在让我们审视下原视代码执行中真正面临的问题。mul2矩阵中的元素是：(0,0), (1,0), …, (N-1,0), (0,1), (1,1), . . . . 如此访问的。元素(0,0)和(0,1)在同一缓存行中，但是当内层循环完成一轮循环时，这个缓存行早就被驱逐出去。对于此例而言，每轮内层循环这三个矩阵各需要1000条缓存行（Intel Core 2处理器每缓存行64字节）。其总和远超只有32k的L1数据缓存所能提供的空间。

但是如果我们在执行内循环时一起处理中间循环的两个迭代会怎么样？这种情况下我们使用两个肯定位于L1数据缓存的double值。如此我们便能将L1数据缓存的未命中率减半。这肯定是一种提升，但是，考虑到缓存行大小，这可能依旧不是最好的方法。Core 2处理器的L1缓冲区每行有64字节。实际值可以通过通过运行时使用如下查询：

1

sysconf (_SC_LEVEL1_DCACHE_LINESIZE)

或者在编译器命令行中使用getconf实用程序以在编译时获得确切的缓存行大小。考虑到sizeof(double)为8字节，意味着在完全利用缓存行的情况下，我们应该能展开8次中间循环。继续顺着这个思路下去，为了也尽可能利用res矩阵让它同时也能写8个值，我们也应该展开8次外层循环。我们此处假设缓存行大小为64字节，但代码也应该能很好的工作，因为两种情况下缓冲行都能被100%利用起来。一般情况最好是在编译期通过getconf实用程序硬编码缓存行大小：

1

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

如果程序是为了通用，应该使用最大的缓存行大小值。使用非常小的L1数据缓存（L1ds）可能意味着并非所有数据都能装入缓存中。然而，这种处理器本来也不适合高性能程序。最后的代码看起来如下所示：

1
2
3
4
5
6
7
8
9

#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];

某种程度上这代码看起来有点吓人，但只是因为它用了一些奇淫技巧。最显而易见的改变就是现在用了6层循环，外层循环的步长变成了SM（缓存行大小除以sizeof(double)），这将能把乘法分解成更具缓存局部性的多个小问题。内存循环迭代了外层循环缺失的部分索引，所以也有3层。唯一取巧的部分就是k2和j2循环的顺序不同，这是因为在实际计算中，只有一个表达式依赖k2，但有两个依赖j2。

其他的部分复杂性来自gcc对数组索引的优化并不好。故此引入了几个额外的变量rres，rmul1，rmul2来指向内存循环共用一些表达式，以优化代码。C/C++的默认别名规则无法帮助编译器做出优化决定（除非使用restrict关键字，否则所有指针访问都是潜在的别名来源）。这就是为什么Fortran在数值编程中依然广受欢迎：它让写高效的代码变得更容易。 4

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

表6.2 矩阵乘法耗时

所有这些工作所获得的回报可见于表6.2。通过避免数据拷贝我们又额外获得了6.1%的性能提升，而且还不用额外的内存空间。如此我们满足了一个通用解决方案的硬性要求，即只要内存能容纳得下结果矩阵，那输入矩阵可以任意的大。

表6.2中还有一列没有讲到。现代处理器如今基本都支持向量化，这些通常被称为多媒体扩展的特化指令，允许同时处理2，4，8或更多个的值。这些通常是SIMD（单指令、多数据）操作，并通过其他操作来将数据转换为正确的格式。Intel提供的SSE2指令集可以同时处理两个double值。指令集参考手册中列举了用于使用SSE2指令集的内置函数。如果使用这些指令集，将会得到额外的7.3%（相比于原始版本）的提升。最后结果是仅需要原视版本的10%的时钟周期。换算成人们熟悉的数值，我们从318 MFLOPS提升到了3.35 GFLOPS。由于我们这里只关心内存相关影响，最终程序代码便放到后面了（译注：参见附录代码6.1）。

需要注意的是，最后一个版本的代码中我们mul2依然有些缓存问题；预取依然没法工作。但是这个问题没法在不转置矩阵的情况下解决。也许以后缓存预取会变得更加智能以识别这个模式，在此之前无需做进一步改动。而且在2.66 GHz的处理器上用单线程实现了3.19 GFLOPS的吞吐其实也不差了。

我们在矩阵乘法示例中所做的优化是利用起已加载的缓存行。我们确保缓存行在被驱逐前，其中的所有数据都会被用到。这肯定是一种特例。

更常见的情况是数据结构填充了一个或多个缓存行，但任意时刻程序只用到了其中部分字段。在图3.11（译注：参见第三章的内容）中我们已经见识过只有少量字段被使用的大数据结构体所造成的影响。

图6.2展示了使用一个大家熟知的程序得到的另一组性能测试数据。这次是相加两个相同列表中的元素。第一种情况是，两个元素均在同一个缓存行中；另一种情况则是，第一个元素在第一个缓存行第二个在下一个缓存行。图标显示了相应的降速。

图6.2 扩散到多缓存行

毫无意外的，所有情况下如果工作集能放进L1数据缓存则不会产生负面影响。一旦L1数据缓存不够用，相比于只使用一个缓存行，使用两个将会付出代价。红线表示数据在内存中线性排列的情况。我们能看到两个爬升规律：当L2不够时大约17%的代价以及当主存不够用时27%的代价。

在随机内存访问的情况中起相关数据则有点不同。当工作集能放进L2缓存时有25%到35%的降速。在此之上则会有大约10%的降速。这不是说代价变小了，而是实际内存访问变得不成比例的更昂贵。数据显示，在某些情况下，元素之间的距离确实会有影响。Random 4 CLs曲线显示由于使用第1和第4缓存行，其会付出更高的代价。

要查看数据结构相对于缓存行的布局，一种简单的方法来是使用 pahole 程序 5。此程序检查二进制文件中定义的数据结构。以包含此定义的程序为例：

1
2
3
4
5

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

得到：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

struct foo {
  int      a; 										/*0    	4 */
  
  /* XXX 4 bytes hole, try to pack */
  
  long int fill[7];									/*8		56 */
  
  /* --- cacheline 1 boundary (64 bytes) --- */
  int      b;										/*64	4 */
};  /* size: 72, cachelines: 2 */
    /* sum members: 64, holes: 1, sum holes: 4 */
    /* padding: 4 */
    /* last cacheline: 8 bytes */

图6.3 pahole执行输出

当在64位机器进行编译时，pahole的输出如图6.3所示。这个输出能告诉我们很多信息，首先，它显示这个数据结构使用了不止一个缓存行。这个工具会假定使用当前处理器的缓存行大小，但也可以通过命令行参数重载这个设置。尤其是当一个数据结构的大小恰好些微超过缓存行大小，而这种类型的对象又会被大量分配时，就应该考虑压缩数据结构。比如有些元素可以用更小的类型，又或者某些字段其实可以一并使用flags的比特位表示。

对于本示例中的情况，其可以很容易的进行压缩，pahole工具也给了相应提示。其输出显示第一个字段后面跟着一个4字节间隙。这个间隙一般是由结构体的字节对齐要求和fill字段共同导致的。很容易便可发现有4字节大小的b字段恰好可以完美填充那个间隙。结果不仅是能消除那个间隙，还能让整个数据结构恰好能放进一个缓存行。这个工具本身就可以进行这种优化。使用--reorganize参数而且添加结构体名到命令行末，其输出将会是优化后的结构体以及其用到的缓存行。除了移动字段来填充间隙，这个工具还能优化比特位，组合填充和间隙，详情参见附录5。

当然，理想情况下是（数据结构中）恰好有一个能放下其后续元素的间隙。要使这种优化起效则要求对象（大小）对齐到缓存行。我们稍后会提到。

pahole工具的输出也能很容易让我们看到是否需要重排字段，让那些需要一起使用字段也储存在一起。这个工具还能看到哪些字段在同一个缓存行上，以及何时应该打乱字段来实现这一点。这个过程不是自动化的，但是工具能帮不少忙。

结构体中每个字段的位置和其被使用的方式都很重要。正如我们在3.5.2节中所看到的那样，缓存行中的Critical Word（译注：翻译成关键字容易混淆，详见3.5.2节）迟到时代码性能更差。这意味着程序应该总是遵守如下两个原则：

  1. 总是将最有可能被用到的字段移动到结构体前面去。
  2. 当访问数据结构时，如果字段的访问顺序不受情况所限，应按照其结构体中定义的顺序进行访问。

对于小型结构体来说意味着应该按照可能的访问顺序排列其字段。处理方法应该足够灵活，以便其他优化也能进行，比如说间隙填充。对于更大的结构体来说，每个缓存行大小区块内的字段应当按照上述原则进行安排。

然而如果一个对象本就希望不对齐，那么重排其字段只是在白费力气。一个对象的对齐取决于其数据类型的对齐要求，每个基础数据类型都有其相应的对齐要求。对于结构化类型，对齐取决于其所有的字段元素中最大的对齐要求。这个值几乎总是会小于缓存行大小。这就意味着即便一个结构体的成员可以整齐的放进同一个缓存行，但是实际分配的对象也有可能不和缓存行大小对齐。有两种方法可以确保对象如其结构体布局设计的一样对齐：

  • 通过显式的对齐要求来分配对象。对于使用malloc的动态分配将会分配一个对齐到最常见请求类型的对象（通常是long double）。然而也可以通过posix_memalign来请求更大的对齐。

    1
2

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

    这个函数会储存新分配的内存指针到变量memptr中。size指示内存块大小并会被对齐到align字节。

    对于由编译器分配的对象（位于.data节，.bss节，以及栈上）可以使用一个变量属性：

    1

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

    此处variable将使用64字节对齐而无关乎类型strtype的对齐要求。这对全局变量和原子变量同样有效。

    对于数组这个而言这个方法可能不想预期那般工作。除非数组中的所有元素都是对齐值的倍数，否则将只有第一个元素会被对齐。这也意味着每个变量都必须要有相应的注解。使用posix_memalign并非完全没有代价，因为对齐可能会导致内存碎片化和（或）更多的内存消耗。

  • 使用类型属性来改变用户自定义类型的对齐要求

    1
2
3

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

    这将指示编译器使用相应的对齐值来分配所有对象，包括数组。虽然还是需要程序员来处理动态对象分配时所请求的对应对齐值。此时需要再次用到posix_memalign。可以非常简单的通过gcc提供的alignof操作符来把其值作为第二个参数传给posix_memalign。

本节前面所提到的多媒体扩展几乎总是要求内存访问时对齐，也就是说，针对某个地址的进行16字节的内存访问，其地址应也是16字节对其的。x86和x86-64处理器也有处理非对齐访问特殊内存操作，但是更慢。对于RISC架构而言硬性对齐要求并不新鲜，它要求所有的内存访问均完全对齐。即便一个架构支持非对齐的访问，有时也慢于使用适当对齐的版本，尤其是当不对齐导致加载和储存使用2个缓存行而非1个。

图6.4 非对齐访问的开销

图6.4展示了非对齐内存访问造成的影响。这个现在大家熟知的测试，测量访问内存（线性或随机）并增加数据元素值的开销，一次使用对齐的队列元素，一次使用故意没对齐的。图表显示了因为非对齐访问所造成的降速。其对线性访问所造成的负面影响显著大于随机访问的版本，因为对于后者来说，开销普遍更高的主存访问部分掩盖了非对齐内存访问的开销。在线性访问的案例中，工作集能放进L2缓存的时候会导致300%的降速。这可以解释为L1缓存的性能降低。一些增加操作现在需要使用两个缓存行，并且开始处理列表元素时通常需要两条缓存行。L1和L2之间的连接单纯变得太拥挤了。

对于一个很大的工作集，非对齐访问依然会造成20%到30%的影响，考虑到对齐访问这样大小的数据时耗时很长，这个影响已经不可不谓不大了。这个图标应该展示了对齐必须被认真对待。即便处理器架构支持非对齐访问，也必须视“它们不像对齐访问那么好”。

不过这些对齐要求也有一些副作用。如果一个原子变量有对齐要求，编译器必须爆炸所有情况下都满足该要求。这并非易事，因为无法控制调用发起点以及他们处理栈的方法。这个问题可以通过两种方法来解决：

  1. 生成的代码里动态的对齐栈，如果必要则插入空隙。这要求代码来检查，生成并回滚栈对齐。
  2. 要求所有的调用者必须栈对齐。

所有常见的ABI（译注：应用程序二进制接口，参见维基）使用第二种方法。如果一个被调用者需要对齐而调用者违反了此规则，那么程序大概率会崩掉。不过保持对齐完好也并非毫无无代价。

一个函数中使用的栈帧大小不必一定得是对齐的整数倍。这意味着如果其从当前栈帧调用其他函数需要填充栈（padding）。对于栈帧大小来说最大的不同是，在大部分情况下，编译器知道其大小，因此它也知道如何调整栈指针来确保从栈帧中调用其他函数时是正确对齐的。事实上大部分编译器只是简单的把栈帧大小向上取整，然后就万事大吉了。

这个处理对齐的简单办法没法适用于变长数组（VLA）或alloca使用的情况。在这些情况中，栈帧的总大小只有在运行时才知道。这时可能就需要用到动态对齐控制（译注：前述的方法1），这会让生成的代码（些微）慢点。

在一些某些架构上，只有多媒体扩展才有严格要求对齐，栈则是最低程度的对齐到普通数据类型，一般分别是32位4字节对齐，64位8字节对齐。在这些系统上，执行对齐会带来没必要开销。这也就意味着这种情况下，如果我们知道它不依赖于强制对齐，那我们也应该避免执行对齐。没有使用多媒体扩展操作的尾函数（那些不会再调用其他函数的函数）不需要对齐。函数如果只会调用不需要对齐的函数则也不需要对齐。如果发现很多不需要对齐的函数，也许可以放宽程序的对齐要求。对于x86程序gcc支持宽松对齐要求：

1

-mpreferred-stack-boundary=2

如果这个选项的值设置为N，那么栈对齐值则是\(2^N\)字节。所以如果值是2则栈对齐值从默认的16字节减少到4字节。在大部分情况下这意味着不需要额外的栈对齐操作，因为入栈和出栈本身就是以4字节为界的。这个目标特定的选项可以帮助减少程序体积和提升执行速度。但是这没法适配到其他很多架构上。哪怕是x86-64一般也不适用，因为其ABI要求浮点数参数通过SSE寄存器传递，而SSE指令要求完全的16字节对齐。尽管如此，只要这个选项可用时它还是能带来一些显而易见的改变的。

并非只有高效的结构体字段排列和对齐能影响缓存效率。如果使用结构体数组，那么整个结构体定义都会影响性能。回想图3.11的结果：随着往数组的元素中增加无用数据，预取（prefecting）的效率则越低，对程序而意味着，工作集越大则性能越差。

对于工作集而言尽可能地利用有效缓存很重要。为了实现这点，可能需要重新安排数据结构。虽然对程序员而言把所有逻辑上同属一处的数据放进相同的数据结构体比较简单，但这可能并不是实现最佳的性能方式。假设我们有如下数据结构：

1
2
3
4
5
6

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

更进一步假设这些结构被储存在一个巨大的数组中，并且有一个任务会定时的将所有未付账单加起来计算预期付款总额。在这种场景下，buyer和buyer_id字段所使用的内存会毫无必要的被加载进缓存。通过图3.11的数据可以判断这个程序会比它应有的性能慢上5倍。

把顶蛋数据结构分离会更好，把前两个字段放进一个结构体，其他字段放进另一个。这个改动当然会增加程序复杂性，但其性能提升可能会让这代价变得值得。

最后让我们来看下另一个缓存优化手段，虽然它对其他层级的缓存也有用，但主要还是在L1数据缓存中起效。如图3.8所示，普通操作会受益于更高的缓存相关性。通常缓存越大，缓存相关性越高。L1数据缓存太大，没法完全关联，但又不够大，不具备L2缓存那样的缓存相关性。如果工作集中很多对象都落在同一缓存集上也会是个问题。因过度使用一个缓存集导致驱逐（缓存行）的情况发生，程序便会感知到延迟，即时此时还有很多缓存没有用到。这类缓存未命中有时被称作冲突未命中（Conflict misses）。由于L1数据缓存使用虚拟地址寻址，这其实能让程序员能有所掌控。如果一起使用的变量也存放在一起，他们落入同一个缓存集的可能就会最小化。图6.5展示问题会出现的多快。

图6.5 缓存相关性影响

在此图中，那个熟悉的测试用例6设NPAD=15（译注：参考第三部分文章，第3.2节），并使用特殊的设置来进行测量。X轴表示列表中两个元素之间的距离，以元素个数为单位进行测量。换而言之，距离2表示下一个元素在前一个元素后面128字节的位置。所有元素在虚拟内存空间内以完全一样间距进行排列。Y轴表示列表长度，当前仅用到1到16，表示工作集从64字节到1024字节不等。Z轴表示遍历每个元素所需的平均时钟周期。

图中展示的结果让人毫不意外。如果只用到少量元素以它们都能放进L1数据缓存的话，访问每个元素只需要3个时钟周期。这个结果对于几乎所有的排列间距都是成立的，因为虚拟地址可以很好的映射到L1数据缓存的槽位中而几乎不会产生冲突。图中有两个特别的间距值会让情况有所不同。如果间距是4096字节（也就是64个元素）的倍数，并且列表长度大于8，则访问每个列表元素的平均时钟周期会大幅增加。在这些情况下所有元素都落在了同一个缓存集，一旦列表长度大于其缓存相关性，缓存条目就会被从L1缓存刷出，下次则要从L2缓存中重读。其代价是访问每个列表元素约10个时钟周期。

通过这个这个图我们能确定处理器使用了总量32KB，缓存集相关性为8的L1数据缓存。这就意味着如有必要，这个测试也能拿来检测这些值。也可以对L2缓存测出相同的效果，但是由于L2使用物理地址索引且容量大得多，所以会更难就是了。

希望程序员能因这个结果数据而对缓存相关性给与更多关注。现实世界中把数据以2的指数为边界排布通常是够用了，但这正是会导致上述情况发生并产生性能降级的场景。非对齐访问由于每次访问需要额外的缓存行，则会进一步的增加冲突未命中的概率。

图6.6 AMD处理器的L1数据缓存库地址

如果采用这个优化手段，其他相关优化也能用。至少对于AMD处理器来说，它把L1数据缓存分成多个独立的Bank。L1数据缓存一个时钟周期能收到两个字，前提是两个字位于不同于的Bank或者位于同一个Bank且索引一样。如图6.6所示，Bank的地址被编码到虚拟地址的几个低比特位。如果一起使用的变量也被存放在一起，那么它们位于不同的Bank或者同Bank也同索引的概率较高。

2.2. 优化L1指令缓存的访问

  编写能良好利用L1指令缓存的代码需要用到类似能良好利用L1数据缓存的技巧。然而问题是，除非直接写汇编代码，否则程序员没法直接影响到L1指令缓存的使用。如果使用编译器，程序员可以通过指示它生成更佳的代码布局，进而间接的影响到L1指令缓存。

代码的一个优势是在跳转之间其是（内存）线性的。在这区间内处理器可以高效的预取内存。而跳转则会打乱它，因为：

  • 跳转目标可能没法静态确定
  • 就算是能静态确定的，如果缓存未命中也会让内存获取花很长时间

这些问题会造成执行停顿并可能严重影响性能。这就是为什么当今的处理器在分支预测（下简称BP，意Branch prediction）上花了大量力气。这些高度特殊化的BP单元会尽可能早的在跳转发生前去预测跳转目标，进而无缝的加载指令到缓存中去。它们同时使用静态和动态规则使之愈发擅长在执行过程中识别模式。

把数据尽快加载到缓存中去甚至比指令缓存还重要。正如第3.1节所提到的那样，指令在执行前需要先解码，为了提速（在x86和x86-64上很重要），指令实际上是以解码后的格式缓存的，而不是从内存中读到的原视字节/字数据。

为了实现最佳的L1指令缓存利用，程序员起码应该考虑如下几个有关代码生成的视角：

  1. 尽可能减少代码体积。但也必须平衡诸如循环展开，内联等优化手段（译注：它们会增加生成代码）。
  2. 代码应该线性执行，没有气泡7
  3. 有必要时可以对齐代码

我们将会根据这些视角，讲一讲一些可用于优化程序的编译器技巧。

编译器有选项可以启用优化等级；一些特定优化方法也能被单独启用。在高优化等级（对gcc而言-O2和-O3）启用的很多优化都关乎循环优化和函数内联。一般来说这些优化都不错。如果被如此优化的代码在总体执行时间中的占了相当一部分，则整体性能会得到提升。尤其是内联函数，允许编译器一次优化更大块的代码，进而生成更能有效利用处理器执行管线的机器码。当程序中的多块能被视作一个单元时，对代码和数据的优化（死代码消除，值域传播，以及其他种种）则更佳。

更大的代码体积意味着对L1指令缓存（当然也包括L2和更高层级的缓存）的压力也更大。这可能导致性能下降。更紧凑的代码会更快。幸运的是gcc有为此而设的相关优化选项。如果-Os被启用编译器将会优化代码体积。会导致代码体积增加的优化手段则会被禁用。使用此选项时常会产生令人惊讶的结果。尤其是当编译器没法有效利用循环展开和内联时，这个选项尤为有价值。

内联也可以被单独控制。编译器有启发式方法和限制来指导内联过程；这些限制可由程序员控制。-finline限制选项指示了一个函数多大时会被视作过大而不适合内联。如果一个函数在多个地方都有调用，那么内联它会导致代码体积爆炸。假设有一个叫inlcand的函数会被f1和f2函数调用，而f1和f2则会被顺序带调用：

表6.3 内联 vs 非内联

表6.3展示了这些函数在内联和非内联情况下可能生成的样子。如果函数inlcand内联，那么生成的代码总大小为 f1 + f2 + 2 x inlcand。如果不内联，其体积则会少一个inlcand函数的大小。如果f1和f2被紧挨着调用，这也是L1指令缓存和L2缓存所需的额外空间。此外：如果inlcand没有被内联，其代码可能还在L1指令缓存中而且将不再需要被再次解码。此外：由于以已经见过这段代码，分支预测单元可能会更好的预测跳转。如果编译器默认的内联函数大小上限并不适合你的程序，那么就应该降低它。

然而也有些情况下，内联是有意义的。如果一个函数仅需要被调用一次那它可能被内联也挺好。这会让编译器有机会做更多优化（诸如值域传递，能大幅提升代码）。内联可能会受限于所设的限制，对于这种情况gcc提供一个特殊选项来指示一个函数总是希望被内联。添加always_inline函数属性将会指示编译器干其名所述的事。

同样的，如果一个函数无论再小也不应被内联，那么可以用noinline函数属性。即便是小函数，如果它们经常会被不同的地方调用，那么使用这个函数属性也是合理的。如果L1指令缓存中的内容能被重用，整体占用降低，一般会弥补额外的函数调用带来的开销。如今的分支预测单元都挺不错的。如果内联能带来更积极的优化时又情况有所不同，这时需要因地制宜的做出决定。

always_inline属性在内联后的代码总是被用到的情况下工作的很好。但如果情况并不如此呢？如果内联后的代码只是偶尔被调用怎么说：

1
2
3
4
5
6

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

这段代码的生成和其源代码结构大体一致。这意味着会先执行A代码块，然后一个条件跳转，如果条件求值为false，继续向前跳转。其次是内联生成的inlfct函数，最后是C代码块。这看起来很合理但有一个问题。

如果条件总是求值为false，则执行流程并不线性。由于预取存在，中间总会有一大块用不上的代码来污染L1指令缓存，而且它还会导致分支预测出现问题。如果分支预测错误，那么这个条件表达式会变得非常低效。

这事一个普遍存在的问题而非内联函数特有的。无论何时条件执行出现一边倒的（也就是表达式求值为一个值的情况远多于另一个值）情况，总会造成错误分支预测进而导致执行管线出现泡泡的潜在风险。这问题可以通过告诉编译器把不常用的代码从主要执行路径中移出来避免。如下图所示，这种情况下由if语句生成的条件跳转会跳转到一个其他地址。

图中上面的部分表示一个简单的代码布局。例如如果B区域是由内联函数inlfct生成的，并通常因为判断条件导致不会执行而是跳过，而处理器预取到的缓存行里，却包含这个鲜有被执行的B区块。通过代码块重排可以解决这个问题，如上图中的下半部分所示。经常执行的代码被线性的放在内存中，而不常执行的代码则被移动到其他不影响预取和L1指令缓存效率的地方去。

gcc提供了两个方法来达成此目的。首先，编译器可以在编译时计算profiling输出，并根据profile安排代码块。我们将在第七节讲到它。第二个办法是通过显式的分支预测。gcc支持__builtin_expect：

1

long __builtin_expect(long EXP, long C)

这会告诉编译器表达式EXP更可能求值为C。返回的值是EXP。__builtin_expect理应被用于条件表达式。在绝大部分情况下它被用于布尔表达式的语境，为了方便可以定义两个辅助宏：

1
2

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

这些宏可以这样用

1

if (likely(a > 1)

如果程序员使用这些宏并启用-freorder-blocks优化选项，gcc则会如上图所示那般重排代码块。这个选项跟随-O2启用但在-Os中禁用。还有另一个gcc可以重排代码块（-freorder-blocks-and-partition）但是由于它没法兼容一场处理所以用处不大。

小循环体还有另一个巨大优势，至少在特定处理器上如此。Intel Core 2前端有一个特殊功能称作循环流检测器（Loop Stream Detector, LSD）。如果一个循环有不超过18条指令（它们所有都不会调用子例程），需要最多4个解码预取16字节，有最多4组分支指令，而且被执行超过64次。然后这个循环有时候就会被锁定在指令队列中，因此当循环再次被用到时能更快就绪。这适用于比如说一个会从外层循环进入多次的内层小循环。即便没有如此特殊的硬件单元，紧凑的循环依然有优势。

内联并不是针对L1指令缓存的唯一优化角度。另一个角度是对齐，如其之于数据那般。区别也显而易见：代码几乎完全是线性的二进制块，也没法在地址空间随意摆放，而且由于是编译器生成的代码程序员也没法直接影响它。虽然依旧有些程序员能控制的方面。

对齐每条指令毫无意义，目标应该是让指令流变得线性。所以对齐应该在战略层面上才有意义。要决定应该在哪假如对齐，须得先知道对齐的优势是啥。让一条指令位于缓存行8的头部意味着预取该缓存行的收益最大化。对指令而言这也意味着解码单元更高效了。所以很容易看到，如果指令一条位于缓存行末尾的指令，处理器必须准备好去读一个新的缓存行并解码指令。如果遇到糟糕的情况（比如说缓存未命中），意味着平均而言，位于缓存行末尾的指令不如位于头部的那般高效的执行。

结合后续推论，如果控制权刚刚转移到有问题的指令（因此预取无效），问题将最为严重。然后我们得出最终结论，代码对齐何时有用：

  • 在函数头
  • 仅通过跳转访问的基础块
  • 某种程度上，循环开始的位置

前两种情况下，对齐的代价很小。当执行到一个新位置，我们选择让它位于缓存行的开始，我们便优化了预取和解码9。编译器通过在对齐导致的间隙中插入nop指令来实现对齐。这些“死代码”会占用少量的空间但不会损害性能。

第三种情况则略有不同：在循环开始的地方对齐可能会导致性能问题。问题是循环开始的地方通常是线性的跟在其他代码后面的。如果不是非常走运时，就会在前面的代码和循环开始的位置之间弄出一个间隙。不像上述的前两种情况，这个间隙没法完全是“死代码”。在执行完前面的指令后，需要执行循环中的第一条指令，这就意味着，在执行完前面的代码后，要么紧跟着一些nop指令，要么得是个无条件跳转到循环开始的位置。两种情况都不是无代价的。尤其是如果循环本身不会被经常执行，那么填充的nop或者跳转的代价会高于对齐循环带来的收益。

有三种方法程序员可以影响代码对齐。显而易见，如果代码用汇编写，那么函数和所有指令都可以显式对齐。汇编器对所有架构都提供.align伪指令来做这事。对于高级语言则必须告诉编译器对齐要求。不像数据类型和变量那样，这对源代码来说是不可能的。取而代之的是一个编译选项：

1

-falign-functions=N

这个选项指示编译器用大于N的下一个2次方的值为边界对齐所有函数。这意味着间隙最多N字节。用一个大的N值，对于小函数来说是一种浪费，对于低频代码代码而言亦是如此。后者在一些库代码中经常发生，因为它往往同时包含着常用和不那么常用的接口。明智的选择选项值，可以提升代码速度或通过避免对齐节省内存。当N等于1或者使用-fno-align-functions选项时，对齐会被禁用。

对于前述情况中的第二项，非线性访问的基础块，则可通过其他选项来控制：

1

-falign-jumps=N

其他所有相关细节，有关内存浪费的警告在此也适用。

前述情况中的第三项也有它独有的选项：

1

-falign-loops=N

再一次，相同的细节和警告在此也同样适用。除了如前面所解释过的，如果对齐地址是被线性访问到的，那么无论是nop还是跳转指令都必须要执行，所以这种对齐有一定的运行时开销。

为了完整性这里提一下，gcc还有一个控制对齐的选项，-falign-labels，它会对齐代码中每个标签（基本上就是每个基本块的开始位置）。这个选项，除了少数例外，大部分情况下都会拖慢代码，故而不要使用。

2.3. 优化L2及更高层级的缓存访问

  之前提到过的所有关于L1缓存的优化都同样适用于L2及更高层级的缓存。对高层级缓存还有两个额外的点：

  • 缓存未命中总是代价高昂的。虽然L1的缓存未命中时，（寄希望）能在L2或更高层级中命中，可以减少这种代价。但显然对最后一级缓存来说就没这种兜底了。
  • L2及更高层级缓存通常在多个核心/超线程之间共享。所有每个执行单元的有效缓存容量并没有其总量那么多。

为了避免代价高价的缓存未命中，工作集大小应该匹配缓存大小。如果数据只需要用到一次则没啥必要，反正缓存如论怎样不会高效起来。我们此处要说的是需要被多次用到的数据，这种情况下如果工作集太大以至于无法塞进缓存，则会导致巨量的缓存未命中，此时即使预取成功也无法避免程序变慢。

即使一个程序需要在一个很大的工作集上执行作业，程序员也应负责让作业以缓存未命中最少的方式执行。只要像使用L1缓存那样，一次在小块数据上执行作业，那么则对于最后一级缓存来说（跑一个很大的作业集）是完全可行的。这方法类似于我们前面所述的优化版本的矩阵乘法。虽然也有不同，比如使用高层级缓存时，每次处理的数据块可以更大。如果代码需要用到L1缓存优化时会变得更加复杂。想象下矩阵乘法中，两个输入矩阵和一个输出矩阵没法一同放进最后一级缓存。这时可能就需要同时优化L1和最后一级缓存的访问。

L1的缓存行大小可能在好几代的处理器中都保持不变；即便不是差异也不会太大。假定较大值一般没啥大问题，在缓存行较小的处理器上，无非就是一次用到两行或者更多。无论哪种情况下，把缓存行大小硬编码进代码并以此进行代码优化是合理的。

对于更高层级的缓存来说，如果程序想变得更通用，情况则有所不同。这些缓存的大小可以非常的宽泛。8倍甚至更多的差距并不少见。也不大可能去假定那个较大的缓存大小作为默认值，因为这将意味着程序会在没有大缓存的机器上跑的很烂。相反的选择同样也不行：假定最小的缓存大小，则可能意味着抛弃了87%以上的缓存。如我们在图3.14中所看到的那样（译注：参见第3部分，图3.14），使用更大缓存对程序运行速度有巨大影响。

这就意味着代码必须动态的缓存行大小。这是属于程序特定的优化。此处我们能说的就是程序员应该正确的计算程序（的资源）需求。不仅是它自身所需要的数据集，高层级缓存往往还有其他用途。比如说，所有指令都是从缓存中加载的。如果用了库函数，缓存使用量可能也会显著增加。这些库函数自身可能也需要数据，这也会进一步的减少可用内存。

一旦我们确定了内存需求的组成，我们就能用之与缓存大小对比。如前所述，这缓存可能会被多个核心共享。当前10不硬编码来获取正确获取相关信息的办法，只能通过/sys文件系统。在图5.2（译注：参见第5部分，图5.2）中我们看过内核发布的硬件信息里有什么。程序需要定位此文件夹：

1

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

对于最后一级缓存，可以通过文件夹内level文件中的最高数值来确定。当文件夹确定后，程序应该读取那个文件夹内size文件的内容，并用其值除以同目录内shared_cpu_map文件内容中非0比特位数量，（最后的结果便是其可用缓存大小）。

这个方法计算出的值是一个安全下边界。有时候程序可能对其他进程和线程的行为有更多了解，如果那些那些线程被安排到同一个核心/超线程上共享缓存，而且已知那部分缓存已知不会被耗尽，那么这个计算的值可能太小了而不是最优的。是否应该使用超过缓存平均分配的那一部分应视情况而定，程序员要么自己做出决定或者交给用户来选择。

2.4 优化TLB的使用

  优化TLB使用的方法有两种。其一是减少程序用到的页数量，这会自然而然的降低TLB未命中率。其二则是通过减少需要分配的高位页目录表数量，来让TLB索引更加廉价。更少的页表意味着更少的内存使用，进而提升查表时的缓存命中率。

第一个优化方法和最少化页错误紧密相关。我们将会在第7部分涵盖这个话题。虽然页错误通常是一次性成本，但是考虑到TLB一般都很小而且会被频繁刷新，TLB未命中就是一种长期代价了。页错误比TLB未命中的代价高好几个数量级，但是如果一个程序只要执行的足够久，程序的某些部分执行的足够频繁，TLB未命中的代价甚至能比页错误还高。因此，对页的优化需要同时从页错误和TLB未命中两个角度综合考虑。区别是，优化页错误要求在页的层面组织代码和数据，而优化TLB则需要在任意时间，使用尽可能少的TLB项。

第二个TLB优化方法甚至更加难以控制。页目录的数量是由进程的地址范围在虚拟地址空间的分布决定的。在地址空间内分布得越广，页目录就更多。地址空间布局随机化（Address Space Layout Randomization， ASLR）的一个副作用就是会导致这种情况出现。ASLR会在运行时随机化栈，DSO，堆，以及可能包括可执行文件的加载地址，以防攻击者猜到函数和变量的地址。

仅当最佳性能很关键时才应该关闭ASLR。除了一些极端情况下，一些额外的页目录的代价低得让采取这步变得毫无必要。一个内核可能可以采取的优化方案是，在任意时候应确保每次映射都不会跨越两个页目录之间的内存边界，这会让ASLR的影响最小化但也不会从根本上弱化它。

只有当显式请求一块地址空间区域时，程序员才会被直接影响到。这通常发生在用MAP_FIXED参数使用mmap。使用这个方法分配地址空间区域非常危险且几乎从未这样做过。然而万一真这么做了，而且也能自由的选择地址，程序员则需要知道上一个页目录的边界，并据此选择合适的请求地址。

3. 预取

  预取的目的是隐藏内存访问的延迟。现今处理器的命令管线和乱序执行能力可以隐藏部分延迟，但是，最多也就是当访问命中缓存时。为了兜住主存访问带来的延迟，命令队列需要非常的长。一些没有乱序执行的处理使用更多核心作为补偿，除非代码都是并行化的，否则这个交换得不偿失。

预取可以进一步的帮助去隐藏延迟。处理器当遇到特定事件（硬件预取）或显式的由程序请求（软件预取）时，其自行执行预取。

3.1. 硬件预取

  触发CPU发起硬件预取的一般是以特定模式连续发生了两次或多次的缓存未命中。这些未命中的可能是后续或者前面的缓存行。以前的实现是只识别临近的缓存行发生未命中的情况。现在的硬件中，也能识别步幅，意思是如果跳过固定数量的缓存行也会被识别为一种模式，并进行适当的处理。

如果每次缓存未命中都触发硬件预取会有害性能。诸如访问全局变量这种随机内存访问模式是很常见的，这也触发预取的话将极大的浪费前端总线（译注：FSB）的带宽。这就是为啥要发起预取起码需要两次缓存未命中。处理器现如今都期望有多个内存访问流。处理器尝试给自动的给每个流计算缓存未命中，如果达到阈值则开始硬件预取。CPU目前可以针对较高层级的缓存追踪8到16个独立的流。

负责进行模式识别的单元一般和它们各自的缓存相关联。L1数据和指令缓存可以有预取单元。L2和更高层级的缓存大概率会有预取单元。L2和更高层级的预取单元由使用相同缓存的核心/超线程所共享。因此8到16个独立流这个数字很快就变得不那么多了。

预期有一个很大的弱点：它没法跨越页边界。

3.2. 软件预取

3.3. 特殊的预取：预测

3.4. 辅助线程

3.5. 直接缓存访问

4. 多线程优化

4.1. 并发优化

4.2. 原子性优化

4.3. 带宽考量

5. NUMA编程

NUMA是一个比较特殊的应用领域，精力有限，暂且不做翻译

6. 相关附录代码

6.1. 矩阵乘法

 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

#include <stdlib.h>
#include <stdio.h>
#include <emmintrin.h>

#define N 1000
double res[N][N] __attribute__((aligned(64)));
double mul1[N][N] __attribute__((aligned(64)));
double mul2[N][N] __attribute__((aligned(64)));
#define SM(CLS / sizeof(double))

int main(void) {
  // ... Initialize mul1 and mul2
  int i, i2, j, j2, k, k2;
  double * restrict rres;
  double * restrict rmul1;
  double * restrict rmul2;
  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) {
          _mm_prefetch( & rmul1[8], _MM_HINT_NTA);
          for (k2 = 0, rmul2 = & mul2[k][j]; k2 < SM; ++k2, rmul2 += N) {
            __m128d m1d = _mm_load_sd( & rmul1[k2]);
            m1d = _mm_unpacklo_pd(m1d, m1d);
            for (j2 = 0; j2 < SM; j2 += 2) {
              __m128d m2 = _mm_load_pd( & rmul2[j2]);
              __m128d r2 = _mm_load_pd( & rres[j2]);
              _mm_store_pd( & rres[j2], _mm_add_pd(_mm_mul_pd(m2, m1d), r2));
            }
          }
        }
  // ... use res matrix
  return 0;
}

  1. 原书地址由此访问 ↩︎

  2. 原文Non-temporal，意指非时域局部性 ↩︎

  3. 我们暂且忽略算术运算导致可能出现的上溢，下溢或者取舍 ↩︎

  4. 理论上1999年引入的C语言的restrict关键字可以解决这个问题，但是编译器还没有跟进，主要原因是有太多错误的现存代码可能会误导编译器进而导致生成错误的目标代码。 ↩︎

  5. Arnaldo Carvalho de Melo. The 7 dwarves: debugging information beyond gdb. In Proceedings of the Linux Symposium, 2007. URL https://ols2006.108.redhat.com/2007/Reprints/melo-Reprint.pdf. 6.2.1 ↩︎ ↩︎

  6. 测试在32位机器上完成，由于NPAD=15意味着每个列表元素恰好占一个64字节大小的缓存行 ↩︎

  7. 气泡是对处理器管线在执行过程必须等待资源而产生的“破洞”的具象化描述。如读者需要更多细节，可参考一些处理器设计的相关资料 ↩︎

  8. 对于一些处理而言，缓存行并不是指令的原子块（译注：指不可细分单位）。Intel Core 2前端会16字节一块提交到解码器。被提交的块都是适当对齐的，并不会跨越缓存行的边界。由于能对预取带来正面影响，对齐到缓存行的开始位置依然是有好处的。 ↩︎

  9. 处理器解码指令通常使用比缓存行更小的单元，对于x86和x86-64而言时16字节 ↩︎

  10. 肯定不久的将来会有更好的办法（译注：指2007年） ↩︎