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

Question

什么是“不利于缓存的代码”和“友好缓存的代码”之间的区别？

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

- Noah Roth

---

这可能会给你一些线索：https://dev59.com/LGkw5IYBdhLWcg3wY5jq - Robert Martin

请注意缓存行的大小。在现代处理器上，通常为64字节。 - John Dibling

这是另一篇非常好的文章。该原则适用于任何操作系统（Linux、MaxOS或Windows）上的C/C++程序：http://lwn.net/Articles/255364/ - paulsm4

相关问题：https://dev59.com/Hmoy5IYBdhLWcg3wkO0K - hookenz

https://dev59.com/KnRA5IYBdhLWcg3w9y50 - Ciro Santilli OurBigBook.com

Answer 1

前提条件

在现代计算机上，只有最低级的内存结构（寄存器）可以在单个时钟周期内移动数据。然而，寄存器非常昂贵，大多数计算机核心只有不到几十个寄存器。在内存谱系的另一端（DRAM），内存非常便宜（即文字意义上的便宜了数百万倍），但需要数百个周期才能在请求后接收数据。为了弥合这种超快速和昂贵与超慢速和便宜之间的差距，出现了高速缓存存储器，按照降序分别命名为L1、L2、L3，速度和成本逐渐降低。其思想是，大部分执行代码将经常访问一小组变量，而其余部分（一个更大的变量集）则很少访问。如果处理器在L1高速缓存中找不到数据，则会查找L2高速缓存。如果没有，那么查找L3高速缓存，如果还没有，就查找主内存。每次“未命中”都会消耗大量时间。

（类比：高速缓存存储器对系统内存，就像系统内存对硬盘存储一样。硬盘存储非常便宜但非常慢）。

缓存是减少延迟影响的主要方法之一。为了引用Herb Sutter的话（参见下面的链接）：“增加带宽很容易，但我们无法通过购买来摆脱延迟”。数据总是通过内存层次结构检索（最小==最快到最慢）。“缓存命中/失效”通常指CPU中最高级别的缓存命中/失效--我所说的最高级别是最大==最慢的。缓存命中率对性能至关重要，因为每个缓存未命中都会导致从RAM（或更糟的情况...）获取数据，这需要很长时间（RAM需要数百个周期，HDD需要数千万个周期）。相比之下，从（最高级别）缓存中读取数据通常只需要几个周期。

在现代计算机体系结构中，性能瓶颈是离开CPU芯片（例如访问RAM或更高级别）的问题。随着时间的推移，这种情况只会变得更糟。目前，增加处理器频率已经不再与提高性能相关。硬件设计方面的努力因此目前重点放在优化缓存、预取、流水线和并发性上。例如，现代CPU芯片约有85%的面积用于缓存，高达99%用于存储/移动数据！

这个主题有很多值得讨论的地方。以下是一些关于缓存、内存层次结构和适当编程的优秀参考资料：

• Agner Fog的页面。在他的优秀文档中，您可以找到涵盖从汇编语言到C++等语言的详细示例。
• 如果您喜欢视频，我强烈建议您观看Herb Sutter在机器架构方面的演讲（YouTube）（特别是在12:00及以后！）。
• Christer Ericson关于内存优化的幻灯片（索尼技术总监）
• LWN.net的文章 "每个程序员都应该了解的有关内存的知识"

缓存友好代码的主要概念

缓存友好代码非常重要的一个方面是关于“局部性原理”的，其目标是将相关数据放置在内存中以实现高效的缓存。就CPU缓存而言，了解缓存行是至关重要的：缓存行是如何工作的？ 以下特定方面对于优化缓存至关重要：

1. 时间局部性：当访问给定的内存位置时，很可能会在不久的将来再次访问相同位置。理想情况下，此信息仍将被缓存。 2. 空间局部性：这指的是将相关数据放置在附近。缓存发生在许多层面上，不仅仅是在CPU中。例如，当您从RAM读取时，通常会获取比所需数据更大的内存块，因为程序很快可能会需要那些数据。HDD缓存也遵循同样的思路。特别是对于CPU缓存，缓存行的概念非常重要。

