用价值投机打败 L1 缓存

摘要：如果我们有一种启发式方法可以廉价地猜测某个值，我们可以使用分支预测器在紧密循环中删除数据依赖性。这允许 CPU 并行运行更多指令，从而提高性能。如果这个解释对您没有多大意义，请继续阅读以了解一些使您的 CPU 变快的魔法！ Per Vognsen 的 twitter 提要充满了简洁的低级好奇心，通常利用 CPU 功能来获得一些性能优势。最近他在推特上提到了一个我从未听说过的技巧——价值投机。 1 该技巧利用分支预测器来猜测值，从而实现更多指令并行性，从而消除 L1 缓存上的瓶颈。请注意，瓶颈不是由于 L1 缓存未命中，而是由于 L1 缓存命中引入了不需要的数据依赖性。反过来，Per 引用了 Paul Khuong 的一篇博客文章，其中包含一个部署此技巧的真实示例。反过来，保罗提到了旁道攻击。 ↩︎ 在这篇文章中，我解释了所涉及的机制，包括分支预测和 CPU 缓存的入门，因此任何具有 C 语言知识以及如何在 CPU 上执行代码的人都应该能够理解。该帖子的代码可在此处获得。所有数字均来自至强 E5-1650 v3，这是一款英特尔 Haswell 处理器，具有 32kB、256kB 和 15MB 的 L1/L2/L3 缓存。代码是用 clang -O3 编译的，而不是用 gcc 编译的，原因稍后解释。在开始之前，我想强调一下 L1 缓存命中几乎肯定不是您的应用程序的瓶颈！这只是一个非常巧妙的技巧，它阐明了一些 CPU 功能，而不是关于如何提高普通 C 代码段性能的指南。

