c++ - 什么是“缓存友好”代码？

Question

“缓存不友好代码”和“缓存友好”代码有什么区别？

如何确保编写缓存高效的代码？

Answer 1

预赛

在现代计算机上，只有最低级别的内存结构（寄存器）才能在单个时钟周期内移动数据。然而，寄存器非常昂贵，并且大多数计算机内核只有不到几十个寄存器。在内存频谱 ( DRAM ) 的另一端，内存非常便宜（即实际上便宜数百万倍），但在请求接收数据后需要数百个周期。为了弥合超快速和昂贵与超慢和便宜之间的差距，高速缓存存储器，以递减的速度和成本命名为 L1、L2、L3。这个想法是大多数执行代码会经常碰到一小组变量，而其余的（更大的一组变量）很少。如果处理器在 L1 缓存中找不到数据，那么它会在 L2 缓存中查找。如果不存在，则为 L3 缓存，如果不存在，则为主存。这些“失误”中的每一个在时间上都是昂贵的。

（类比是缓存内存是系统内存，系统内存是硬盘存储。硬盘存储非常便宜但非常慢）。

缓存是减少延迟影响的主要方法之一。用 Herb Sutter 的话说（参见下面的链接）：增加带宽很容易，但我们无法摆脱延迟。

始终通过内存层次结构检索数据（最小 == 最快到最慢）。缓存命中/未命中通常是指 CPU 中最高级别缓存的命中/未命中——最高级别是指最大的 == 最慢的。缓存命中率对性能至关重要，因为每次缓存未命中都会导致从 RAM（或更糟......）获取数据，这需要花费大量时间（RAM 需要数百个周期，HDD 需要数千万个周期）。相比之下，从（最高级别）缓存读取数据通常只需要几个周期。

在现代计算机架构中，性能瓶颈是让 CPU 死掉（例如访问 RAM 或更高）。随着时间的推移，这只会变得更糟。处理器频率的提高目前不再与提高性能相关。问题是内存访问。因此，CPU 中的硬件设计工作目前主要集中在优化缓存、预取、流水线和并发性上。例如，现代 CPU 将大约 85% 的芯片用于缓存，而将高达 99% 的芯片用于存储/移动数据！

关于这个话题有很多话要说。以下是关于缓存、内存层次结构和正确编程的一些很好的参考资料：

• 阿格纳雾的页面。在他的优秀文档中，您可以找到涵盖从汇编到 C++ 的语言的详细示例。
• 如果您喜欢视频，我强烈建议您看一看 Herb Sutter 关于机器架构的演讲 (youtube)（特别是查看 12:00 及以后的时间！）。
• Christer Ericson（技术总监@Sony）关于内存优化的幻灯片
• LWN.net 的文章《每个程序员都应该知道的内存知识》

缓存友好代码的主要概念

缓存友好代码的一个非常重要的方面就是局部性原则，其目标是将相关数据靠近内存以允许有效缓存。就 CPU 缓存而言，了解缓存行以了解其工作原理非常重要：缓存行如何工作？

以下特定方面对于优化缓存非常重要：

1. 时间局部性：当访问给定的内存位置时，很可能在不久的将来再次访问相同的位置。理想情况下，该信息仍将被缓存。
2. 空间局部性：这是指将相关数据彼此靠近放置。缓存发生在许多级别上，而不仅仅是在 CPU 中。例如，当您从 RAM 中读取数据时，通常会获取比特别要求的更大的内存块，因为程序通常很快就会需要这些数据。HDD 缓存遵循相同的思路。特别是对于 CPU 高速缓存，高速缓存行的概念很重要。

使用适当的c++容器

缓存友好与缓存不友好的一个简单示例是c ++std::vector与std::list. a 的元素std::vector存储在连续的内存中，因此访问它们比访问 a 中的元素更容易缓存std::list，后者将其内容存储在所有地方。这是由于空间局部性。

Bjarne Stroustrup 在这个 youtube 剪辑中给出了一个非常好的说明（感谢@Mohammad Ali Baydoun 提供链接！）。

在数据结构和算法设计中不要忽视缓存

只要有可能，请尝试以允许最大程度地使用缓存的方式调整您的数据结构和计算顺序。这方面的一种常用技术是缓存阻塞 （Archive.org 版本），这在高性能计算中极为重要（参见例如ATLAS）。

了解并利用数据的隐式结构

另一个简单的例子，该领域的许多人有时会忘记存储二维数组的列优先（例如fortran、matlab）与行优先排序（例如c、c++ ）。例如，考虑以下矩阵：