使用合适的c++容器

缓存友好和不友好的简单例子是c++的std::vector和std::list。 std::vector的元素存储在连续的内存中，因此访问它们比访问std::list中的元素更加缓存友好，后者将其内容存储在各个位置。这是由于空间局部性。

Bjarne Stroustrup在this youtube clip中给出了一个非常好的说明（感谢@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++类中使用虚方法的性能成本是多少？

常见问题

现代多处理器缓存架构中的一个常见问题被称为false sharing。当每个单独的处理器试图使用另一个内存区域中的数据并尝试将其存储在同一缓存线中时，就会发生这种情况。这会导致包含其他处理器可以使用的数据的缓存行被反复覆盖。在这种情况下，不同的线程通过引发缓存未命中使彼此等待。 还请参阅（感谢@Matt提供的链接）：如何以及何时对齐缓存行大小？ RAM内存中缓存不良的一个极端症状（这可能不是您在此上下文中所指的）被称为 thrashing。这发生在进程持续生成页面错误（例如访问当前页面中不存在的内存）需要磁盘访问的情况下。

- Marc Claesen

---

也许您可以进一步解释，在多线程代码中，数据也可能过于局部（例如，虚假共享）。 - TemplateRex

芯片设计师可以认为有多少级缓存是有用的。通常，他们在速度和大小之间进行平衡。如果您可以使L1缓存像L5一样大且同样快，那么您只需要L1。 - Rafael Baptista

我知道在StackOverflow上空洞的同意帖子是不被赞同的，但这是我迄今为止看到的最清晰、最好的答案。做得非常好，Marc。 - Jack Aidley

@JackAidley 谢谢你的赞扬！当我看到这个问题受到的关注量时，我想许多人可能会对一个相当详尽的解释感兴趣。我很高兴它有用。 - Marc Claesen

你没有提到的是，缓存友好的数据结构被设计为适合缓存行，并对齐内存以最大限度地利用缓存行。非常好的回答！太棒了。 - hookenz

Answer 2

除了@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多兆像素24 bpp图像），则此效果可能非常显著（速度提高数个数量级）；因此，如果您需要进行许多垂直扫描，则通常最好先将图像旋转90度，然后执行各种分析，将不友好缓存的代码限制到旋转操作中。

- Matteo Italia

---

错误，应该是x<width吗？ - mowwwalker

现代图像编辑器使用瓦片作为内部存储，例如64x64像素的块。这对于本地操作（放置涂点、运行模糊滤镜）更加缓存友好，因为大多数情况下相邻的像素在内存中都是双向接近的。 - maxy

我在我的机器上尝试了一个类似的例子，并发现时间是相同的。还有其他人尝试过计时吗？ - gsgx

@I3arnon：不是的，第一个更加缓存友好，因为通常情况下，在C语言中数组是按行主序（http://en.wikipedia.org/wiki/Row-major_order）存储的（当然，如果你的图像以某种原因按列主序存储，则相反）。 - Matteo Italia

等一下...image[0][1]与image[0][2]相邻。因此内部循环应该遍历第二个索引，对吧？for each y in rows: (fetch a whole row, hopefully) for each x in cols: ...image[y][x]...。这使得你的第一个代码片段是正确的，而不是第二个。我有什么遗漏吗？ - Gauthier

@Gauthier：是的，第一个片段是正确的；我认为当我写这个的时候，我是在考虑“只需要从……到……就可以破坏一个工作应用程序的性能”。 - Matteo Italia

Answer 3

优化缓存使用主要涉及两个因素。

引用局部性

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

• 空间

空间维度也归结为两件事：首先，我们希望将信息密集地打包在一起，这样更多的信息就可以适应有限的内存。 这意味着（例如）需要显着改善计算复杂度才能证明基于指针连接的小节点的数据结构比较好。

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

