如何编写最好地利用 CPU 缓存来提高性能的代码？

这可能听起来像一个主观的问题，但我在寻找的是具体的实例，您可能会遇到与此相关的。

  1. How to make code, cache effective/cache friendly (more cache hits, as few cache misses as possible)? From both perspectives, data cache & program cache (instruction cache), 也就是说，一个人的代码中与数据结构和代码构造相关的东西，应该注意什么才能使其高效缓存。

  2. 是否存在必须使用/避免的特定数据结构，或者是否存在访问该结构成员的特定方式等等。.使代码缓存有效。

  3. 在这个问题上，是否应该遵循/避免任何程序结构(if、 for、 switch、 break、 goto、 ...)、代码流(for inside an if、 if inside a for 等等) ？

我期待着听到个人经验相关的缓存高效代码一般。它可以是任何编程语言(C，C + + ，Assembly，...) ，任何硬件目标(ARM，Intel，PowerPC，...) ，任何操作系统(Windows，Linux，S ymbian，...) ，等等。.

多样性将有助于更好地深入了解它。

72338 次浏览
小开

我可以这样回答(2) : 在 C + + 世界中，链表可以很容易地杀死 CPU 缓存。在可能的情况下，数组是更好的解决方案。对于其他语言是否也适用这种情况，我们没有经验，但很容易想象会出现同样的问题。

小开

缓存以“缓存线路”的形式排列，(实际)内存以这种大小的块读取和写入。

因此，包含在单个缓存行中的数据结构效率更高。

类似地，访问连续内存块的算法将比以随机顺序跳过内存的算法更有效。

不幸的是，不同处理器之间的缓存行大小差异很大，因此无法保证在一个处理器上最优的数据结构在其他处理器上是有效的。

小开

真不敢相信没有更多的答案了。无论如何，一个经典的例子是迭代一个“由内而外”的多维数组:

pseudocode
for (i = 0 to size)
for (j = 0 to size)
do something with ary[j][i]

这种缓存效率低下的原因是，当您访问单个内存地址时，现代 CPU 将从主内存加载具有“近”内存地址的缓存行。我们在内部循环中迭代数组中的“ j”(外部)行，因此对于每次通过内部循环的行，缓存行将导致刷新并加载一行靠近[ j ][ i ]条目的地址。如果改为等效:

for (i = 0 to size)
for (j = 0 to size)
do something with ary[i][j]

它会跑得更快。

小开

缓存最有效的数据结构是数组。缓存工作得最好，如果您的数据结构是按照 CPU 一次读取整个缓存线路(通常是32字节或更多)的顺序布局的话。

任何以随机顺序访问内存的算法都会破坏缓存，因为它总是需要新的缓存线路来容纳随机访问的内存。另一方面，顺序运行数组的算法是最好的，因为:

  1. 它给 CPU 提供了一个预读的机会，例如，投机性地将更多的内存放入缓存，这将在以后访问。这种预读提供了巨大的性能提升。

  2. 在一个大的数组上运行一个紧密的循环也允许 CPU 缓存在循环中执行的代码，并且在大多数情况下允许您完全从缓存内存执行一个算法，而不必阻塞外部内存访问。

小开

除了数据访问模式之外，缓存友好代码的一个主要因素是数据 尺寸。更少的数据意味着更多的数据可以放入缓存。

这主要是与内存对齐的数据结构的一个因素。“传统”观点认为数据结构必须在单词边界上对齐，因为 CPU 只能访问整个单词，如果一个单词包含多个值，你就必须做额外的工作(读-修改-写，而不是简单的写)。但是缓存可以使这个参数完全无效。

类似地，Java 布尔数组为每个值使用一个完整的字节，以便允许直接操作单个值。如果使用实际位，可以将数据大小减少8倍，但是访问单个值变得更加复杂，需要位移和掩码操作(BitSet类可以为您做到这一点)。但是，由于缓存效果，这仍然比在数组较大时使用布尔[]要快得多。IIRC I 曾经通过这种方式获得了2或3倍的加速。

