6.4 缓存原理

CPU的运算速度比内存快很多倍，CPU访问内存需要等待几百个时钟周期，而CPU大部分时间都在等待内存数据，这就是著名的“内存墙“问题。为了弥补CPU和内存之间的速度差距，现代CPU都引入了多级高速缓存（Cache），理解缓存的工作原理，对于写出高性能的代码至关重要。

CPU缓存的层次结构

现代CPU通常有三级缓存：L1、L2、L3缓存，速度从快到慢，容量从小到大，离CPU越近速度越快，价格越高，容量越小。

┌─────────────────────────┐
│       CPU寄存器         │  速度：1ns  容量：几百字节
├─────────────────────────┤
│       L1缓存            │  速度：1-2ns  容量：32KB-64KB 每个核心独立
├─────────────────────────┤
│       L2缓存            │  速度：3-5ns  容量：256KB-512KB 每个核心独立
├─────────────────────────┤
│       L3缓存            │  速度：10-20ns  容量：几MB到几十MB 所有核心共享
├─────────────────────────┤
│       主存（内存）      │  速度：100ns  容量：几GB到几十GB
└─────────────────────────┘

各级缓存的特点

L1缓存：每个CPU核心独立拥有，分为L1i（指令缓存）和L1d（数据缓存），分别存储指令和数据，速度最快，容量最小。
L2缓存：也是每个核心独立拥有，比L1大，速度稍慢，存储核心近期使用的指令和数据。
L3缓存：多个核心共享，比L2大，速度更慢，用来协调多个核心之间的数据共享。

缓存的工作原理

缓存的设计基于程序的局部性原理：

程序在运行时，对内存的访问是不均匀的，在一段时间内，总是倾向于访问某一小部分内存区域。

局部性分为两种：

时间局部性：如果某个数据被访问了，那么它在不久的将来很可能会被再次访问。（比如循环中的变量）
空间局部性：如果某个数据被访问了，那么它附近的数据也很可能会被访问。（比如数组的顺序访问）

缓存就是利用局部性原理，把CPU近期可能访问的数据从内存加载到缓存中，让CPU可以快速访问。

缓存的基本操作

读操作：CPU要读取某个地址的数据时，首先检查缓存中是否有这个数据：
- 缓存命中（Cache Hit）：数据在缓存中，直接从缓存读取，速度很快
- 缓存缺失（Cache Miss）：数据不在缓存中，需要从内存读取，同时把数据和附近的一块数据加载到缓存中
写操作：CPU要写入数据时，有两种写策略：
- 写直达（Write Through）：同时写入缓存和内存，实现简单，但写入速度慢
- 写回（Write Back）：只写入缓存，标记缓存行为脏，当缓存行被替换时才写回内存，性能更高，是现在主流的写策略

缓存行（Cache Line）

缓存不是以字节为单位存储的，而是以缓存行为单位，缓存行是缓存和内存之间传输数据的最小单位，通常大小是64字节。

当缓存缺失时，会把整个64字节的缓存行从内存加载到缓存中，而不仅仅是需要的那个字节
这就是空间局部性的体现，因为访问一个数据后，附近的数据很可能也会被访问，提前加载到缓存可以提升后续访问的速度

注意：缓存行的大小是64字节，意味着如果你的程序访问数组中的一个元素，整个64字节的数组元素都会被加载到缓存中，顺序访问数组时后面的元素都已经在缓存里了，速度非常快。

缓存映射方式

缓存如何确定内存地址对应哪个缓存位置？有三种映射方式：

直接映射：每个内存地址只能映射到一个固定的缓存位置，实现简单，但冲突率高
全相联映射：每个内存地址可以映射到任意缓存位置，冲突率低，但成本高，速度慢
组相联映射：缓存分成多个组，每个内存地址映射到固定的组，可以放到组内的任意位置，是直接映射和全相联的折中，也是现在CPU常用的映射方式，比如8路组相联，就是每个组有8个缓存行。

缓存一致性（MESI协议）

在多核CPU中，每个核心有自己的L1/L2缓存，多个核心可能缓存了同一个内存地址的数据，需要保证各个核心的缓存数据一致，这就是缓存一致性。

主流的缓存一致性协议是MESI协议，每个缓存行有四个状态：

M（Modified，修改）：缓存行的数据被修改了，和内存不一致，只有当前核心有这个副本
E（Exclusive，独占）：缓存行的数据和内存一致，只有当前核心有这个副本
S（Shared，共享）：缓存行的数据和内存一致，多个核心都有这个副本
I（Invalid，无效）：缓存行的数据无效，不能使用

