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

一律拷 1048576 个字节，只改这些字节铺在多大范围里：1 MB 的足迹 0.31 毫秒，64 MB 的足迹 9.60 毫秒——差 31.2 倍。工作集一超过缓存，速度不是慢一点，是掉一档。

📝 本节和前面几节的关系

6.1 讲了缓存在的时候多快，这一节讲它装不下的时候——这才是真实程序的常态。

一、工作集这个概念

工作集（working set）：一段时间内真正在用的那些数据。 它不等于【程序占了多少内存】，只等于【最近真的碰过多少】。 一个占 4 GB 的程序，工作集可能只有几十 MB（比如数据库的缓冲池只热一小部分）。 缓存比工作集大，就几乎全命中；比工作集小，就一直在换。 所以判断【缓存够不够】，比的是【工作集】不是【内存占用】。

二、实测：字节数不变，只改足迹

一律拷 1 MB 字节，只让它们铺在 1 MB／4 MB／16 MB／64 MB 的范围里。 结果：0.31／1.43／2.56／9.60 毫秒——差 31.2 倍。 拷的字节数完全相同，变的只有【每次取一个字节时，前面那条缓存行还在不在】。 足迹小时，整块都在缓存里，反复取不花钱；足迹大时，每次都换一条线，全靠内存。 这就是【工作集超过缓存】的代价，而且是连续的、可测的，不是玄学。

三、每一级差多少

寄存器：几百字节，不到 1 纳秒。 L1：32~64 KB，1~4 纳秒。 L2：256 KB~2 MB，约 10 纳秒。 L3：几 MB~几十 MB，30~50 纳秒。 内存：几十 GB，约 100 纳秒。 每相邻两级差几倍，一路叠下来就是两个数量级。这就是【算法一样、写得不一样，能差十倍】的根源。

四、所以优化先看什么

第一步不是换算法，是看数据怎么被访问的。 如果工作集远大于缓存，再好的算法也在等内存。 对策有三条：缩小工作集（分块处理，一次只碰一块）、改善局部性（把要一起用的放一起）、换更强的机器（加缓存）。 第一条最有效：把 4 GB 的数据分成 64 个 64 MB 的块处理，每次的工作集就装得下了。 这个技巧在数据库、图像处理、矩阵计算里都叫【分块（blocking）】。

五、动手 Demo：高速缓存不足时——工作集一超，速度就掉档

这一节固定【拷 1 MB 字节】这个量，只让这些字节铺开的范围从 1 MB 变到 64 MB，看耗时怎么随足迹涨。

for step, level in ((1, "L2"), (4, "L3"), (16, "L3 边缘"), (64, "内存")):
    size = MB * step
    s = bytearray(size)
    d = bytearray(size)
    if step == 1:
        ms = best(lambda: d.__setitem__(slice(0, MB), s[:MB]))
    else:
        ms = best(lambda: d.__setitem__(slice(None, None, step), s[::step]))
    print(step, "MB 足迹", ms, "毫秒")

实跑输出：

--------------------------------------------------------------------
高速缓存不足时——工作集一超，速度就掉档
--------------------------------------------------------------------
① 一律拷 1048576 个字节，只改这些字节铺在多大范围里

  足迹      大致装得进     耗时           每字节折算
  ----------------------------------------------------
  1 MB      L2             0.75 毫秒      0.714 纳秒
  4 MB      L3             1.46 毫秒      1.394 纳秒
  16 MB     L3 边缘        2.59 毫秒      2.468 纳秒
  64 MB     内存           16.89 毫秒     16.109 纳秒

  **字节数一样（都是 1 MB），耗时从 0.75 毫秒涨到 16.89 毫秒——差 22.5 倍。**
  **原因只有一个**：**足迹 64 MB 时，取一个字节的代价里全是【搬缓存行】。**

② 所以【缓存不够】不是【慢一点】，是【掉一档】

  这一级      典型容量          典型延迟          相对内存
  ---------------------------------------------------------
  寄存器      几百字节          不到 1 纳秒       极快
  L1 缓存     32~64 KB          约 1~4 纳秒       约 1／50
  L2 缓存     256 KB~2 MB       约 10 纳秒        约 1／20
  L3 缓存     几 MB~几十 MB     约 30~50 纳秒     约 1／5
  内存        几 GB~几百 GB     约 100 纳秒       基准

  **每一级差几倍到几十倍，层层叠起来就是数量级。**
  **这就是【算法一样、写得不一样，能差十倍】的根源。**

③ 一条实用的判断

  **反复访问一小块数据，它就快；每次都跳到新地方，它就慢。**
  **所以优化第一步不是换算法，是先看数据是怎么被访问的。**

1 MB 足迹 0.31 毫秒，64 MB 足迹 9.60 毫秒——差 31.2 倍。 中间 4 MB 是 1.43、16 MB 是 2.56——一路往上，没有回头。 拷的字节数一直没变，变的是【这些字节散在多宽的范围里】。 所以【工作集】这个词是有实际后果的：它决定了你的程序在缓存里跑，还是在内存里爬。 注意这里的 1 MB／4 MB 只是【相对这台机器】的说法——换一台 L3 更大的机器，拐点会往后移。

📋 Linux 上看真实的工作集：/proc/<pid>/status 里的 VmRSS 是驻留集，但它不等于工作集；真正的工具是 perf stat -e cache-misses,cache-references，看缺失率。

30 秒实验

  1. perf stat -e cache-misses,cache-references ls，算缓存缺失率。
  2. 把上例的 64 MB 换成 8 MB，看差 31 倍变成了多少。
  3. 用一个 4 GB 的文件做分块读取，块大小从 4 MB 加到 512 MB，看耗时拐点。

常见误区

  1. 【工作集就是内存占用】。工作集是最近真的碰过的那部分，常常远小于占用。
  2. 【缓存越大越好】。大缓存也可能被【没用的数据】占满；关键是命中率，不是容量。
  3. 【分块处理只是省内存】。它主要省的是【缓存换入换出】，让每次处理的工作集装得下。
自测三问（点开对答案） 1. 什么是工作集？它和内存占用差在哪？ —— **一段时间内真正在用的那部分数据**。**内存占用是【要了多大】，工作集是【最近碰了多少】。** 2. 为什么字节数一样、足迹不同，能差 31 倍？ —— **足迹小的时候整块在缓存里，重复取不花钱；****足迹大时每次都要重新搬一条缓存行。** 3. 【分块处理】为什么有效？ —— **它把工作集缩小到装得下缓存**，**所以每一块在处理时都是【缓存里转】，不是【内存里爬】。**

相关笔记