Sherfiter's wiki for fun

第 7 章 · 存储层次与 Cache

第 1 章埋了一个问题:为什么 L1 缓存只有 32KB,还要拆成指令、数据两半?为什么 12 个线程共享一份 L3?先把谜底用的参数从机器里读出来(Linux 上这个目录就是缓存的户口本):

$ cat /sys/devices/system/cpu/cpu0/cache/index0/size
32K
$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64

第一个数是容量,第二个数 64 字节是缓存行(cache line)的粒度:CPU 和内存之间的搬运,最小单位就是它,哪怕你只读 1 个字节,也有一整行 64 字节被拉进缓存。理解了「一切按行搬运」,Cache 的三件套(怎么放、怎么换、怎么写)全是顺着它长出来的。本章的目标:把这三个机制亲手算一遍,然后回头解释几个你迟早会撞上的性能现象:为什么按行遍历二维数组快几倍、为什么链表遍历慢得冤枉、为什么多线程改相邻变量也能互相拖慢。

7.1 前提:程序访存是偏心的

Cache 能生效,靠的是程序访存的统计规律,即局部性:

  • 时间局部性:刚访问过的地址,很可能马上再访问。循环变量 i、热点函数、当前事务的数据。
  • 空间局部性:访问了某地址,很可能马上访问它旁边。顺序扫数组、顺序执行指令,都是。

一个朴素循环两头占全:

for (int i = 0; i < n; i++)   // i 被反复读写:时间局部性
    sum += a[i];              // a[0], a[1], a[2]...:空间局部性

注意这是统计规律,不是硬件承诺。反例就是链表:p = p->next 每一步跳到堆里一个随机地址,空间局部性为零,缓存行里拉进来的 63 个「邻居」字节全都白拿。这是「链表几乎永远输给动态数组」的真正原因,和算法复杂度无关,和内存访问模式有关。

7.2 一座金字塔和一笔期望账

存储器的速度和容量天生成反比,工程师的解法是全都要:堆一座金字塔,越往上越小越快,把热点数据尽量顶在上层:

寄存器    <1 ns          几十个
L1        ~1 ns          32~64 KB   (每核私有,指令数据各一份)
L2        ~4 ns          几百 KB~几 MB  (每核私有)
L3        ~15~40 ns      几十 MB    (全核共享)
主存      ~100 ns        几十 GB
SSD       ~100 μs        TB 级

(数字是现代桌面机的典型量级,具体值 lscpu、lstopo 都能看到。记住比例感:L1 比主存快百倍,主存比 SSD 快千倍,每下一层,速度掉一个量级以上。)

性能用一笔期望账算:

平均访存时间 = 命中时间 + 缺失率 × 缺失代价

命中率 95% 听着很高?代入算一下:命中 1 ns,缺失代价 100 ns,平均 = 1 + 0.05 × 100 = 6 ns,是命中时间的 6 倍。这就是为什么缓存设计的一切努力都围绕压低缺失率,也解释了下一节为什么愿意为「减少冲突」花那么多硬件。

7.3 怎么放:地址切块,三种方案

主存的块要放进 Cache,得有个摆放规则。先把 32 位地址切成三段(以 L1 32KB、64 字节行、8 路组相联为例):

| 标记 Tag  (21 位) | 组号 Index (6 位) | 行内偏移 Offset (6 位) |
  • 偏移 6 位:64 字节的行内找哪个字节。
  • 组号 6 位:32KB ÷ 64B ÷ 8 路 = 64 组,块落到哪一组由它决定。
  • 标记:剩下的高位,用来辨认「这一组里的哪一块才是我要的」。

摆放规则三种,是「自由度与查找成本」的三个刻度:

直接映射:每块只能去唯一一个位置(组号一除就定)。查找最快,代价是冲突:两个常用块若组号相同,会反复互踢,命中率崩塌。我写过一段真实翻车代码:两个大数组的下标始终差 64 组号模 64 的整数倍,直接映射下互相驱逐,程序慢得离谱,换组相联立刻痊愈。

全相联:想去哪去哪。查找要并行比较所有行的标记(内容寻址存储器 CAM),面积功耗爆炸,只配给 TLB 这种小表用。

