帮助编译器

编译器在优化代码方面，能做到相当出色。但有些编码方式会让编译器难以处理。一些技巧会打破编译器能做出的假设。本节中，我们会探讨一些应尽量避免的事情，以及如何养成习惯，让编译器更容易遵从我们的本意。

减少顺序依赖

如果不管编译器能否推断出操作顺序，那它就无法提前完成工作。将翻译好的代码合成为中间形式，有些编译器会用到一个指标：静态单赋值形式(static single assignment form，SSA)。它基于这样的想法：一旦变量被初始化赋值后，就不再修改，如果确实需要修改，就创建新变量。不过在循环中还无法应用，因为只要是传输操作，所赋的值都需要改变。不过我们可以尝试去逼近，这样就能帮助编译器理解：修改、分配值时的意图。粗略过一遍 Haskell、Erlang、Single-Assignment C 等语言现在的功能和教程，就有足够的线索，学会以单赋值的方式写代码。

这样更容易看出编译器在哪里要分支，并且可以让写入更加明确。同时也意味着在编译器不得不停止写入内存的位置，我们可以强迫它在所有情况下写入。这样处理更同质化，因而保证流的效率。

减少内存依赖

由于依赖关系存在，链表的开销很大，不过这属于另一种依赖关系。内存很慢，我们当然希望执行操作时它能及时加载。但是需要加载的地址本身也还在加载时，就没法作弊了。指针驱动的树形算法很慢，不是因为内存查找，而是因为链式内存查找。

如果想让 map、set 的实现更快，可以尝试宽节点算法，如 B-树，或 B*-树。希望将来某天，STL 中的 std::map 和 std::set 的实现可以自由选择。

如果有一个组合风格的实体-组件-系统，不过是基于指针的组合，那通过两层指针来获取组件的速度就会变慢。如果这些组件里还有指针，问题只会更复杂。

尽量减少获取所需数据的跳转次数。每一次依赖于先前数据的跳转，都可能会导致读取主内存引发的停顿。

察觉缓冲区写入

写入时要考虑的问题，与读取时相同。尽可能保持连续。尽量让可修改的值与只读的值分开，也与只写的值分开。

简而言之，连续写入，单次大量写入，用上所有字节，避免零散的字节。之所以这样尝试，因为它不仅有助于激活、停用不同内存页，也能帮助编译器做优化。

假设有一块缓存，有时知道如何绕过它也很重要。如果知道当前加载的数据只会用一次，或至少短时间内不会从缓存中获益，那了解如何避免污染缓存就很有用了。用简单的方法实现变换，能够帮助编译器将污染缓存的操作，修正为完全绕过缓存的指令。这些流式操作通过避免挤出随机访问的内存，从而让缓存获益。

