# 写出 cache-friendly 的代码 —— 把前面所有缓存知识落到编码习惯

> 前面 cache/ 下讲了缓存怎么组织（[cache-organization.md](/concepts/cache/cache-organization.md)）、伪共享（[mesi.md](/concepts/cache/mesi.md)）、TLB（[tlb.md](/concepts/cache/tlb.md)）、对齐（[memory-alignment.md](/concepts/cache/memory-alignment.md)）——都是"机制"。本篇是**落地篇**:把这些机制翻译成**日常编码时能照做的习惯**,回答一个实际问题——**"我该怎么写代码,才能让 CPU 缓存帮我、而不是拖我后腿?"**


> 一句话立场:**现代 CPU 上,决定性能的往往不是"算了多少次",而是"数据在不在缓存里"。** 一次 L1 命中 ~1ns、一次内存 miss ~100ns——差 100 倍。cache-friendly 编码的全部,就是**让访问尽量命中缓存**。

## 一、两条根本原则:时间局部性 + 空间局部性

缓存之所以有效,全靠程序的**局部性(locality)**。写 cache-friendly 代码,本质就是主动制造这两种局部性:

| 原则 | 含义 | 缓存为什么受益 |
|------|------|---------------|
| **时间局部性(temporal)** | 刚访问过的数据,**很快会再访问** | 它还在缓存里 → 第二次命中 |
| **空间局部性(spatial)** | 访问了一个地址,**相邻地址也很快会访问** | 缓存按 **64B cache line** 整条拉取,相邻数据顺带进了缓存 → 后续命中 |

```plantuml
@startuml
skinparam shadowing false
skinparam rectangle {
  BackgroundColor<<good>> #C8E6C9
  BorderColor<<good>> #388E3C
  BackgroundColor<<bad>> #FFCDD2
  BorderColor<<bad>> #C62828
}
rectangle "cache-friendly\n顺序/紧凑访问\n→ 每拉一条 64B line,\n里面 8~16 个元素都会被用到\n→ 高命中" <<good>> as G
rectangle "cache-hostile\n随机/跳跃/指针追逐\n→ 每拉一条 line 只用 1 个元素,\n其余 63B 白拉、还挤掉别的\n→ 高 miss" <<bad>> as B
G -right-> B : 反面
@enduml
```

> **核心直觉**:缓存以 **64 字节的行**为单位搬运(见 [cache-organization.md](/concepts/cache/cache-organization.md))。你每碰一个字节,硬件都把它所在的整条 64B 拉进缓存。**用满这条行(相邻数据都用到)= 高效;每条行只用一个字节就跳走 = 把带宽和缓存都浪费了。** 下面的所有技巧,都是这一条的推论。

## 二、顺序访问 >> 随机访问(空间局部性)

最基本、也最有效的一条:**按内存顺序访问,别跳着来**。

```cpp
// ✅ 顺序:每条 cache line 拉进来,里面 16 个 int 全用到
for (int i = 0; i < N; i++) sum += a[i];
// ❌ 大跨步:每次跳很远,每条 line 只用一个元素就走
for (int i = 0; i < N; i += 16) sum += a[i];   // 每次一条新 line,浪费 15/16
```

**二维数组尤其要注意行优先**。C/C++ 是**行优先(row-major)** 存储,`a[i][j]` 的内存顺序是 `j` 变化最快:

```cpp
// ✅ 内层遍历列 j —— 顺着内存走,连续命中
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        sum += a[i][j];
// ❌ 内层遍历行 i —— 每次跨一整行(N 个元素)的距离,几乎每次 miss
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        sum += a[i][j];   // 大矩阵下能慢好几倍!
```

> 这是最经典的 cache 陷阱:两段代码算的东西**一模一样**,只是循环嵌套顺序反了,大矩阵下慢 5~10 倍。原因纯粹是访问顺序——一个顺着 cache line 走、一个每次跳一整行。**记住:让最内层循环走内存里最连续的那一维。**

## 三、数据紧凑:结构体布局、SoA vs AoS

缓存效率还取决于**你关心的数据在内存里挤得有多紧**——同样一条 64B line 里,有用数据占比越高越好。

### 3.1 结构体去 padding、按大小排成员

编译器为对齐插的 padding 会撑大结构体,让一条 cache line 装更少有效元素(详见 [memory-alignment.md](/concepts/cache/memory-alignment.md))。**成员按大小降序排**能挤掉空洞,结构体更小 → 一条 line 装更多 → 遍历数组更少 miss。

