“缓存不友好代码”和“缓存友好”代码之间有什么区别？
如何确保编写高效缓存代码？
在现代计算机上，只有最低级别的存储器结构（寄存器）可以在单个时钟周期内移动数据。然而，寄存器非常昂贵，并且大多数计算机核心具有少于几十个寄存器（总数为几百到几千字节）。在存储器频谱（DRAM）的另一端，存储器非常便宜（即，便宜几百万倍），但在接收数据的请求之后需要数百个周期。为了弥合超快速和昂贵以及超慢速和廉价之间的这种差距，缓存存储器，称为L1，L2，L3，速度和成本降低。我们的想法是，大多数执行代码经常会遇到一小组变量，其余的（很多变量集）很少。如果处理器无法在L1缓存中找到数据，那么它将在L2缓存中查找。如果不存在，则L3缓存，如果不存在，则为主存。这些“未命中”中的每一个都是昂贵的。
（类比是缓存是系统内存，因为系统内存太硬盘存储。硬盘存储超级便宜但速度很慢）。
缓存是减少延迟影响的主要方法之一。用Herb Sutter解释（参见下面的链接）：增加带宽很容易，但我们无法摆脱延迟。
始终通过内存层次结构检索数据（最小==最快到最慢）。缓存命中/未命中通常是指CPU中最高级缓存中的命中/未命中 - 最高级别I表示最大==最慢。缓存命中率对性能至关重要，因为每次缓存未命中都会导致从RAM中获取数据（或者更糟糕......），这需要花费大量时间（RAM需要数百个周期，HDD需要数千万个周期）。相比之下，从（最高级别）高速缓存读取数据通常只需要少量的周期。
在现代计算机体系结构中，性能瓶颈是使CPU死亡（例如访问RAM或更高）。这只会随着时间的推移而变得更糟。处理器频率的增加目前不再与提高性能相关。问题是内存访问。因此，CPU中的硬件设计工作目前主要集中在优化高速缓存，预取，流水线和并发性上。例如，现代CPU在高速缓存上花费大约85％的死亡，在存储/移动数据时花费高达99％！
关于这个问题有很多话要说。以下是有关缓存，内存层次结构和正确编程的一些很好的参考：
缓存友好代码的一个非常重要的方面是关于the principle of locality，其目标是将相关数据放在内存中以允许有效的缓存。就CPU缓存而言，了解缓存行以了解其工作原理非常重要：How do cache lines work?
以下特定方面对优化缓存非常重要：
使用适当的c++容器
缓存友好与缓存不友好的一个简单例子是c++的std::vector与std::list。 std::vector的元素存储在连续的内存中，因此访问它们比访问std::list中的元素更加缓存友好，this youtube clip将其内容存储在整个地方。这是由于空间局部性。
Bjarne Stroustrup在cache blocking中给出了一个非常好的例子（感谢@Mohammad Ali Baydoun的链接！）。
不要忽视数据结构和算法设计中的缓存
尽可能尝试以允许最大程度地使用缓存的方式调整数据结构和计算顺序。这方面的一个常用技术是(Archive.org version) ATLAS，它在高性能计算中非常重要（例如fortran）。
了解并利用隐含的数据结构
另一个简单的例子是该领域的许多人有时会忘记的是柱主要（例如matlab，c）与行主要排序（例如c++，1 2
3 4
）用于存储二维数组。例如，请考虑以下矩阵：
1 2 3 4在行主要排序中，它作为1 3 2 4存储在内存中;在列主要排序中，这将存储为M。很容易看出，不利用此排序的实现将很快遇到（容易避免！）缓存问题。不幸的是，我经常在我的领域（机器学习）看到这样的东西。 @MatteoItalia在他的回答中更详细地展示了这个例子。
当从存储器中获取矩阵的某个元素时，它附近的元素也将被提取并存储在高速缓存行中。如果利用排序，这将导致更少的内存访问（因为后续计算所需的接下来的几个值已经在高速缓存行中）。
为简单起见，假设高速缓存包含单个高速缓存行，该高速缓存行可以包含2个矩阵元素，并且当从存储器中取出给定元素时，下一个也是如此。假设我们想要对上面的示例2x2矩阵中的所有元素求和（让我们称之为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
中更改行索引）：
Why is processing a sorted array faster than processing an unsorted array?
在这个简单的例子中，利用排序大约使执行速度加倍（因为内存访问需要比计算总和更多的周期）。在实践中，性能差异可能更大。
避免不可预测的分支
现代架构的特色是流水线和编译器在重新排序代码方面变得非常擅长，以最大限度地减少因内存访问造成的延迟。当您的关键代码包含（不可预测的）分支时，很难或不可能预取数据。这将间接导致更多缓存未命中。
这里解释得非常好（感谢@ 0x90的链接）：c++
避免使用虚函数
在virtual的背景下，What is the performance cost of having a virtual method in a C++ class?方法在缓存未命中方面代表了一个有争议的问题（普遍的共识是，在性能方面应该尽可能避免它们）。虚拟函数在查找过程中可能会导致缓存未命中，但只有在不经常调用特定函数时才会发生这种情况（否则它可能会被缓存），所以这被一些人视为非问题。有关此问题的参考，请查看：false sharing
具有多处理器高速缓存的现代体系结构中的常见问题称为How and when to align to cache line size?。当每个单独的处理器尝试使用另一个内存区域中的数据并尝试将其存储在同一缓存行中时，会发生这种情况。这会导致缓存行 - 包含另一个处理器可以使用的数据 - 一次又一次地被覆盖。实际上，在这种情况下，不同的线程会通过引发缓存未命中而使彼此等待。另见（感谢@Matt的链接）：thrashing
RAM内存中缓存不佳的极端症状（可能不是你在这种情况下的意思）就是所谓的// 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] ...
}
}
。当进程连续生成需要磁盘访问的页面错误（例如，访问不在当前页面中的内存）时，会发生这种情况。
除了@Marc Claesen的回答之外，我认为缓存不友好代码的一个有启发性的经典示例是按列而不是按行扫描C二维数组（例如位图图像）的代码。
一行中相邻的元素在存储器中也是相邻的，因此按顺序访问它们意味着以递增的存储顺序访问它们;这是缓存友好的，因为缓存倾向于预取连续的内存块。
相反，逐列访问这些元素是缓存不友好的，因为同一列上的元素在内存中彼此远离（特别是，它们的距离等于行的大小），所以当你使用这种访问模式时在内存中跳来跳去，可能会浪费在内存中检索附近元素的缓存。
而破坏性能所需的一切就是从中走出来
// 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] ...
}
}
至
std::valarray在具有小缓存和/或使用大阵列（例如，当前机器上的10百万像素24 bpp图像）的系统中，这种效果可能非常显着（速度的几个数量级）;因此，如果您必须进行多次垂直扫描，通常最好先旋转90度的图像，然后再执行各种分析，将缓存不友好的代码限制为旋转。
优化缓存使用主要归结为两个因素。
第一个因素（其他人已经提到过）是参考地点。参考的位置确实有两个维度：空间和时间。
空间维度也归结为两件事：首先，我们希望密集地收集信息，因此更多信息将适合有限的内存。这意味着（例如）您需要在计算复杂性方面进行重大改进，以证明基于指针连接的小节点的数据结构。
其次，我们希望将一起处理的信息也放在一起。典型的缓存在“行”中工作，这意味着当您访问某些信息时，附近地址的其他信息将与我们触摸的部分一起加载到缓存中。例如，当我触摸一个字节时，缓存可能会在该字节附近加载128或256个字节。为了利用这一点，您通常希望安排的数据最大化您同时使用同时加载的其他数据的可能性。
对于一个非常简单的例子，这可能意味着线性搜索与二进制搜索相比可能比您预期的更具竞争力。一旦从缓存行加载了一个项目，使用该缓存行中的其余数据几乎是免费的。只有当数据足够大以至于二进制搜索减少了您访问的缓存行数时，二进制搜索才会明显变得更快。
时间维度意味着当您对某些数据执行某些操作时，您希望（尽可能）一次对该数据执行所有操作。
既然你已将其标记为C ++，我将指出一个相对缓存不友好设计的经典示例：valarray。 a = b + c + d;重载大多数算术运算符，所以我可以（例如）说a（其中b，c，d和(a[n] + b[n]) * (c[n] + d[n]);都是valarray）来对这些数组进行元素添加。
这样做的问题在于它遍历一对输入，将结果放入临时，遍历另一对输入，依此类推。对于大量数据，一次计算的结果可能会在用于下一次计算之前从缓存中消失，因此我们最终会在获得最终结果之前重复读取（和写入）数据。如果最终结果的每个元素都像a[n]，我们通常更喜欢读每个b[n]，c[n]，d[n]和n一次，做计算，写结果，增加valarray并重复'直到我们完成.2
第二个主要因素是避免线路共享。要理解这一点，我们可能需要备份并查看缓存的组织方式。最简单的缓存形式是直接映射。这意味着主存储器中的一个地址只能存储在缓存中的一个特定位置。如果我们使用两个映射到缓存中相同位置的数据项，它会很糟糕 - 每次我们使用一个数据项时，另一个必须从缓存中刷新以便为另一个数据项腾出空间。缓存的其余部分可能为空，但这些项不会使用缓存的其他部分。
为了防止这种情况，大多数缓存都被称为“set associative”。例如，在4路组关联高速缓存中，主存储器中的任何项目都可以存储在高速缓存中的4个不同位置中的任何位置。因此，当缓存要加载项目时，它会查找这四项中最近最少使用的3项，将其刷新到主内存，并将新项目加载到其位置。
问题可能相当明显：对于直接映射缓存，碰巧映射到同一缓存位置的两个操作数可能导致不良行为。 N路组关联高速缓存将数量从2增加到N + 1。将缓存组织成更多“方式”需要额外的电路并且通常运行得更慢，因此（例如）8192路组关联缓存也很少是一个好的解决方案。
最终，这个因素在便携式代码中更难以控制。您对数据放置位置的控制通常相当有限。更糟糕的是，从地址到高速缓存的确切映射在其他类似处理器之间变化。但是，在某些情况下，可能值得做一些事情，比如分配一个大缓冲区，然后只使用你分配的部分内容来确保数据共享相同的缓存行（即使你可能需要检测确切的处理器和相应地采取行动）。
还有另一个相关项目称为“虚假共享”。这出现在多处理器或多核系统中，其中两个（或更多）处理器/核心具有独立的数据，但属于同一高速缓存行。这会强制两个处理器/内核协调对数据的访问，即使每个处理器/内核都有自己独立的数据项。特别是如果两者交替修改数据，这可能导致大幅减速，因为数据必须在处理器之间不断地穿梭。通过将缓存组织成更多“方式”或任何类似的方式，这都无法轻易解决。防止它的主要方法是确保两个线程很少（最好是从不）修改可能位于同一缓存行中的数据（对于控制分配数据的地址的难度有相同的警告）。
valarray的使用率很低，看到有人这样做，我至少会感到有些惊讶。virtual（专为性能而设计）是如何造成这种严重错误的，那么它归结为一件事：它真的是为像老款Crays这样的机器设计的，它们使用快速主内存而没有缓存。对他们来说，这确实是一个近乎理想的设计。欢迎来到面向数据的设计世界。基本的口头禅是排序，消除分支，批量，消除typical C++ Bullshit呼叫 - 所有步骤朝着更好的地方。
既然您用C ++标记了问题，那么这就是强制性的Pitfalls of Object Oriented Programming。托尼·阿尔布雷希特的for(i=0;i<N;i++) {
for(j=0;j<N;j++) {
dest[i][j] = 0;
for( k==;k<N;i++) {
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];
}
}
}
}
的每次访问都将是缓存未命中。
有许多不同的方法可以优化缓存。这是一个非常简单的示例：不是在内部循环中每个缓存行读取一个项目，而是使用所有项目：
http://stumptown.cc.gt.atl.ga.us/cse6230-hpcta-fa11/slides/11a-matmul-goto.pdf
如果高速缓存行大小为64字节，并且我们在32位（4字节）浮点数上运行，则每个高速缓存行有16个项目。通过这种简单的转换，缓存未命中数减少了大约16倍。
Fancier转换在2D图块上运行，针对多个缓存（L1，L2，TLB）进行优化，等等。
谷歌搜索“缓存阻塞”的一些结果：
http://software.intel.com/en-us/articles/cache-blocking-techniques
http://www.youtube.com/watch?v=IFWgwGMMrh0
一个优化的缓存阻塞算法的精彩视频动画。
http://en.wikipedia.org/wiki/Loop_tiling
循环平铺非常密切相关：
Product
今天的处理器可以处理多级级联存储区域。因此CPU将拥有CPU芯片本身的一堆内存。它可以非常快速地访问这个内存。有一个不同级别的缓存，每个缓存访问（和更大）比下一个更慢，直到你到达不在CPU上的系统内存，并且访问速度相对慢。
从逻辑上讲，对于CPU的指令集，您只需在巨大的虚拟地址空间中引用内存地址即可。当您访问单个内存地址时，CPU将获取它。在过去，它只会获取该地址。但是今天CPU会在你要求的位周围获取一堆内存，并将其复制到缓存中。它假定如果您要求特定地址很可能很快就会要求附近的地址。例如，如果您要复制缓冲区，则可以从连续的地址读取和写入 - 一个接着一个。
所以今天当你获取一个地址时，它会检查第一级缓存以查看它是否已经将该地址读入缓存，如果它没有找到它，那么这是一个缓存未命中，它必须转到下一级别缓存找到它，直到它最终必须进入主内存。
缓存友好代码尝试将访问保持在内存中，以便最大限度地减少缓存未命中。
所以一个例子就是想象你想复制一个巨大的二维表。它在内存中连续排列到达行，后一行紧跟着一行。
如果您从左到右一次一行地复制元素 - 这将是缓存友好的。如果您决定一次将表复制一列，则可以复制完全相同的内存量 - 但这将是缓存不友好的。
需要澄清的是，不仅数据应该是缓存友好的，它对代码同样重要。这是分支预测，指令重新排序，避免实际划分和其他技术的补充。
通常，代码越密集，存储它所需的缓存行就越少。这导致更多高速缓存行可用于数据。
代码不应该遍布整个地方的函数，因为它们通常需要一个或多个自己的缓存行，从而导致数据的缓存行更少。
函数应该从高速缓存行对齐友好的地址开始。虽然有（gcc）编译器开关，但是要注意，如果函数非常短，则每个函数占用整个高速缓存行可能是浪费。例如，如果最常用的三个函数适合一个64字节高速缓存行，那么与每个高速缓存行具有自己的行并且导致两个高速缓存行不太可用于其他用途相比，这样做更少浪费。典型的对齐值可以是32或16。
因此，花一些额外的时间来使代码密集。测试不同的构造，编译并查看生成的代码大小和配置文件。
正如@Marc Claesen所提到的，编写缓存友好代码的方法之一是利用存储数据的结构。除了编写缓存友好代码的另一种方法是：改变我们的数据存储方式;然后编写新代码来访问存储在这个新结构中的数据。
这在数据库系统如何线性化表的元组并存储它们的情况下是有意义的。存储表的元组有两种基本方法，即行存储和列存储。在行存储中，顾名思义，元组以行方式存储。让我们假设一个名为int32_t key, char name[56]的表存储了3个属性，即int32_t price和64，所以元组的总大小是Product字节。
我们可以通过创建一个大小为N的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是表中的行数。这种内存布局也称为结构数组。所以Product的结构可以是：
Product类似地，我们可以通过创建3个大小为N的数组，为/* 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个数组可以是：
Product现在，在加载结构数组（行布局）和3个单独的数组（列布局）之后，我们在内存中的SELECT SUM(price)
FROM PRODUCT
表上有行存储和列存储。
现在我们转到缓存友好代码部分。假设我们表上的工作负载是这样的，我们在price属性上有一个聚合查询。如
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];
对于列存储，我们可以将上面的SQL查询转换为
64列存储的代码将比此查询中的行布局的代码更快，因为它只需要属性的子集，而在列布局中，我们只是访问价格列。
假设缓存行大小为cacheline_size/product_struct_size = 64/64 = 1字节。
在读取缓存行时行布局的情况下，只读取1（cacheline_size/price_int_size = 64/4 = 16）元组的价格值，因为我们的结构大小为64字节，它填满了我们的整个缓存行，因此对于每个元组，缓存未命中行布局的情况。
在读取高速缓存行的列布局的情况下，读取16（TPC-H）元组的价格值，因为存储在存储器中的16个连续价格值被带入高速缓存，因此对于每第16个元组，如果出现高速缓存未命中列布局。
因此，在给定查询的情况下，列布局将更快，并且在表的列的子集上的此类聚合查询中更快。您可以使用wikipedia基准测试数据自己尝试这样的实验，并比较两种布局的运行时间。关于面向列的数据库系统的qazxswpoi文章也很好。
因此，在数据库系统中，如果事先知道查询工作负载，我们可以将数据存储在布局中，这些布局适合工作负载中的查询并从这些布局访问数据。在上面的示例中，我们创建了一个列布局，并将我们的代码更改为计算总和，以便它变得缓存友好。
请注意，缓存不仅仅缓存连续内存。它们有多条线（至少4条），因此通常可以有效地存储不连续和重叠的存储器。
所有上述示例中缺少的是测量基准。关于表现有很多神话。除非你测量它，否则你不知道。除非您有明确的改进，否则不要使代码复杂化。