Ulrich Drepper 在 What every programmer should know about memory [#!UDrepper!#] 一文中谈到了内存的方方面面，其中对于如何充分利用计算机硬件很有意思。这篇文章中，他用非时间性(non-temporal)这个词来描述我们称之为流的各种操作。这些非时间性的内存操作之所以有用，是因为它们完全绕过了缓存。粗看似乎是个糟糕的选择，但正如其名称暗示的，流式数据短期不可能被召回到寄存器中，所以在缓存中保有这些数据毫无意义，反倒会挤出潜在有用的数据。因此，流式操作允许一定程度上决定哪些重要，哪些肯定算不上。

别名(Aliasing)

别名是指相同的内存地址可能被多个指针引用。因此，如果写入一个指针，则需要在读取前重新加载。举个例子，假设要找的值是通过引用而不是值确定的，如果有任何函数，有几率影响到该引用指向的内存，那在做比较之前，就必须重读该引用。实际上，正是因为它是指针，而非值，才导致了这样的问题。

以不可变的方式处理数据的原因之一，就是为优化做准备。C++ 给程序员提供了很多自讨苦吃的办法，其中最厉害的就是，不仔细使用内存指针时，能引发意外的副作用。考虑如下代码：

如果只是想得到一个长度 99，且都是 'X' 的字符串，这份代码完全没问题。然而，有这种可能，memcpy 需要一个一个字节地复制。为了加快速度，通常会一次载入大量内存地址，在它们全部进入缓存后再保存出来。如果写入输出数据可能会修改到输入的缓冲区，那就得非常谨慎了。现在考虑这个问题：

编译器能发现 q 不受影响，且很乐意解开循环，或是用一个寄存器的值替换对 q 的检查。但反过来看这段代码：

编译器无法判断 q 是否会受对 p 的操作的影响，所以它每次检查循环的结束时都要存储 p 并重新加载 q。这就是所谓的别名，不知道两个正在使用的变量的地址是否不同，所以为了保证代码功能正确，必须把这些变量当作可能位于相同地址来处理。

返回值优化

如果要返回多个值，通常是通过引用参数，或是填充一个对象的引用。许多情况下，通过值返回开销其实很低，许多编译器可以把它变成一次非拷贝操作。

如果一个函数试图通过在返回过程中原地构造一个结构，它可以将构造过程直接转移到将接收它的值中，无需拷贝。

利用 std::pair 或其他小的临时结构能有效帮助更多代码以值的形式运行，不仅从本质上让推理变得更容易，编译器也更容易优化。

缓存行利用率

我们知道，一次内存请求总是至少会读到一个完整的高速缓存行。这个完整缓存行包含多个字节数据。写这本书时，常见的缓存行大小似乎已经稳定在了 64 字节。基于这些信息，就可以推测出哪些数据只通过与其他数据的相对位置来访问开销更低。

在第 6 章(查找)，我们用这些信息决定数据的位置和数量，通过示例，创建了快速查找表，该表使用两层线性查找，结果比二分查找要快。

当有一个要加载到内存中的对象，就需要计算出缓存行与对象的大小之间的差值。这个差值就是可以存入免费读取的数据的大小。利用这个空间去回答该类的常见问题，就能显著提升速度，因为不会再额外访问内存了。

例如，考虑有一部分要迁移到组件的代码，但仍有一个实体类指向组件数组中的一条可选行。这种情况下，我们可以将这些实体在用的元素，整合成比特集，缓存在实体类的后半部分。于是实体与实体间的交互，就可以省去在未匹配行时查找数组的过程。它还可以提高渲染性能，渲染器可以立即知道没有受伤，然后只显示满血图标，或什么都不显示。

第 16 章中，代码 16.11 尽量利用对象的初始缓存行，应对对象其余部分的问题，从结果来看，获得了不同程度的收益。完全缓存结果的情况下，则有巨大改进。如果结果无法快速计算，并又急需，缓存也被占用，也能有 $25\%$ 的改进。能够缓存结果时，根据缓存命中情况，也有不同程度的性能改进。总而言之，利用缓存行上的额外数据总是比基础的检查有进步。

i5-4430	@ 3.00GHz
Average	11.31ms	[基础-直接检查 map]
Average	9.62ms	[部分缓存 (25%)]
Average	8.77ms	[部分缓存 (50%)]
Average	3.71ms	[基础-有缓存]
Average	1.05ms	[部分缓存 (95%)]
Average	0.30ms	[完整缓存]

<>

总的来说，只要知道，加载任意内存都是在加载一个完整的高速缓存行。目前，64 字节的缓存行，相当于一个 4x4 的浮点数矩阵，8 个 double，16 个 int，一个 64 字符的 ASCII 字符串，或者 512 位。

伪共享(False Sharing)

如果某个 CPU 核心不与其他核心共享资源，那它一定可以独立全速运行，是么？不一定。即使 CPU 核心是在独立数据上工作，有时它也会被缓存阻塞。

与线性写入遇到的问题相反，在向同一缓存行写入数据时，会干扰到线程。不过随着编译器进步，这种情况已经相对少了很多。想要重现它，观察其影响的话，只有关闭优化才有极小的几率验证。

这个想法源于多个线程可能读取、写入同一个缓存行，但不一定是缓存行中的相同地址。确保任意快速更新的变量保存在线程内，不管是堆栈还是线程局部存储，都可以相对容易地避免这种情况。其他的数据，只要不是定期更新，就很难引起冲突。

这个特殊的问题，已经有很多人在谈论，但实际情况与实际问题所呈现的不同。在优化前后持续跟进，确保真的是这个问题，即便能力很强的人也可能在此跌跟头。

那么，如何判断是这个问题？如果多线程代码在增加内核时，处理速度不是线性增长，那就可能被伪共享所扰。看看线程在哪里写，尽量彻底从共享内存移除写操作。常见的例子，如将一些数组相加，并在全局共享位置更新总和，如代码 。

FalseSharing 函数中，sum 作为共享资源被写入，每个线程都会触发缓存清理，并在其他核心更新自己在缓存行中的元素之前，将缓存行标记为脏。在第二个函数 LocalAccumulator，每个线程在写结果前，都会先在内部求和。

注意推测执行

推测执行，能提前准备可能用到的指令和数据，有效地在确定需要之前，就完成工作，但有时也会带来不利影响。如，之前提到的代码，已经部分以组件形式实现。目前用来表示可选行的比特集，可能通过推测，载入这些数组的信息。因为有推测执行，所以需要注意代码是否意外预取了数据，同时在等待某个比较结果。这些推测操作在 SPECTRE 和 MELTDOWN 漏洞的新闻中都有所提及。

如果可以，通过预先计算低阶断言减少分支预测引发的读取，将普通查询的结果存储在行中，对于大多数机器来说都有很大收益，而对于内存延迟高、CPU 与内存带宽比率高的机器，就是更大的收益。尝试降低分支预测错误对数据带来的副作用的技术，一般来说也不错。即便只在可行时缓存，将结果存在初始部分，随时间推移，也能节省带宽。

在缓存行利用率部分，数据显示，获取数据的可能性，似乎也会影响进程的速度，并且比预期的还要多得多。因而人们相信，非必要数据的推测性负载可能不利于整体吞吐量。

即便只能缓存一个请求是否会返回结果，那也有用。保留是否有符合该描述的条目的数据，以避免查询复杂的数据结构，能够提高速度，且很少带来副作用。

分支预测

CPU 停顿的主要原因之一，归根结底，要么是无事可做；要么是预测得不好，不得已去分解已经完成的工作。如果代码推测执行，请求了不必要的内存，那负载就浪费了内存带宽。已完成的工作会被否决，重新开始（或继续）正确的工作。要解决这个问题，有些方法可以让代码无分支；还有方法是了解 CPU 的分支预测机制，并帮助它解决。

如果预测足够明显(trivial)，大多数时候预测器都能做对。如果确保大块的条件始终是为 true 或 false，那预测器犯的错误会更少。举个简单的例子，如代码 ，根据传入的数据，预测是否需要累加。如果 CPU 支持，大多数编译器可以用条件移动 (conditional move) 指令优化这里。如果把工作做得更真实些，那就算开了全局优化，在对数据排序以提高分支可预测性的情况下，也能看到非常大的差别 。另一个重点，如果编译器能提供帮助，就让它来吧。优化后的明显的例子只在与常规工作负载对比时才凸显其明显，但如果实际工作被优化为条件执行，那排序数据就是浪费了。

i5-4430	@ 3.00GHz
Average	4.40ms	[随机分支]
Average	1.15ms	[有序分支]
Average	0.80ms	[明显随机分支]
Average	0.76ms	[明显有序分支]

<>

分支是因为数据产生的，记住，分支不好的原因不是因为跳转开销大，而是因为预测错误所做的工作必须撤销。因此，务必记住虚表指针也是数据。不批量更新，就无法最大化利用分支预测器，但即使根本不触发分支预测器，也可能会基于数据提交指令序列。

避免被驱逐

如果读者常与其他人合作(很多人如此)，那针对很多缓存性能差的问题,最简单的办法就是考虑到其他部分的代码。如果工作在一台多核机器上（显然是，除非能回到过去），那很可能所有的进程都在分享、争夺机器上的缓存。毫无疑问，你的代码会被从缓存中驱逐。数据也是如此。要降低代码和数据被驱逐的几率，尽量保持代码和数据处于小规模，如果可以，还要处理突发情况。

这个建议其实很简单。短小的代码不仅不易被驱逐，并且，如果能迅速完成，那在被覆盖前就有机会完成适当的工作量。有些缓存架构无法判断缓存中的元素最近是否被用过，所以他们依靠这些元素的添加时间，作为优先驱逐的标准。特别是，有些 Intel 的 CPU 会因为 L3 需要驱逐，就去驱逐 L1 和 L2 缓存行，但 L3 并不能完全访问 LRU 信息。Intel 的 CPU 还有些其他魔法，能减少这种情况，但确实仍会发生。

为此，尽量想办法向编译器保证在处理的数据是对齐的，是位于 4、8、16 的倍数的数组中。这样编译器就无需添加预处理和后处理代码来处理不对齐、不规则大小的数组。一个数组中多出 3 个无用元素，那将其作为长度为 N * 4 的数组来处理可能会更好。

自动矢量化

自动矢量化能让应用程序运行得更快，只需启用它组织代码，编译器就可以做出安全假设，并将指令从标量变为矢量。

有许多常规的例子可以被彻底矢量化。如代码 ，常规到大多数编译器打开优化时都会对其矢量化。问题是这段代码没什么保证，所以即使处理数据的速度相当快，它在指令缓存中占用的空间，也多于必要。

如果做些简单保证（如对齐指针），并提供给编译器一些元素数量的保证，就能够减少分发的汇编指令。虽然从单个案例的尺度看没什么帮助，但对于大型代码库，要解码的指令数量削减了，因而指令缓存效果也会增强。代码 在孤立测试中并不快，但最终可执行文件更小，生成的代码不到原先的一半。这属于微型基准测试的一个问题，它们没法每次都展示系统是如何一起工作、相互斗争的。现实的测试中，修正指针对齐能极大提高性能。而在小型测试平台中，内存吞吐量通常是唯一瓶颈。

需要注意，确保循环足够简单，并且总能执行其循环体。如果循环必须基于数据中断，那就不能确保完成所有元素的处理，意味着它必须逐个处理每个元素。代码 中，引入基于数据的中断，使得该函数从一个快速并行的 SIMD 操作的自动矢量循环，变成了一个单步循环。这里要注意，分支本身并不会导致矢量化崩溃，基于数据退出循环才会。如，代码，分支可以变为其他操作。还有一种情况，调用函数往往也会破坏矢量化，因为通常无法保证副作用。而如果该函数是constexpr，那它就更有可能被放进循环体中，且不会破坏矢量化。某些编译器中，一些数学函数能够以矢量形式呈现，如 minabs、sqrt、tan、pow 等。可以试着找出当前编译器可以矢量化的内容。某种程度上，手动去写要做的一些列操作往往也有帮助，因为尝试缩短 C++ 代码的话，可能会导致编译器允许做的事情出现轻微歧义。但要特别注意，确保完全展开。如果只写入部分输出流，就没法输出整个 SIMD 数据，所以要写输出变量，哪怕读取只是为了去写输出。

别名也会影响自动矢量化，指针可以重叠时，同一 SIMD 寄存器的不同成员间，就可能存在依赖关系。考虑代码 ，该函数的第一个版本是每个成员会加它后面的一个相邻成员。这个函数没什么意义，只是用来举例。它成对累加，直到最后一个 float。因此，无法简单地矢量化。第二个函数，虽然同样没有意义，但其步长够大，自动矢量化就能找到方法，计算每步的多个值。

不同的编译器会根据写代码的方式，管理不同数量的矢量。一般来说，代码越简单，编译器就越有可能优化它。

未来十年，编译器会越来越好。Clang 已经比 GCC 尝试解开更多循环，可能也会出现许多检测、优化常规代码的新方法。写作本书时，Matt Godbolt 实现的在线 Compiler Explorer 就是个很好的工具。能够看到代码如何被编译成汇编，也就能看到什么可以，也会被矢量化、优化、重排、以其他方式转变成机器可读形式。记住，汇编指令的数量，并不是衡量代码快慢的好标准，SIMD 操作并非在所有情况下都更快。只要不是通过摸着下巴想想这段指令是不是很牛皮来衡量代码的运行情况，应该就没事了。