设计代码以适应 CPU 缓存？

Question

在编写模拟时，我的朋友说他喜欢尝试将程序编写得足够小以适合缓存。这有什么实际意义吗？据我所知，缓存比 RAM 和主内存更快。是否可以指定您希望程序从缓存运行或至少将变量加载到缓存中？我们正在编写模拟，因此任何性能/优化增益都是巨大的好处。

如果您知道任何解释 CPU 缓存的好链接，请向我指出该方向。

Answer 1

大多数 C/C++ 编译器更喜欢针对大小而不是“速度”进行优化。也就是说，由于缓存效应，较小的代码通常比展开的代码执行得更快。

Answer 2

如果我是你，我会确保我知道代码的哪些部分是热点，我将其定义为

• 不包含任何函数调用的紧密循环，因为如果它调用任何函数，那么 PC 将花费大部分时间在该函数上函数，
• 它占执行时间的很大一部分（例如 >= 10%），您可以从分析器中确定这一点。 （我只是手动对堆栈进行采样。）

如果您有这样的热点，那么它应该适合缓存。我不确定你是如何告诉它这样做的，但我怀疑它是自动的。

Answer 3

至少对于典型的桌面 CPU，您无法直接指定太多有关缓存使用情况的信息。不过，您仍然可以尝试编写缓存友好的代码。在代码方面，这通常意味着展开循环（仅举一个明显的例子）很少有用——它扩展了代码，而现代 CPU 通常会最大限度地减少循环的开销。通常，您可以在数据方面做更多的事情，以提高引用的局部性，防止错误共享（例如，两个常用的数据片段将尝试使用缓存的同一部分，而其他部分保持未使用）。

编辑（为了使某些观点更加明确）：

典型的 CPU 具有许多不同的缓存。现代桌面处理器通常至少有 2 级（通常是 3 级）缓存。根据（至少几乎）普遍共识，“1 级”是距离处理元素“最近”的缓存，并且数字从那里开始向上（接下来是 2 级，之后是 3 级，等等）

在大多数情况下，（至少）一级缓存分为两半：指令缓存和数据缓存（Intel 486 几乎是我所知道的唯一例外，指令和数据都有一个缓存 - 但它是如此彻底过时了，可能不值得太多思考）。

在大多数情况下，缓存被组织为一组“行”。高速缓存的内容通常一次一行地读取、写入和跟踪。换句话说，如果 CPU 要使用缓存行任何部分的数据，则整个缓存行将从下一个较低级别的存储中读取。离CPU越近的高速缓存通常较小，并且具有较小的高速缓存线。

这种基本架构导致了缓存的大部分特性，这些特性对于编写代码很重要。您希望尽可能将某些内容读入缓存一次，用它完成您要做的所有事情，然后继续执行其他操作。

这意味着当您处理数据时，通常最好读取相对少量的数据（足够少到适合缓存），尽可能多地处理该数据，然后继续处理下一个数据块。数据。像快速排序这样的算法可以将大量输入快速分解为逐渐变小的部分，这或多或少是自动完成的，因此它们往往对缓存相当友好，几乎不管缓存的精确细节如何。

这也会影响您编写代码的方式。如果您有这样的循环：

for i = 0 to whatever
   step1(data);
   step2(data);
   step3(data);
end for

您通常最好将尽可能多的步骤串在一起，最多为适合缓存的数量。一旦缓存溢出，性能就会急剧下降。如果上面第 3 步的代码足够大，以至于无法放入缓存中，那么通常最好将循环分成两部分，如下所示（如果可能）：

for i = 0 to whatever
    step1(data);
    step2(data);
end for

for i = 0 to whatever
    step3(data);
end for

循环展开是一个相当激烈争论的主题。一方面，它可以生成对 CPU 更加友好的代码，从而减少循环本身执行的指令的开销。同时，它可以（并且通常会）增加代码大小，因此它对缓存相对不友好。我自己的经验是，在综合基准测试中，往往会对大量数据进行少量处理，您可以从循环展开中获得很多好处。在更实用的代码中，您往往会对单个数据进行更多处理，但您获得的收益会少得多，而且缓存溢出导致严重性能损失的情况并不特别罕见。

数据缓存的大小也受到限制。这意味着您通常希望数据尽可能密集地打包，以便缓存中容纳尽可能多的数据。仅举一个明显的示例，与指针链接在一起的数据结构需要在计算复杂性方面获得相当多的收益，以弥补这些指针使用的数据缓存空间量。如果要使用链接数据结构，通常至少要确保将相对较大的数据链接在一起。

