准备工作

在现代计算机上，只有最低级别的内存结构（寄存器）可以在单个时钟周期内移动数据。然而，寄存器非常昂贵，大多数计算机核心只有不到几十个寄存器。在存储器频谱（DRAM）的另一端，存储器非常便宜（即实际上便宜数百万倍），但在请求接收数据后需要数百个周期。为了弥补超高速和昂贵以及超慢速和廉价之间的差距，高速缓冲存储器被命名为L1、L2、L3，以降低速度和成本。其想法是，大多数正在执行的代码将经常触及一小组变量，而其余的（一组大得多的变量）则很少触及。如果处理器在一级缓存中找不到数据，那么它会在二级缓存中查找。如果不存在，则为三级缓存，如果不存在则为主内存。这些“失误”中的每一个在时间上都是昂贵的。

（类似于高速缓冲存储器是系统存储器，就像系统存储器是硬盘存储一样。硬盘存储非常便宜，但速度非常慢）。

缓存是减少延迟影响的主要方法之一。套用赫伯·萨特的话（下面的cfr.links）：增加带宽很容易，但我们无法买到摆脱延迟的方法。

始终通过内存层次结构检索数据（最小==最快到最慢）。缓存命中/未命中通常是指CPU中最高级别缓存中的命中/未中——最高级别我指的是最大的==最慢的。缓存命中率对性能至关重要，因为每次缓存未命中都会导致从RAM（或更糟……）中提取数据，这需要大量时间（RAM需要数百个周期，HDD需要数千万个周期）。相比之下，从（最高级别）缓存读取数据通常只需要几个周期。

在现代计算机体系结构中，性能瓶颈是离开CPU芯片（例如访问RAM或更高版本）。随着时间的推移，情况只会变得更糟。处理器频率的增加目前与性能的提高不再相关。问题是内存访问。因此，CPU的硬件设计工作目前主要集中于优化缓存、预取、管道和并发。例如，现代CPU在缓存上花费了85%的内存，在存储/移动数据上花费了99%！

关于这个问题，有很多话要说。以下是关于缓存、内存层次结构和正确编程的一些重要参考：

阿格纳·福格的页面。在他的优秀文档中，您可以找到涵盖从汇编到C++等语言的详细示例。如果你喜欢视频，我强烈建议你去看看赫伯·萨特（Herb Sutter）的机器架构演讲（youtube）（特别是12:00及以后！）。Christer Ericson（技术总监@Sony）关于内存优化的幻灯片LWN.net的文章“每个程序员都应该了解内存”

缓存友好代码的主要概念

缓存友好代码的一个非常重要的方面是关于局部性的原则，其目标是将相关数据放在内存中以实现高效缓存。就CPU缓存而言，了解缓存线是很重要的，以了解其工作原理：缓存线是如何工作的？

以下特定方面对于优化缓存非常重要：

时间位置：当访问给定的内存位置时，很可能在不久的将来再次访问相同的位置。理想情况下，此时仍将缓存此信息。空间位置：这是指将相关数据放置在彼此接近的位置。缓存发生在许多级别，而不仅仅是在CPU中。例如，当您从RAM读取数据时，通常会提取比特定要求更大的内存块，因为程序很快就会需要这些数据。HDD缓存遵循同样的思路。特别是对于CPU缓存，缓存线的概念非常重要。

使用适当的c++容器

缓存友好与缓存不友好的一个简单例子是c++的std:：vector与std:：list。std:：vector的元素存储在连续内存中，因此访问它们比访问std:：list中的元素更容易缓存，std:：列表将其内容存储在各处。这是由于空间位置。

Bjarne Stroustrup在这段youtube视频中给出了一个很好的例子（感谢@Mohammad Ali Baydoun的链接！）。

在数据结构和算法设计中不要忽视缓存

只要可能，尽量调整数据结构和计算顺序，以最大限度地利用缓存。这方面的一种常见技术是缓存阻塞（Archive.org版本），这在高性能计算（例如ATLAS）中非常重要。

了解并利用数据的隐式结构

另一个很简单的例子，很多业内人士有时会忘记，即用于存储二维数组的列主排序（如fortran、matlab）与行主排序（例如c、c++）。例如，考虑以下矩阵：

1 2
3 4

在行主排序中，它存储在内存中，为1 2 3 4；在列主排序中，这将存储为1 3 2 4。很容易看出，不利用这种排序的实现将很快遇到（容易避免！）缓存问题。不幸的是，我经常在我的领域（机器学习）看到这样的东西@MatteoTalia在回答中更详细地展示了这个例子。

当从内存中提取矩阵的某个元素时，它附近的元素也将被提取并存储在缓存行中。如果利用排序，这将导致更少的内存访问（因为后续计算所需的下几个值已经在缓存行中）。

