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

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

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

197971 次浏览
小开
最佳答案

初步

在现代计算机上，只有最低级别的内存结构（登记册）可以在一个时钟周期内移动数据。然而，寄存器非常昂贵，大多数计算机内核的寄存器不到几十个。在内存谱的另一端（DRAM），内存非常便宜（即字面上的便宜几百万倍），但在请求后需要数百个周期来接收数据。为了弥合超快和昂贵以及超慢和便宜之间的差距，速度和成本不断下降的高速缓冲存储器被命名为L1、L2、L3。我们的想法是，大多数执行代码将经常触及一小部分变量，其余的（更大的变量集）不经常。如果处理器在L1缓存中找不到数据，那么它会在L2缓存中查找。如果没有，那么L3缓存，如果没有，主存储器。这些“未命中”中的每一个都在时间上是昂贵的。

（类比是缓存内存是系统内存，就像系统内存是硬盘存储一样。硬盘存储超级便宜但非常慢）。

缓存是减少延迟影响的主要方法之一。套用Herb Sutter（参见下面的链接）：增加带宽很容易，但我们买不到解决延迟的方法。

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

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

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

缓存友好代码的主要概念

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

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

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

使用适当的容器

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

Bjarne Stroustrup在这个youtube剪辑中给出了一个非常好的例子（感谢@Mohammad阿里Baydoun的链接！）。

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

只要有可能，尽量调整数据结构和计算顺序，以最大限度地利用缓存。这方面的一种常见技术是缓存阻塞（Archive.org版本），这在高性能计算中非常重要（cfr.例如ATLAS）。

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

另一个简单的例子，领域中的许多人有时会忘记，是用于存储二维数组的列主排序（例如9;fortran&9;" rel="tag">fortran，9;matlab&9;" rel="tag">matlab）与行主排序（例如9;c&9;" rel="tag">c，）。例如，考虑以下矩阵：

1 23 4

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

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

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

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

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

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

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++类中使用虚拟方法的性能成本是多少？9;c++&在C++类中使用虚拟方法的性能成本是多少？9;" rel="tag">c++的上下文中，virtual方法代表了一个关于缓存未命中的有争议的问题（普遍的共识是，在性能方面应该尽可能避免它们）。虚拟函数在查找过程中会导致缓存未命中，但这只发生在如果特定的函数不经常被调用（否则它很可能被缓存），所以这被一些人认为不是问题。有关此问题的参考，请查看：在C++类中使用虚拟方法的性能成本是多少？

常见问题

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

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

小开

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

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

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

破坏表演的唯一方法就是从

// Cache-friendly version - processes pixels which are adjacent in memoryfor(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 reasonfor(unsigned int x=0; x<width; ++x){for(unsigned int y=0; y<height; ++y){... image[y][x] ...}}

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

小开

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

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

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

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

举个例子，想象你想复制一个巨大的二维表。它在内存中以连续的到达行组织，一行紧随下一行。

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

小开

欢迎来到面向数据设计的世界。基本的口头禅是排序、消除分支、批处理、消除virtual调用——所有步骤都是为了更好的局部性。

既然你用C++标记了这个问题，这里是强制性的典型的C++废话。Tony Albrecht的面向对象编程的缺陷也是对这个主题的一个很好的介绍。

小开

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

朴素矩阵乘法看起来像：

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

小开

优化缓存使用主要归结为两个因素。

引用的地方性

第一个因素（其他人已经提到过）是指称的局部性，指称的局部性实际上有两个维度：空间和时间。

  • 空间

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

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

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

  • 时间

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

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

这种方法的问题在于它遍历一对输入，将结果放入临时输入，遍历另一对输入，依此类推。对于大量数据，一次计算的结果可能在下一次计算中使用之前从缓存中消失，因此我们最终会重复读取（和写入）数据，然后才能得到最终结果。如果最终结果的每个元素类似于(a[n] + b[n]) * (c[n] + d[n]);，我们通常更喜欢读取每个a[n]、b[n]、c[n]和d[n]一次，进行计算，写入结果，增加n并重复'直到我们完成。2

线路共享

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

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

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

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

  • 虚假分享

还有一个相关的项目，称为“错误共享”。这发生在多处理器或多核系统中，其中两个（或更多）处理器/内核具有单独的数据，但落在同一缓存行中。这迫使两个处理器/内核协调它们对数据的访问，即使每个处理器/内核都有自己的单独数据项。特别是如果两者交替修改数据，这可能会导致巨大的速度减慢，因为数据必须在处理器之间不断穿梭。这不容易通过将缓存组织成更多“方式”或类似的方式来解决。防止它的主要方法是确保两个线程很少（最好永远不会）修改可能在同一缓存行中的数据（对于控制分配数据的地址的难度有相同的警告）。

  1. 了解C++的人可能想知道这是否可以通过表达式模板等方式进行优化。我很确定答案是肯定的，这是可以做到的，如果可以，那可能是一个相当大的胜利。然而，我不知道有人这样做过，但是，考虑到valarray被使用的很少，看到有人这样做，我至少也会有点惊讶。

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

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

小开

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

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

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

一个函数应该从一个缓存行对齐友好的地址开始。尽管有（gcc）编译器开关来实现这一点，但请注意，如果函数很短，每个函数占用整个缓存行可能是浪费的。例如，如果三个最常用的函数适合一个64字节的缓存行，这比每个函数都有自己的行并导致两条缓存行不可用于其他用途的浪费要少。典型的对齐值可能是32或16。

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

小开

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

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

小开

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

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

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

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. */

类似地，我们可以通过创建一个大小为N的3个数组来模拟主存储器中非常基本的列存储查询执行，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. */

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

现在我们继续讨论缓存友好的代码部分。假设我们表上的工作负载是这样的，我们有一个关于价格属性的聚合查询。例如 

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字节。

在行布局的情况下，当读取缓存行时，只读取1（cacheline_size/product_struct_size = 64/64 = 1）元组的价格值，因为我们的结构大小为64字节，它填满了我们的整个缓存行，所以对于每个元组，在行布局的情况下都会发生缓存未命中。

在列布局的情况下，当读取高速缓存行时，读取16（cacheline_size/price_int_size = 64/4 = 16）元组的价格值，因为存储在内存中的16个连续价格值被带入高速缓存，所以对于每16个元组，在列布局的情况下都会发生高速缓存未命中。

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

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


提交答案