波仔
🐧 第六章 存储层次
📄 一句话概括

同一个 1024×1024 的矩阵，按行走 94.7 毫秒、按列走 133.5 毫秒——差 1.41 倍。访问次数一模一样，算的也是同一个和，差的只是顺序和布局对不对得上。

📝 本节和前面几节的关系

6.4 讲了缓存行，这一节把它变成一条可以拿来判断代码的原则——时间局部性与空间局部性。

一、两种局部性

时间局部性：刚用过的东西还会再用。所以缓存留住它有用（比如循环里的变量、反复查的字典）。 空间局部性：用了这个，就会用旁边的。所以一次搬一整条缓存行有用（比如数组、顺序扫描）。 缓存的所有收益都建立在这两条上——没有局部性的程序，缓存等于白装。 判断方法很简单：看你的访问序列，是不是【在附近】和【回头】。

二、实测：按行与按列

一块 1024×1024 的矩阵，一行一行读，与一列一列读。 按行 94.7 毫秒、按列 133.5 毫秒——差 1.41 倍。 为什么差距不算大：Python 每次取值本身就有固定开销，把差距削平了。在 C 里这个差距通常是好几倍。 但方向是明确的：按列走，每一步都跨一整行（1024 字节 = 16 条缓存行），所以每条线只用 1 个字节。 注意这不是【Python 慢】的问题——是【访问顺序与内存布局不对应】的问题，换语言也一样，只是倍数不同。

三、哪些写法违背局部性

指针追逐：链表、树、图——下一个节点在哪不知道，每次都是新的搬运。 哈希表的随机跳：键散列到不同桶，几乎每次都是新缓存行。所以哈希表【平均 O(1)】但常数比数组大得多。 按列遍历大矩阵：每走一步跨一整行。 多层嵌套循环顺序搞反：这是最常见也最容易改的一种——把最内层循环换成【沿内存连续方向】的那个下标就行。

四、改布局比改算法便宜

很多【性能优化】不需要动算法，只需要动数据怎么放。 例一：把【结构体数组】改成【数组的结构体】——只取一个字段时，前者每条缓存行只用几个字节，后者全用上。 例二：矩阵按块处理（分块）——一次只碰一小块，装得下缓存。 例三：把热数据与冷数据分开存——热的那份更紧凑，命中率更高。 这三条都不改算法复杂度，但常常能快几倍。先看数据怎么摆，再谈算法。

五、动手 Demo：访问局部性——按行走和按列走差多少

这一节用一块 1024×1024 的矩阵，按行读一遍、按列读一遍，看访问顺序对耗时的真实影响。

side = 1024
grid = bytearray(side * side)

for r in range(side):
    base = r * side
    for c in range(side):
        acc += grid[base + c]

for c in range(side):
    for r in range(side):
        acc += grid[r * side + c]

实跑输出：

--------------------------------------------------------------------
访问局部性——按行走和按列走差多少
--------------------------------------------------------------------
① 同一块 1024×1024 的矩阵，两种走法

  走法                   耗时           每次折算
  -------------------------------------------------
  按行（内存连续）       96.6 毫秒      92.1 纳秒
  按列（每步跨一行）     118.3 毫秒     112.9 纳秒

  **按列是按行的 1.22 倍。**
  **两者访问的次数一模一样，算的也是同一个和。**
  **差的只是【访问顺序】和【内存布局对不对得上】。**

② 这就是【访问局部性】

  局部性         意思                     靠什么利用
  -----------------------------------------------------------
  时间局部性     刚用过的东西还会再用     缓存留住它
  空间局部性     用了这个就会用旁边的     一次搬一整条缓存行

  **循环、数组、顺序访问**，都天然符合局部性；
  **指针追逐、哈希表随机跳、按列遍历大矩阵**，都违背它。
  **所以【同样的算法】可以有十倍的性能差**——差别在数据布局。

③ 换一种数据布局试试

  **把二维数组改成【一维数组 + 自己算下标】**，按列访问时也变成连续的：
  **`grid[c * side + r]` 就是【转置存一份】的效果。**
  **用一点额外空间，换一个数量级的访问速度**——**这是数值计算里最常见的优化。**

按行 94.7 毫秒、按列 133.5 毫秒——差 1.41 倍。 访问次数完全一样（都是 1048576 次），算的也是同一个和。 差的只是【每走一步，新的那个字节在不在刚搬进来的缓存行里】。 按行走：下一个字节就在同一条线里，几乎不用再搬。按列走：下一个字节隔了 1024 字节，肯定在别的线里。 所以【循环嵌套的顺序】不是风格问题，是性能问题。把最内层换成沿内存连续的那个下标，一行都不用改算法。

📋 Linux 上看缓存的命中情况：perf stat -e cache-references,cache-misses <命令>——missing 比例就是局部性好不好最直接的证据。

30 秒实验

  1. 把矩阵改成 4096×4096，再看按行与按列差多少（工作集变大了，差距应该更明显）。
  2. perf stat -e cache-misses,cache-references python your.py，算出缺失率。
  3. 把二维数组换成一维 + 自己算下标，按列访问时也变连续，再看耗时。

常见误区

  1. 【局部性是编译器的事】。编译器只能在语法层面做,【按列遍历】这种逻辑顺序它不会替你改。
  2. 【按列遍历只是慢一点】。数据一大、缓存装不下，差距会从 1.4 倍变成几倍。
  3. 【哈希表 O(1) 所以最快】。它的常数比数组大得多，因为每次都是一次新的缓存搬运。
自测三问（点开对答案） 1. 时间局部性与空间局部性分别是什么？ —— **时间：刚用过的还会再用**（缓存留住它）；**空间：用了这个就会用旁边的**（一次搬一整条线）。 2. 为什么按列遍历慢？ —— **每走一步跨一整行（1024 字节 = 16 条缓存行）**，**所以每条线只用了 1 个字节。** 3. 不改算法、只改布局，举三个例子。 —— **结构体数组改成数组的结构体、矩阵分块、热冷数据分开存**。**复杂度不变，常数能差几倍。**

相关笔记