当某个核心修改了缓存行，其他核心的对应缓存行会被标记为无效，需要从内存重新读取，保证数据一致。

伪共享问题

伪共享（False Sharing）是多核CPU下常见的性能问题，会严重降低程序的性能。

什么是伪共享

当两个不同的变量存储在同一个缓存行中，两个不同的核心分别修改这两个变量时，即使它们互不相关，也会导致缓存行不断地在两个核心之间失效和同步，性能急剧下降。

示例：

// 两个变量a和b在内存中相邻，位于同一个64字节的缓存行中
long a;
long b;

// 核心1不断修改a
void core1() {
    while(1) a++;
}

// 核心2不断修改b
void core2() {
    while(1) b++;
}

这种情况下，虽然两个核心修改的是不同的变量，但因为它们在同一个缓存行，每次修改都会导致另一个核心的缓存行失效，需要重新从内存读取，性能比单线程还慢很多，这就是伪共享。

如何避免伪共享

缓存行填充：在变量之间填充无用的字节，让不同的变量位于不同的缓存行：

// 每个变量占64字节，独占一个缓存行
struct {
    long a;
    char padding[64 - sizeof(long)]; // 填充到64字节
    long b;
    char padding2[64 - sizeof(long)];
} data;

或者使用编译器的对齐属性，让变量按64字节对齐。

注意：不要过度填充，会浪费缓存空间，只需要在会被多个核心并发修改的变量之间填充即可。

缓存性能优化方法

理解缓存原理，我们可以写出对缓存更友好的代码，提升程序性能：

1. 充分利用局部性

时间局部性：尽量让最近访问过的数据尽快再次访问，避免被换出缓存
- 把常用的数据放在一起，减少分散访问
- 避免在循环中访问大量不相关的数据
空间局部性：尽量顺序访问连续的内存地址
- 数组优先顺序访问，避免随机访问
- 数据结构设计尽量紧凑，避免过多的指针跳转
- 多维数组按行优先顺序访问（C/C++是行优先）

示例：顺序访问 vs 随机访问

// 顺序访问数组，速度非常快，缓存命中率接近100%
for (int i = 0; i < N; i++) {
    sum += array[i];
}

// 按列访问二维数组，空间局部性差，缓存命中率低，速度慢很多
for (int j = 0; j < N; j++) {
    for (int i = 0; i < N; i++) {
        sum += array[i][j];
    }
}
// 优化：交换内外层循环，改为行优先访问，速度提升很多
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        sum += array[i][j];
    }
}

2. 优化数据结构

结构体成员按访问频率排序：把经常一起访问的成员放在一起，按大小排序，减少结构体的大小
避免过度使用指针：指针跳转是随机访问，缓存命中率低，尽量使用数组和连续存储
使用更小的数据类型：用更小的类型可以让更多的数据放到缓存里，提升缓存利用率，比如能用int就不用long，能用float就不用double

3. 避免伪共享

多线程并发修改的变量要注意缓存行对齐，避免在同一个缓存行
尽量让每个线程访问自己的数据，避免多个线程修改同一缓存行的数据

4. 使用大页（Huge Page）

普通页大小是4KB，大页是2MB或者1GB，使用大页可以：

减少页表的大小，节省内存
提升TLB命中率，减少TLB miss的开销
适合内存占用大、访问连续的应用，比如数据库、Java虚拟机、大数据处理等

5. 缓存预热

对于需要低延迟的场景，可以提前把要访问的数据加载到缓存中，避免第一次访问时的缓存缺失延迟。

性能分析工具

可以使用以下工具分析程序的缓存命中率：

perf：Linux下的性能分析工具，可以统计cache-misses、TLB-misses等事件
valgrind：可以模拟缓存行为，统计缓存命中率
Intel VTune：Intel的性能分析工具，图形化展示缓存使用情况

优化缓存性能的核心指标是缓存命中率，命中率越高，程序性能越好。

思考问题

什么是局部性原理？时间局部性和空间局部性分别是什么？举例说明。
为什么顺序访问数组比随机访问快很多？
什么是伪共享？它为什么会导致性能下降？如何避免伪共享？
缓存行的大小通常是多少？它的大小对程序性能有什么影响？

Keyboard shortcuts

计算机基础通识讲义