什么是“缓存”
“ 缓存不友好的代码 ”和“ 缓存友好的 ”代码有什么区别？
我怎样才能确保我编写缓存高效的代码？
预赛
在现代计算机上，只有最低级别的内存结构（ 寄存器 ）可以在单个时钟周期内移动数据。 但是，寄存器非常昂贵，大多数计算机内核的寄存器少于几十个（总共几百或几千个字节）。 在内存频谱（ DRAM ）的另一端，内存非常便宜（即便宜数百万次），但在接收数据请求后需要数百个周期。 为了弥补超高速和昂贵以及超慢和廉价之间的差距， 高速缓存存储器被称为L1，L2，L3，速度和成本都在下降。 这个想法是，大多数执行代码通常会碰到一小部分变量，而其他变量（更大的一组变量）很少。 如果处理器无法在L1缓存中找到数据，则会在L2缓存中查找。 如果不存在，则L3缓存，如果不存在，则存储主内存。 这些“错失”中的每一个在时间上都很昂贵。
（比较而言，缓存是指系统内存，因为系统内存是硬盘存储。硬盘存储非常便宜，但速度很慢）。
缓存是减少延迟影响的主要方法之一（参见我在开始时链接的Herb Sutter谈话）。 为了解释Herb Sutter（cfr。links below）： 增加带宽很容易，但我们无法从延迟中购买我们的方式 。
数据总是通过内存层次结构检索（最小==最快到最慢）。 缓存命中/未命中通常是指CPU中最高级别缓存中的命中/未命中 - 最高级别是指最慢=最慢。 缓存命中率对于性能至关重要，因为每次缓存未命中都会导致从RAM（或更糟糕的）中提取数据，这需要花费大量时间（RAM数百个周期，HDD数千万个周期）。 相比之下，从（最高级别）缓存中读取数据通常只需要几个周期。
在现代计算机体系结构中，性能瓶颈是让CPU死掉（例如访问RAM或更高）。 随着时间的推移，这只会变得更糟。 处理器频率的增加目前不再与提高性能相关。 问题是内存访问。 因此CPU中的硬件设计工作目前主要集中于优化高速缓存，预取，管道和并发。 例如，现代CPU在缓存上花费约85％，在存储/移动数据上花费高达99％！
关于这个问题有很多需要说的。 以下是关于缓存，内存层次结构和正确编程的一些很好的参考资料：
缓存友好代码的主要概念
缓存友好代码的一个非常重要的方面是关于局部性原则 ，其目标是将相关数据放在内存中以允许有效的缓存。 就CPU高速缓存而言，了解高速缓存行以了解其工作原理非常重要：高速缓存行如何工作？
以下特定方面对优化高速缓存非常重要：
使用适当的c ++容器
一个简单的缓存友好与缓存不友好的例子是c ++的std::vector与std::list 。 std::vector元素存储在连续的内存中，因此访问它们比访问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内存中缓存不良的极端症状（这可能不是您在这种情况下的含义）是所谓的颠簸。 当进程不断产生页面错误（例如，访问不在当前页面中的内存）而需要磁盘访问时，会发生这种情况。
除了@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+百万像素24bpp图像），这种效果可能相当戏剧化（速度的几个数量级）; 因此，如果您必须进行多次垂直扫描，通常最好先旋转90度的图像，稍后再执行各种分析，将缓存不友好的代码限制为旋转。
优化缓存使用主要归结为两个因素。
参考地点
第一个因素（其他人已经提到）是参考的地点。 参考地点确实有两个方面：空间和时间。
空间维度也归结为两件事：首先，我们想要密集包装我们的信息，所以更多的信息将适用于有限的记忆。 这意味着（例如）您需要计算复杂性的重大改进来证明基于由指针连接的小节点的数据结构。
其次，我们希望将一起处理的信息放在一起。 一个典型的缓存工作在“线路”，这意味着当你访问一些信息时，附近地址的其他信息将被加载到缓存中，并与我们触及的部分相关联。 例如，当我触摸一个字节时，高速缓存可能会在该字段附近加载128或256个字节。 为了充分利用这些优势，您通常需要安排数据，以最大限度地提高您还可以使用同时加载的其他数据的可能性。
只是一个非常简单的例子，这可能意味着线性搜索比二元搜索更有竞争力。 一旦你从缓存行加载了一个项目，使用该缓存行中的其余数据几乎是免费的。 只有数据足够大，二分查找才能减少您访问的缓存行数时，二分查找速度才会明显加快。
时间维度意味着当您对某些数据执行某些操作时，您希望（尽可能）一次对该数据执行所有操作。
既然你已经把它标记为C ++，我会指出一个相对缓存不友好的设计的典型例子： std::valarray 。 valarray重载了大多数算术运算符，所以我可以（例如）说a = b + c + d; （其中a ， b ， c和d都是valarrays）来完成这些数组的元素相加。
与此相关的问题是它通过一对输入，将结果放入一个临时值，遍历另一对输入，等等。 有了大量的数据，一次计算的结果可能会在下一次计算中使用之前从缓存中消失，所以我们在获得最终结果之前会重复读取（并写入）数据。 如果最终结果的每个元素都是(a[n] + b[n]) * (c[n] + d[n]); ，我们通常宁愿每读一遍a[n] ， b[n] ， c[n]和d[n] ，做计算，写结果，递增n并重复直到我们完成。
线路共享
第二个主要因素是避免线路共享。 为了理解这一点，我们可能需要备份并查看缓存的组织方式。 直接映射最简单的缓存形式。 这意味着主内存中的一个地址只能存储在缓存中的一个特定地点。 如果我们使用映射到缓存中相同位置的两个数据项，那么它工作得很糟糕 - 每次我们使用一个数据项时，必须从缓存中清除另一个数据项，以便为另一个数据项腾出空间。 缓存的其余部分可能是空的，但这些项目不会使用缓存的其他部分。
为了防止这种情况，大多数缓存都是所谓的“集合关联”。 例如，在4路组关联高速缓存中，主存中的任何项目都可以存储在高速缓存的4个不同位置中的任意位置。 因此，当缓存要加载一个项目时，它会在这四个项目中查找最近最少使用的项目，将其刷新到主内存中，然后将新项目加载到它的位置。
这个问题可能相当明显：对于直接映射的缓存，碰巧映射到相同缓存位置的两个操作数可能导致不良行为。 N路组关联缓存将数量从2增加到N + 1。 将缓存组织成更多的“途径”需要额外的电路，并且通常运行速度较慢，因此（例如）8192路组相关缓存很少是一个好的解决方案。
最终，这个因素在便携式代码中更难以控制。 您对数据放置位置的控制通常相当有限。 更糟糕的是，从地址到缓存的确切映射在其他类似处理器之间有所不同。 然而，在某些情况下，可能需要分配一个较大的缓冲区，然后仅使用您分配的部分内容来确保数据共享相同的缓存行（即使您可能需要检测确切的处理器和采取行动做到这一点）。
还有另一个名为“虚假分享”的相关项目。 这出现在多处理器或多核系统中，其中两个（或更多）处理器/内核具有独立的数据，但落入相同的高速缓存行中。 这迫使两个处理器/内核协调它们对数据的访问，即使每个处理器都有自己独立的数据项。 特别是如果两者交替修改数据，这可能会导致大量减速，因为数据必须在处理器之间不停地传送。 这不能通过将缓存组织成更多的“方式”或类似的东西来解决。 防止它的主要方式是确保两个线程很少（最好永远不会）修改可能在同一个缓存行中的数据（对于控制分配数据的地址的难度有相同的警告）。
那些熟悉C ++的人可能会想知道这是否可以通过表达式模板等方式进行优化。 我很确定答案是肯定的，可以做到，如果是的话，这可能是一个非常可观的胜利。 然而，我并没有意识到有人这么做过，并且，由于valarray得到了很少的使用，我也至少有点惊讶于看到有人这样做。
如果有人想知道valarray （专为性能而设计）如何可能会出现这种严重错误，那么可以归结为一件事情：它确实是为像Crays这样的机器设计的，它使用了快速主内存并且没有缓存。 对他们来说，这确实是一个近乎理想的设计。
是的，我正在简化：大多数缓存并不真正衡量最近最少使用的项目，但他们使用了一些启发式方法，旨在接近该方法，而不必为每个访问保留一个完整的时间戳。
上一篇: What is a "cache