小开

编写程序使其最小化。这就是为什么在 GCC 中使用 O3优化并不总是一个好主意的原因。它占据了更大的尺寸。通常情况下-O 和-O2一样好。这完全取决于所使用的处理器。YMMV.

一次处理一小块数据。这就是为什么当数据集很大时，效率较低的排序算法可以比快速排序运行得更快。想办法把大数据集分解成小数据集。其他人建议这样做。

为了帮助您更好地利用指令的时间/空间位置，您可能需要研究如何将代码转换为程序集。例如:

for(i = 0; i < MAX; ++i)
for(i = MAX; i > 0; --i)

这两个循环产生不同的代码，即使它们只是通过数组进行解析。在任何情况下，您的问题都是非常具体的架构。因此，严格控制缓存使用的唯一方法是了解硬件的工作原理并为其优化代码。

小开

如果您对内存和软件如何交互感兴趣，我建议您阅读 Ulrich Drepper 撰写的由9部分组成的文章 每个程序员都应该知道的关于内存的知识。它也可以作为 一份104页的 PDF。

与这个问题特别相关的部分可能是 第二部分(CPU 缓存)和 第五部分(程序员可以做什么-缓存优化)。

小开

基本规则实际上相当简单，棘手的地方在于它们如何应用到代码中。

缓存的工作原理有两个: 时间局部性和空间局部性。 前者的思想是，如果您最近使用了某个数据块，您可能很快就会再次需要它。后者意味着，如果您最近使用了地址 X 的数据，那么您可能很快就需要地址 X + 1。

缓存试图通过记住最近使用的数据块来适应这种情况。它使用缓存线路，通常大小为128字节左右，因此即使您只需要一个字节，包含它的整个缓存线路也会被拉入缓存中。因此，如果之后需要下面的字节，它就已经在缓存中了。

这意味着您总是希望自己的代码尽可能地利用这两种形式的局部性。不要在记忆中乱跳。在一个小区域尽可能多地做工作，然后转移到下一个区域，在那里尽可能多地做工作。

一个简单的例子是1800年的答案所显示的2D 数组遍历。如果一次遍历一行，就是顺序读取内存。如果按照列的方式进行，您将读取一个条目，然后跳到一个完全不同的位置(下一行的开始) ，读取一个条目，然后再次跳转。当您最终返回到第一行时，它将不再位于缓存中。

这同样适用于代码。跳转或分支意味着缓存使用效率较低(因为不是按顺序读取指令，而是跳转到不同的地址)。当然，小的 if 语句可能不会改变任何东西(您只是跳过了几个字节，所以您仍然会停留在缓存区域内) ，但函数调用通常意味着您跳到了一个可能不会被缓存的完全不同的地址。除非是最近打来的。

不过，指令缓存的使用通常远不是一个问题。您通常需要担心的是数据缓存。

在结构或类中，所有成员都是连续布局的，这很好。在数组中，所有条目也是连续布局的。在链表中，每个节点被分配到一个完全不同的位置，这是不好的。指针通常倾向于指向不相关的地址，如果取消引用它，可能会导致缓存丢失。

如果您希望利用多个核，那么可能会非常有趣，因为通常情况下，一次只有一个 CPU 的 L1缓存中可能有任何给定的地址。因此，如果两个核不断访问相同的地址，这将导致不断缓存失败，因为他们正在争夺地址。

小开

要问如何编写代码，缓存有效缓存友好和其他大多数问题，通常是问如何优化一个程序，这是因为缓存对性能有如此巨大的影响，以至于任何优化的程序都是缓存有效缓存友好的。

我建议阅读有关优化，这个网站上有一些很好的答案。 就书籍而言，我推荐使用 计算机系统: 程序员的视角，它有一些关于正确使用缓存的精美文本。

(b.t.w-如果一个程序是来自硬盘的 呼叫...)

小开