1 2
3 4

在行优先排序中，这在内存中存储为1 2 3 4; 在列优先排序中，这将存储为1 3 2 4. 很容易看出，不利用这种排序的实现将很快遇到（很容易避免！）缓存问题。不幸的是，我在我的领域（机器学习）中经常看到这样的东西。@MatteoItalia 在他的回答中更详细地展示了这个例子。

当从内存中获取矩阵的某个元素时，它附近的元素也将被获取并存储在缓存行中。如果利用了排序，这将导致更少的内存访问（因为后续计算所需的接下来的几个值已经在缓存行中）。

为简单起见，假设高速缓存包含一个可以包含 2 个矩阵元素的高速缓存行，并且当从内存中获取给定元素时，下一个也是。假设我们想要对上面示例 2x2 矩阵中的所有元素求和（我们称之为M）：

利用排序（例如在c++中首先更改列索引）：

M[0][0] (memory) + M[0][1] (cached) + M[1][0] (memory) + M[1][1] (cached)
= 1 + 2 + 3 + 4
--> 2 cache hits, 2 memory accesses

不利用排序（例如在c++中首先更改行索引）：

M[0][0] (memory) + M[1][0] (memory) + M[0][1] (memory) + M[1][1] (memory)
= 1 + 3 + 2 + 4
--> 0 cache hits, 4 memory accesses

在这个简单的例子中，利用排序大约可以使执行速度加倍（因为内存访问比计算总和需要更多的周期）。在实践中，性能差异可能会大得多。

避免不可预测的分支

现代架构具有流水线功能，编译器正变得非常擅长重新排序代码以最大程度地减少由于内存访问而导致的延迟。当您的关键代码包含（不可预测的）分支时，很难或不可能预取数据。这将间接导致更多的缓存未命中。

这在这里解释得很好（感谢@0x90 的链接）：为什么处理排序数组比处理未排序数组更快？

避免虚函数

在c++的上下文中，virtual方法代表了关于缓存未命中的一个有争议的问题（普遍的共识是，在性能方面应该尽可能避免它们）。虚函数在查找过程中可能会导致缓存未命中，但这仅在不经常调用特定函数时才会发生（否则它可能会被缓存），因此这被某些人认为不是问题。有关此问题的参考，请查看：在 C++ 类中使用虚拟方法的性能成本是多少？

常见问题

具有多处理器缓存的现代架构中的一个常见问题称为错误共享。当每个单独的处理器尝试使用另一个内存区域中的数据并尝试将其存储在同一高速缓存行中时，就会发生这种情况。这会导致缓存线——其中包含另一个处理器可以使用的数据——被一次又一次地覆盖。实际上，在这种情况下，不同的线程通过引发缓存未命中来使彼此等待。另请参阅（感谢@Matt 的链接）：如何以及何时与缓存行大小对齐？

RAM 内存中缓存不佳的一个极端症状（这可能不是您在此上下文中的意思）是所谓的thrashing。当进程不断产生需要磁盘访问的页面错误（例如访问不在当前页面中的内存）时，就会发生这种情况。

Answer 2

除了@Marc Claesen 的回答，我认为缓存不友好代码的一个有启发性的经典示例是按列而不是按行扫描C 二维数组（例如位图图像）的代码。

一行相邻的元素在内存中也是相邻的，因此按顺序访问它们意味着按内存升序访问它们；这是缓存友好的，因为缓存倾向于预取连续的内存块。

相反，按列访问这些元素对缓存不友好，因为同一列上的元素在内存中彼此相距很远（特别是，它们的距离等于行的大小），所以当你使用这种访​​问模式时，你在内存中跳跃，可能会浪费缓存在内存中检索附近元素的努力。

而破坏表演所需要的只是从

// Cache-friendly version - processes pixels which are adjacent in memory
for(unsigned int y=0; y<height; ++y)
{
    for(unsigned int x=0; x<width; ++x)
    {
        ... image[y][x] ...
    }
}

到

// Cache-unfriendly version - jumps around in memory for no good reason
for(unsigned int x=0; x<width; ++x)
{
    for(unsigned int y=0; y<height; ++y)
    {
        ... image[y][x] ...
    }
}

在具有小缓存和/或使用大阵列（例如，当前机器上的 10+ 百万像素 24 bpp 图像）的系统中，这种效果可能非常显着（速度上几个数量级）；出于这个原因，如果您必须进行多次垂直扫描，通常最好先将图像旋转 90 度，然后再执行各种分析，从而将不友好缓存的代码限制在旋转中。

