缓存基础解释与缓存友好型编程基础

讨论了如何使用快速核心内存（约32,000个字）作为更大、更慢的核心内存（约1,000,000个字）的从属内存（slave）。

通过这种方式，可以在实际使用案例中设计出接近于更快内存的有效访问时间（effective access time），而不是较慢的内存。

-《从属内存与动态存储分配》（1965年，莫里斯·威尔克斯）

我们总是被迫进行缓存友好的编程。

现代处理器不仅在CPU性能方面有所提升，内存带宽和缓存效率也成为了性能的关键因素。

即使执行相同的运算，根据内存访问方式的不同，性能差异可能会非常大。理解和优化这一点就是缓存优化编程。

那么，让我们来理解一下什么是缓存。

什么是缓存？

缓存是用于解决CPU与内存（RAM）之间速度差距的高速存储器。

每当CPU处理数据时，如果每次都直接访问RAM，性能会大大降低，因此缓存会存储经常使用的数据以缩短访问时间。

缓存具有分层结构，现代缓存通常分为L1、L2、L3三层（少数情况下甚至有L4）。

L1最小且最快，而L3则逐渐变大但速度变慢。

那么，这一切是如何开始的呢？

缓存的历史

缓存的需求本身在冯·诺依曼的经典论文中已被认识到，这篇论文奠定了冯·诺依曼架构的基础。

在这篇论文中，已经意识到高速运算单元和内存速度之间的不平衡，并间接暗示了类似缓存解决方案的必要性。

缓存的确切起源可以追溯到莫里斯·威尔克斯教授的《从属内存与动态存储分配》（1965年，莫里斯·威尔克斯）。在这篇文章中，缓存被称为“从属内存”（Slave Memory）。

从属内存意味着它是一个依赖于主内存工作的层级结构，表示缓存会复制主内存（Core Memory）的部分数据并使用它。

当时（1960年代中期），计算机技术正在迅速发展，但...

内存系统存在严重的冯·诺依曼瓶颈（Von Neumann bottleneck）现象。

原因是当时的主内存（Core Memory）主要使用磁芯内存（Magnetic Core Memory），虽然稳定，但读写速度为微秒级别，无法跟上CPU的快速运算速度，从而导致整个系统的性能下降。

因此，由于CPU与内存之间的数据传输速度差异，冯·诺依曼瓶颈问题变得非常严重。

（莫里斯·威尔克斯Maurice Wilkes）

在这个过程中，威尔克斯教授在1965年的《从属内存与动态存储分配》中提出了从属内存的概念。

从属内存（Slave Memories）是指在CPU和主内存之间设置一个高速的小规模内存层，以提高对常用数据的访问速度，从而提升整体系统性能。这是现代缓存的雏形。

随后，IBM System/360 Model 85基于莫里斯·威尔克斯教授的从属内存概念克服了技术障碍，并首次在商用系统中引入了这一概念，同时确立了“缓存”这一术语。

“缓存”一词源自法语“cache”（藏匿处），意指隐藏常用数据以便快速访问的存储器。

尽管按现在的标准来看，其容量仅为KB级别，非常小，但它确实帮助提升了CPU性能。

这被认为是L1（一级缓存）的雏形。不过，当时只使用了“缓存”这一名称，并没有使用L1这个称呼。

随着后来多层结构的整理，才逐步划分为L1和L2。

无论如何，仅靠L1缓存无法完全弥合CPU和主内存之间的速度差距，因此需要更大容量的缓存来辅助L1。

随着新一代处理器的速度越来越快，CPU周期时间和主内存访问时间之间的差距将进一步扩大。

这种差距的增加使得设计单级缓存变得更加困难。

也就是说，很难设计出既能足够快以匹配快速的CPU周期时间，又能足够大以有效隐藏较慢主内存访问时间的单级缓存。

解决这个问题的一种方法是使用多级缓存（multi-level cache hierarchy） 。

本文研究了多级缓存的组成方式及其与程序执行时间的关系。

-《性能最优多级缓存层次结构的特性》（Steven Przybylski, Mark Horowitz, John Hennessy, 1989）

最初并没有明确称为L2（二级缓存）的名称，但随着1980年代后期多级缓存结构需求的出现，这一概念逐渐确立。

1989年引入了多级缓存结构（Multi-Level cache hierarchy），相关论文《性能最优多级缓存层次结构》分析了其必要性。

无论如何，L1之后出现了L2，并以外部芯片的形式搭载L2缓存。直到英特尔奔腾Pro（1995年）才在CPU封装内集成了L2缓存（On-Chip Cache），使L2缓存得以广泛普及。