### 3.2 SoA vs AoS:只用部分字段时,拆开存

假设遍历一百万个粒子,**只累加它们的 `x` 坐标**:

```cpp
// ❌ AoS (Array of Structs):x 和不相关的字段挤在一起
struct Particle { float x, y, z; int id; char name[16]; };  // 32 字节
Particle ps[N];
for (int i = 0; i < N; i++) sum += ps[i].x;
//   每条 64B line 只有 2 个 x 有用,其余 y/z/id/name 全被顺带拉进来占着缓存 → 浪费
// ✅ SoA (Struct of Arrays):同类字段连续存
struct Particles { float x[N], y[N], z[N]; int id[N]; };
Particles ps;
for (int i = 0; i < N; i++) sum += ps.x[i];
//   每条 64B line 装 16 个 x,全部有用 → 命中率拉满,还能自动向量化(SIMD)
```

| | AoS(对象数组) | SoA(数组的结构) |
|---|---|---|
| 布局 | 一个对象的所有字段挨着 | 同一字段的所有值挨着 |
| 只用部分字段遍历 | 差:每条 line 混入无关字段 | **好:每条 line 全是有用数据** |
| 用整个对象(逐个处理) | 好 | 差:一个对象的字段散在各数组 |
| SIMD 向量化 | 难 | **易** |

> 准则:**看你的热点循环用对象的哪些字段**。只批量处理少数几个字段(数值计算、ML、图形)→ **SoA**;每次都要完整对象(OOP 逻辑)→ **AoS**。这是 data-oriented design 的核心取舍。

### 3.3 冷热字段分离

一个结构体里若既有**每次都碰的热字段**、又有**极少用的冷字段**,把冷字段拆到别处(或用指针),让热字段更紧凑地挤进 cache line:

```cpp
// ❌ 热字段 count 和冷字段 debug_log 混在一起 → 遍历 count 时把 log 也拉进缓存
struct Node { int count; char debug_log[256]; Node* next; };
// ✅ 冷字段拆出去,热路径的 Node 更小、一条 line 装更多
struct Node { int count; Node* next; ColdData* cold; };
```

## 四、避免指针追逐(pointer chasing)

链表、树、哈希表(拉链)这类**靠指针跳来跳去**的结构,是 cache 的天敌:每个节点是独立 malloc 的、**散落在堆各处**,遍历时每跳一个节点就是一次几乎必然的 cache miss(还可能带 TLB miss,见 [tlb.md](/concepts/cache/tlb.md))。

```cpp
// ❌ 链表遍历:next 指向哪不知道,每步一次 miss、CPU 预取器也猜不到
for (Node* p = head; p; p = p->next) sum += p->val;
// ✅ 换成连续数组:顺序访问、预取器友好、每条 line 用满
for (int i = 0; i < n; i++) sum += arr[i].val;
```

对策:

- **能用数组/vector 就别用 list**——连续内存吊打链表,即便理论复杂度相同(`std::vector` 的遍历通常远快于 `std::list`)。
- **必须用链式结构**:用**内存池/arena** 集中分配节点,让它们在内存里尽量连续(减少 miss + 帮预取器)。
- **哈希表**:开放寻址(`absl::flat_hash_map`)比拉链(`std::unordered_map`)更 cache-friendly——数据在一块连续数组里,不是散落的节点。

## 五、多线程:别让缓存"打架"(伪共享)

单线程管好局部性,多线程还要防**伪共享(false sharing)**——两个线程各写各的变量,却因为落在**同一条 cache line** 上,互相把对方的缓存打成无效,cache line 在两核间"乒乓"(详见 [mesi.md](/concepts/cache/mesi.md))。

```cpp
// ❌ 伪共享:counters[0] 和 counters[1] 在同一条 64B line,两线程各写一个 → 疯狂失效
long counters[NUM_THREADS];
// ✅ 每个计数器独占一条 cache line
struct alignas(64) PaddedCounter { long v; };
PaddedCounter counters[NUM_THREADS];
```

> 注意方向:**单线程遍历要"紧凑"(数据挤进少的 line),多线程各写各的要"隔离"(热点变量独占 line)**——两个相反的手法,判断依据是"单线程访问还是多核并发写"(见 [memory-alignment.md](/concepts/cache/memory-alignment.md) 第五节)。

## 六、其他实用技巧