Answer 3

优化缓存使用很大程度上归结为两个因素。

参考地点

第一个因素（其他人已经提到过）是参考地点。不过，参考位置确实有两个维度：空间和时间。

• 空间

空间维度也归结为两件事：首先，我们希望将信息密集打包，以便更多信息适合有限的内存。这意味着（例如）您需要在计算复杂性方面进行重大改进，以证明基于由指针连接的小节点的数据结构是合理的。

其次，我们希望将一起处理的信息也放在一起。典型的缓存以“行”工作，这意味着当您访问某些信息时，附近地址的其他信息将与我们接触的部分一起加载到缓存中。例如，当我触摸一个字节时，缓存可能会在该字节附近加载 128 或 256 个字节。为了利用这一点，您通常希望将数据安排得最大限度地提高您也使用同时加载的其他数据的可能性。

仅举一个非常简单的例子，这可能意味着线性搜索与二分搜索相比可能比您预期的更具竞争力。从缓存行加载一个项目后，使用该缓存行中的其余数据几乎是免费的。只有当数据足够大以至于二进制搜索减少了您访问的缓存行数时，二进制搜索才会变得明显更快。

• 时间

时间维度意味着当您对某些数据进行一些操作时，您希望（尽可能）一次对该数据进行所有操作。

由于您已将其标记为 C++，因此我将指出一个相对缓存不友好设计的经典示例：std::valarray. valarray重载大多数算术运算符，因此我可以（例如）说a = b + c + d;（其中a、、b和都是 valarrays）对这些数组进行逐元素加法c。d

这样做的问题是它遍历一对输入，将结果放入一个临时的，遍历另一对输入，等等。对于大量数据，一次计算的结果可能会在用于下一次计算之前从缓存中消失，因此我们最终会在获得最终结果之前反复读取（和写入）数据。如果最终结果的每个元素都类似于(a[n] + b[n]) * (c[n] + d[n]);，我们通常更喜欢读取每个a[n],和一次b[n]，进行计算，写入结果，递增并重复，直到完成。²c[n]d[n]n

线路共享

第二个主要因素是避免线路共享。要理解这一点，我们可能需要备份并查看一下缓存是如何组织的。最简单的缓存形式是直接映射。这意味着主存中的一个地址只能存储在缓存中的一个特定位置。如果我们使用映射到缓存中同一位置的两个数据项，则效果不佳——每次我们使用一个数据项时，都必须从缓存中刷新另一个数据项，以便为另一个腾出空间。缓存的其余部分可能是空的，但这些项目不会使用缓存的其他部分。

为了防止这种情况，大多数缓存都是所谓的“集合关联”。例如，在 4 路组关联缓存中，主内存中的任何项目都可以存储在缓存中的 4 个不同位置中的任何一个。因此，当缓存要加载一个项目时，它会在这四个项目中查找最近最少使用的^{3 个}项目，将其刷新到主内存，并在其位置加载新项目。

问题可能相当明显：对于直接映射缓存，碰巧映射到同一缓存位置的两个操作数可能会导致不良行为。N 路组关联缓存将数量从 2 增加到 N+1。将缓存组织成更多“方式”需要额外的电路并且通常运行速度较慢，因此（例如）8192 路集关联缓存也很少是一个好的解决方案。

最终，这个因素在可移植代码中更难控制。您对数据放置位置的控制通常相当有限。更糟糕的是，从地址到缓存的确切映射在其他相似的处理器之间会有所不同。然而，在某些情况下，可能值得做一些事情，例如分配一个大缓冲区，然后只使用您分配的部分内容来确保数据不会共享相同的缓存行（即使您可能需要检测确切的处理器和采取相应的行动来做到这一点）。

• 虚假分享

还有另一个相关的项目称为“虚假共享”。这出现在多处理器或多核系统中，其中两个（或更多）处理器/内核具有独立的数据，但位于同一高速缓存行中。这迫使两个处理器/内核协调它们对数据的访问，即使每个处理器/内核都有自己的单独数据项。特别是如果两者交替修改数据，这可能会导致速度大幅下降，因为数据必须在处理器之间不断穿梭。这不能通过将缓存组织成更多“方式”或类似的方式来轻松解决。防止它的主要方法是确保两个线程很少（最好从不）修改可能位于同一高速缓存行中的数据（同样需​​要注意控制数据分配地址的难度）。

---

1. 那些熟悉 C++ 的人可能想知道这是否可以通过表达式模板之类的东西进行优化。我很确定答案是肯定的，这是可以做到的，如果是的话，这可能是一个相当大的胜利。然而，我不知道有人这样做过，而且考虑到很少有人这样做valarray，我至少会有点惊讶地看到有人这样做。

