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

同样拷 4 MB 字节，连续拷 2.10 毫秒，每 16 字节取一个要 18.33 毫秒——差 8.7 倍。字节数一模一样，差的只是这些字节铺在多大范围里。

📝 本节和前面几节的关系

第 5 章讲完内存怎么分，这一章往上看：CPU 眼里内存不是平的，是分层的。这一节先看清最贴身的那一层——高速缓存。

一、缓存是什么

CPU 算得比内存快得多：一次加法几纳秒，取一次内存要上百纳秒。差两个数量级。 所以 CPU 里塞了一小块很快的存储器，把最近用过的数据复制一份放着——这就是高速缓存（cache）。 它不改变内存的容量，只改变【取数的速度】。代价是【复制】与【判断在不在】，但这两件事由硬件做，不花钱。 一句话：缓存是【把常用的东西放在手边】，不是【把东西变小】。

二、搬运的单位是缓存行

缓存不是按字节搬的，是按【行】搬的——现代 x86 与 ARM 都是 64 字节一行。 所以你要一个字节，它搬一整条 64 字节的线。 这带来一个直接后果：连续用 64 个字节，只付一次搬运费；每隔 64 字节用 1 个字节，付 64 次。 实测：同样拷 4 MB，连续拷 2.10 毫秒；每 16 字节取一个，要 18.33 毫秒。字节数一样，慢 8.7 倍。 差的不是【搬了多少】，是【搬来的用没用上】。

三、硬件还会猜

预读（prefetch）：你顺序访问时，硬件猜你还要往后读，提前把后面的行搬进来。 猜对了就白赚，猜错了白搬。 所以【顺序访问】比【跳跃访问】占便宜——不只是缓存行的关系，还有预读的关系。 这也是为什么【数组遍历】比【链表遍历】快：数组的下一个元素地址可预测，链表的不可预测。 两者复杂度一样，常数可以差十倍。

四、这条规则怎么用

一、把要一起用的数据放在一起。结构体按访问频率排字段，热字段挤在同一条缓存行里。 二、能用数组就别用链表。除非你需要频繁在中间插入删除——那时候链表省的是搬移，不是缓存。 三、二维数据要【按行走】。按列走等于每一步都换一条缓存行（6.5 实测）。 注意这三条都不是【改算法】，是【改布局】——性价比最高的一类优化。

五、动手 Demo：高速缓存——为什么顺序访问比跳跃访问快

这一节拷同样多的字节，一个让这些字节集中在 4 MB 里，一个让它们横跨 64 MB，比一比耗时。

import time
MB = 1024 * 1024
src = bytearray(64 * MB)
dst = bytearray(64 * MB)
m = 4 * MB

def best(f, rep=5):
    r = []
    for _ in range(rep):
        t0 = time.perf_counter()
        f()
        r.append((time.perf_counter() - t0) * 1000)
    return min(r)

a = best(lambda: dst.__setitem__(slice(0, m), src[:m]))
b = best(lambda: dst.__setitem__(slice(None, None, 16), src[::16]))
print("连续 4MB", a, "毫秒")
print("跨 64MB 取 4MB", b, "毫秒")

实跑输出：

--------------------------------------------------------------------
高速缓存——为什么顺序访问比跳跃访问快
--------------------------------------------------------------------
① 同样拷 4 MB 字节，只改这些字节铺在多大范围里

  走法                 拷了多少字节     足迹      耗时
  -----------------------------------------------------------
  连续拷 4 MB          4 MB             4 MB      2.03 毫秒
  每 16 字节取一个     4 MB             64 MB     19.43 毫秒

  **拷的字节数一模一样，第二种慢了 9.6 倍。**
  **区别只有一个**：**第一种只在 4 MB 里转，第二种横跨了整个 64 MB。**
  **前者全在缓存里，后者大部分要从内存里搬。**

② 为什么【跨得远】就要重新搬

  机制         连续时                     跳跃时
  -------------------------------------------------------------
  缓存行       搬一次 64 字节，全用上     搬一次，只用几个字节
  硬件预读     猜你要往后走，提前搬       猜不中，白搬
  命中位置     几乎全在 L1／L2            很多要走到内存

  **记住这句话**：**缓存的搬运单位是【一条 64 字节的缓存行】，不是【一个字节】。**
  **所以【用得上你搬来的东西】比【搬得少】更重要。**

③ 这条规则在你写的代码里长什么样

  写法                 缓存友好吗     为什么
  -------------------------------------------------------------------
  按行遍历二维数组     友好           下一个元素就在同一行里
  按列遍历二维数组     不友好         每走一步就跨一整行
  链表遍历             不友好         节点散在堆上，猜不到下一个在哪
  数组遍历             友好           地址连续，预读能跟上

  **这就是【数组常常比链表快】的真正原因**——**不是复杂度，是缓存。**
  **两者复杂度一样，但常数可以差十倍。**

连续 2.10 毫秒、跨 64 MB 18.33 毫秒——差 8.7 倍。 两个都拷了 4 MB 字节，区别只在【这 4 MB 铺在多大范围里】。 前者全在缓存里转，后者大部分要从内存里搬。 注意这里还只是【内存】这一层的差距——如果这些数据在磁盘上，差距会是几千倍。 所以【数据放在哪】比【代码怎么写】更能决定快慢。

📋 Linux 上看缓存的规格：lscpu | grep -i cache——L1d／L1i／L2／L3 各自多大、几路组相联都列出来。

30 秒实验

  1. lscpu | grep -i cache，看这台机器的 L1／L2／L3 各多大。
  2. 把上例的步长从 16 改成 64，看耗时怎么变。
  3. 把数组换成链表（Python 的 list of dict），比一次遍历耗时。

常见误区

  1. 【缓存是按字节搬的】。是按64 字节一条缓存行搬的，所以你用不完就浪费。
  2. 【缓存越大越快】。决定快慢的是命中率，不是容量；装了一堆用不上的东西，命中率反而低。
  3. 【缓存是操作系统管的】。CPU 里的缓存完全是硬件管的，操作系统只负责页缓存（6.8）那一层。
自测三问（点开对答案） 1. 为什么顺序访问比跳跃访问快？ —— **因为缓存按 64 字节一条线搬**：**连续用能全用上，跳跃用只用到几个字节；****而且硬件预读只猜得中顺序访问。** 2. 实测里两个走法拷的字节数一样，为什么差 8.7 倍？ —— **字节数一样，但【铺开的范围】不一样**：**4 MB 全在缓存里，64 MB 大部分在内存里。** 3. 数组比链表快的真正原因是什么？ —— **地址连续，缓存行与预读都能用上**；**链表节点散在堆上，每一个都可能是一次新的搬运。**

相关笔记