随着CPU核心数量的增加，每个核心高效共享缓存并保持数据一致性成为了一个重要的课题。

而为了解决这个问题，L3缓存应运而生。

（首款搭载L3缓存的消费级CPU——英特尔奔腾4 Extreme Edition 2003）

当然，在当前环境中，L3缓存作为多核环境中的共享缓存提升了性能。但在现代系统中，由于CPU与内存之间的带宽问题以及图形和AI计算的增长，对超高速内存访问的需求使得L4缓存的重要性日益凸显。

L4缓存不仅可以与CPU共享，还可以与集成GPU（iGPU）共享。

实际上，英特尔在2013年推出了名为Crystal Well的L4缓存，但由于成本过高，目前尚未像L3那样广泛商业化，主要用于高性能服务器。

现在，让我们总结一下缓存的层次结构。

缓存的层次结构（Memory Hierarchy）

层次	容量	访问时间	位置	特点
L1	32~64KB	1~4 CPU周期	CPU核心内置	- 最快且最小的缓存 - 指令缓存和数据缓存分离（L1I, L1D）
L2	256KB~1MB	10~20周期	CPU核心附近	- 每个核心单独拥有 - 比L1缓存大但速度较慢
L3	16~64MB	50~100周期	多个核心共享	- 多个核心共享的缓存 - 负责缓存一致性管理
L4	64MB~256MB+	150~300周期	CPU封装内或外部芯片	- 用于部分高性能服务器、AI计算、集成GPU（iGPU） - 可与CPU、GPU、内存控制器共享
DRAM	8GB~1TB+	300~500周期	主板DIMM插槽	- 系统整体内存 - 比L4缓存大但速度较慢 - 易失性存储器（断电后数据丢失）

从L1到L4，容量逐渐增大但速度逐渐变慢。当发生缓存未命中时，必须参考DRAM，这会显著降低CPU性能。

当从RAM中获取数据时，通常需要100~300个周期。

随着L4缓存容量的增加，它变得越来越像DRAM，使用快速DRAM比搭载L4缓存更具成本效益，因此目前消费者PC中尚未积极采用L4缓存。

特别是随着HBM（高带宽内存）的出现，L4缓存的作用被取代，因此L4目前仅用于服务器、AI加速器等特殊环境。

不过，未来会发生什么还不得而知。

缓存的工作原理

接下来，让我们解释一下缓存的工作原理。

（缓存直接映射图）

缓存行（Cache Line）

缓存行是缓存存储和管理数据的最小单位。当CPU从内存中获取数据时，不是以单个字节或字为单位获取，而是以固定大小的数据块（缓存行）为单位一次性获取。通过这种方式，提高了内存访问效率，并利用数据局部性（Locality）优化性能。

在现代系统中，缓存行通常为64字节（即512位）。在过去，也有使用16字节或32字节的情况，但近年来64字节已成为标准。

缓存行不仅包含数据，还包括元数据（标签、有效位、脏位等）。

缓存行的结构

缓存行在缓存中作为一个“槽”或“条目”存储，包含以下信息：

数据（Data）： 从主内存中获取的实际数据块（例如：64字节）。不仅包括CPU请求的数据，还包括周围的数据（利用空间局部性）。
标签（Tag）： 表示该缓存行引用的主内存地址信息，用于识别数据来自哪个内存位置。
有效位（Valid Bit）： 表示该缓存行是否包含有效的数据（0：空，1：有效）。
脏位（Dirty Bit）： 在写回（write-back）缓存中使用，表示缓存行中的数据已被修改但尚未与主内存同步。
其他元数据： 包括用于缓存替换策略（如LRU，最近最少使用）的时间信息、缓存一致性状态（MESI协议中的Modified、Exclusive、Shared、Invalid等）。

缓存行的操作原理

缓存行决定了CPU访问内存时如何获取和管理数据。

以下是操作过程的逐步说明：

1. 缓存命中（Cache Hit）与未命中（Cache Miss）

当CPU请求内存地址X的数据时，缓存会检查该地址所属的缓存行。

命中： 如果请求的地址已经在缓存行中，则直接从缓存返回数据（快速访问）。
未命中： 如果缓存行中没有，则从主内存中获取包含该地址及其周围数据的整个缓存行。

2. 数据预取（Fetching）

当发生缓存未命中时，CPU会以缓存行大小（例如64字节）为单位获取请求的数据。

例如：请求地址0x1000的数据时，会一次性获取0x1000~0x103F（64字节范围）的数据。

