编写缓存友好代码
基本原则
利用 编写对缓存友好的代码。
核心策略
1. 循环步长为 1（顺序访问）
// 良好：步长为 1，空间局部性好
for (int i = 0; i < n; i++)
sum += a[i];
// 较差：大步长，空间局部性差
for (int i = 0; i < n; i++)
sum += a[i * stride];2. 多维数组的正确遍历顺序
// 良好：按行顺序遍历（C 数组的行优先存储）
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
sum += a[i][j];
// 较差：按列遍历，步长=n，空间局部性差
for (int j = 0; j < n; j++)
for (int i = 0; i < n; i++)
sum += a[i][j];3. 选择合适的数据布局
- 结构体数组（AoS） vs 数组结构体（SoA）
- 将经常一起访问的字段放在相邻位置
- 对热点数据的紧凑表示
4. 分块处理
将大块数据分成能放入的块来处理，详见 。
相关笔记：
链接到
- 上一个知识点：6.9 局部性原理
- 下一个知识点：6.11 缓存命中与不命中