| 技巧 | 说明 |
|------|------|
| **分块(blocking/tiling)** | 大矩阵运算按能塞进 L1/L2 的小块处理,让块内数据反复用(时间局部性)。矩阵乘法分块能快数倍 |
| **热数据集中** | 把频繁访问的数据放一起、和冷数据分开,提高热工作集的缓存驻留 |
| **预取(prefetch)** | 硬件预取器能识别顺序/固定步长访问、提前拉数据;顺序访问就是在配合它。不规则访问可用 `__builtin_prefetch` 手动提示(但慎用,先测) |
| **减小工作集** | 让热循环的数据总量能装进 L1/L2(几十 KB~MB),而不是每次刷穿到内存 |
| **对齐到 cache line** | 热点数据结构 `alignas(64)`,避免跨 line、利于 SIMD(见 [memory-alignment.md](/concepts/cache/memory-alignment.md)) |

## 七、怎么验证:用 perf 看,别凭感觉

cache-friendly 优化**必须测量驱动**——改完对比 cache-miss 和 IPC(见 [../code/perf.md](/tools/code/perf.md)):

```bash
# 看缓存命中情况和 IPC:miss 高、IPC 低 = 缓存不友好
perf stat -e cycles,instructions,cache-references,cache-misses,LLC-load-misses ./app
#   cache-misses / cache-references = miss 率;优化后应下降、IPC 应上升
# 定位是哪段代码 cache-miss 集中
perf record -e cache-misses ./app && perf report
# 多线程伪共享专用
perf c2c record ./app && perf c2c report      # 找跨核争抢的 cache line(HITM)
# TLB(大跨步/随机访问的另一个受害者)
perf stat -e dTLB-load-misses ./app
```

判读:**cache-miss 率高 + IPC 低**,说明 CPU 大量时间在等内存(见 [cpu-microarch-overview.md](/concepts/microarch/cpu-microarch-overview.md) 的 backend stall)——回头查访问模式(顺序?)、数据布局(紧凑?SoA?)、有没有伪共享。

## 八、一张速查清单

- [ ] **顺序访问**,别跳跃;二维数组内层走最连续的维(行优先)
- [ ] **数据紧凑**:结构体成员按大小排、去 padding
- [ ] 只用部分字段批量处理 → **SoA**;冷热字段分离
- [ ] **少用链表/散节点**,优先连续数组/vector;必须用则内存池集中分配
- [ ] 多线程热点变量 **`alignas(64)` 防伪共享**
- [ ] 大数据运算 **分块** 让块内数据反复用
- [ ] 热工作集尽量 **装进 L1/L2**
- [ ] **用 `perf` 测**(cache-misses/IPC/c2c),别凭感觉

## 九、和本仓库其他文档的关系

- **机制来源**:[cache-organization.md](/concepts/cache/cache-organization.md)(cache line 64B、命中判定——本篇一切的物理基础)、[i-cache.md](/concepts/cache/i-cache.md)(代码侧的缓存——代码膨胀/布局也影响性能)、[tlb.md](/concepts/cache/tlb.md)(大跨步/随机访问还会撞 TLB)、[memory-alignment.md](/concepts/cache/memory-alignment.md)(对齐、padding、SoA)。
- **多线程**:[mesi.md](/concepts/cache/mesi.md)(伪共享的原理)、[atomic.md](/concepts/cache/atomic.md)(原子争用)。
- **为什么 miss 这么伤**:[cpu-microarch-overview.md](/concepts/microarch/cpu-microarch-overview.md)(cache miss → 流水线 backend stall → IPC 塌)、[cache-organization.md](/concepts/cache/cache-organization.md) 的周期表(L1~1ns vs 内存~100ns)。
- **NUMA 上更进一步**:[../numa/numa.md](/concepts/numa/numa.md)(跨节点访问,cache-friendly 之外还要 NUMA-local)。
- **观测**:[../code/perf.md](/tools/code/perf.md)(cache-misses、c2c、IPC)。

## 十、一句话总结

> **cache-friendly 编码的全部,就是制造局部性、让访问命中缓存(命中 ~1ns vs miss ~100ns,差 100 倍)。核心是缓存按 64B 行搬运——用满每条行才高效。落地成习惯:顺序访问别跳跃(二维数组内层走最连续维)、数据紧凑(去 padding、只用部分字段就 SoA、冷热分离)、少用指针追逐的链表/散节点(优先连续数组)、多线程热点变量 alignas(64) 防伪共享、大运算分块让数据反复用。注意"单线程要紧凑、多核要隔离"是两个相反方向。最后——一切以 perf 的 cache-misses/IPC 测量为准,别凭感觉。**