1.2 存储层次与局部性

存储层次为什么存在，以及局部性如何变成可测量的性能差异

学习目标

读完这一节，你应该能够：

解释为什么计算机不干脆全部使用最快的存储器。
说出时间局部性和空间局部性的定义，并在代码里指出它们。
预测一段循环代码的访存性能大致如何，并说明理由。

一、存储层次的由来：一个三角约束

制造存储器时，有三个目标互相冲突：

目标	含义
快	访问延迟低
大	容量大
便宜	单位容量成本低、占用芯片面积小

物理现实是：你只能同时满足其中两个。

寄存器用的是最快的电路，但每个只有几个字节，而且总量极其有限。
SRAM 很快，但每个存储单元要用 6 个晶体管，面积大。
DRAM 每个单元只要 1 个晶体管加一个电容，所以能做到几十 GB，但访问慢得多。
SSD 和磁盘更便宜、更大，但慢了若干个数量级。

既然不能全都用最快的，工程上的解法就是：用一个金字塔，把常用的数据放在塔尖，不常用的放在塔底。

        容量小 / 快 / 贵
        ┌───────────────┐
        │    寄存器      │   ← 编译器管理
        ├───────────────┤
        │    L1 / L2     │   ← 硬件自动管理
        ├───────────────┤
        │      L3        │
        ├───────────────┤
        │   主存 DRAM     │   ← 操作系统管理
        ├───────────────┤
        │   SSD / 磁盘    │
        └───────────────┘
        容量大 / 慢 / 便宜

💡 这个金字塔能工作的唯一前提，是程序对存储的访问不是随机的。

如果程序下一步要访问的数据完全无法预测，那么把任何东西放进快的那一层都是浪费——因为它几乎没有机会被再次用到。这个"可预测性"就是下一节的局部性。

二、两种局部性

局部性（locality） 指的是：程序倾向于重复访问一小部分数据。

它有两种形态。

时间局部性（temporal locality）

刚被访问过的数据，很可能在不久的将来被再次访问。

典型来源：循环里的变量、被反复调用的数据结构。

total = 0
for x in data:
    total += x        # total 被反复读写，它会被放在寄存器里

total 就是时间局部性的教科书例子。它每次迭代都被访问两次，所以硬件/编译器会想尽办法把它留在最快的存储里（寄存器）。

空间局部性（spatial locality）

被访问过的地址附近的数据，很可能很快也被访问。

典型来源：顺序遍历数组。

for i in range(len(a)):
    s += a[i]         # a[0], a[1], a[2] ... 地址连续

因为访问是连续的，硬件可以在你只要 a[0] 的时候，顺手把 a[0] 后面的一整块（通常是 64 字节，即 16 个 4 字节浮点数）都搬进来。后面 15 次访问就都命中在这块已经搬进来的数据里了。

👉 空间局部性是"批量搬运"能成立的前提。如果访问是跳跃的，批量搬来的数据大部分用不上，带宽就浪费了。

三、局部性怎么变成性能：一个可测量的例子

看这两段做同一件事的代码，它们的运算次数完全相同：

# 写法 A：按行遍历
for i in range(N):
    for j in range(N):
        total += m[i][j]

# 写法 B：按列遍历
for j in range(N):
    for i in range(N):
        total += m[i][j]

在多数语言里（C、C++、NumPy 的默认布局），二维数组是按行连续存储的：m[0][0]、m[0][1]、……、m[0][N-1]、m[1][0]……排成一条直线。

写法 A 沿着这条直线走。每次搬进来的一块数据，接下来 15 次访问都能用上。
写法 B 每一步都跳 N 个元素。如果 N 比较大（比如 4096），每次访问都落在不同的块里——搬来 64 字节，只用掉 4 字节，其余 60 字节立刻被丢弃。

结果是：写法 B 的实际访存次数可以是写法 A 的十几倍，即使两者的浮点加法次数一模一样。

⚠️ 这不是"理论上的担忧"。在 Python 里用嵌套列表跑这两段代码，或者用 C 编译后跑，都能观察到接近一个数量级的差异。第 1.6 节的实验会带你亲手测出来。

