正常
写对缓存友好的代码:布局、对齐与决策
前三篇咱们把缓存的机制讲透了:复杂度不是一切、内存比计算慢 100 倍、数据按 64 字节缓存行整块搬、缩小类型未必更快。这一篇把这些机制收拢成一套能落地的工程方法——面对一个具体场景,你怎么一步步把代码改得对缓存友好。最后还会聊一个笔者自己实测踩到的坑:AoS/SoA 这个经典优化,在本机就是测不出差异。
第一条:数据连续排布,优先于节点分散
这是所有缓存友好原则里最硬的一条,也是第一篇实验直接证明过的。std::vector 的数据是一段连续内存,遍历时完美利用缓存行和硬件预取;std::list、std::set、std::map 这些节点式容器,每个节点单独分配、散落在堆各处,每次跳节点都是潜在的 cache miss。
回顾第一篇那张表:N=262144 时,排序 vector 的二分查找(8090 us)把同为 O(log n) 的 std::set(19903 us)甩出两倍多。复杂度完全相同,差距纯粹来自连续 vs 分散。所以只要不需要节点式容器的特定语义(频繁中间插入删除、迭代器稳定性),std::vector 几乎总是更缓存友好的选择。
这一条推到极致,就是连你的自定义数据结构也应该尽量连续存。比如存一万条记录,用 std::vector<Record> 而不是 std::vector<std::unique_ptr<Record>>——后者每个 Record 都单独 new 在堆上,访问时跳指针,缓存性能跟 std::list 一样糟。
第二条:冷热分离,把频繁访问的字段拆出来
一个结构体里,各个字段被访问的频率往往天差地别。比如一个 Player 结构体:
cpp
struct Player {
std::string name; // 冷: 只在显示名字时用
int level; // 热: 每帧的逻辑都查
std::vector<Item> inventory; // 冷: 只在打开背包时用
Vector3 position; // 热: 物理和渲染每帧都读
int health; // 热: 战斗逻辑频繁读
// ... 还有一堆冷字段
};如果你把这些字段全塞在一个 Player 里,再用 std::vector<Player> 存所有玩家,问题就来了:Player 这个结构体很大(几百字节),一个缓存行只能装下零点几个玩家。游戏每帧只访问 position 和 health,但每次读它们,整条缓存行被拉进来,里面绝大部分是这次根本用不到的 name、inventory——缓存行有效率极低。
解法叫冷热分离:把高频访问的热字段单独拎出来,放进一个紧凑的结构体;冷字段留在另一个结构体,通过索引或指针关联。
cpp
struct PlayerHot {
Vector3 position;
int level;
int health;
}; // 紧凑, 一个缓存行能装好几个玩家
struct PlayerCold {
std::string name;
std::vector<Item> inventory;
// ... 其它冷字段
std::uint32_t hot_index; // 关联到 PlayerHot
};
std::vector<PlayerHot> hot_data; // 主循环遍历这个, 缓存友好
std::vector<PlayerCold> cold_data; // 只在需要时才访问主循环遍历 hot_data 时,每个缓存行塞下好几个玩家的热字段,cache miss 大幅减少。冷字段平时不碰,只有玩家打开背包这种偶尔的操作才去查 cold_data,那时慢一点也无所谓。这是游戏引擎、数据库内核、HFT 系统里非常通用的设计手法。
第三条:AoS vs SoA(以及一个诚实的实测)
冷热分离推到极致,就是经典的 AoS vs SoA 之争。AoS(Array of Structs)是 std::vector<Particle>,每个粒子的 x/y/z 挨在一起;SoA(Struct of Arrays)是三个独立数组 x[]、y[]、z[]。当你只需要对所有粒子的 x 做某种运算(比如物理模拟里更新 x 坐标),SoA 只遍历 x[] 数组,缓存行全是有效的 x;AoS 则每次读一个 x 都把无用的 y/z 也拉进缓存行,有效率只有 1/3。
理论上 SoA 应该快得多。于是笔者跑了个实验:400 万粒子,只累加 x 字段,AoS(数组 45.8 MB,每缓存行有效率 6%)对 SoA(x 数组 15.3 MB,有效率 100%)。结果:
text
只累加 x 字段, N=4000000
AoS: 9875.1 us (数组 45.8 MB, 每个缓存行有效数据 4/64=6%)
SoA: 9902.4 us (x数组 15.3 MB, 每个缓存行有效数据 16/16=100%)
SoA / AoS = 1.00x没差异。笔者把 AoS 的无用字段塞到 7 个(结构体 32 字节,数组 122 MB,缓存行有效率跌到 12.5%),还是 1.01x,几乎一样。
为什么理论上的优势没体现?因为在笔者这台 Zen 5 上,这个简单累加被几个东西联手掩盖了:编译器自动向量化把循环重写得很快、硬件预取器提前把后面的数据都拉进来了、再加上 volatile 累加每次都要写内存(写成了瓶颈,把读的缓存差异淹没了)。在这些条件叠加下,AoS 浪费的那点缓存行,被预取器默默补了回来。
理论优化,在你的机器上未必成立
这是一个比"SoA 更快"重要得多的教训。AoS/SoA 的理论优势是真实的——在很多真实项目(游戏引擎、物理模拟)里,切到 SoA 确实带来成倍提升。但那些场景通常访问模式更复杂、字段更多、没有这么容易向量化。在笔者这个简单累加里,优势被现代 CPU 的预取和向量化吃掉了。结论只有一个:任何"理论上更快"的优化,在你自己的目标场景上实测之前,都只是假设。这条纪律跟 微基准那场最后一篇讲的相关性是一回事——别拿理论排名当代码决策。
那 SoA 到底什么时候值得切?当你满足这几个条件时:访问模式只碰结构体的一小部分字段、数据量大到撑爆缓存、计算密集到 load 真的成了瓶颈、或者你确定要手动 SIMD 向量化(SoA 天然适合 SIMD)。否则 AoS 更简单、可读性更好,先用着,等 profiler 真的指出这块是瓶颈再改。
第四条:注意访问顺序,顺序远快于随机
这条第二篇实验直接证明过:同一个 8MB 数组,顺序访问 0.27 ns/elem,随机访问 4.55 ns/elem,差 17 倍。落到代码里意味着:
- 遍历二维数组按行不要按列。
for (i) for (j) a[i][j]是连续的(行优先存储),反过来的for (j) for (i) a[i][j]每次跳一整行,cache miss 满天飞。 - 嵌套循环里,内层访问的内存要连续。如果你在做一个矩阵乘法或图像处理,把连续访问的维度放在最内层循环。
- 避免"跳着"访问数组。如果一个算法的下标是
i = (i * 7) % n这种,预取器抓不到规律,等于随机访问。
第五条:多线程下小心 false sharing
最后提一个多线程场景的坑,这一篇不展开实测,只讲机制。如果你的两个线程分别写不同的变量,但这两个变量恰好落在同一条缓存行里(64 字节内),麻烦就来了:线程 A 改了它那个变量,整条缓存行在 A 的私有 L1 里变脏;硬件为了保持一致性,得让线程 B 所在核的这条缓存行失效,B 下次读自己的变量时就得重新从 A 那边拉过来。两个线程明明写的是不同数据,却互相把对方的缓存行反复踢来踢去,性能崩塌。这叫 false sharing(伪共享)。
解法是对齐填充:把高频写的共享变量用 alignas(64) 单独撑满一条缓存行,保证不同线程的热变量不落在同一条上。
cpp
struct alignas(64) PaddedCounter {
std::atomic<std::uint64_t> value{0};
// alignas(64) 让这个结构体占满一整条缓存行
// 不同线程的计数器互不干扰
};这是高性能并发代码里的标准手法。详细的多线程缓存一致性(MESI 协议那些)留给以后讲并发时展开,这里你先记住:false sharing 是真实存在的性能杀手,多线程写共享数据时,对齐填充是默认要做的事。
一份缓存友好的决策清单
把上面几条收拢成一份面对具体场景时的思考清单:
- 数据结构选连续的。能用
std::vector就别用节点式容器,除非它的特定语义是必需的。 - 结构体够大时,做冷热分离。把高频字段单独拎出来紧凑存放。
- 数据类型选合适的。第三篇讲过,存储为主的字段(尤其枚举)果断缩,算术密集的字段别盲目缩,实测决定。
- 遍历按内存连续顺序。内层循环访问连续内存,别跳着访问。
- 多线程写共享数据时,对齐填充防 false sharing。
- 最重要的一条:改完就测。所有上面的优化都是"可能有效",到底有没有效、有效多少,profiler 和 benchmark 才说了算。
这套东西听起来像常识,但每一条都是踩过坑才会真正记住的。Jonathan 这场演讲最大的价值,不是教你某个技巧,而是让你在写每一行访问内存的代码时,脑子里下意识闪过一句:"这个访问模式,缓存行有效率是多少?"——养成这个直觉,你就是比大多数人写得更快的那个人。