组相联:折中,也是全行业的选择。先按组号定组,组内任意放;查的时候并行比较组内 8 路(或 16 路)标记。冲突还在,但概率被组内自由度稀释。

查一次缓存的完整流程,拿地址 0x12345678 走一遍(L1 32KB/64B/8路):

偏移 = 0x78 低 6 位 = 0x38      (行内第 56 字节)
组号 = 地址中间 6 位 = 0x1E     (落到第 30 组)
比较第 30 组 8 路的 Tag 是否等于地址高 21 位
命中 → 从对应行的偏移 56 处读出数据,~1ns
未命中 → 去 L2,同时把这行(64B)拉进第 30 组,踢掉一行的旧数据

7.4 怎么换:LRU 和它的穷人版

组满了,新块进来要踢旧块。理想是 LRU(最久未用的先走),精确实现要记全排列,硬件做不起。实际用近似:伪 LRU(树形位图,每层一位记「哪半边最近用过」),或者干脆随机。别小看「近似」:4 路的伪 LRU 和真 LRU 的命中率差距通常在 1% 以内,硬件成本差一个数量级,这笔账工程上闭着眼都选近似。顺带一提,第 8 章虚拟内存的页面置换和这里是同一个问题的另一个尺度,连 LRU 用不上(缺页代价太大,用时钟近似)这一点都平行复刻。

7.5 怎么写:写直达、写回与脏位

读的缺失只是慢,写的麻烦在于「两份副本」:缓存里有,内存里也有,写的时候改谁?

写直达(write-through):同时写缓存和内存。内存永远新鲜,简单,但每次写都付 100ns,写密集程序吃不消。

写回(write-back):只写缓存,给行加一位「脏位」标记;被踢出去时才把脏行写回内存。写得快(以缓存速度),省内存带宽,代价是多一位状态和替换时的写回延迟。现代 CPU 的缓存几乎清一色写回。

两个配套细节:写缺失时通常「写分配」(把块拉进来再改,赌你还会继续写这块);写直达机型会配一个写缓冲队列,CPU 扔进去就走人,后台排队写内存。多核时代还有第三层问题:四个核各有一份缓存,谁的数据算数?这要靠 MESI 一类一致性协议,每个核监听总线上别的核对共享行的读写,把自己缓存里的过期行作废。这就是「伪共享」的病根:两个线程各写各的变量,物理上却住在同一个 64 字节行里,一个写,另一个核的整行作废,来回拉锯。解法朴素得离谱:把高频写的变量各自填充对齐到不同行(C 里 alignas(64))。

常见错误

  • 按列遍历行主序数组。a[j][i] 外层 j 内层 i,每次跳一整行的距离,一个缓存行用 8 个字节就作废。行主序语言(C、Java)里嵌套循环的内层下标应该是「走得最快的那维」。
  • 热循环里访问一堆指针 chasing 的结构。链表、树、图的节点散在堆上,节点越小越分散越惨。把大数据从「指针数组」改成「下标数组 + 连续存储」是真实优化案例里最常见的一招。
  • 多线程变量随便放。计数器们挤在一个结构体里被多个线程同时改,伪共享让性能随核数不升反降。用 padding 或 per-thread 局部变量隔开。

练习

  1. 手算:按 7.3 的参数(32KB、64B、8 路),给出地址 0x00ABCD40 的组号和行内偏移,并算出该地址所在缓存行的首地址。
  2. 手算:L1 命中 1ns、缺失去 L2 花 12ns、L2 缺失去主存再花 80ns,L1 缺失率 4%、L2 缺失率 20%,求一次访存的平均时间。
  3. 动手:写一个 4096×4096 的 int 数组,分别按行、按列求和各计时;把两个时间除一下,和理论预期(缓存行 64B、int 4B,一行 16 个元素)对一下量级。
  4. 思考:为什么 L1 拆成指令、数据两半(第 1 章那个问题现在能答了),L3 却不分?提示:回看第 6 章结构冒险,再想想 L3 的访问压力和容量约束。
豫ICP备2026027944号