深入浅出访存优化

发表于 分类于 ， 阅读次数：

深入浅出访存优化

时间：2026/04/09

关键词：缓存、cache line、局部性、AoS/SoA、stride、blocking、false sharing、带宽、延迟
核心目标：理解“为什么同样是 O(n)，不同内存访问方式会有非常大的性能差异”。

1. 为什么访存优化这么重要

很多程序并不是算得慢，而是等内存等得慢。

现代 CPU 的特点是：

  • 算术单元非常快
  • 主存访问相对很慢
  • 一旦 cache miss，CPU 可能要空等很多周期

所以高性能编程里经常会出现这种现象：

  • 算法复杂度没变
  • 指令数也没怎么变
  • 只是换了数据布局和访问顺序
  • 性能却提升一大截

这背后的核心就是访存模式。

2. CPU 不是直接从内存一格一格取数据

2.1 缓存层级

可以先粗略理解成：

  • L1：最小、最快
  • L2：更大、稍慢
  • L3：更大、共享、再慢一些
  • DRAM：远慢于缓存

因此访问一个数据时：

  • 如果在缓存里，代价较低
  • 如果不在，就会发生 cache miss，从更慢层级取

2.2 cache line

CPU 取数据通常不是只取一个字节或一个 int，而是按缓存行成块搬运。

常见 cache line 大小是：

  • 64 字节

这意味着：

  • 如果你访问了 a[i]
  • 那么 a[i] 周围的一片数据往往也会一起进缓存

所以连续访问会特别受益。

3. 两种最重要的局部性

3.1 空间局部性

如果你访问了某个地址，附近地址也很可能马上会被访问。
连续数组遍历就是最典型例子。

3.2 时间局部性

如果你刚访问过某个数据，很可能短时间内还会再访问它。

例如：

1
2
3
4
for (size_t i = 0; i < n; ++i) {
    sum += a[i];
    sum += a[i];
}

第二次访问 a[i] 很可能仍在缓存里。

4. 为什么顺序访问通常比随机访问快

看两个模式：

1
2
3
for (size_t i = 0; i < n; ++i) {
    sum += a[i];
}

和：

1
2
3
for (size_t i = 0; i < n; ++i) {
    sum += a[idx[i]];
}

第二种如果 idx 很随机，就容易出现：

  • cache line 利用率低
  • 硬件预取器很难提前猜中
  • CPU 长时间等待内存

这就是为什么：

  • 链表遍历
  • 稀疏随机访问
  • 指针追逐

常常会显著慢于顺序数组遍历。

5. AoS 与 SoA

这是访存优化里最经典的话题之一。

5.1 AoS：Array of Struct

1
2
3
4
5
6
struct Particle {
    float x, y, z;
    float vx, vy, vz;
};

std::vector<Particle> a;

特点：

  • 单个对象的属性紧挨着存
  • 适合“经常整对象一起处理”的场景

5.2 SoA：Struct of Arrays

1
2
3
4
struct Particles {
    std::vector<float> x, y, z;
    std::vector<float> vx, vy, vz;
};

特点：

  • 同一属性的数据连续存储
  • 更适合批量处理同一字段
  • 常更利于 SIMD / GPU / cache

5.3 什么时候 SoA 更有优势

如果你的计算主要是：

1
2
3
for (...) {
    x[i] += vx[i] * dt;
}

那么 SoA 往往更好，因为：

  • 访问字段连续
  • 每个 cache line 里装的都是“当前真正要用的数据”

5.4 什么时候 AoS 更自然

如果逻辑经常要完整处理单个对象，例如：

  • 读一个粒子的全部属性
  • 面向对象接口较多

AoS 可能更直观。

经验上：

  • 计算密集且按字段批量处理时，优先考虑 SoA
  • 业务逻辑围绕单对象时，AoS 更自然

6. stride（步长）为什么会直接影响性能

6.1 连续步长访问

1
2
3
for (size_t i = 0; i < n; ++i) {
    sum += a[i];
}

这通常最好。

6.2 大步长访问

1
2
3
for (size_t i = 0; i < n; i += 16) {
    sum += a[i];
}

问题在于：

  • 每次只用到一个 cache line 里的很少一部分
  • 带宽利用率低

6.3 二维数组里的列访问

假设按行连续存储：

1
2
3
4
5
for (size_t j = 0; j < m; ++j) {
    for (size_t i = 0; i < n; ++i) {
        sum += a[i][j];
    }
}

如果内层循环跨行跳，会比按行访问差很多。

因此多维数据常见经验是：

  • 内层循环尽量走连续维

7. blocking / tiling：为什么分块常常更快

当工作集太大，无法完全放进缓存时，可以按块处理。

7.1 直觉

不要一次把全量数据扫完再回来重扫，而是：

  • 先拿一小块
  • 在这小块上做尽量多的计算
  • 让这小块在缓存中被充分复用

7.2 矩阵乘法是最典型场景

朴素矩阵乘法经常很慢，不是乘法本身慢，而是访存复用差。
分块后的核心收益是：

  • 提高缓存命中
  • 减少大跨度反复读

7.3 图像处理也一样