然而，在很多情况下，我发现我最初学到的用于将数据放入微型处理器中的微量内存中的技巧（大部分）已经过时了几十年，在现代处理器上效果很好。现在的目的是在缓存而不是主内存中容纳更多数据，但效果几乎相同。在相当多的情况下，您可以认为 CPU 指令几乎是免费的，并且整体执行速度由缓存（或主内存）的带宽控制，因此从密集格式中解包数据的额外处理可以在你的恩惠。当您处理的数据足够多而无法全部放入缓存时尤其如此，因此整体速度取决于主内存的带宽。在这种情况下，您可以执行很多指令来节省一些内存读取，并且仍然领先。

并行处理可能会加剧这个问题。在许多情况下，重写代码以允许并行处理实际上不会导致性能提升，有时甚至会导致性能损失。如果整体速度由从 CPU 到内存的带宽控制，那么让更多内核竞争该带宽不太可能有任何好处（并且可能会造成重大损害）。在这种情况下，使用多核来提高速度通常归结为做更多的事情来更紧密地打包数据，并利用更多的处理能力来解包数据，因此真正的速度增益来自于减少消耗的带宽，而额外的内核可以避免浪费时间从更密集的格式中解包数据。

并行编码中可能出现的另一个基于缓存的问题是变量共享（和错误共享）。如果两个（或更多）核心需要写入内存中的同一位置，则保存该数据的缓存行最终可能会在核心之间来回穿梭，以使每个核心都可以访问共享数据。结果通常是并行运行的代码比串行（即在单核上）运行的速度慢。这种情况有一种变体，称为“错误共享”，其中不同内核上的代码写入单独的数据，但不同内核的数据最终位于同一缓存行中。由于缓存纯粹根据整行数据来控制数据，因此数据无论如何都会在核心之间来回移动，从而导致完全相同的问题。

Answer 4

这是一篇关于缓存/内存优化的非常好的论文的链接克里斯特·埃里克森（因《战神 I/II/III》而闻名）。它已经有几年的历史了，但仍然非常相关。

Answer 5

What Every Programmer Should Know About 一篇有用的论文将告诉您比您想了解的更多有关缓存的信息乌尔里希·德雷珀的记忆。 Hennessey 非常彻底地涵盖了它。 Christer 和 Mike Acton 也就此写了很多好文章。

我认为你应该更多地担心数据缓存而不是指令缓存——根据我的经验，dcache 未命中更频繁、更痛苦，并且更有效地修复。

Answer 6

更新：2014 年 1 月 13 日
根据这位高级芯片设计师的说法，缓存未命中现在是代码性能的压倒性主导因素，因此就加载、存储、整数的相对性能瓶颈而言，我们基本上一直回到了 80 年代中期和快速 286 芯片。算术和缓存未命中。

Cliff Click @ Azul 的现代硬件速成课程
。
。
。
。
。

--- 我们现在让您回到定期安排的计划 ---

有时，示例比描述如何做某事更好。本着这种精神，这里有一个特别成功的示例，展示了我如何更改一些代码以更好地在芯片缓存上使用。这是不久前在 486 CPU 上完成的，后来迁移到第一代 Pentium CPU。对性能的影响是相似的。

示例：下标映射

下面是我用来将数据放入具有通用用途的芯片缓存中的技术示例。

我有一个 1,250 个元素长的双浮点向量，这是一条尾巴很长的流行病学曲线。曲线的“有趣”部分只有大约 200 个唯一值，但我不希望 2 边 if() 测试弄乱 CPU 的管道（因此长尾，可以用作最极端的下标）蒙特卡洛代码会吐出的值），并且我需要代码中“热点”内的十几个其他条件测试的分支预测逻辑。

我确定了一个方案，使用 8 位整数向量作为双精度向量的下标，并将其缩短为 256 个元素。小整数在零之前的 128 之前和零之后的 128 之前都具有相同的值，因此除了中间的 256 个值之外，它们都指向 double 向量中的第一个或最后一个值。

这将双精度数的存储需求缩减至 2k，8 位下标的存储需求缩减至 1,250 字节。这将 10,000 字节缩减为 3,298 个字节。由于程序花费了 90% 或更多的时间在此内部循环中，因此这 2 个向量从未被推出 8k 数据缓存。该程序的性能立即提高了一倍。在计算 1+00 万抵押贷款的 OAS 值的过程中，该代码被命中约 1000 亿次。

由于曲线的尾部很少被触及，因此很可能只有微小 int 向量的中间 200-300 个元素实际上保存在缓存中，以及代表 1/8 的兴趣百分比的 160-240 个中间双精度数。对于我花了一年多优化的程序来说，一个下午就完成了性能的显着提高。

我同意 Jerry 的观点，因为我的经验也表明，将代码向指令缓存倾斜并不像优化数据缓存那么成功。这是我认为 AMD 的通用缓存不如 Intel 的独立数据和指令缓存那么有用的原因之一。 IE：您不希望指令占用缓存，因为它没有太大帮助。部分原因是 CISC 指令集最初是为了弥补 CPU 和内存速度之间的巨大差异而创建的，除了 80 年代末的一个偏差之外，这几乎总是如此。