行共享

第二个主要因素是避免行共享。为了理解这一点，我们可能需要回顾一下缓存的组织方式。最简单的缓存形式是直接映射。这意味着主存中的一个地址只能存储在缓存中的一个特定位置。如果我们使用的两个数据项映射到缓存中的同一个位置，那么情况就不太好--每次使用一个数据项时，其他数据项都必须从缓存中刷新出来，以便为其他数据项腾出空间。缓存的其余部分可能是空的，但这些条目不会使用缓存的其他部分。

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

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

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

还有另一个相关的问题称为“虚假共享”。这出现在多处理器或多核系统中，其中两个（或更多）处理器/核心具有分开但落在同一缓存行中的数据。这迫使两个处理器/核心协调访问数据，即使每个处理器都有自己单独的数据项。特别是如果两个处理器交替修改数据，则可能会导致大规模的减速，因为数据必须不断在处理器之间穿梭。这也不能通过将缓存组织成更多“路”或类似方法来轻松解决。防止它的主要方法是确保两个线程很少（最好从不）修改可能位于相同缓存行中的数据（有关在哪里分配数据的地址难以控制的警告同样适用）。

熟悉C ++的人可能会想知道是否可以通过诸如表达式模板之类的东西进行优化。我非常确定答案是肯定的，如果可以，那么这可能是一个相当大的胜利。但是，我没有听说过有人这样做，并且考虑到几乎没有人使用valarray，看到有人这样做我会感到至少有点惊讶。

如果有人想知道为什么valarray（专门设计用于提高性能）会出现如此严重的问题，那就归结于一件事：它确实是为像旧Cray这样使用快速主存和没有缓存的机器而设计的。对于它们来说，这真的是一个几乎理想的设计。

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

- Jerry Coffin

---

我喜欢你回答中额外提供的信息，特别是valarray的例子。 - Marc Claesen

终于有一个关于集合关联性的简明描述了！编辑后：这是SO上最具信息量的答案之一。谢谢。 - Engineer

Answer 4

欢迎来到数据导向设计世界。基本口号是：排序、消除分支、批处理、消除virtual函数调用，所有这些步骤都是为了更好的局部性。

既然您用C++标记了问题，这里有一份必备的典型的C++废话。Tony Albrecht的《面向对象编程的陷阱》也是该主题的很好的入门材料。

- arul

---

“batch” 是什么意思，有些人可能不理解。 - 0x90

批处理：不是针对单个对象执行操作，而是针对一批对象执行操作。 - arul

阻塞、阻塞寄存器、阻塞缓存。 - 0x90

阻塞/非阻塞通常指对象在并发环境中的行为。 - arul

批处理 == 向量化 - Amro

“排序、消除分支、批处理”，这正是60年前主机所做的事情！哈哈，即使现在，通过按表的主键对输入文件进行排序，也会因为缓冲而带来明显的加速。 - RonJohn

Answer 5

仅仅叠加：缓存不友好代码与缓存友好代码的经典例子是对矩阵乘法进行“缓存分块”。

朴素的矩阵乘法如下：

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

- Krazy Glew

---

阅读此文的人可能也会对我的关于矩阵乘法的文章感兴趣，链接为 http://martin-thoma.com/matrix-multiplication-python-java-cpp 。在那篇文章中，我测试了“缓存友好”的 ikj 算法和不友好的 ijk 算法，并使用它们来计算两个 2000x2000 的矩阵相乘。 - Martin Thoma

“k==;” 这是打错了吗？ - TrebledJ

Answer 6

现今的处理器与许多级联记忆区域一起工作。因此，CPU将拥有一些位于CPU芯片本身上的内存。它可以非常快速地访问这些内存。有不同级别的缓存，每个级别的访问速度都比下一个级别慢（但容量更大），直到您到达系统内存，在CPU上没有这种内存，并且相对较慢。

