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

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

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

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

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

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

核心直觉:缓存以 64 字节的行为单位搬运(见 cache-organization)。你每碰一个字节,硬件都把它所在的整条 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)。成员按大小降序排能挤掉空洞,结构体更小 → 一条 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)。

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)。

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 第五节)。

六、其他实用技巧

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

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

cache-friendly 优化必须测量驱动——改完对比 cache-miss 和 IPC(见 perf):

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 的 backend stall)——回头查访问模式(顺序?)、数据布局(紧凑?SoA?)、有没有伪共享。

八、一张速查清单

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

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

机制来源:cache-organization(cache line 64B、命中判定——本篇一切的物理基础)、i-cache(代码侧的缓存——代码膨胀/布局也影响性能)、tlb(大跨步/随机访问还会撞 TLB)、memory-alignment(对齐、padding、SoA)。
多线程:mesi(伪共享的原理)、atomic(原子争用)。
为什么 miss 这么伤:cpu-microarch-overview(cache miss → 流水线 backend stall → IPC 塌)、cache-organization 的周期表(L1~1ns vs 内存~100ns)。
NUMA 上更进一步:numa(跨节点访问,cache-friendly 之外还要 NUMA-local)。
观测:perf(cache-misses、c2c、IPC)。
配套实验:仓库 demos/false-sharing/（cd demos/false-sharing && make run）直接感受伪共享的几倍差距;demos/cpu-demo/ 的 make release 演示优化器如何改掉热点。

十、一句话总结

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

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

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

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

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

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

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

3.3 冷热字段分离 ​

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

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

六、其他实用技巧 ​

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

八、一张速查清单 ​

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

十、一句话总结 ​