我最喜欢的另一种有利于数据缓存并破坏指令缓存的技术是在结构定义中使用大量位整数，并且通常使用尽可能小的数据大小。要屏蔽 4 位 int 来保存一年中的月份，或 9 位来保存一年中的日期等，需要 CPU 使用掩码来屏蔽这些位正在使用的主机整数，这会缩小数据，有效地增加了缓存和总线大小，但需要更多指令。虽然这种技术生成的代码在综合基准测试中表现不佳，但在用户和进程争夺资源的繁忙系统上，它的效果却非常好。

Answer 7

大多数情况下，这将作为一个占位符，直到我有时间正确地讨论这个主题，但我想分享我认为是一个真正突破性的里程碑 - 在新的英特尔 Hazwell 微处理器中引入专用位操作指令。

当我在 StackOverflow 上编写一些代码来反转 4096 位数组中的位时，这一点变得非常明显，在 PC 推出 30 多年后，微处理器并没有在位上投入太多注意力或资源，我希望改变。特别是，对于初学者来说，我很乐意看到 bool 类型成为 C/C++ 中的实际位数据类型，而不是目前浪费得可笑的字节。

更新：2013 年 12 月 29 日

我最近有机会优化一个环形缓冲区以毫秒粒度跟踪系统上 512 个不同资源用户的需求。有一个计时器每毫秒触发一次，它添加了最新切片的资源请求的总和并减去第 1,000 个时间片的请求，其中包括现在 1,000 毫秒之前的资源请求。

头向量和尾向量在内存中是紧挨着的，除了先是头向量，然后是尾向量，然后从数组的开头开始。然而，（滚动）Summary 切片位于一个固定的、静态分配的数组中，该数组与其中任何一个都不是特别接近，甚至不是从堆中分配的。

思考这一点并研究代码，一些细节引起了我的注意。

1. 传入的需求被同时添加到 Head 和 Summary 切片中，在相邻的代码行中彼此相邻。

2. 当计时器触发时，Tail 会从 Summary 切片中减去，并且结果会保留在 Summary 切片中，如您所料

3. 当计时器触发时调用的第二个函数会提前为环提供服务的所有指针。尤其....
   Head 覆盖了 Tail，从而占用了相同的内存位置
   新的 Tail 占用了接下来的 512 个内存位置，或者包裹了

4. 用户希望在管理的需求数量方面具有更大的灵活性，从 512 到 4098，甚至更多。我认为最可靠、最简单的方法是将 1,000 个时间片和摘要片一起分配为一个连续的内存块，这样摘要片就不可能最终成为不同的长度比其他 1,000 个时间片要多。

5. 鉴于上述情况，我开始想知道，如果我不让 Summary 切片保留在一个位置，而是让它在 Head 和 Tail 之间“漫游”，那么我是否可以获得更高的性能，因此它总是紧挨着Head 用来添加新的需求，当计时器触发时，Tail 就在 Tail 旁边，并且必须从 Summary 中减去 Tail 的值。

我正是这么做的，但随后在这个过程中发现了一些额外的优化。我更改了计算滚动摘要的代码，以便将结果保留在尾部，而不是摘要切片中。为什么？因为下一个函数正在执行 memcpy() 将 Summary 切片移动到 Tail 刚刚占用的内存中。 （奇怪但真实，尾部引导头部，直到环缠绕时的末端）。通过将求和结果保留在 Tail 中，我不必执行 memcpy()，我只需将 pTail 分配给 pSummary。

以类似的方式，新的 Head 占用了现在已过时的 Summary 切片的旧内存位置，因此，我再次将 pSummary 分配给 pHead，并使用 memset 将其所有值清零为零。

引导到环的末端（实际上是一个鼓，512 条轨道宽）的是 Tail，但我只需将其指针与常量 pEndOfRing 指针进行比较即可检测该情况。所有其他指针都可以分配其前面的向量的指针值。 IE：我只需要对 1:3 的指针进行条件测试即可正确包装它们。

最初的设计使用字节整数来最大化缓存使用率，但是，我能够放松这一限制 - 满足用户要求每毫秒处理每个用户更高的资源计数 - 使用无符号短整型并且仍然双倍性能，因为即使有 3 个相邻的 512 个无符号短整型向量，L1 缓存的 32K 数据缓存也可以轻松容纳所需的 3,720 字节，其中 2/3 位于刚刚使用的位置。仅当尾部、摘要或头部包装是由 8MB L3 缓存中的任何重要“步骤”分隔的 3 个中的 1 个时。

该代码的总运行时内存占用量低于 2MB，因此它完全在片上缓存中运行，即使在具有 4 核的 i7 芯片上，也可以运行该进程的 4 个实例，而不会降低性能，并且运行 5 个进程时总吞吐量略有上升。这是关于缓存使用的巨著。