让你的CPU怒不可遏的数据访问模式
本文探讨了低效的数据访问模式如何导致CPU性能严重下降。通过分析内存布局、缓存行填充、伪共享等问题，展示了不友好的数据访问模式会触发缓存未命中、流水线停顿等底层惩罚，最终使程序运行速度大幅降低。文章以"最慢的加法"为例，揭示了数据结构设计对性能的深远影响。
背景速读
- 这篇博客探讨的是"CPU 缓存不命中"（cache miss）对程序性能的毁灭性影响。现代 CPU 有多级缓存（L1/L2/L3），访问缓存的速度比访问主存快一到两个数量级；如果代码的数据访问模式导致缓存反复失效（即缓存未命中），性能会暴跌几十倍。
- 作者从一道经典面试题出发：对一个按行优先（row-major）存储的二维数组，按列遍历（col‑wise）为什么比按行遍历（row‑wise）慢得多？原因就是按列访问破坏了空间局部性，导致缓存行被频繁替换。
- 文章进一步展示了几种"让 CPU 愤怒"的模式：链表指针追逐（pointer chasing）、跳表（skiplist）随机访问、大哈希表的遍历等——它们共同的特点是"随机跳跃"，每次访问都需要从主存重新加载数据。
- 最后作者用实验数据说明，同样数量的操作，缓存友好的顺序访问比缓存不友好的随机访问快 10-100 倍，并给出了改用数组（而非链表）、合并数据（struct of arrays 而非 array of structs）等实用建议。