我们有一个简单的链表数据类型，以及一个对给定链表的所有元素求和的函数： typedef struct Node { uint64_t value ;结构节点 *next ; // 最后一个节点为 NULL } Node ; uint64_t sum1 (Node * node ) { uint64_t value = 0 ; while (node) { value += node ->value ;节点=节点->下一个； } 返回值； } 到现在为止还挺好。我们的测试用例是这样工作的：构建一个链表，其中节点在连续内存中按顺序存在，然后查看将它们全部加起来需要多长时间： // 分配 5MB 的链表节点，并按顺序链接它们，使用 // 随机`value` 中的数据。 uint64_t n = 312500 llu； // 312500 * sizeof(Node) = 312500 * 16 bytes = 5000000 bytes Node *nodes = malloc (n * sizeof (Node)); for ( uint64_t i = 0 ; i < n - 1 ; i ++) { 节点 [i ].value = random_uint64 ();节点 [i ].next = &nodes [i + 1 ]; } 节点 [n - 1 ].value = random_uint64 ();节点 [n - 1 ].next = NULL ; // 现在求和。 sum1 (&nodes [ 0 ]);在具有相对较旧的 Xeon E5-1650 v3 的服务器上，使用示例数据运行 sum1 需要 0.36 毫秒，这意味着我们正在以大约 14GB/s 的速度处理我们的链表。在本文的其余部分，我们将确定瓶颈并通过价值推测来解决它，从而使该数据集的吞吐量达到 30GB/s。修复的影响取决于数据集的大小。如果它已经完全在 CPU 缓存中，那么改进会更加明显，否则我们很快就会受到从 RAM 读取数据的速度的限制。此图显示了不同大小数据集的性能改进（越高越好）：该图显示了 sum1 的性能以及三个改进函数 sum2、sum3 和 sum4 的性能。如果数据完全适合 L1 缓存（16kB 数据集），我们从 sum1 中的 14GB/s 吞吐量到 sum4 中超过 40GB/s，而适合 L2 和 L3 缓存（128kB 数据集）的数据集性能略有下降和 5MB 数据集）。如果数据集不完全适合任何 CPU 缓存（~4GB 数据集），我们会从 10GB/s 到 15GB/s，这与 RAM 允许的速度一样快。 2

有关为什么我认为 15GB/s 是不诉诸更深层次变化的限制的更多数据，请参阅最后一节中的评论。 ↩︎ 现代 CPU 不是串行处理指令，而是同时处理许多指令。他们一次读取许多指令，将它们分阶段分解，然后尝试用尽可能多的指令中的尽可能多的任务来填充他们拥有的所有计算单元。 3 例如，现代英特尔处理器的设计吞吐量为每个时钟周期 4 条指令，而 AMD Zen 处理器的吞吐量高达 5 或 6 条。4 然而，当想要并行执行指令时，分支会带来挑战。让我们回到我们的函数 sum1：为了扩展这个主题，您可以开始阅读乱序执行和流水线。 ↩︎ Agner Fog 的微架构文档包含大量有关 Intel 和 AMD x86 处理器流水线特性的详细信息。每个架构的吞吐量数字通常在“管道”部分。 ↩︎ uint64_t sum1 (Node * node ) { uint64_t value = 0 ; while (node) { value += node ->value ;节点=节点->下一个； } 返回值； }; rdi = 节点和 rax = 值。 ; rax 是返回值寄存器（我们正在返回值） sum1: xor rax , rax ;值 = 0 测试 rdi , rdi ;如果节点为 NULL，则退出，否则开始循环 je 结束循环：添加 rax , qword ptr [ rdi ] ; value += node->value mov rdi , qword ptr [ rdi + 8 ] ;节点 = 节点->下一个测试 rdi , rdi ;如果节点不为空，则重复循环，jne 循环；否则退出结束ret

循环体由 4 条指令组成，最后一条是跳转。在没有特殊措施的情况下，必须在执行下一条指令之前执行直到 jne 的每条指令，因为我们需要知道我们是要到循环的开头还是继续。换句话说，条件跳转会在 CPU 内部的指令级并行性中引入障碍。然而，一次执行多条指令非常重要，以至于所有现代 CPU 中都存在专用硬件——分支预测器——以对每次条件跳转时我们将采用的方式进行有根据的猜测。其工作原理的细节超出了本博文的范围，但从概念上讲，您的 CPU 会在程序运行时观察您的程序，并尝试通过记住过去发生的事情来预测将采用哪个分支。 5 除了一直有用的 Agner Fog（参见微架构文档的第 3 节），Dan Luu 有一篇很好的博客文章，解释了执行分支预测的各种方法。 ↩︎ 即使对分支预测知之甚少，我们也希望预测器能够为我们的测试用例做一个很好的工作——除了我们停止使用列表之外，我们总是回到循环的开始。在 Linux 上，我们可以通过 perf stat 验证这种情况：分支预测器在 99.96% 的时间内都正确。所以 CPU 可以随意并行化我们的指令，对吗？ …对？ ; rdi = 节点和 rax = 值。循环：添加 rax ， qword ptr [ rdi ] ； value += node->value mov rdi , qword ptr [ rdi + 8 ] ;节点 = 节点->下一个测试 rdi , rdi ;如果节点不为空，则重复循环，jne 循环；否则 exit 要递增值（ rax ），我们需要知道节点（ rdi ）的值，这取决于循环的前一次迭代。因此，循环的每次迭代之间存在数据依赖性：我们必须在迭代 n 时完成读取 node->next ( [rdi + 8]) ，然后才能开始在迭代 n+1 处执行加法。

此外，加载节点的下一个值的 mov 是循环中最慢的指令。现代 CPU 在添加数字方面比从内存中读取要好得多。为此，CPU 和主存之间存在一系列快速缓存。从主内存读取和写入的所有操作通常都经过缓存——如果我们感兴趣的数据不存在，CPU 将加载一块内存（“缓存线”，x86 上的 64 字节），其中包含我们想要的数据进入缓存。 6 最快的缓存通常称为 L1（连续的缓存层可预测地称为 L2、L3 ……）。当涉及到 CPU 缓存时，我们的设置是最好的情况——我们顺序读取一堆内存，沿途利用每个字节。然而，即使 L1 缓存非常快，它也不是免费的：在我们的 mov 中读取它大约需要 4 个 CPU 周期，而添加、测试和 jne 需要 1 个 CPU 周期。 7 因此，通过单个循环迭代所需的周期数受从 L1 缓存读取所需的 4 个周期的限制。我从测试程序的至强获得的数据大致与此一致：我说“通常”是因为可以使用流式 SIMD 指令避免缓存，这些指令可以绕过缓存写入或复制内存。然而，这些方法是可选的，默认情况下所有内存都通过缓存。 ↩︎ 同样，Agner Fog 的性能页面是我能找到的最好的资源来获取这些数字。例如，如果想要找到 Haswell CPU 的这些编号： add、test 和 jne 的编号位于指令表的 Haswell 部分。

↩︎16KB，10000次迭代SUM1：8465052097154389858，1.12us，14.25GB /秒，3.91循环/ ELEM，1.03 instrs /周期，3.48GHz，4.01 instrs / elem128kB，10000次迭代SUM1：6947699366156898439，9.06us，14.13GB / S，3.95周期/elem, 1.01 instrs/cycle, 3.49GHz, 4.00 instrs/elem5000kB, 100 次迭代 sum1: 2134986631019855758, 0.36ms, 14.07GB/s, 3,91.emstrs/elem4,4.00 instrs/elem5000kB, 100迭代 sum1: 15446485409674718527, 0.43 s, 9.94GB/s, 5.60 cycle/elem, 0.71 instrs/cycle, 3.48GHz, 4.00 instrs/elem 重要的数字是cycles/elem和instrs/cycle。我们为每个列表元素（即每次循环迭代）花费大约 4 个周期，对应于每个周期大约 1 条指令的吞吐量。鉴于所讨论的 CPU 设计为每周期 4 条指令的吞吐量，我们浪费了大量可用的 CPU 魔法，因为我们一直在等待 L1 缓存。我们终于得到了诀窍。如前所述，我们一直在等待读取下一个节点地址是什么。然而，在我们的设置中，我们在一个连续的内存块中分配列表，因此节点总是彼此相邻。所以这里的关键思想是：尝试通过碰撞前一个值来猜测下一个节点。如果猜测错误，则将节点设置为“真实”的下一个值。在 C 中，它是这样的： uint64_t fast_sum (Node * node ) { uint64_t value = 0 ;节点 * 下一个 = NULL ; while (node) { value += node ->value ;下一个=节点->下一个； // 猜测下一个值节点++; // 但如果我们猜错了，请修复它（以防节点 // 彼此相邻）。如果（节点！=下一个）{节点=下一个； } } 返回值；这看起来很奇怪。我们仍在比较节点中读取 node->next != next 以确保我们的猜测是正确的。因此，乍一看，这似乎不是一种改进。

这就是分支预测器的用武之地。在大多数节点彼此相邻的列表的情况下（如我们的测试代码中的情况），分支预测器将猜测 if (node != next) { .. . } 分支没有被采用，因此我们将通过循环迭代而不必等待 L1 读取。请注意，当分支预测器错误时（例如当列表结束时，或者如果我们有不连续的节点），CPU 将需要回溯并从失败的分支预测中重新运行，这是代价高昂的（15 到 20 个周期我们的处理器 8)。然而，如果列表大部分是连续的，这个技巧就会起作用并使我们的函数快 50-200%。请参阅 Agner Fog 的微体系结构文档中 Haswell 处理器的“错误预测惩罚”。 ↩︎ 然而，要完成最终代码并显示数字，还有最后一个挑战——让编译器相信我们的代码值得编译。让我们回到我们在 C 中展示的用于价值推测的代码： uint64_t fast_sum (Node * node ) { uint64_t value = 0 ;节点 * 下一个 = NULL ; while (node) { value += node ->value ;下一个=节点->下一个；节点++；如果（节点！=下一个）{节点=下一个； } } 返回值； gcc 和 clang 很容易推断出这种猜测在语义上毫无意义，然后编译我们的技巧，使 fast_sum 的编译版本与 sum1 相同。这是一个编译器智能撤销人类关于我们正在编译的底层平台的知识的例子。

Per Vognsen 的要点使用以下技巧来让编译器运行——这是对 sum1、sum2 的第一个改进： static uint64_t sum2 (Node *node ) { uint64_t value = 0 ; while (node) { value += node ->value ;节点 *predicted_next = 节点 + 1 ;节点 *next = 节点 ->next ; if (next == Predicted_next) { // 通过让编译器认为我们在这里改变了 predicted_next 来防止编译器优化这个显然毫无意义的分支。 // // 但是，此技巧不适用于 GCC，仅适用于 clang。 GCC 在这里 // 推导出 `next` 和 `predicted_next` 是相同的，因此 // 将它们合并到同一个变量中，这重新引入了 // 我们想要摆脱的数据依赖性。 asm ( "" : "+r" (predicted_next ));节点 = 预测_下一个； } else { 节点=下一个； } } 返回值；然而，正如评论中所解释的那样，gcc 仍然没有完全爱上它。 9 此外，clang 生成的循环并没有想象的那么紧凑，每个元素需要 10 条指令。所以我求助于手动写出一个更好的循环，我们称之为 sum3: 10 这就是我坚持使用 clang 来写这篇文章的原因。我不知道 Per 在他的测试中使用的是什么编译器。 ↩︎ 这里我展示了 Intel 语法中的汇编版本，但在代码中我编写了内联汇编，使用 AT&T 语法，因为它更好地支持。 ↩︎ ; rax = 值，rcx = 下一个，rdi = 节点；注意 rax 是返回值寄存器（我们正在返回值） sum3: xor rax , rax ;值 = 0 异或 rcx , rcx ; next = NULL 测试 rdi , rdi ;如果节点为空，则走到最后，je end；否则开始循环 loop_body: add rax , qword ptr [ rdi ] ; value += node->value mov rcx , qword ptr [ rdi + 8 ] ; next = node->next add rdi , 16 ; node++ cmp rcx , rdi ;如果 node 不等于 next，则 jne assign_node ；转到assign_node，否则jmp loop_body ;重新启动循环assign_node: mov rdi , rcx ;节点 = 下一个测试 rdi , rdi ;如果节点不为空，则重新启动循环， jne loop_body ；否则退出。 end: ret 代码依赖于这样一个事实：如果 node 等于 next，我们在增加它之后不能为 NULL，避免了额外的测试，并且每个元素只取 6 条指令（从 loop_body 到assign_node）。最后，sum4 与 sum3 相同，但 loop_body 展开了 16 次。

16KB，10000次迭代SUM1：8465052097154389858，1.12us，14.25GB / S，3.91循环/ ELEM，1.03 instrs /周期，3.48GHz，4.01 instrs / ELEM SUM2：8465052097154389858，0.57us，27.95GB / S，1.99循环/ ELEM， 5.02 instrs/cycle, 3.48GHz, 10.01 instrs/elem sum3: 8465052097154389858, 0.41us, 39.23GB/s, 1.42cycles/elem, 4.23 instrs/cycle, 3.45052097154389858, 0.41us, 39.23GB/s, 4.23 instrs/cycle, 36805209715438986 /s, 1.34 周期/elem, 3.80 instrs/cycle, 3.48GHz, 5.07 instrs/elem128kB, 10000 次迭代 sum1: 6947699366156898439, 9.06us, 14.13GB,95.5 GHz instrs/s,14.13GB,95.4 周期 instr/s,4.0 GHz instrs/elem128kB, 10000 次迭代/ ELEM SUM2：6947699366156898439，4.75us，26.95GB / S，2.07循环/ ELEM，4.84 instrs /周期，3.48GHz，10.00 instrs / ELEM SUM3：6947699366156898439，3.85us，33.23GB / S，1.68循环/ ELEM，3.58 instrs /周期，3.48GHz，6.00 instrs / ELEM SUM4：6947699366156898439，3.36us，38.14GB /秒，1.46循环/ ELEM，3.46 instrs /周期，3.49GHz，5.06 instrs / elem5000kB，100次迭代SUM1：2134986631019855758，0.36ms，14.07 GB/s, 3.96 周期/ elem, 1.01 instrs/cycle, 3.48GHz, 4.00 instrs/elem sum2: 2134986631019855758, 0.19ms, 26.25GB/s, 2.12 周期/elem, 4.71 instrs/cycle, 4.00 instrs/elem sum2,4045758, 0.19ms, 26.25GB/s, 4.71 instrs/cycle, 4.00 instrs.855755758 104 1000000000000000000000000引28.69GB/s, 1.94 周期/elem, 3.09 instrs/cycle, 3.48GHz, 6.00 instrs/elem sum4: 2134986631019855758, 0.16ms, 30.30GB/s, 1.84,55 GHz instrs/elem, 1.84s.36 周期 instr.367 周期elem4294MB, 1 次迭代 sum1: 15446485409674718527, 0.43 s, 9.94GB/s, 5.60 周期/elem, 0.71 instrs/周期, 3.48GHz, 4.00 instrs/elem 4803,407s/elem 4803,40s/elem 4803,407s/elem 4804,873.71s/elem 4804,80.71s/elem 4804,873.73/48526:70 2.45 instrs /周期，3.48GHz，10.00 instrs / ELEM SUM3：15446485409674718527，0.29 S，14.72GB / S，3.77循环/ ELEM，1.59 instrs /周期，3.47GHz，6.00 instrs / ELEM SUM4：15446485409674718527，0.29 S，15.02GB /s, 3.70 cycle/elem, 1.37 instrs/cycle, 3.47GHz, 5.06 instrs/elem 前三个数据集适合 L1 / L2 / L3 缓存。在这些情况下，改进非常明显，sum3 / sum4 以每秒大约 4 条指令的速度处理数据，这应该接近我测试代码的处理器的限制。当数据不适合缓存时，瓶颈就会填充它，我们以大约 15 GB/s 的速度处理数据。我相信这是从 RAM 中“简单”单线程读取所能达到的最快速度，并且它与来自 sysbench 的数据一致：RAM 读取速度可能可以使用 SIMD 流指令或通过从多个线程读取来提高，尽管实施起来会复杂得多。这样我们就完成了这个低级技巧的旅程！如果你想要更多这样的东西，我再怎么推荐 Per 的帐户也不为过——弄清楚他的技巧是如何工作的，这很有教育意义。感谢 Alexandru Scvortov、Niklas Hambüchen、Alex Appetiti 和 Carter T Schonwald 阅读本文的草稿。 Niklas 还澄清了一些有关 RAM 速度的细节，并建议使用 sysbench 来特别测量单线程 RAM 读取速度。