这是利用了空间局部性（spatial locality） ，假设相邻数据很快会被使用。

3. 缓存行存储

获取的缓存行存储在缓存的槽中。

直接映射（Direct-Mapped）： 每个内存地址映射到固定的缓存行位置。
组相联（Set-Associative）： 存储在多个缓存行（集合）中的一个，由替换策略（如LRU）决定。
全相联（Fully Associative）： 可以存储在缓存中的任何位置（现实中很少见）。

当缓存已满时，会替换现有缓存行（replacement）。

4. 写操作

写命中（Write Hit）：
- 写直达（Write-Through）： 同时更新缓存和主内存。
- 写回（Write-Back）： 仅更新缓存并设置脏位，稍后再同步到主内存。
写未命中（Write Miss）：
- 写分配（Write-Allocate）： 获取缓存行并在缓存中写入后更新。
- 非写分配（No-Write-Allocate）： 直接写入主内存而不使用缓存。

5. 缓存一致性

在多核CPU中，每个核心的缓存行可能引用相同的内存地址。

通过MESI协议等机制保持缓存行之间的数据一致性。

缓存的主要概念解释

局部性（Locality）

时间局部性（Temporal Locality）： 当重复使用相同数据时，缓存命中率会提高。
空间局部性（Spatial Locality）： 当顺序访问相邻内存地址时效率更高。

缓存未命中的三种类型

（图片来源：https://rocketcdn.me/what-is-a-cache-hit-ratio/）

1. 强制未命中（Compulsory Miss）

定义：首次访问数据时发生的缓存未命中，无法避免的必然未命中。也称为“冷未命中”或“首次引用未命中”。

原因：缓存为空时，或程序首次使用特定数据时，缓存中不存在该数据。

特点：主要发生在程序执行初期，数据一旦被加载到缓存中，这种类型的未命中就会减少。

示例：程序启动时第一次读取数组int array[100]的array[0]时，缓存中没有数据，因此发生强制未命中。之后访问array[0]时则为缓存命中。

减少方法：通过硬件预取器或软件预取数据，可以减少强制未命中。虽然无法完全消除，但可以改善初始加载速度。

2. 冲突未命中（Conflict Miss）

定义：即使缓存中有空间，但由于其他数据占据了相同的缓存行而导致的缓存未命中。也称为“映射未命中”。

原因：当缓存为直接映射（direct-mapped）或组相联（set-associative）时，多个内存地址映射到同一缓存行，导致冲突。

特点：与缓存大小无关，取决于缓存映射方式和数据访问模式。

示例：假设有4个缓存行（每行64字节）且为直接映射，地址0x1000和0x2000映射到同一缓存行（例如第0行）。先加载0x1000，再访问0x2000时，0x1000被驱逐（Eviction），再次访问0x1000时发生冲突未命中。

减少方法：使用2路、4路组相联缓存以减少冲突可能性；通过数据填充（Padding）调整内存布局以避免数据冲突；对齐数据结构以最小化冲突。

3. 容量未命中（Capacity Miss）

定义：当缓存大小不足以容纳所有活动数据（working set）时发生的缓存未命中。由于缓存容量不足，频繁使用的数据被驱逐（Eviction）并需要重新获取。

原因：程序的数据集大小超过缓存容量时，发生频率增加。

特点：直接依赖于缓存大小，与关联性或映射方式关系不大。

示例：在一个具有256KB L2缓存的系统中，反复遍历1MB数组时，前256KB加载到缓存中，但随着数组末尾的到达，超出的数据覆盖了先前的缓存行。当再次回到开头时，因缓存被驱逐的数据导致容量未命中。

减少方法：增加缓存大小（如L2、L3等）以缓解容量问题；通过改进数据局部性（例如块处理）减少工作集；选择高效算法以减少不必要的数据访问。

缓存未命中的三种类型通常被称为“3C模型”。

总缓存未命中率 = 强制未命中 + 冲突未命中 + 容量未命中。

通过这种方式，尽量减少缓存未命中是程序员能力的体现。

减少3C缓存未命中的方法示例

强制未命中： 第一次访问不可避免的未命中 → 使用预取缓解。
冲突未命中： 相同缓存行冲突 → 使用8路组相联 + 填充解决。
容量未命中： 超过缓存容量 → 使用分块（Blocking）分割数据集。

非缓存友好代码

int array[1024][1024]; // 4MB（每个元素4字节）
for (int j = 0; j < 1024; j++) 
{ // 按列优先访问
    for (int i = 0; i < 1024; i++) 
    {
        array[i][j] = i + j; // 按列访问（非连续）
    }
}