2. 如果有人想知道valarray（专为提高性能而设计）怎么会出现如此严重的错误，可以归结为一件事：它确实是为像旧的 Crays 这样的机器设计的，它使用快速的主内存并且没有缓存。对他们来说，这确实是一个近乎理想的设计。

3. 是的，我正在简化：大多数缓存并没有真正精确地测量最近最少使用的项目，但它们使用一些旨在接近该值的启发式算法，而不必为每次访问保留完整的时间戳。

Answer 4

欢迎来到面向数据的设计世界。基本的口头禅是排序、消除分支、批处理、消除virtual呼叫——所有步骤都朝着更好的位置迈进。

由于您使用 C++ 标记了问题，因此这里是强制性的典型 C++ 废话。Tony Albrecht 的Pitfalls of Object Oriented Programming也是对该主题的一个很好的介绍。

Answer 5

只是堆积：缓存不友好与缓存友好代码的经典示例是矩阵乘法的“缓存阻塞”。

朴素矩阵乘法如下所示：

for(i=0;i<N;i++) {
   for(j=0;j<N;j++) {
      dest[i][j] = 0;
      for( k=0;k<N;k++) {
         dest[i][j] += src1[i][k] * src2[k][j];
      }
   }
}

如果N很大，例如，如果N * sizeof(elemType)大于缓存大小，那么每次访问都src2[k][j]将是缓存未命中。

有许多不同的方法可以为缓存优化它。这是一个非常简单的示例：不是在内部循环中每个缓存行读取一个项目，而是使用所有项目：

int itemsPerCacheLine = CacheLineSize / sizeof(elemType);

for(i=0;i<N;i++) {
   for(j=0;j<N;j += itemsPerCacheLine ) {
      for(jj=0;jj<itemsPerCacheLine; jj+) {
         dest[i][j+jj] = 0;
      }
      for( k=0;k<N;k++) {
         for(jj=0;jj<itemsPerCacheLine; jj+) {
            dest[i][j+jj] += src1[i][k] * src2[k][j+jj];
         }
      }
   }
}

如果缓存线大小为 64 字节，并且我们在 32 位（4 字节）浮点数上进行操作，那么每个缓存线有 16 个项目。通过这个简单的转换，缓存未命中的数量减少了大约 16 倍。

更高级的转换在 2D 切片上运行，针对多个缓存（L1、L2、TLB）进行优化，等等。

谷歌搜索“缓存阻塞”的一些结果：

http://stumptown.cc.gt.atl.ga.us/cse6230-hpcta-fa11/slides/11a-matmul-goto.pdf

http://software.intel.com/en-us/articles/cache-blocking-techniques

优化缓存阻塞算法的精彩视频动画。

http://www.youtube.com/watch?v=IFWgwGMMrh0

循环平铺非常密切相关：

http://en.wikipedia.org/wiki/Loop_tiling

Answer 6

今天的处理器与许多级别的级联内存区域一起工作。因此 CPU 将在 CPU 芯片本身上有一堆内存。它可以非常快速地访问此内存。有不同级别的缓存，每一个的访问速度都比下一个慢（并且更大），直到您到达不在 CPU 上且访问速度相对慢得多的系统内存。

从逻辑上讲，对于 CPU 的指令集，您只需引用巨大虚拟地址空间中的内存地址。当您访问单个内存地址时，CPU 将去获取它。在过去，它只会获取那个单一的地址。但是今天 CPU 会在您请求的位周围获取一堆内存，并将其复制到缓存中。它假设如果您要求一个特定的地址，您很可能很快就会要求附近的地址。例如，如果您正在复制缓冲区，您将从连续地址读取和写入 - 一个接一个。

所以今天当你获取一个地址时，它会检查第一级缓存，看看它是否已经将该地址读入缓存，如果没有找到，那么这是一个缓存未命中，它必须进入下一级缓存找到它，直到它最终必须进入主内存。

缓存友好的代码尝试使访问在内存中保持紧密，以便最大限度地减少缓存未命中。

例如，假设您想复制一个巨大的二维表。它在内存中以连续的到达行组织，然后一行紧随其后。

如果您从左到右一次复制一行元素 - 那将是缓存友好的。如果您决定一次复制表一列，您将复制完全相同数量的内存 - 但它对缓存不友好。

Answer 7