为了简单起见，假设缓存包含一个缓存行，该缓存行可以包含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++环境中，虚拟方法在缓存未命中方面是一个有争议的问题（普遍的共识是，在性能方面应尽可能避免使用虚拟方法）。虚拟函数在查找过程中可能会导致缓存未命中，但只有在不经常调用特定函数（否则很可能会被缓存）的情况下才会发生这种情况，因此有些人认为这不是问题。有关此问题的参考，请查看：在C++类中使用虚拟方法的性能成本是多少？

常见问题

在具有多处理器缓存的现代体系结构中，一个常见的问题称为错误共享。当每个处理器试图使用另一个内存区域中的数据并试图将其存储在同一缓存行中时，就会发生这种情况。这会导致缓存行（其中包含另一个处理器可以使用的数据）被一次又一次覆盖。实际上，在这种情况下，不同的线程会导致缓存未命中，从而使彼此等待。另请参见（感谢@Matt提供的链接）：如何以及何时调整缓存行大小？

RAM内存缓存不佳的一个极端症状（这可能不是本文中的意思）是所谓的抖动。当进程连续生成需要磁盘访问的页面故障（例如访问不在当前页面中的内存）时，就会发生这种情况。

准备工作

在现代计算机上，只有最低级别的内存结构（寄存器）可以在单个时钟周期内移动数据。然而，寄存器非常昂贵，大多数计算机核心只有不到几十个寄存器。在存储器频谱（DRAM）的另一端，存储器非常便宜（即实际上便宜数百万倍），但在请求接收数据后需要数百个周期。为了弥补超高速和昂贵以及超慢速和廉价之间的差距，高速缓冲存储器被命名为L1、L2、L3，以降低速度和成本。其想法是，大多数正在执行的代码将经常触及一小组变量，而其余的（一组大得多的变量）则很少触及。如果处理器在一级缓存中找不到数据，那么它会在二级缓存中查找。如果不存在，则为三级缓存，如果不存在则为主内存。这些“失误”中的每一个在时间上都是昂贵的。

（类似于高速缓冲存储器是系统存储器，就像系统存储器是硬盘存储一样。硬盘存储非常便宜，但速度非常慢）。

缓存是减少延迟影响的主要方法之一。套用赫伯·萨特的话（下面的cfr.links）：增加带宽很容易，但我们无法买到摆脱延迟的方法。

始终通过内存层次结构检索数据（最小==最快到最慢）。缓存命中/未命中通常是指CPU中最高级别缓存中的命中/未中——最高级别我指的是最大的==最慢的。缓存命中率对性能至关重要，因为每次缓存未命中都会导致从RAM（或更糟……）中提取数据，这需要大量时间（RAM需要数百个周期，HDD需要数千万个周期）。相比之下，从（最高级别）缓存读取数据通常只需要几个周期。

在现代计算机体系结构中，性能瓶颈是离开CPU芯片（例如访问RAM或更高版本）。随着时间的推移，情况只会变得更糟。处理器频率的增加目前与性能的提高不再相关。问题是内存访问。因此，CPU的硬件设计工作目前主要集中于优化缓存、预取、管道和并发。例如，现代CPU在缓存上花费了85%的内存，在存储/移动数据上花费了99%！

关于这个问题，有很多话要说。以下是关于缓存、内存层次结构和正确编程的一些重要参考：

阿格纳·福格的页面。在他的优秀文档中，您可以找到涵盖从汇编到C++等语言的详细示例。如果你喜欢视频，我强烈建议你去看看赫伯·萨特（Herb Sutter）的机器架构演讲（youtube）（特别是12:00及以后！）。Christer Ericson（技术总监@Sony）关于内存优化的幻灯片LWN.net的文章“每个程序员都应该了解内存”

缓存友好代码的主要概念

缓存友好代码的一个非常重要的方面是关于局部性的原则，其目标是将相关数据放在内存中以实现高效缓存。就CPU缓存而言，了解缓存线是很重要的，以了解其工作原理：缓存线是如何工作的？

以下特定方面对于优化缓存非常重要：

时间位置：当访问给定的内存位置时，很可能在不久的将来再次访问相同的位置。理想情况下，此时仍将缓存此信息。空间位置：这是指将相关数据放置在彼此接近的位置。缓存发生在许多级别，而不仅仅是在CPU中。例如，当您从RAM读取数据时，通常会提取比特定要求更大的内存块，因为程序很快就会需要这些数据。HDD缓存遵循同样的思路。特别是对于CPU缓存，缓存线的概念非常重要。

使用适当的c++容器

缓存友好与缓存不友好的一个简单例子是c++的std:：vector与std:：list。std:：vector的元素存储在连续内存中，因此访问它们比访问std:：list中的元素更容易缓存，std:：列表将其内容存储在各处。这是由于空间位置。