💡 这个例子说明了一件事：O(N²) 这样的复杂度分析只数了"运算次数"，但真实性能由"搬运次数"决定。两者可以差一个数量级。 这是本篇最想传达的区分。

四、两个放大因素：步长与工作集大小

步长（stride）

步长是连续两次访问之间跨过的元素个数。

步长	每个 64 字节块被用到的字节数	有效带宽
1（连续）	64	接近峰值
2	32	约一半
4	16	约四分之一
16（每个块取 1 个 float）	4	约十六分之一

有效带宽的意思是：尽管硬件把整个块都搬了回来，你的程序真正用上的只有一小部分。剩下的带宽全浪费了。

工作集大小（working set）

工作集是程序在某个时间段内反复访问的数据总量。

工作集小于某一级 cache 的容量 → 这一级能留住数据，性能好。
工作集大于该级容量 → 数据被反复挤出再载入，cache 形同虚设。

👉 这解释了为什么同样一段代码，处理 1 MB 数据时很快，处理 1 GB 数据时就慢得多——不是代码变了，是数据放不下了。

第 1.6 节的实验会让你扫一遍工作集大小，亲眼看到性能在 cache 容量边界处掉台阶。

五、把局部性变成可操作的准则

读到这里，你手上应该有四条可以直接拿来改代码的准则：

让最内层循环访问连续内存。 循环顺序不是风格问题，它决定访存效率。
复用刚搬进来的数据。 如果一块数据要被用很多次，想办法在这块数据还在快存储里的时候把它用完——这就是分块（第 1.3 节）。
注意数据布局。 结构体数组（AoS）和数组结构体（SoA）的局部性完全不同；转置一个矩阵会把访问模式从最优变成最差。
控制工作集。 能分块处理的，就不要一次全载入。

六、与 AI Infra 的连线

1. 张量的内存布局是真实存在的性能变量。

深度学习框架里的张量默认也是行主序（row-major）。所以"按哪个维度归约""矩阵乘的循环怎么排"这些事情，不是实现细节，而是直接决定性能的设计选择。你在 PyTorch 里见到的 contiguous()、stride()、reshape 与 view 的区别，全部源自这里。

2. GPU 的合并访存（coalescing）与 CPU 的 Cache line 是同一个思想。

GPU 上一个线程组（warp，通常是 32 个线程）如果访问连续的地址，硬件会把它们合并成一次内存事务；如果地址是跳着的，就会拆成很多次事务。这和第 1.2 节讲的"每个块被用到多少字节"是完全同构的问题——只是换了个名字。

3. 分块（tiling）是第 1.3 节和第三篇的共同主题。

CPU 上由硬件自动做的 cache 分块，在 GPU 上需要程序员手工把数据搬进一块可寻址的快速存储（shared memory）。理解 CPU 这一侧，是理解 GPU kernel 优化的最短路径。

关键结论

存储层次的存在，是因为"快、大、便宜"三者不可兼得。
层次结构能工作的前提是局部性：时间局部性（同一数据反复用）和空间局部性（相邻数据一起用）。
局部性差会让实际访存次数远高于运算次数，性能差一个数量级——而复杂度分析看不出来。
步长决定每个块被用到的比例；工作集大小决定数据能否留在快存储里。
四条操作准则：连续访问、复用数据、注意布局、控制工作集。

自测问题

为什么不能把所有存储器都做成寄存器那么快？从物理约束的角度解释。
下面两段代码，哪一段局部性更好？为什么？

# 甲
for i in range(N):
    for j in range(N):
        c[i][j] = a[i][j] + b[i][j]

# 乙
for j in range(N):
    for i in range(N):
        c[i][j] = a[i][j] + b[i][j]

一个步长为 8 的遍历（按 4 字节 float 计），每个 64 字节的块平均被用到多少字节？有效带宽大约是峰值的几分之一？
同一段代码，输入 4 MB 时很快，输入 400 MB 时慢很多。用"工作集"解释这个现象。
你的同事说"我把循环顺序改了一下，性能提升了 5 倍"。这个提升可能来自哪里？为什么？