例如卷积、滤波、stencil 计算，都常通过 tile/block 改善访存。

8. 预取与硬件预取器

现代 CPU 会尝试根据访问规律提前把数据搬进缓存，这就是硬件预取。

它更擅长：

  • 连续访问
  • 稳定步长访问

它不擅长：

  • 随机访问
  • 指针跳转
  • 强数据依赖链

所以很多“看起来只是更整齐的循环”之所以更快，本质上是在帮硬件预取器工作。

9. false sharing：并发里最隐蔽的访存杀手之一

9.1 它是什么

两个线程虽然更新的是不同变量，但这两个变量落在同一个 cache line 里。
结果两个核心会频繁抢这个 cache line 的所有权，导致性能急剧下降。

9.2 例子

1
2
3
4
struct CounterPair {
    std::atomic<int> a;
    std::atomic<int> b;
};

如果线程 1 只写 a，线程 2 只写 b，理论上彼此独立；
但如果 a 和 b 在同一 cache line，就可能 false sharing。

9.3 典型缓解方式

  • padding
  • alignas(64)
  • 每线程局部累加，最后汇总

这在并行归约、线程本地统计里特别常见。

10. 对齐、padding 与缓存布局

10.1 对齐影响加载效率

对齐良好的数据更利于：

  • 高效加载
  • SIMD 指令
  • cache line 对齐访问

10.2 结构体布局会影响缓存利用率

1
2
3
4
struct A {
    char flag;
    double value;
};

编译器可能为了对齐插入 padding。
如果一个结构体很大，而你每次只用其中一两个字段，就会带来缓存浪费。

这也是为什么“对象设计”会直接变成“性能设计”。

11. 分支与访存也常常绑定在一起

下面这类代码既影响分支预测，也影响访存效率：

1
2
3
if (a[i] > 0) {
    sum += heavy_table[a[i]];
}

如果：

  • a[i] > 0 高度不可预测
  • heavy_table 访问又很随机

性能通常会明显变差。

所以优化时别把“计算”和“访存”割裂看，它们常是一起出问题的。

12. 为什么 vector 通常比 list 更快

很多人第一次接触会觉得：

  • list 插入删除是 O(1)
  • vector 中间插删是 O(n)

于是误以为 list 应该经常更快。
但现实里，很多遍历型或批量处理场景中，vector 常常更快，原因就在于：

  • 连续内存
  • cache 友好
  • 更利于预取与向量化

所以算法复杂度只是第一层，访存模式是第二层。

13. 多线程写入时为什么要分区

如果多个线程写同一个大数组，比较好的模式通常是：

  • 每个线程负责一个连续区间
  • 尽量避免多个线程反复改同一个 cache line

不好的模式则常见于：

  • 交错写入
  • 所有线程抢同一个计数器
  • 共享小对象频繁原子更新

这会带来：

  • cache line 争用
  • false sharing
  • 带宽浪费

14. GPU 视角下为什么更重视 SoA

GPU 更强调大规模并行和合并访问（coalescing）。
因此当一批线程访问同一字段的连续元素时，SoA 往往比 AoS 更有优势。

所以很多 CPU/GPU 共享的高性能数据结构设计原则其实是相通的：

  • 扁平化
  • 连续化
  • 尽量批处理同类字段

15. 访存优化的实战原则

可以直接记这几条：

15.1 尽量连续访问

先改访问顺序，再谈别的。

15.2 尽量缩小热数据集

把频繁访问的数据做得更紧凑。

15.3 尽量增加复用

让已经进缓存的数据多用几次。

15.4 尽量避免无意义共享

特别是在并行代码里。

15.5 用数据布局服务算法

不是“先写一个漂亮对象模型，再看性能”，而是：

  • 哪种布局更适合核心计算，就优先哪种

16. 常见误区

16.1 只盯算法复杂度，不看访存

两个同为 O(n) 的实现，真实速度可能差很多倍。

16.2 误以为 cache 是“编译器问题”

缓存问题本质上是：

  • 数据布局问题
  • 访问顺序问题
  • 并发共享问题

16.3 把所有对象都做成“大而全”

热路径只用两个字段时，大结构体会造成大量无效搬运。

16.4 并发场景只关注锁，不关注 cache line

很多“看起来没锁争用”的程序，其实卡在 false sharing。

17. 一页总结

访存优化可以压缩成一句话：

让 CPU/GPU 更容易在更少次、更连续、更可预测的内存访问中拿到真正需要的数据。

最关键的实践点有：

  1. 顺序访问优于随机访问
  2. 连续布局优于分散指针结构
  3. SoA 在按字段批量处理时常优于 AoS
  4. 分块能提升缓存复用
  5. 并发时要警惕 false sharing

18. 建议继续补充的相关主题

和本篇衔接最紧密的内容：

  1. vector 容器优化
  2. 自动向量化与 SIMD
  3. NUMA 与多路 CPU 访存
  4. GPU 合并访存与 shared memory
  5. 矩阵分块与 stencil 优化

19. 参考资料

  1. Intel Optimization Manual
    https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html

  2. cppreference: alignas
    https://en.cppreference.com/w/cpp/language/alignas