什么是“caching友好”的代码？
有人可能举一个“caching不友好的代码”和“caching友好”的代码版本的例子？
我怎样才能确保我编写caching高效的代码？
预赛
在现代计算机上，只有最低级别的内存结构（ 寄存器 ）可以在单个时钟周期内移动数据。 但是，寄存器非常昂贵，大多数计算机内核的寄存器less于几十个（总共几百到几千个字节 ）。 在内存频谱（ DRAM ）的另一端，内存非常便宜（即便宜几百万次 ），但是在请求接收数据之后需要数百个周期。 为了弥补这种超高速，昂贵和超低速，廉价的差距， 高速caching和低成本的命名为L1，L2，L3。 这个想法是，大多数执行代码会经常碰到一小部分variables，而其余部分（更大的一组variables）很less。 如果处理器在L1caching中找不到数据，则会在L2caching中查找。 如果不存在，那么L3caching，如果不存在，主存储器。 这些“错失”中的每一个在时间上是昂贵的。
（比如高速缓冲存储器就是系统内存，因为系统内存是硬盘存储的，硬盘存储是非常便宜的，但速度很慢）。
caching是减less等待时间影响的主要方法之一（参见我在开始时链接的Herb Sutter谈话）。 用Herb Sutter来解释（cfr。links below）： 增加带宽是很容易的，但是我们不能从延迟中购买我们的方式 。
数据总是通过内存层次结构检索（最小==最快到最慢）。 高速caching命中/未命中通常是指在CPU中的最高级别的高速caching中的命中/未命中 – 最高级别我是最大=最慢的。 caching命中率对于性能至关重要，因为每次caching未命中都会导致从RAM（或更糟糕的）中获取数据，这花费了大量的时间（RAM数百个周期，HDD数千万个周期）。 相比之下，从（最高级别）caching中读取数据通常只需要几个周期。
在现代计算机体系结构中，性能瓶颈是使CPU死亡（例如，访问RAM或更高）。 这只会随着时间的推移而变得更糟。 处理器频率的增加目前不再与提高性能相关。 问题是内存访问。 因此，CPU中的硬件devise工作目前主要集中于优化高速caching，预取，pipe道和并发。 例如，现代CPU在高速caching上花费约85％，在存储/移动数据上高达99％！
关于这个问题有很多要说的。 以下是关于caching，内存层次结构和正确编程的一些很好的参考资料：
- Agner雾的页面 。 在他的优秀文档中，您可以find涵盖从汇编到C ++的各种语言的详细示例。
- 如果您正在观看video，我强烈build议查看Herb Sutter关于机器架构（youtube）的讨论 （特别是在12:00以后！）。
- 关于内存优化的幻灯片由Christer Ericson （技术总监@索尼）
- LWN.net的文章“ 每个程序员应该知道什么内存 ”
caching友好代码的主要概念
caching友好代码的一个非常重要的方面是关于局部性原则 ，其目标是将相关数据放在内存中以允许有效的caching。 就CPU高速caching而言，了解高速caching行以了解其工作原理非常重要： 高速caching行如何工作？
以下几个方面对优化caching非常重要：
- 时间局部性 ：当一个给定的内存位置被访问时，在不久的将来很可能再次访问相同的位置。 理想情况下，这些信息仍然会被caching。
- 空间局部性 ：这是指将相关数据放在彼此靠近的地方。 caching发生在许多层次上，而不仅仅是在CPU中。 例如，当你从RAM中读取数据时，通常会比特定的内存获取更大的内存块，因为很多时候程序会很快需要这些数据。 HDDcaching遵循相同的思路。 特别是对于CPU高速caching， 高速caching行的概念非常重要。
使用适当的c ++容器
caching友好与caching不友好的简单例子是c ++的std::vector与std::list 。 std::vector元素存储在连续的内存中，因此访问它们比访问std::list元素要友善得多。 这是由于空间局部性。
Bjarne Stroustrup在这个youtube剪辑中给出了一个非常好的例子（感谢@Mohammad Ali Baydoun的链接！）。
不要忽视数据结构和algorithmdevise中的caching
只要有可能，就尽可能地调整数据结构和计算顺序，以最大限度地利用caching。 在这方面常见的技术是高速caching阻塞 （Archive.org版本） ，这在高性能计算（例如ATLAS ）中是非常重要的。
知道并利用隐含的数据结构
另外一个很简单的例子，很多人在这个领域里有时会忘记用于存储二维数组的列主要（例如fortran ， matlab ）和行主要sorting（例如c ， c ++ ）。 例如，考虑以下matrix：
1 2 3 4
在行主sorting中，这被存储在内存中1 2 3 4 ; 在列主要顺序这将被存储为1 3 2 4 。 很容易看出，不利用这种sorting的实现将很快遇到（容易避免的）caching问题。 不幸的是，在我的领域（机器学习），我经常看到这样的东西。 @MatteoItalia在他的回答中更详细地展示了这个例子。
当从内存中获取matrix的某个元素时，它附近的元素也将被获取并存储在caching行中。 如果sorting被利用，这将导致更less的存储器访问（因为后续计算所需的接下来的几个值已经在高速caching行中）。
为了简单起见，假定caching包括一个可以包含2个matrix元素的单个caching行，并且当给定元素从存储器中取出时，下一个元素也是。 假设我们想要在上面的例子2×2matrix中的所有元素的总和（让我们称之为M ）：
利用sorting（例如，首先在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
不利用sorting（例如，首先在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
在这个简单的例子中，利用sorting大约使执行速度翻倍（因为内存访问比计算总和需要更多的周期）。 在实践中，性能差异可能更大。
避免不可预知的分支
现代架构的特点是pipe道和编译器在重新sorting代码方面变得非常优秀，以最大限度地减less由于内存访问造成的延迟。 当您的关键代码包含（不可预知的）分支时，预取数据是困难的或不可能的。 这将间接导致更多的caching未命中。
这里解释得非常好（感谢@ 0x90的链接）： 为什么处理sorting的数组比未sorting的数组更快？
避免虚拟function
在c ++的情况下， virtual方法代表了一个关于caching未命中的争议性问题（一般认为应该尽可能地避免在性能方面的问题）。 虚拟函数在查找过程中会导致caching未命中，但是这只有在特定的函数没有经常被调用的情况下才会发生（否则可能会被caching），所以这被认为是一个非问题。 有关此问题的参考，请查看： 在C ++类中使用虚拟方法的性能成本是多less？
常见的问题
具有多处理器caching的现代体系结构中的一个常见问题是错误共享 。 当每个单独的处理器试图使用另一个存储器区域中的数据并尝试将其存储在相同的caching行中时，会发生这种情况。 这会导致包含另一个处理器可以使用的数据的caching行被一次又一次地覆盖。 有效地，不同的线程在这种情况下通过诱导caching未命中而相互等待。 另请参阅（感谢@Matt的链接）： 如何以及何时alignmentcaching行大小？
RAM存储器中caching不良的极端症状（这可能不是你在这种情况下的意思）就是所谓的颠簸 。 当进程不断产生页面错误（例如，访问不在当前页面中的存储器）而需要磁盘访问时，会发生这种情况。
除了@Marc Claesen的回答之外，我认为caching不友好代码的一个有启发意义的典型例子是代码扫描C二维数组（例如位图图像）列而不是行方式的代码。
在一行中相邻的元素在内存中也是相邻的，因此按顺序访问它们意味着以上升的内存顺序访问它们; 这是caching友好的，因为caching倾向于预取连续的内存块。
相反，以列方式访问这样的元素是caching不友好的，因为同一列上的元素在内存上彼此远离（特别是它们的距离等于行的大小），所以当你使用这种访问模式时在内存中跳跃，可能会浪费在附近的内存中检索元素caching的努力。
而所有这一切都是为了毁掉这个表演
// 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] ... } }
在小caching和/或大arrays（例如当前机器上的10+百万像素24bpp图像）的系统中，这种效果可能相当戏剧化（速度的几个数量级）。 因此，如果必须进行多次垂直扫描，通常最好先旋转90度的图像，稍后再执行各种分析，将caching不友好的代码限制在旋转状态。
优化caching使用主要归结为两个因素。
参考的地点
其他人已经提到的第一个因素是参考的地点。 参考地点确实有两个维度：空间和时间。
- 空间的
空间维度也归结为两件事情：首先，我们要密集包装我们的信息，所以更多的信息将适合于有限的记忆。 这意味着（例如）您需要计算复杂性的重大改进来certificate基于由指针连接的小节点的数据结构。
其次，我们希望将一起处理的信息放在一起。 一个典型的caching工作在“行”，这意味着当你访问一些信息时，附近地址的其他信息将被加载到caching与我们触摸的部分。 例如，当我触摸一个字节时，高速caching可能会在该字段附近加载128或256个字节。 为了利用这一点，您通常需要安排的数据最大化的可能性，你也可以使用同时加载的其他数据。
只是一个非常简单的例子，这可能意味着一个线性search可以比二元search更有竞争力比你所期望的。 一旦你从一个caching行加载了一个项目，使用该caching行中的其余数据几乎是免费的。 只有数据足够大，二分查找才能减less您访问的caching行数，二分查找速度才会明显加快。
- 时间
时间维度意味着当您对某些数据执行某些操作时，您希望（尽可能）一次对该数据执行所有操作。
既然你已经把它标记为C ++，我会指出一个相对caching不友好的devise的典型例子： std::valarray 。 valarray重载了大多数算术运算符，所以我可以（例如）说a = b + c + d; （其中a ， b ， c和d都是数字）来完成这些数组的元素相加。
问题在于，它通过一对input，把结果放在一个临时的地方，穿过另一对input，等等。 有了大量的数据，一次计算的结果可能会在下一次计算之前从caching中消失，所以最终我们得到最终结果之前，会重复读取（并写入）数据。 如果最终结果的每个元素都是(a[n] + b[n]) * (c[n] + d[n]); ，我们通常宁愿读a[n] ， b[n] ， c[n]和d[n] ，做计算，写结果，递增n并重复'直到我们完成了。 2
线路共享
第二个主要因素是避免线路共享。 为了理解这一点，我们可能需要备份并查看caching的组织方式。 直接映射最简单的cachingforms。 这意味着主存储器中的一个地址只能存储在caching中的一个特定地点。 如果我们使用映射到caching中相同位置的两个数据项，那么效果会很糟糕 – 每次我们使用一个数据项时，另一个数据项必须从caching中清除，为另一个数据项腾出空间。 其余的caching可能是空的，但这些项目不会使用caching的其他部分。
为了防止这种情况，大多数caching是所谓的“集合关联”。 例如，在一个4路组关联caching中，来自主存储器的任何项都可以存储在caching中的4个不同位置。 所以，当caching要加载一个项目时，它会查找这四个项目中最近最less使用的3个项目，将其刷新到主内存中，然后将新项目加载到它的位置。
这个问题可能相当明显：对于直接映射的caching，发生映射到相同caching位置的两个操作数可能导致不良行为。 N路组关联caching将数量从2增加到N + 1。 将caching组织成更多的“途径”需要额外的电路，通常运行速度较慢，因此（例如）8192路组相关caching很less是一个好的解决scheme。
最终，这个因素在便携式代码中更难以控制。 您对数据放置位置的控制通常相当有限。 更糟糕的是，地址到caching的确切映射在其他类似的处理器之间是不同的。 然而，在某些情况下，可能需要分配一个大的缓冲区，然后只使用您分配的部分来确保数据共享相同的caching行（即使您可能需要检测确切的处理器，采取行动做到这一点）。
- 虚假分享
还有另外一个名为“虚假分享”的相关项目。 这出现在多处理器或多核系统中，其中两个（或更多）处理器/内核具有独立的数据，但落在相同的高速caching行中。 这迫使两个处理器/内核协调对数据的访问，尽pipe每个处理器/内核都有自己独立的数据项。 特别是如果两者交替修改数据，这可能会导致大量的减速，因为数据必须在处理器之间不断地传送。 这不能通过将caching组织成更多“方式”或类似的东西来解决。 防止这种情况的主要方式是确保两个线程很less（最好不要）修改可能在同一个caching行中的数据（对于控制分配数据的地址的难度有相同的警告）。
-
那些熟悉C ++的人可能会怀疑，这是否可以通过类似expression式模板的优化来开放。 我敢肯定，答案是肯定的，如果是的话，这可能是一个非常可观的胜利。 然而，我并不知道有人这样做了，而且给了我们多less小小的
valarray，我也至less有些惊讶地发现有人也这样做了。 -
如果有人想知道如何
valarray（专为性能而devise）可能是这个严重错误，它归结为一件事情：它真的是devise用于像老Crays，使用快速主内存和没有caching的机器。 对他们来说，这确实是一个近乎理想的devise。 -
是的，我正在简化：大多数caching并没有真正测量最近最less使用的项目，但是他们使用了一些启发式的方法，而不必为每个访问保留一个完整的时间戳。
欢迎来到面向数据devise的世界。 基本的口号是sorting，消除分支，批次，消除virtual呼叫 – 迈向更好的地方的所有步骤。
既然你用C ++标记了这个问题，下面是强制的典型的C ++ Bullshit 。 托尼·阿尔布雷希特的面向对象编程的陷阱也是对这个主题的一个很好的介绍。
只是堆积如下：高速caching不友好与高速caching友好的代码的典型例子是matrix乘法的“高速caching阻塞”。
天真的matrix繁殖看起来像
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)大于caching大小，则对src2[k][j]每一次访问都将是caching未命中。
对caching进行优化的方法有很多种。 下面是一个非常简单的例子：不是在内部循环中读取每个caching行的一个项目，而是使用所有的项目：
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==;k<N;i++) { for(jj=0;jj<itemsPerCacheLine; jj+) { dest[i][j+jj] += src1[i][k] * src2[k][j+jj]; } } } }
如果高速caching行大小是64字节，并且我们正在32位（4字节）的浮点数上运行，则每个高速caching行有16个项目。 通过这个简单的转换，caching未命中的数量减less了大约16倍。
Fancier转换在2D图块上运行，优化多个caching（L1，L2，TLB）等等。
谷歌search“caching阻止”的一些结果：
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
一个优化的caching阻塞algorithm的一个很好的videoanimation。
http://www.youtube.com/watch?v=IFWgwGMMrh0
循环平铺非常密切相关：
今天的处理器与许多级联存储区域一起工作。 所以CPU会有一堆CPU芯片本身的内存。 它有非常快的访问这个内存。 有不同级别的caching，每个caching的访问速度都比下一个速度慢（而且要大一些），直到到达不在CPU上的系统内存，访问速度相对较慢。
从逻辑上讲，对于CPU的指令集，您只需在巨大的虚拟地址空间中引用内存地址即可。 当你访问一个单一的内存地址时，CPU将会去取它。 在过去，它只能获取那个单一的地址。 但是，如今CPU将在你所要求的位周围获取一堆内存，并将其复制到caching中。 它假设如果你要求一个特定的地址，很可能你很快就会要求附近的地址。 例如，如果您正在复制缓冲区，则会从连续的地址读取和写入 – 一个接一个地读取。
所以今天当你获取一个地址的时候，它会检查第一级的caching，看看它是否已经把这个地址读入了caching，如果没有find它，那么这是一个caching未命中的事情，它必须到达下一级cachingfind它，直到它最终必须走出主存。
高速caching友好的代码尝试保持访问在内存中靠近在一起，以便最大限度地减lesscaching未命中。
所以一个例子可以想象你想复制一个巨大的二维表。 内存中连续排列，排在后一排。
如果您从左到右一次将元素复制一行 – 这将是caching友好的。 如果您决定一次复制表中的一列，则会复制完全相同数量的内存 – 但这样会导致caching不友好。
需要澄清的是，不仅数据应该是caching友好的，对代码来说同样重要。 这是除了分支预测，指令重新sorting，避免实际分裂和其他技术。
通常情况下，代码越密集，将需要更less的caching行来存储它。 这会导致更多的caching行可用于数据。
该代码不应该在整个地方调用函数，因为它们通常会需要一个或多个自己的caching行，从而导致数据caching行较less。
函数应该在一个caching线alignment友好的地址开始。 虽然有（gcc）编译器开关，但请注意，如果函数非常短，则每个函数占用整个caching行可能是浪费的。 例如，如果三个最常用的函数适合一个64字节的高速caching行，那么比每个高速caching行都有其自己的行并且导致两个高速caching行可用于其他用途更less的浪费。 典型的alignment值可以是32或16。
所以花一些额外的时间来使代码密集。 testing不同的结构，编译和审查生成的代码大小和configuration文件。
请注意，caching不仅仅是caching连续的内存。 它们有多行（至less4个），所以不连续和重叠的内存通常可以被有效地存储。
所有上述例子中缺less的是测量的基准。 关于表演有很多神话。 除非你测量它，否则你不知道。 除非你有一个明显的改进，否则不要使代码复杂化。
正如@Marc Claesen所说，编写caching友好代码的方法之一就是利用存储数据的结构。 除此之外，编写caching友好代码的另一种方式是：改变数据存储的方式; 然后编写新的代码来访问存储在这个新结构中的数据。
在数据库系统如何线性化表格的元组并存储它们的情况下，这是有意义的。 有两种基本的方法来存储表的元组，即行存储和列存储。 在行存储中顾名思义，元组被存储在行中。 假设一个名为Product的表被存储了3个属性，即int32_t key, char name[56]和int32_t price ，所以一个元组的总大小是64字节。
我们可以通过创build一个大小为N的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. */
同样，我们可以通过创build3个大小为N的数组，在主内存中模拟一个非常基本的列存储查询执行，对于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个独立数组（列布局）之后，我们在存储在我们的表中的行上存储了行存储和列存储。
现在我们转到caching友好的代码部分。 假设我们的表上的工作量是这样的，我们有一个价格属性聚合查询。 如
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];
列存储的代码将比这个查询中的行布局的代码更快，因为它只需要属性的一个子集，在列布局中，我们正在做的就是只访问价格列。
假设高速caching行大小是64字节。
在读取高速caching行的行布局的情况下，只读取1（ cacheline_size/product_struct_size = 64/64 = 1 ）元组的价格值，因为我们的结构大小为64字节并填充了整个高速caching行对于每个元组，在行布局的情况下都会发生caching未命中。
在读取高速caching行的列布局的情况下，读取16（ cacheline_size/price_int_size = 64/4 = 16 ）元组的价格值，因为存储在存储器中的16个连续价格值被带入高速caching中，所以对于每个在列布局的情况下，第十六元组caching未命中。
因此，在给定查询的情况下，列布局将更快，并且在表的列子集上的这种聚集查询中速度更快。 您可以使用TPC-H基准testing的数据为您自己尝试这种实验，并比较两种布局的运行时间。 维基百科关于列式数据库系统的文章也很好。
因此，在数据库系统中，如果事先知道查询工作负载，我们可以将数据存储在适合工作负载查询的布局中，并从这些布局访问数据。 在上面的例子中，我们创build了一个列布局，并且改变了我们的代码来计算总和，这样它就变成了caching友好的。
