cache
07. Cache 原理
0. 本章先解决什么问题
Cache 是组成原理里最影响程序性能的概念之一。
你以后会反复遇到这些现象:
- 数组顺序遍历快,链表可能慢。
- 同样 O(n),实际时间差很多。
- 多线程修改不同变量也可能互相拖慢。
- 第一次访问慢,后面访问快。
- 数据结构稍微换个布局,性能变化很大。
这些现象背后的核心是:
CPU 太快,内存太慢。
Cache 用小而快的存储保存近期可能要用的数据。
本章要从局部性、cache line、命中/未命中、映射、替换、写策略、一致性、伪共享讲清 Cache。
这张图把 cache line 的直觉画出来:CPU 访问一个地址时,附近一整段数据可能一起进入 Cache。顺序访问能吃到空间局部性,随机访问或大步长访问更容易让 CPU 停下来等内存。
这张图怎么读
图里的关键单位是 cache line,不是单个变量。
CPU 要一个地址
-> Cache 以一整行搬运附近数据
-> 接下来访问附近地址就可能命中
所以你要把访问模式画出来:
| 访问模式 | Cache 视角 |
|---|---|
| 连续访问 | 一次 miss 后吃到多个相邻元素 |
| 随机访问 | 每次可能拉一行只用一个值 |
| 大步长访问 | 每个 cache line 只用少量数据 |
| 多核写相邻变量 | 可能产生伪共享 |
Cache 不是“自动加速器”。它奖励局部性,惩罚随机跳转和不友好的数据布局。
1. 为什么需要 Cache
CPU 执行一条简单计算可能非常快,但访问主内存慢得多。
如果每次读写都直接等内存:
CPU 取数据
-> 等内存
-> 计算
-> 再等内存
CPU 会大量空转。
Cache 放在 CPU 和内存之间:
CPU -> L1 -> L2 -> L3 -> 内存
目标是:
把最近可能用的数据提前放到离 CPU 更近的地方。
2. 局部性原理
Cache 能有效,是因为大多数程序访问数据不是完全随机。
| 局部性 | 含义 | 例子 |
|---|---|---|
| 时间局部性 | 访问过的数据未来可能再次访问 | 循环变量、热点配置 |
| 空间局部性 | 访问某地址后,附近地址也可能访问 | 数组顺序遍历 |
如果程序有局部性,Cache 命中率高。
如果程序没有局部性,Cache 很难帮忙。
3. Cache line:缓存按块搬运
Cache 通常不是一个 byte 一个 byte 搬,而是按 cache line 搬。
例如一次搬 64 byte:
访问地址 X
-> 把 X 所在的一整条 cache line 搬进 Cache
如果数组元素连续:
a[0] a[1] a[2] a[3] …
访问 a[0] 时,后面的元素可能已经一起进 Cache。
如果链表节点分散:
node1 -> node2 -> node3
每次跳转都可能访问新的 cache line,甚至新的内存页。
4. 命中和未命中
| 情况 | 含义 |
|---|---|
| cache hit | 数据在 Cache 中,访问快 |
| cache miss | 数据不在 Cache,需要去下一级取 |
未命中会带来等待:
L1 miss
-> 查 L2
-> L2 miss
-> 查 L3
-> L3 miss
-> 查内存
越往下越慢。
程序性能常常不是:
CPU 不会算
而是:
CPU 一直在等数据。
5. Cache 映射:内存块放到哪里
Cache 比内存小得多,所以内存块不能全部放进去。
需要决定:
某个内存块可以放到 Cache 的哪些位置?
常见思想:
| 映射方式 | 直觉 |
|---|---|
| 直接映射 | 每个内存块只能放固定位置 |
| 全相联 | 可以放任何位置 |
| 组相联 | 先定位到组,再在组内选择位置 |
直接映射简单但容易冲突。全相联灵活但硬件成本高。组相联是常见折中。
冲突示意:
地址 A 和地址 B 映射到同一 cache 位置
反复访问 A、B
-> 互相淘汰
-> 命中率下降
这叫冲突 miss。
手推:直接映射 Cache 为什么会被两个地址打架
假设一个非常小的直接映射 Cache,只有 4 个位置。内存块放入 Cache 的位置由:
cache_index = block_number % 4
那么:
block 0 -> index 0
block 4 -> index 0
block 8 -> index 0
如果程序反复访问:
block 0, block 4, block 0, block 4…
它们会不断互相替换。虽然 Cache 总容量可能还没被其他数据用满,但这两个地址因为映射到同一个位置而持续 miss。
这就是冲突 miss 的直觉:不是工作集一定太大,而是地址映射位置撞车。
6. Cache miss 的类型
常见三类:
| 类型 | 含义 |
|---|---|
| 冷启动 miss | 第一次访问,Cache 里还没有 |
| 容量 miss | 工作集太大,Cache 放不下 |
| 冲突 miss | 不同地址映射位置冲突,互相挤掉 |
对应优化方向不同:
| miss 类型 | 可能方向 |
|---|---|
| 冷启动 | 预热、预取 |
| 容量 | 缩小工作集、分块处理 |
| 冲突 | 改布局、改访问步长 |
7. 替换策略
Cache 满了,需要淘汰旧数据。
常见策略思想:
| 策略 | 直觉 |
|---|---|
| LRU | 最近最少使用的先淘汰 |
| 近似 LRU | 硬件用低成本方式接近 LRU |
| Random | 随机淘汰 |
| FIFO | 先进先出 |
硬件真实策略可能很复杂。学习阶段抓住一点:
Cache 空间有限,访问模式决定谁留下、谁被淘汰。
8. 写策略:写 Cache 后怎么办
读比较简单:Cache 没有就去下一级拿。
写更复杂。写入 Cache 后,什么时候写回内存?
| 策略 | 含义 | 取舍 |
|---|---|---|
| write-through | 写 Cache 同时写下一级 | 一致性简单,写入成本高 |
| write-back | 先写 Cache,之后再写回 | 性能好,需要脏位和回写 |
write-back 里,被修改但还没写回下一级的 cache line 叫 dirty。
如果 dirty line 被淘汰,就必须先写回。
这和文件系统缓存、数据库缓冲池有相似思想:
先写快的缓存
之后再把脏数据刷到底层
9. 多级 Cache
现代 CPU 通常有多级 Cache:
| 层级 | 特点 |
|---|---|
| L1 | 最快,最小,通常每个核心独有 |
| L2 | 比 L1 大,稍慢 |
| L3 | 更大,通常多个核心共享 |
访问路径:
L1 hit -> 直接返回
L1 miss -> 查 L2
L2 miss -> 查 L3
L3 miss -> 查内存
越靠近 CPU 越快,但容量越小。
10. 多核 Cache 一致性
多核系统里,每个核心可能有自己的 Cache。
问题:
核心 1 修改了变量 x
核心 2 的 Cache 里还有旧的 x
系统必须维护一致性。
简化过程:
核心 1 写入某 cache line
其他核心对应副本失效或更新
这保证程序不会长期看到完全不一致的数据,但也带来成本。
多核共享写入频繁时,cache line 会在核心之间来回移动,性能可能明显下降。
11. 伪共享 false sharing
伪共享是非常实用的性能坑。
两个线程修改不同变量:
线程 A 修改 x
线程 B 修改 y
但 x 和 y 落在同一个 cache line:
cache line:
[x][y]
硬件以 cache line 为一致性单位。
所以:
A 写 x -> B 的整条 cache line 失效
B 写 y -> A 的整条 cache line 失效
它们没有共享同一个变量,却共享同一个 cache line,所以互相拖慢。
解决思路:
- 分离高频写变量。
- 填充 padding。
- 分片计数。
- 减少多核同时写同一附近区域。
反例:减少锁不一定能解决伪共享
有些性能问题看起来像锁竞争,但去掉锁后仍然慢。原因可能是多个核心仍在写同一条 cache line。
| 现象 | 可能原因 |
|---|---|
| 每个线程写自己的计数器,但吞吐仍低 | 计数器数组相邻,落在同一 cache line |
| CPU 使用率高但有效吞吐差 | cache line 在核心之间来回失效 |
| 加 padding 后变快 | 原问题是伪共享,不是算法复杂度 |
所以多线程性能分析要区分:
- 逻辑共享:多线程读写同一个变量
- 物理共享:多线程写不同变量,但变量落在同一 cache line
硬件一致性按 cache line 工作,软件语义上的“不同变量”不一定能避免硬件层共享。
12. Cache 友好的数据结构
Cache 友好通常意味着:
- 数据连续。
- 工作集小。
- 顺序访问。
- 少指针跳转。
- 少随机访问。
- 结构紧凑。
对比:
| 数据布局 | Cache 影响 |
|---|---|
| 连续数组 | 空间局部性强 |
| 链表 | 节点分散,容易 miss |
| 大对象数组 | 每次带入很多不需要字段 |
| 分离冷热字段 | 热字段更容易留在 Cache |
| 分块矩阵 | 提高块内局部性 |
这就是为什么数据结构学习不能只看 Big-O。硬件访问模式也重要。
13. 联系实际:如何从 Cache 角度分析性能
如果一个 O(n) 程序比另一个 O(n) 慢很多,问:
- 数据是否连续?
- 每次访问是否顺序?
- 是否有大量指针跳转?
- 工作集是否超过 Cache 容量?
- 是否每次只用 cache line 里很少一部分?
- 是否多线程频繁写同一 cache line?
- 是否存在随机访问或大步长访问?
- 是否能分块处理,让热点数据留在 Cache?
典型优化方向:
把随机访问改成顺序访问
把分散对象改成连续存储
把大任务切成能放进 Cache 的块
减少共享写
压缩热数据结构
小实验:用访问顺序观察 Cache
你不需要一开始就上复杂性能工具。先设计三个访问模式,观察同一批数据在不同访问顺序下的耗时差异:
| 访问模式 | 伪代码 | 预期现象 | 背后机制 |
|---|---|---|---|
| 顺序访问 | for i = 0..n-1: use a[i] | 通常最快 | 每条 cache line 被充分利用 |
| 大步长访问 | for i = 0..n-1 step k: use a[i] | 可能变慢 | 每次带入一条 line,却只用其中很少数据 |
| 随机访问 | for i in shuffled_indexes: use a[i] | 通常最不稳定 | 空间局部性差,预取也更难命中 |
实验时要注意:
- 数据规模要大到超过 L1/L2 Cache,否则差异可能不明显。
- 每组访问重复多轮,避开冷启动误差。
- 不要在循环里打印,打印会淹没内存访问成本。
- 比较的是访问模式,不要同时改变计算逻辑。
这类实验能帮你把“理论复杂度一样”拆开看:同样是 O(n),顺序扫数组和随机跳内存,对硬件来说完全不是同一种工作。
排障卡:复杂度一样,为什么实际速度差很多
遇到两个方案 Big-O 相同但性能差异很大时,可以先问:
- 数据是否连续,还是靠指针散落在堆上?
- 每次访问是否能顺着 cache line 向前推进?
- 单个元素是否太大,导致一条 cache line 里装不下几个有效字段?
- 热字段和冷字段是否混在一起,浪费 Cache 容量?
- 多线程是否在写相邻字段,引发 cache line 来回失效?
Cache 分析的价值在于把“玄学变快/变慢”变成可解释的资源问题:Cache 容量有限,cache line 是搬运单位,访问模式决定命中率。
14. 学完本章你能解决什么问题
学完这一章,你应该能解决或开始分析这些问题:
- Cache 为什么存在?
- 时间局部性和空间局部性是什么?
- cache line 为什么解释了数组快、链表慢?
- cache hit 和 cache miss 对性能有什么影响?
- Cache 映射和冲突 miss 是什么?
- write-through 和 write-back 有什么区别?
- 多核 Cache 一致性为什么会带来成本?
- 什么是伪共享,为什么不同变量也会互相拖慢?
- 如何让数据结构和访问模式更 cache 友好?
Cache 是软件和硬件交界处最重要的性能概念之一。掌握它,你会更容易看穿“复杂度一样但速度差很多”的真实原因。