存储层级与编程
处理器越来越快，但内存跟不上。这个差距被称为存储墙（Memory Wall）。为了缓解它，计算机采用了存储层级（Memory Hierarchy）：用速度换容量，用容量换速度，在成本和性能之间找平衡。
| 层级 | 典型容量 | 访问延迟 | 技术 |
|---|---|---|---|
| 寄存器 | ~1 KB | ~0.3 ns | 触发器 |
| L1 缓存 | 32-64 KB | ~1 ns | SRAM |
| L2 缓存 | 256 KB-1 MB | ~4 ns | SRAM |
| L3 缓存 | 8-64 MB | ~10-20 ns | SRAM |
| DRAM | 8-512 GB | ~100 ns | 电容 |
| SSD | 256 GB-8 TB | ~10-100 μs | NAND Flash |
| HDD | 1-20 TB | ~5-10 ms | 磁性盘片 |
如果把 L1 缓存的 1 秒类比为 1 秒：L2 约 4 秒，L3 约 15 秒，DRAM 约 1.5 分钟，SSD 约 1-2 天，HDD 约 1-2 个月。差距触目惊心。
存储层级的两个核心原理：
- 时间局部性（Temporal Locality）：最近访问的数据很可能再次被访问。缓存利用这一点保留最近使用过的数据。
- 空间局部性（Spatial Locality）：访问某个地址后，其邻近地址很可能被访问。缓存利用这一点以块（Cache Line，通常 64 字节）为单位加载数据。
缓存如何知道一个内存地址对应的数据是否在缓存中？这需要地址映射机制。
直接映射（Direct-Mapped）：每个内存块只能映射到一个固定的缓存行。地址的某些位直接决定缓存行索引。
优点：实现简单、查找快（无需比较）。缺点：容易冲突——如果程序频繁访问映射到同一缓存行的不同内存块，会导致冲突失效（Conflict Miss）。
全相联（Fully Associative）：每个内存块可以放入缓存的任意位置。
优点：无冲突失效。缺点：查找需要并行比较所有缓存行的 Tag，硬件成本高、功耗大。
组相联（Set-Associative）：折中方案。缓存被分为若干组（Set），每个内存块映射到一个固定组，但在组内可以放入任意行（Way）。
例如 4-way 组相联：每组有 4 个缓存行，查找时只需比较组内 4 个 Tag。现代 CPU 的 L1 通常是 8-way，L2/L3 是 16-way 或更高。
一个内存地址在缓存查找中被划分为三部分：
Tag | Set Index | Block Offset
Offset 决定块内字节位置（如 64B 块需要 6 位），Set Index 决定映射到哪个组，Tag 用于比较判断是否命中。
组相联缓存中，当一个组的所有 Way 都被占满，又有新数据要进来时，需要选择替换哪个缓存行。
- LRU（Least Recently Used）：替换最久未被访问的行。最接近最优，但实现需要为每个缓存行维护访问时间戳，硬件开销大。
- FIFO（First In First Out）：替换最早进入缓存的行。实现简单，但忽略了访问频率。
- Random（随机）：随机选一个替换。出乎意料地有效——研究表明在高相联度下，随机替换与 LRU 的性能差距很小，但硬件实现简单得多。
- PLRU（Pseudo-LRU）：用树状结构近似 LRU，是实际处理器的常用选择。
现代 CPU 的 L3 缓存通常采用 随机替换或 PLRU，因为巨大的缓存容量使得精确 LRU 的存储开销不可接受。
缓存友好的代码本质上是在利用空间局部性和时间局部性。最常见的例子是二维数组遍历：
// 行优先：缓存友好
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
sum += a[i][j]; // 访问 a[i][0], a[i][1], a[i][2]... 连续
// 列优先：缓存不友好
for (int j = 0; j < N; j++)
for (int i = 0; i < N; i++)
sum += a[i][j]; // 访问 a[0][j], a[1][j], a[2][j]... 跨行跳跃C 语言的二维数组在内存中是行优先（Row-Major）存储的。行优先遍历时，每次访问的地址连续（相差 sizeof(element)），可以充分利用缓存行的空间局部性。列优先遍历时，每次跳跃一整行（N * sizeof(element)），几乎每个访问都导致缓存未命中。
对于一个 4096×4096 的 double 数组（约 128 MB）：
• 行优先：几乎全部 L1 命中，耗时 ~50 ms
• 列优先：几乎全部 L1 未命中，耗时 ~500+ ms
10 倍差距，完全相同的算法，只是遍历顺序不同。
另一个关键技术是分块（Tiling/Blocking）。当数据量超过缓存容量时，把大问题切成小块，让每个块能装进缓存：
// 矩阵乘法分块
for (int ii = 0; ii < N; ii += B)
for (int jj = 0; jj < N; jj += B)
for (int kk = 0; kk < N; kk += B)
// B×B 的小块在缓存中完成计算
for (int i = ii; i < ii+B; i++)
for (int j = jj; j < jj+B; j++)
for (int k = kk; k < kk+B; k++)
C[i][j] += A[i][k] * B[k][j];合适的块大小 B 让 A、B、C 的子矩阵都能驻留在 L1/L2 缓存中，大幅减少内存访问次数。配合 SIMD 向量化，分块矩阵乘法的性能可以达到峰值浮点性能的 80-90%。
- 为什么现代 CPU 的 L1 缓存通常是 32-64 KB，而不是更大？增大 L1 会有什么副作用？
- 设计一个实验：用
perf stat -e cache-misses,cache-references测量行优先 vs 列优先遍历的缓存命中率差异。 - 链表（Linked List）的顺序访问 vs 数组的顺序访问，哪个对缓存更友好？为什么？如果链表节点在内存中随机分布，有什么优化方法？
- ARM 的 big.LITTLE 架构中，大核和小核的缓存配置不同。为什么大核需要更大的 L2/L3？任务调度器如何决定线程放在大核还是小核上？