只有一篇文章涉及到这个问题，但是在进程之间共享数据时会出现一个大问题。您希望避免多个进程试图同时修改相同的缓存行。这里需要注意的是“虚假”共享，即两个相邻的数据结构共享一条缓存线，对其中一条的修改会使另一条缓存线失效。这可能导致缓存线路在共享多处理器系统数据的处理器缓存之间不必要地来回移动。避免这种情况的一种方法是对齐和填充数据结构，将它们放在不同的行上。

小开

缓存的存在是为了减少 CPU 在等待内存请求完成时停机的次数(避免内存 潜伏期) ，作为第二个效果，可能是为了减少需要传输的数据总量(保留内存 带宽)。

避免内存获取延迟的技术通常是首先要考虑的事情，而且有时会有很大帮助。有限的内存带宽也是一个限制因素，特别是对于多核和多线程应用程序，其中许多线程希望使用内存总线。一组不同的技术有助于解决后一个问题。

改进 空间位置意味着确保将每个缓存线路映射到缓存之后都能完全使用。当我们研究了各种标准基准测试之后，我们发现在取消缓存线之前，很大一部分标准基准测试未能100% 地使用所取得的缓存线。

提高高速缓存线路的利用率有三个方面的帮助:

  • 它倾向于在缓存中放入更有用的数据，从本质上增加了有效的缓存大小。
  • 它往往将更有用的数据放在同一条缓存线上，从而增加了在缓存中找到所请求数据的可能性。
  • 它减少了对内存带宽的需求，因为会有更少的提取。

常见的技巧有:

  • 使用较小的数据类型
  • 组织数据以避免对齐漏洞(通过减小大小对结构成员进行排序是一种方法)
  • 小心标准的动态内存分配器，它可能会引入漏洞，并在内存升温时将数据分散在内存中。
  • 确保在热循环中实际使用了所有相邻的数据。否则，请考虑将数据结构分解为 hot 和 cold 组件，以便 hot 循环使用 hot 数据。
  • 避免显示不规则访问模式的算法和数据结构，并支持线性数据结构。

我们还应该注意，除了使用缓存之外，还有其他隐藏内存延迟的方法。

现代 CPU: s 通常有一个或多个 硬件预取程序。他们训练在一个隐藏的失误，并试图发现规律。例如，在几次错过后续的缓存行之后，hw 预取程序将开始将缓存行提取到缓存中，以预测应用程序的需求。如果您有一个常规的访问模式，那么硬件预取器通常可以做得很好。如果您的程序没有显示常规的访问模式，您可以通过自己添加 预取指令来改进。

重新分组指令的方式使缓存中总是丢失的指令彼此靠近，CPU 有时可以重叠这些抓取，以便应用程序只维持一次延迟命中(内存级并行性)。

为了减少总体内存总线压力，您必须开始寻址所谓的 暂时的位置。这意味着您必须在数据尚未从缓存中清除时重用它。

合并触及相同数据(环路融合)的循环，以及使用称为 瓷砖或 挡住了的重写技术，都力求避免这些额外的内存获取。

虽然对于这种重写练习有一些经验法则，但是您通常必须仔细考虑带循环的数据依赖关系，以确保不会影响程序的语义。

在多核世界中，这些东西才是真正有价值的，在多核世界中，添加第二个线程后，通常不会看到很多吞吐量改进。

小开

除了对齐结构和字段之外，如果你的结构已经分配了堆，你可能需要使用支持对齐分配的分配器; 像 _aligned_malloc(sizeof(DATA), SYSTEM_CACHE_LINE_SIZE);一样，否则你可能会有随机错误共享; 请记住，在 Windows 中，默认堆有一个16字节的对齐。

小开

用户 1800信息对“经典示例”的注释(注释太长)

我想检查两个迭代顺序(“外部”和“内部”)的时间差，所以我用一个大型2D 数组做了一个简单的实验:

measure::start();
for ( int y = 0; y < N; ++y )
for ( int x = 0; x < N; ++x )
sum += A[ x + y*N ];
measure::stop();