从逻辑上讲，对于CPU的指令集，您只需在一个巨大的虚拟地址空间中引用内存地址。当您访问单个内存地址时，CPU会去获取它。在旧日子里，它将只获取该单个地址。但是今天，CPU将获取您请求的一堆围绕该位的内存，并将其复制到缓存中。它认为，如果您请求了特定地址，则很可能您很快会请求附近的地址。例如，如果要复制缓冲区，则会从连续地址读取和写入-一个接一个。

因此，今天当您获取地址时，它会检查第一级缓存以查看是否已将该地址读入缓存中，如果找不到它，则这是缓存未命中，必须转到下一级缓存来查找，直到最终必须转到主内存。

缓存友好的代码试图将内存访问保持在相邻位置，以最小化缓存未命中。

因此，一个例子是想象您要复制一个巨大的二维表。它按连续的行组织在内存中，每一行紧随其后。

如果您从左到右逐行复制元素，则这将是缓存友好的。如果您决定逐列复制表格，则复制的内存量完全相同-但这不太友好。

- Rafael Baptista

Answer 7

需要澄清的是，不仅数据应该具有缓存友好性，代码同样重要。这是除了分支预测、指令重新排序、避免实际除法和其他技术之外的一项措施。

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

代码不应在各个地方调用函数，因为它们通常需要一个或多个自己的缓存行，从而减少了用于数据的缓存行数量。

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

因此，请花费额外的时间使代码更加紧凑。测试不同的结构，编译并审查生成的代码大小和配置文件。

- Olof Forshell

Answer 8

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

这在数据库系统将表的元组线性化并存储的情况下是有道理的。存储表的元组有两种基本方式，即行存储和列存储。在行存储中，元组按行存储。假设一个名为Product的表被存储，具有3个属性，即int32_t key, char name[56]和int32_t price，因此一个元组的总大小为64字节。

我们可以通过创建一个大小为N的Product结构体数组，在主内存中模拟非常基本的行存储查询执行，其中N是表中的行数。这样的内存布局也称为结构体数组。因此，Product的结构体可能如下所示：

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属性的三个数组可能如下所示：

/* 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基准测试中的数据自行尝试这样的实验，并比较两种布局的运行时间。wikipedia关于列导向数据库系统的文章也很好。在数据库系统中，如果查询工作负载事先已知，我们可以将数据存储在适合工作负载的布局中，并从这些布局访问数据。在上面的示例中，我们创建了一个列布局，并更改了代码以计算总和，使其成为缓存友好型。

- user2603796

Answer 9

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

以上所有示例中缺少的是经过测量的基准。关于性能存在许多神话。除非进行测量，否则您将不知道。除非您有经过测量的改进，否则不要使代码复杂化。

- Tuntable

Answer 10

缓存友好的代码是经过优化以有效利用CPU缓存的代码。这通常涉及以一种利用空间和时间局部性的方式组织数据，即相关数据很可能被存储在内存中相邻位置，并且频繁访问的数据很可能在不久的将来再次被访问。

有几种方法可以使代码更加缓存友好，包括：

1. 使用连续的内存布局：通过在内存中存储连续块的数据，您可以利用空间局部性，减少缓存未命中的数量。 2. 使用数组：当需要顺序访问数据时，数组是数据结构的不错选择，因为它们允许您利用时间局部性并将热点数据保留在缓存中。 3. 谨慎使用指针：指针可用于访问非连续存储在内存中的数据，但如果过度使用，则可能导致缓存未命中。如果必须使用指针，请尝试以利用空间和时间局部性的方式使用它们，以最小化缓存未命中。 4. 使用编译器优化标志：大多数编译器都具有优化标志，可用于优化CPU缓存的使用。这些标志可以帮助最小化缓存未命中的数量，提高代码的整体性能。

需要注意的是，优化CPU缓存使用的具体技术将取决于您系统的特定要求和限制。可能需要尝试不同的方法，以找到最适合您需求的最佳解决方案。

- Kyrylo Cherneha