c++ - 什么是 “cache-friendly”代码？

Question

“缓存不友好的代码”和“缓存不友好的”代码有什么区别？

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

Answer 1

初赛
在现代计算机上，只有最低级别的内存结构(寄存器)才能在单个时钟周期内移动数据。但是，寄存器非常昂贵，并且大多数计算机内核只有不到几十个寄存器。在内存频谱的另一端( DRAM )，内存非常便宜(即便宜了数百万倍)，但是在请求接收数据后需要花费数百个周期。为了弥合超快和昂贵之间以及超慢和便宜之间的差距，是高速缓存存储器，它们以降低速度和成本的方式命名为L1，L2，L3。这个想法是，大多数执行代码经常会碰到一小组变量，而其余部分(一大组变量)则很少。如果处理器无法在L1缓存中找到数据，那么它将在L2缓存中查找。如果不存在，则为L3缓存，如果不存在，则为主内存。这些“缺失”中的每一个在时间上都是昂贵的。
(类比是缓存是系统内存，因为系统内存太硬盘存储。硬盘存储非常便宜，但速度很慢)。
缓存是减少延迟影响的主要方法之一。解释Herb Sutter(下面的链接):增加带宽很容易，但是我们不能摆脱的延迟。
始终通过内存层次结构检索数据(最小==最快到最慢)。高速缓存命中/未命中通常是指CPU最高级别的高速缓存中的命中/未命中-最高水平是指最大==最慢。高速缓存命中率对于性能至关重要，因为每次高速缓存未命中都会导致从RAM中获取数据(或更糟的是...)，这需要花费很多的时间(RAM数百个周期，HDD数千万个周期)。相比之下，从(最高级别)高速缓存读取数据通常只需要几个周期。
在现代计算机体系结构中，性能瓶颈正在使CPU失效(例如访问RAM或更高级别)。随着时间的推移，这只会变得更糟。当前，处理器频率的增加不再与提高性能有关。 问题是内存访问。 因此，CPU的硬件设计工作目前主要集中在优化缓存，预取，管道和并发上。例如，现代CPU将大约85％的裸片用于高速缓存，而将高达99％的裸片用于存储/移动数据!
关于这个话题有很多要说的。这是有关缓存，内存层次结构和正确编程的一些出色引用:

Agner Fog's page。在他的出色文档中，您可以找到涵盖从汇编到C++的语言的详细示例。

如果您喜欢视频，我强烈建议您看一看Herb Sutter's talk on machine architecture (youtube)(具体检查12:00及之后!)。

Slides about memory optimization by Christer Ericson(索尼技术总监)

LWN.net的文章"What every programmer should know about memory"

缓存友好代码的主要概念
缓存友好型代码的一个非常重要的方面就是 the principle of locality ，其目标是将相关数据紧密放置在内存中以实现高效的缓存。就CPU缓存而言，了解缓存行以了解其工作方式非常重要: How do cache lines work?
以下特定方面对于优化缓存非常重要:

时间位置:当访问给定的存储位置时，很可能在不久的将来再次访问同一位置。理想情况下，此信息仍将在此时进行缓存。

空间位置:这是指将相关数据放置得彼此靠近。缓存发生在许多级别，而不仅仅是在CPU中。例如，当您从RAM中读取数据时，通常会提取比专门要求的更大的内存块，因为程序经常会很快需要该数据。 HDD缓存遵循相同的思路。特别是对于CPU高速缓存，高速缓存行的概念很重要。

使用适当的c++容器
缓存友好与缓存不友好的简单示例是 c++的 std::vector与 std::list。 std::vector的元素存储在连续的内存中，因此与访问 std::list的元素(将其内容存储在整个地方)相比，访问它们更易于缓存。这是由于空间局部性。
Bjarne Stroustrup在 this youtube clip中给出了一个很好的例子(感谢@Mohammad Ali Baydoun提供的链接!)。
在数据结构和算法设计中不要忽略高速缓存
只要有可能，请尝试以最大程度利用缓存的方式调整数据结构和计算顺序。在这方面，一种常见的技术是 cache blocking (Archive.org version)，它在高性能计算(例如 ATLAS)中非常重要。
了解并利用数据的隐式结构
另一个简单的示例(该字段中的许多人有时会忘记)是用于存储二维数组的列大顺序(例如 fortran， matlab)和行大顺序(例如 c， c++)。例如，考虑以下矩阵:

1 2
3 4

在行优先排序中，它以 1 2 3 4的形式存储在内存中；按照列大顺序排列，这将存储为 1 3 2 4。不难看出，不利用此顺序的实现将很快遇到(很容易避免!)缓存问题。不幸的是，我在我的 Realm (机器学习)中经常看到类似的东西。 @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的链接): Why is processing a sorted array faster than processing an unsorted array?
避免使用虚函数
在 c++的上下文中， virtual方法代表有关缓存未命中的有争议的问题(存在一个普遍共识，即就性能而言应尽可能避免使用)。虚拟函数可能会在查找过程中导致缓存未命中，但是只有在不经常调用特定函数的情况下才会发生这种情况(否则可能会被缓存)，因此某些人将其视为非问题。有关此问题的引用，请 checkout : What is the performance cost of having a virtual method in a C++ class?
常见问题
在具有多处理器缓存的现代体系结构中，一个常见的问题称为 false sharing。当每个单独的处理器尝试使用另一个存储区域中的数据并将其存储在同一高速缓存行中时，就会发生这种情况。这会导致一次又一次地覆盖高速缓存行(其中包含另一个处理器可以使用的数据)。实际上，在这种情况下，不同的线程会导致缓存未命中，从而使彼此等待。
另请参见(感谢@Matt提供链接): How and when to align to cache line size?
RAM内存缓存不足的一种极端症状(在这种情况下可能不是您的意思)就是所谓的 thrashing。当进程连续产生需要磁盘访问的页面错误(例如访问不在当前页面中的内存)时，就会发生这种情况。