第二个案件与 for循环交换。

较慢的版本(“ x 优先”)是0.88秒，较快的版本是0.06秒。这就是缓存的威力:)

我使用了 gcc -O2，但仍然对循环进行了 没有优化。里卡多所说的“大多数现代编译器可以自己解决这个问题”是站不住脚的

小开

我在一个游戏引擎中看到的一个例子是将数据从对象中移动到它们自己的数组中。一个受物理学影响的游戏对象也可能有很多其他的数据。但是在物理更新循环中，引擎所关心的只是位置、速度、质量、包围盒等数据。因此，所有这些都被放置到它自己的数组中，并尽可能地为 SSE 进行优化。

因此，在物理循环过程中，物理数据采用矢量数学的方法按数组顺序进行处理。游戏对象使用它们的对象 ID 作为各个数组的索引。它不是指针，因为如果必须重新定位数组，指针可能会失效。

在许多方面，这违反了面向对象设计模式，但是通过将需要在同一个循环中操作的数据放在一起，它使代码运行速度快了很多。

这个例子可能已经过时了，因为我认为大多数现代游戏都使用像 Havok 这样的预先构建的物理引擎。

小开

关于数据结构选择、访问模式等一般性建议已经有了很多答案。在这里，我想添加另一个代码设计模式，称为 软件管道，它使用活动缓存管理。

这个想法借鉴了其他流水线技术，例如 CPU 指令流水线。

这种类型的模式最适用于

  1. 可以分解为合理的多个子步骤，S [1] ，S [2] ，S [3] ，... 其执行时间大致相当于 RAM 访问时间(? 60-70ns)。
  2. 接受一批输入，并对它们执行上述多个步骤以获得结果。

让我们看一个只有一个子过程的简单例子。 通常情况下，代码应该是:

def proc(input):
return sub-step(input))

为了获得更好的性能，您可能需要在一个批处理中向函数传递多个输入，以便分摊函数调用开销，并增加代码缓存的本地性。

def batch_proc(inputs):
results = []
for i in inputs:
// avoids code cache miss, but still suffer data(inputs) miss
results.append(sub-step(i))
return res

然而，如前所述，如果步骤的执行与 RAM 访问时间大致相同，那么您可以进一步改进代码，使其类似于下面这样:

def batch_pipelined_proc(inputs):
for i in range(0, len(inputs)-1):
prefetch(inputs[i+1])
# work on current item while [i+1] is flying back from RAM
results.append(sub-step(inputs[i-1]))
        

results.append(sub-step(inputs[-1]))

执行流程应该是这样的:

  1. 预取(1) 要求 CPU 将输入[1]预取到缓存中，其中预取指令将 P 循环本身并返回，而在后台输入[1]将在 R 循环之后到达缓存中。
  2. Works _ on (0) cold miss on 0 and works on it，这需要 M
  3. 预取(2) 发出另一个取
  4. Works _ on (1) 如果 P + R < = M，则输入[1]应该在此步骤之前已经在缓存中，从而避免数据缓存丢失
  5. 作品 _ 关于(2) ..。

可能涉及更多的步骤，然后您可以设计一个多阶段管道，只要步骤的时间和内存访问延迟匹配，您将遭受很少的代码/数据缓存丢失。然而，这个过程需要通过许多实验来调整，以找到正确的步骤分组和预取时间。由于其所需的努力，它看到更多的采用在高性能数据/包流处理。在 DPDK QoS Enqueue 流水线设计中可以找到一个很好的生产代码示例: Http://dpdk.org/doc/guides/prog_guide/qos_framework.html 第21.2.4.3章排队管道。

可以找到更多信息:

Https://software.intel.com/en-us/articles/memory-management-for-optimal-performance-on-intel-xeon-phi-coprocessor-alignment-and

Http://infolab.stanford.edu/~ullman/dragon/w06/lectures/cs243-lec13-wei.pdf


提交答案