缓存友好代码

int array[1024][1024];
for (int i = 0; i < 1024; i++) 
    { // 按行优先访问
    for (int j = 0; j < 1024; j++) 
    {
        array[i][j] = i + j; // 按行访问（连续）
    }
}

（C语言系列中的缓存友好代码编写）

1. 利用空间局部性的顺序访问

在二维数组中，C语言系列中按列（Column）访问会导致内存地址不连续，缓存行频繁更换。

例如，array[0][0]之后访问array[1][0]时，两者相差4096字节（1024*4），缓存行（64字节）无法充分利用相邻数据，导致容量未命中增加。

因此，按行访问时，array[i][j] -> array[i][j+1]仅相差4字节，可以利用空间局部性。

（不过，这是因为C语言按行存储数据。如果是Matlab等按列存储的语言，则应按列访问。）

非缓存高效代码

int array[4096][4096]; // 64MB
for (int i = 0; i < 4096; i++) 
{
    for (int j = 0; j < 4096; j++) 
    {
        array[i][j] *= 2;
    }
}

分块处理以提高缓存效率

int array[4096][4096];
const int BLOCK_SIZE = 64; // 与缓存行（64字节）和数组大小对齐
for (int ii = 0; ii < 4096; ii += BLOCK_SIZE) 
{
    for (int jj = 0; jj < 4096; jj += BLOCK_SIZE) 
    {
        for (int i = ii; i < ii + BLOCK_SIZE && i < 4096; i++) 
        {
            for (int j = jj; j < jj + BLOCK_SIZE && j < 4096; j++) 
            {
                array[i][j] *= 2; // 按64x64块处理
            }
        }
    }
}

2. 分块处理以减少容量未命中

将大数据集分成适合缓存大小的块以最小化容量未命中。

例如，64MB数组会超过L2（1MB）或L3（16MB）缓存，随着数组末尾的到达，最初加载的数据被驱逐并重新获取，导致容量未命中增加。

将数据分成64x64块（16KB）进行处理，每个块更有可能保留在缓存中。

非缓存高效结构

struct Data 
{
    int a; // 4字节
    int b; // 4字节
} data[1024];
    
for (int i = 0; i < 1024; i++) 
{
    data[i].a = i; // 可能映射到同一缓存行
    data[(i + 256) % 1024].b = i; // 高概率发生冲突
}

缓存高效结构

struct Data 
{
    int a; // 4字节
    int b; // 4字节
    char padding[56]; // 添加填充以匹配64字节缓存行
} data[1024];
for (int i = 0; i < 1024; i++) 
{
    data[i].a = i;
    data[i].b = i; // 连续访问，最小化冲突
}

3. 使用数据填充减少冲突未命中

在原始代码中，data[i]和data[i+256]可能映射到相同的缓存行。通过将结构体大小填充到64字节，确保每个元素映射到唯一的缓存行。

这样可以改变访问模式为顺序访问，增强时间和空间局部性。

*数据填充（Data Padding）：为了内存对齐和缓存性能优化，在数据间插入额外的空白空间（Padding），减少伪共享（False Sharing）。

此外，还有缓存阻塞、分块等示例，但由于篇幅限制，这里不再赘述。

无论如何，这些都是典型的示例，以下是一些编写缓存友好代码的提示。

缓存友好代码编写技巧

顺序访问 ：按行处理数组以充分利用缓存行。
调整数据大小 ：将工作数据集调整为适合缓存大小（L1：32KB，L2：256KB等）。
填充：将结构体对齐到缓存行（64字节）边界以避免冲突。
预取：使用显式或隐式预取来减少强制未命中。
循环优化 ：设计嵌套循环，使内部循环访问连续内存。

此外，在选择算法时也需要注意。

例如，快速排序和归并排序的平均时间复杂度相同，
但快速排序具有缓存友好的访问模式，而归并排序由于需要额外的内存空间，可能导致缓存效率较低。

让常见情况更快（Make the common case fast）——David Patterson

正如我们之前所见，缓存并不仅仅是“快速内存”。
它是一个控制数据流动的预测系统，同时也是连接硬件与软件的桥梁和翻译者。

因此，作为程序员，我们肩负着将硬件与软件紧密连接的重要使命。
我们的任务不仅仅是编写代码，更是成为在硬件与软件之间架起桥梁的人，就像一个让两者流畅沟通的翻译者。

我们所做的，不仅仅是写代码，而是向硬件传递我们的想象，赋予它生命，让它理解我们的意图并与软件协同工作。