Bjarne Stroustrup在这段youtube视频中给出了一个很好的例子（感谢@Mohammad Ali Baydoun的链接！）。

在数据结构和算法设计中不要忽视缓存

只要可能，尽量调整数据结构和计算顺序，以最大限度地利用缓存。这方面的一种常见技术是缓存阻塞（Archive.org版本），这在高性能计算（例如ATLAS）中非常重要。

了解并利用数据的隐式结构

另一个很简单的例子，很多业内人士有时会忘记，即用于存储二维数组的列主排序（如fortran、matlab）与行主排序（例如c、c++）。例如，考虑以下矩阵：

1 2
3 4

在行主排序中，它存储在内存中，为1 2 3 4；在列主排序中，这将存储为1 3 2 4。很容易看出，不利用这种排序的实现将很快遇到（容易避免！）缓存问题。不幸的是，我经常在我的领域（机器学习）看到这样的东西@MatteoTalia在回答中更详细地展示了这个例子。

当从内存中提取矩阵的某个元素时，它附近的元素也将被提取并存储在缓存行中。如果利用排序，这将导致更少的内存访问（因为后续计算所需的下几个值已经在缓存行中）。

为了简单起见，假设缓存包含一个缓存行，该缓存行可以包含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++环境中，虚拟方法在缓存未命中方面是一个有争议的问题（普遍的共识是，在性能方面应尽可能避免使用虚拟方法）。虚拟函数在查找过程中可能会导致缓存未命中，但只有在不经常调用特定函数（否则很可能会被缓存）的情况下才会发生这种情况，因此有些人认为这不是问题。有关此问题的参考，请查看：在C++类中使用虚拟方法的性能成本是多少？

常见问题

在具有多处理器缓存的现代体系结构中，一个常见的问题称为错误共享。当每个处理器试图使用另一个内存区域中的数据并试图将其存储在同一缓存行中时，就会发生这种情况。这会导致缓存行（其中包含另一个处理器可以使用的数据）被一次又一次覆盖。实际上，在这种情况下，不同的线程会导致缓存未命中，从而使彼此等待。另请参见（感谢@Matt提供的链接）：如何以及何时调整缓存行大小？

RAM内存缓存不佳的一个极端症状（这可能不是本文中的意思）是所谓的抖动。当进程连续生成需要磁盘访问的页面故障（例如访问不在当前页面中的内存）时，就会发生这种情况。

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

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

正如@Marc Claesen提到的，编写缓存友好代码的方法之一是利用存储数据的结构。除此之外，编写缓存友好代码的另一种方法是：更改数据的存储方式；然后编写新代码以访问存储在该新结构中的数据。

这在数据库系统如何线性化表的元组并存储它们的情况下是有意义的。存储表的元组有两种基本方法，即行存储和列存储。行存储，顾名思义，元组是按行存储的。假设存储的名为Product的表具有3个属性，即int32_t key、char name[56]和int32_tprice，因此元组的总大小为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. */

类似地，我们可以通过创建3个大小为N的数组，为Product表的每个属性创建一个数组，来模拟主内存中非常基本的列存储查询执行。这种内存布局也称为数组结构。因此，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个单独的数组（列布局）之后，我们在内存中的表Product上有行存储和列存储。

现在我们转到缓存友好的代码部分。假设我们表上的工作负载是这样的，即我们对price属性有一个聚合查询。例如

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个连续价格值被带到缓存中，因此在列布局情况下，每十六个元组都会出现缓存未命中。

因此，在给定查询的情况下，列布局将更快，而在表的列子集上的此类聚合查询中，列布局会更快。您可以使用TPC-H基准测试中的数据自己进行这样的实验，并比较两种布局的运行时间。维基百科关于面向列的数据库系统的文章也很好。

因此，在数据库系统中，如果预先知道查询工作负载，我们可以将数据存储在适合工作负载中查询的布局中，并从这些布局中访问数据。在上面的示例中，我们创建了一个列布局，并将代码更改为计算和，使其变得缓存友好。

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

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

使用连续内存布局：通过在连续内存中存储数据块，可以利用空间位置和减少缓存未命中的数量。使用数组：当您需要按顺序访问数据，因为它们允许您利用时间局部性，并将热数据保存在缓存中。小心使用指针：指针可用于访问不连续存储在内存中，但它们也会导致如果过度使用，缓存将丢失。如果您需要使用指针，尝试以利用空间的方式使用它们以及时间局部性，以最小化缓存未命中。使用编译器优化标志：大多数编译器都有优化可用于优化CPU缓存使用的标志。这些标志可以帮助减少缓存未命中的数量代码的总体性能。

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

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

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

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

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

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