📚 什么是局部性？
在计算机体系结构中，局部性原理 (Locality of Reference) 是缓存系统的理论基础。它描述了一个被大量实验验证的事实：
在一段较短时间内，程序往往反复访问一小部分地址空间。
这一原理可以拆分为两种形式，它们从不同角度描述了程序的访问模式：
⏰ 时间局部性
Temporal Locality
刚被访问过的地址，很快会再次被访问
🗺 空间局部性
Spatial Locality
某个地址被访问后，相邻地址很快也会被访问
🚀 为什么局部性如此重要？
因为 CPU 和内存之间存在着巨大的速度差距。现代计算机用多级缓存来弥补这个鸿沟，而缓存之所以有效，正是因为局部性原理：
L2 Cache
~4ns
256 KB-1 MB
Main Memory
~100ns
8-128 GB
关键数字：内存访问约 100ns，L1 缓存约 1ns —— 差了 100 倍！
如果程序具有良好的局部性，大部分访问都能命中缓存，程序就"感觉"像是在用 1ns 的超快内存。
⏰ 时间局部性详解
定义：如果一个内存位置被访问，那么在不久的将来它很可能再次被访问。
这很好理解——就像你看书时，遇到一个重要概念会反复回看同一页。程序也一样，循环中的变量、频繁调用的函数指令，都会被一遍又一遍地访问。
📄 典型例子：循环中的计数器
C
int sum_array(int arr[], int n) {
int sum = 0; // sum 被访问 n+1 次 (1次写入 + n次读写)
int i; // i 被访问 3n 次 (n次比较 + n次自增 + n次数组下标)
for (i = 0; i < n; i++) {
sum += arr[i]; // sum 和 i 每轮循环都被访问 → 强时间局部性!
}
return sum;
}
📊 时间局部性可视化
⏰ 变量 sum 在循环中被反复访问（横轴 = 循环迭代次数，纵轴 = 访问频率）
▲ 每次迭代都访问同一个变量 sum —— 完美的时间局部性，sum 始终停留在 L1 缓存中
🌎 更多时间局部性的场景
| 场景 | 说明 |
|---|
| 循环变量 | for 循环的计数器 i 每轮都被读/写 |
| 指令缓存 | 循环体中的指令被反复取指执行 |
| 频繁调用的函数 | 函数的机器码留在指令缓存中 |
| 栈顶变量 | 函数的局部变量活跃期间反复使用 |
🗺 空间局部性详解
定义：如果一个内存位置被访问，那么它附近的位置也很可能很快被访问。
这也很好理解——就像你看书时，读完第 3 页接下来会看第 4 页。程序中，数组元素连续存放、结构体字段紧密排列，顺序访问时就会自然产生空间局部性。
📄 典型例子：顺序遍历数组
C
// 顺序访问 —— 完美的空间局部性
for (int i = 0; i < n; i++) {
process(arr[i]); // arr[0], arr[1], arr[2] ... 连续地址！
}
C
// 跳跃访问 —— 空间局部性差
for (int i = 0; i < n; i += 16) {
process(arr[i]); // arr[0], arr[16], arr[32] ... 地址间隔大！
}
📊 空间局部性可视化
🗺 顺序扫描数组时的内存访问模式（每个格子 = 一个数组元素）
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
▲ 访问 arr[0] 时，CPU 一次性将 arr[0]~arr[3]（或更多）载入缓存行（通常 64 字节），接下来几次访问全部命中缓存！
❌ 跨步访问 (步长 16)
缓存命中率 ~20%
🌎 更多空间局部性的场景
| 场景 | 说明 |
|---|
| 顺序遍历数组 | 数组在内存中连续存放，挨着访问自然命中同一缓存行 |
| 结构体字段访问 | struct 的字段在内存中相邻，访问一个后常访问其他 |
| 指令顺序执行 | CPU 按序取指，相邻指令在同一缓存行 |
| 函数调用栈 | 栈帧紧邻，局部变量集中在小范围内 |
🎮 交互演示：亲自感受局部性
下面是一个简化的内存模型（16x16 = 256 个单元）。点击按钮，观察不同访问模式下的缓存命中情况：
时间局部性（反复访问同一位置）
空间局部性（连续访问相邻位置）
未访问
⚡ 经典案例：行优先 vs 列优先遍历
这是理解空间局部性最经典的例子，也是实际工程中导致性能差异数十倍的真实原因：
C
// 假设有一个 1024 x 1024 的 int 数组
int matrix[1024][1024];
// ✅ 行优先遍历 —— 快！（~4ms）
for (i = 0; i < 1024; i++)
for (j = 0; j < 1024; j++)
sum += matrix[i][j];
// 每行连续访问 1024 个 int → 完美空间局部性
// C 语言数组按行存储：matrix[0][0], matrix[0][1], ... matrix[0][1023], matrix[1][0] ...
C
// ❌ 列优先遍历 —— 慢！（~20ms，慢 5 倍！）
for (j = 0; j < 1024; j++)
for (i = 0; i < 1024; i++)
sum += matrix[i][j];
// 每列跳跃 1024 个 int = 4096 字节 → 每次都可能缓存未命中
C 语言二维数组在内存中的真实布局（按行存储）
[0][0]
[0][1]
[0][2]
[0][3]
[0][4]
[0][5]
[0][6]
[0][7]
[1][0]
[1][1]
[1][2]
[1][3]
[1][4]
[1][5]
[1][6]
[1][7]
[2][0]
[2][1]
[2][2]
[2][3]
[2][4]
[2][5]
[2][6]
[2][7]
→ 行优先：连续访问，缓存行完美命中
↓ 列优先：每次跳 8 个元素，缓存行浪费
📋 两者对比总结
|
⏰ 时间局部性 |
🗺 空间局部性 |
| 核心含义 |
同一个位置会被反复访问 |
相邻位置会被依次访问 |
| 直觉类比 |
反复翻看同一页笔记 |
按顺序一页一页往后翻 |
| 典型代码 |
循环变量、循环体内的指令 |
数组遍历、结构体字段访问 |
| 缓存机制 |
LRU 策略保留最近使用的行 |
预取相邻的缓存行 |
| 优化方向 |
减少不必要的数据重载 |
使用紧凑的数据结构、顺序访问 |
| 破坏因素 |
数据集太大，缓存装不下 |
跨步访问、链表随机跳转 |
🔧 实战：如何利用局部性优化程序
1. 顺序访问代替随机访问
C
// ❌ 差：链表遍历，每个节点的位置不可预测
while (node != NULL) {
process(node->data);
node = node->next; // 下一个节点在哪？不知道！
}
// ✅ 好：数组遍历，下一个元素就在旁边
for (i = 0; i < n; i++)
process(arr[i]); // arr[i+1] 就在 arr[i] 旁边！
2. 小步长优于大步长
C
// 步长 = 1：每个 int 4 字节，一个 64B 缓存行装 16 个 → 命中率极高
for (i = 0; i < n; i++) arr[i]++;
// 步长 = 16：每个元素跨 64 字节 = 正好跳过一整个缓存行 → 命中率极低
for (i = 0; i < n; i += 16) arr[i]++;
3. 数据紧凑排列
C
// ❌ 差：AoS (Array of Structs)，如果只需要 x 坐标也要加载 y 和 z
struct Point { float x, y, z; };
Point points[10000];
// ✅ 好：SoA (Struct of Arrays)，需要的字段紧凑连续
struct Points {
float x[10000]; // 单独访问 x 时完全连续
float y[10000];
float z[10000];
};
4. 分块算法 (Blocking / Tiling)
C
// 矩阵乘法：分块使数据块适合放进缓存
for (ii = 0; ii < N; ii += BLOCK) // 外层按块循环
for (jj = 0; jj < N; jj += BLOCK)
for (kk = 0; kk < N; kk += BLOCK)
// 对小块做矩阵乘法，小块能完全放入 L1/L2 缓存
for (i = ii; i < ii+BLOCK; i++)
for (j = jj; j < jj+BLOCK; j++) {
int sum = 0;
for (k = kk; k < kk+BLOCK; k++)
sum += A[i][k] * B[k][j];
C[i][j] += sum;
}
分块的威力：朴素矩阵乘法：O(n³) 次内存访问，但大部分都缓存未命中。
分块后，小块数据驻留在缓存中，性能可提升 2~10 倍。
🎓 自测小练习
学完了？来测试一下理解程度：
第 1 题
下面的代码片段主要利用了哪种局部性？
for (int i = 0; i < 1000; i++) {
arr[i] = arr[i] + arr[i-1];
}
A. 只有时间局部性
B. 时间局部性 + 空间局部性
C. 只有空间局部性
D. 没有局部性
第 2 题
下面哪种数据结构对空间局部性最不友好？
A. C 语言数组
B. C++ std::vector
C. 链表（每个节点通过指针连接）
D. 连续内存的 struct 数组
第 3 题
在 C 语言中遍历 int matrix[1024][1024]，以下哪种方式更快？
A. 外层循环 i (行)，内层循环 j (列)
B. 外层循环 j (列)，内层循环 i (行)
C. 速度一样，编译器会优化
第 4 题
一个循环中反复读取全局配置变量 config.flag，这主要体现了什么？
A. 时间局部性
B. 空间局部性
C. 两者都有
💡 一句话记住
时间局部性 = 反复看同一个地方（"我又回来了"）
空间局部性 = 看完这里看旁边（"顺便看看隔壁"）
程序的局部性越好，缓存命中率越高，程序跑得越快。写代码时，优先考虑顺序访问、紧凑数据、小步长。