局部性原理
概念
局部性原理（Principle of Locality）是指程序倾向于重复访问最近使用过的数据（或指令）以及附近的数据。这是高速缓存能够有效工作的基础。
时间局部性（Temporal Locality）
- 最近被访问过的数据/指令在不久的将来很可能再次被访问
- 示例：循环中的循环变量、累加器
- 利用：将数据保留在缓存中
空间局部性（Spatial Locality）
- 被访问过的数据附近的数据很可能在不久的将来被访问
- 示例：数组的顺序访问、指令的顺序执行
- 利用：一次加载一个缓存块（多个相邻数据）
步长与局部性
- 步长为 1 的遍历具有良好的空间局部性
- 步长大则空间局部性差
- 多维数组的遍历顺序至关重要
// 良好的空间局部性（步长=1）
for (int i = 0; i < n; i++)
sum += a[i];
// 差的空间局部性（大步长）
for (int i = 0; i < n; i++)
sum += a[i * 100];局部性是缓存工作的基础
正是利用了局部性原理，将最近使用的数据块加载到缓存中。
相关笔记：
链接到
- 上一个知识点：6.8 固态硬盘SSD
- 下一个知识点：6.10 编写缓存友好代码