《深入理解计算机系统》读书笔记：存储器层次结构

存储器层次结构的核心理念

计算机的存储器并不是一个单一的、均匀的组件。它是一个层次结构，从最快的寄存器到最慢的磁盘，每一层都充当下一层的缓存。这个设计的核心目标：

用层次结构制造「无限大且无限快」的存储器幻觉。

层次结构

| 层级 | 类型 | 访问时间 | 容量 | |------|------|---------|------| | L0 | 寄存器 | ~0.3ns | <1KB | | L1 | SRAM | ~1ns | ~32KB | | L2 | SRAM | ~4ns | ~256KB | | L3 | SRAM | ~12ns | ~8MB | | L4 | DRAM (主存) | ~100ns | ~16GB | | L5 | 磁盘 | ~10ms | ~1TB |

从 L0 到 L5，访问时间增长了约 10^7 倍，而容量也增长了约 10^9 倍。

局部性原理

存储器层次结构能够有效工作，依赖于程序的两种局部性：

时间局部性

被引用过一次的内存位置，很可能在不久的将来再次被引用。

// 循环中的变量 sum 具有良好的时间局部性
int sum = 0;
for (int i = 0; i < n; i++) {
    sum += a[i];  // sum 在每次迭代中被访问
}

空间局部性

如果一个内存位置被引用了，那么程序很可能在不久的将来引用附近的位置。

// 数组遍历具有良好的空间局部性
for (int i = 0; i < n; i++) {
    sum += a[i];  // a[0], a[1], a[2]... 连续访问
}

缓存命中与不命中

当程序需要访问某个数据时：

先查 L1 缓存 → 命中则直接返回
不命中则查 L2 → 依此类推
最终从主存或磁盘加载，并逐级填充缓存

不命中的三种类型

冷不命中：缓存为空时的首次访问，不可避免
冲突不命中：多个数据映射到同一缓存行
容量不命中：工作集超过缓存容量

对程序性能的启示

理解存储器层次结构后，写代码时应该：

关注空间局部性 — 顺序访问数组优于跳跃访问
关注时间局部性 — 循环中反复使用的变量保持在寄存器中
利用缓存行 — 连续存储的数据结构对缓存友好

// 行优先遍历（缓存友好）
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        sum += a[i][j];

// 列优先遍历（缓存不友好）
for (int j = 0; j < n; j++)
    for (int i = 0; i < n; i++)
        sum += a[i][j];

同样的计算量，行优先遍历可能比列优先快 10 倍以上，因为前者充分利用了空间局部性。

总结

存储器层次结构是计算机系统最优雅的设计之一。它不需要程序员关心细节，却自动地利用程序的局部性来提升性能。但理解它的工作原理，能帮助我们写出对缓存更友好的代码。

原始的硬件限制催生了优雅的层次设计。好的工程不是消除约束，而是在约束中创造价值。