简单来说：缓存不友好代码与缓存友好代码的典型例子是矩阵乘法的“缓存阻塞”。

朴素矩阵乘法看起来像：

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倍。

Fancier变换对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

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

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

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

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

所以，花一些额外的时间让代码更密集。测试不同的构造，编译并检查生成的代码大小和配置文件。

欢迎来到面向数据设计的世界。基本的口头禅是“排序”、“消除分支”、“批处理”和“消除虚拟呼叫”，所有这些步骤都是为了更好地定位。

既然你用C++标记了这个问题，这里是强制性的典型C++废话。托尼·阿尔布雷希特（Tony Albrecht）的《面向对象编程的陷阱》也是对这一主题的一个很好的介绍。

优化缓存使用率主要取决于两个因素。

参考地点

第一个因素（其他人已经提到）是参考的地方性。然而，引用的地点实际上有两个维度：空间和时间。

空间的

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

第二，我们希望将一起处理的信息也位于一起。典型的缓存以“行”方式工作，这意味着当您访问某些信息时，附近地址的其他信息将与我们接触的部分一起加载到缓存中。例如，当我触摸一个字节时，缓存可能会在该字节附近加载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并重复，直到完成。2

线路共享

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

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

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

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

虚假共享

还有一个相关的项目叫做“虚假分享”。这出现在多处理器或多核系统中，其中两个（或多个）处理器/核具有独立的数据，但位于同一缓存线中。这迫使两个处理器/内核协调对数据的访问，即使每个处理器/内核都有自己的独立数据项。特别是如果两个处理器交替修改数据，这可能会导致数据在处理器之间不断穿梭，从而导致速度大幅放缓。通过将缓存组织成更多的“方式”或类似的方式，这是不容易解决的。防止这种情况的主要方法是确保两个线程很少（最好永远不会）修改可能位于同一缓存行中的数据（同时也要注意控制数据分配地址的难度）。

熟悉C++的人可能会想，这是否可以通过表达式模板等方式进行优化。我很肯定答案是肯定的，这是可能的，如果是的话，这可能是一场相当可观的胜利。然而，我不知道有人这样做，而且考虑到valarray的使用量很少，看到有人这么做，我至少会有点惊讶。如果有人想知道valarray（专门为性能而设计的）是如何严重错误的，那就归结为一件事：它确实是为像旧版Crays这样的机器设计的，使用了快速的主内存，没有缓存。对他们来说，这真的是一个近乎理想的设计。是的，我在简化：大多数缓存并没有精确地测量最近最少使用的项目，但它们使用了一些启发式方法，目的是为了接近这一点，而不必为每次访问保留完整的时间戳。

今天的处理器可以处理许多级别的级联内存区域。因此，CPU芯片上会有一堆内存。它可以快速访问此内存。有不同级别的缓存，每次访问速度都比下一次慢（并且更大），直到您到达不在CPU上且访问速度相对较慢的系统内存。

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

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

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

所以一个例子是假设你想要复制一个巨大的二维表格。它在内存中以连续的到达行组织，一行紧接着下一行。

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

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

以上所有示例中缺少的是衡量基准。关于表演有很多神话。除非你测量它，否则你不知道。除非有明显的改进，否则不要使代码复杂化。