需要澄清的是，不仅数据应该是缓存友好的，它对代码同样重要。这是对分支预测、指令重新排序、避免实际除法和其他技术的补充。

通常，代码越密集，存储它所需的缓存行就越少。这导致更多的高速缓存行可用于数据。

代码不应到处调用函数，因为它们通常需要一个或多个自己的缓存行，从而导致数据的缓存行更少。

函数应该从缓存行对齐友好的地址开始。尽管有（gcc）编译器开关用于此，但请注意，如果函数非常短，每个函数占用整个高速缓存行可能是浪费的。例如，如果三个最常用的函数可以放在一个 64 字节的高速缓存行中，那么这比如果每个函数都有自己的高速缓存行并导致两条高速缓存行可供其他用途使用的情况更少，则浪费更少。典型的对齐值可以是 32 或 16。

所以花一些额外的时间来使代码密集。测试不同的结构，编译和查看生成的代码大小和配置文件。

Answer 8

正如@Marc Claesen 提到的，编写缓存友好代码的方法之一是利用我们的数据存储结构。除此之外，编写缓存友好代码的另一种方式是：改变我们的数据存储方式；然后编写新代码来访问存储在这个新结构中的数据。

这在数据库系统如何线性化表的元组并存储它们的情况下是有意义的。存储表的元组有两种基本方法，即行存储和列存储。顾名思义，在行存储中，元组是按行存储的。让我们假设一个名为Product正在存储的表有 3 个属性，即int32_t key, char name[56]和int32_t price，所以一个元组的总大小是64字节。

我们可以通过创建一个大小为 N 的结构数组来模拟主内存中非常基本的行存储查询执行Product，其中 N 是表中的行数。这种内存布局也称为结构数组。所以 Product 的结构可以是：

struct Product
{
   int32_t key;
   char name[56];
   int32_t price'
}

/* create an array of structs */
Product* table = new Product[N];
/* now load this array of structs, from a file etc. */

类似地，我们可以通过创建 3 个大小为 N 的数组来模拟主内存中非常基本的列存储查询执行，每个数组对应Product表的每个属性。这种内存布局也称为数组结构。所以 Product 的每个属性的 3 个数组可以是：

/* create separate arrays for each attribute */
int32_t* key = new int32_t[N];
char* name = new char[56*N];
int32_t* price = new int32_t[N];
/* now load these arrays, from a file etc. */

Product现在，在加载了结构数组（行布局）和 3 个单独的数组（列布局）之后，我们的内存中的表上就有了行存储和列存储。

现在我们转到缓存友好代码部分。假设我们表上的工作负载使得我们对价格属性进行聚合查询。如

SELECT SUM(price)
FROM PRODUCT

对于行存储，我们可以将上面的 SQL 查询转换为

int sum = 0;
for (int i=0; i<N; i++)
   sum = sum + table[i].price;

对于列存储，我们可以将上面的 SQL 查询转换为

int sum = 0;
for (int i=0; i<N; i++)
   sum = sum + price[i];

列存储的代码将比此查询中的行布局代码更快，因为它只需要属性的一个子集，而在列布局中，我们正在这样做，即只访问价格列。

假设高速缓存行大小为64字节。

在读取缓存行时的行布局的情况下，仅cacheline_size/product_struct_size = 64/64 = 1读取 1( ) 元组的价格值，因为我们的 struct 大小为 64 字节并且它填满了我们的整个缓存行，因此对于每个元组都会发生缓存未命中以防万一的行布局。

在读取缓存行时的列布局情况下，读取 16( cacheline_size/price_int_size = 64/4 = 16) 个元组的价格值，因为存储在内存中的 16 个连续价格值被带入缓存，因此每第 16 个元组发生一次缓存未命中，以防万一列布局。

因此，在给定查询的情况下，列布局将更快，并且在对表的列子集进行此类聚合查询时更快。您可以使用TPC-H基准测试中的数据自己尝试这样的实验，并比较两种布局的运行时间。关于面向列的数据库系统的维基百科文章也很好。

因此，在数据库系统中，如果事先知道查询工作负载，我们可以将数据存储在适合工作负载查询的布局中，并从这些布局中访问数据。在上面的例子中，我们创建了一个列布局并改变了我们的代码来计算总和，这样它就变得缓存友好了。

Answer 9

请注意，缓存不仅仅缓存连续内存。它们有多行（至少 4 行），因此通常可以同样有效地存储不连续和重叠的内存。

上述所有示例都缺少测量基准。关于性能有很多神话。除非你测量它，否则你不知道。除非您有可衡量的改进，否则不要使您的代码复杂化。