内存层级 入门
读一个字节要 1.6 ns 还是 10 ms，只取决于它已经在哪儿。6 个 section:代价、为啥层级是被逼出来的、64 字节的 line、局部性、悬崖，以及速查。
一次 load 到底花多少
最快的答案和最慢的答案之间隔着 6 个数量级。这一页后面的一切，都是这条跨度的后果。
我们的 curl 进程把一个 URL 字符串放在内存某处。读它的第一个字节是一条指令，不管哪一级应答都一模一样；变的只有那段等待。下面每个数字都出自同一台机器：3.2 GHz 的 Intel Golden Cove 核、 48 KB L1d、1.25 MB L2、30 MB L3、双通道 DDR5-6400。
7 个地方可能存着这个字节，由谁应答决定一切。把滑块沿着这些级往下拖 ——应答的那一级旁边那条是它的延迟(对数轴), 读数里给的是同一个数字换算成周期：
注意跨度到底长在哪。芯片内部那 4 级从 0.31 ns 到 15.6 ns —— 整颗核里差 50 倍。然后往 DRAM 迈一步，再往存储迈一大步。缩放成一次 L1 命中等于 1 秒， 就在 50 秒外，在 72 天外。
民间说法是，层级每往下一步大约 100 倍。这句话值得核对而不是复读：把较快的那一级和较慢的那一级分别放到两个滑块上，读它们之间的倍数：
这个说法在芯片内部远远偏大，在芯片外面又远远偏小。L2 比 L1 是 2.9 倍、 L3 比 L2 是 3.3 倍、DRAM 比 L3 是 5.1 倍 —— 一段缓坡。然后DRAM 到 SSD 一步就是 1250 倍。这不是一段楼梯，是一段末端带悬崖的缓坡。
延迟只有和它挤掉的工作放在一起才有意义。一次 load 还没回来时，核继续发射它能找到的任何指令，而它填不满的发射槽才是真正的账单。拖动这次 load 的延迟，看着槽消失：
80 ns 时，核已经烧掉 256 个周期、按每周期 3 条算是 768 个指令槽。乱序执行能回收调度窗口里刚好存在的那些独立工作 —— 几十条，不是八百条 —— 这就是内存受限的循环 IPC 掉到 1 以下的原因，而同一颗核在它已经拿到的数据上能稳住 3。
核不是一次只等一个未命中。它有 10 个 line-fill buffer, 所以最多能有 10 个未命中同时在途, Little 定律把这个数直接变成带宽。把在途数量往上拖：
10 个各 64 字节的未命中、每 80 ns 一批，就是8.0 GB/s —— 只占两条 DDR5-6400 通道能给的 7.8%。单核喂不满这台机器的内存系统，大约要十来个核。这种不对称正是单线程 microbenchmark 和满载服务器对「内存有多贵」给出不同答案的原因。
而且分歧的方向没人预留过。当这些核加起来逼近通道能供的峰值时，请求开始互相排队，每颗核看到的延迟就不再是个常数：
看这条曲线远在总线塞满之前就离开了 80 ns 那条线。用到峰值的 80% 时要等 160 ns,95% 时是 460 ns。每张延迟表上印的都是空闲数字，在一台安静的机器上量的，而它恰恰是最不可能描述生产环境的那个数字。
诚实的代价不是「80 ns」。这一页剩下的部分，讲的都是怎么别付这笔钱。
为啥它必须是个层级
快、大、便宜。今天任意两个都造得出来，3 个一起造不出来。层级就是这个「造不出来」的样子。
大家第一个抓来的解释是光速，而那是个错的解释。信号在铜里大约 15 厘米每纳秒，所以距离确实给每次访问垫了下限 —— 怪它之前值得先量一量。
把内存块从 ALU 旁边拖开。那几条刻度分别是裸片边缘、封装边缘，以及板子另一头的 DIMM 插槽；读数是光凭这段距离就要付的往返：
注意这买不到多少。60 毫米一来一回是 0.80 ns —— 2.6 个周期。 DRAM 要 80 ns 才应答，是它的 100 倍。距离只定下限，别的都不管；剩下的等待发生在存储阵列本身里面。
两种技术就在这儿分道。一个 SRAM 单元是 6 个晶体管接成的锁存器，自己保住自己的状态。一个 DRAM 单元是 1 个晶体管加 1 个电容，而电容上的电荷会漏掉。把时间从上次刷新往后拖：
超过 64 ms,电荷掉到读出阈值以下，这一位就没了，所以 DDR4 在这个窗口内刷新每一行 —— 8192 条刷新命令，每 7.8 µs 一条。读这个单元同样会把它放空，所以每次读之后都跟着一次写回。是这一串动作，不是那根导线，构成了 80 ns。
为这份脆弱换来的是密度，而密度就是价格。一位在 SRAM 里要 6 个晶体管，在 DRAM 里只要 1 个多，而这个差距会沿整条供应链复利。把你想要的容量往上拖，看哪几行还买得起：
到 1 TB 时，磁盘是 $15,SRAM 是 $409,600 —— 同样的字节差 26,667 倍。一台配 1 TB 缓存级 SRAM 的机器不是慢也不是热，它只是压根不会是任何人会买的产品。
就算钱是白来的，你还是造不出来，因为阵列越大越慢：字线更长、灵敏放大器更多、译码器更深。把缓存的容量往上拖，从曲线上读访问延迟：
看曲线穿过本核那 3 个实测点。 1 MB 的 L1 要 14.6 个周期才应答 —— 这正是 L2 已经要的数。世上没有「又大又快的缓存」这种东西：你造出来的是下一级，只是取错了名字。
于是这些级被摞起来，而摞起来本身又带出一个问题：一条 line 待在 L2 里时，L3 还留不留副本？切换策略、拖动核数 —— 这一摞能装下多少对上它花在副本上的多少:
包含式 L3 让一致性变便宜：一次 snoop 在 L3 上没命中，就可证明在它上面每个 L2 上都没命中。代价是容量 —— 8 核时，30 MB 的 L3 里有 10 MB 装的全是副本。互斥式设计拿到 40 MB，换来的是必须广播。
搬运的单位是 line
缓存从不搬一个字节。它一次搬 64 个，放进一个由地址算出来的槽，顺手把原来那条踢掉。
64 字节从 Pentium 4 起就是 x86 的 line 长度，Arm 的 Cortex 和 Neoverse 也是这个数 —— 这条带子画的就是它。
沿着这条带子拖动正在读的那个 word。每个格子是一个 8 字节的 word，上面的括号标出包含它的那条 line, 只有轮廓的格子是跟着一起被搬来、没人请的字节:
注意你怎么移动，代价都不变。这个 word 还是下一个，事务都是同样的 64 字节、同样的 80 ns; 你能控制的只有你用掉了其中多少。「空间局部性」这个词的全部内容就是这个。
这个 64 并不通用，而一旦你为它做填充，这件事就要紧了： IBM POWER 和 Apple silicon 一次搬 128 字节，所以 sysctl hw.cachelinesize 在 M 系列 Mac 上回答 128, 在旁边那台 Intel Mac 上回答 64。于是把结构体补到 64 字节、想让两个核不抢同一条 line 的做法，在一半的机器上什么也没买到 —— HotSpot 把 @Contended 字段补到 128。哪个数字都是同一个折中：每个有用字节摊多少 tag 对搬来多少没人要的数据。
一个按跨步走内存的循环直接决定了这个比例。设定元素之间的跨步再读那条计量条 —— 它是程序真正碰到的、每条取来的 line 里的比例：
跨步一到 , 每个 4 字节元素就独占一条 line:每 64 字节里用到 4 个,6.3%, 同样的答案要付 16 倍的内存流量。过了 画面就不再变坏，因为它没法更坏 —— 一个元素一条 line 已经是地板。
line 落进哪个槽，由地址自己决定：切成 3 个字段，除了移位和掩码没有别的算术。拖动地址，再换容量，看index 和 tag 之间的分界线怎么移：
最低 6 位是 offset —— line 内部的第几个字节 —— 根本不会送到缓存。接下来那几位是 index, 只有它们挑选组。两个在这几位上相同的地址会抢同一组，不管它们在内存里离多远。
一组不止装一条 line，装几条就是相联度。这里 8 条热行 index 到同一组，循环按环形走它们。把每组的路数往上拖：
看未命中率是掉下悬崖，不是滑下斜坡。7 路时，每一轮都刚好踢掉循环下一步要的那条；到 8 路，8 条 line 全都留住，未命中率是 0。问题不在容量 —— 这一组按字节算从来没满过，只是按路数满了。
这道悬崖背后有一条策略。组满了总得踢掉一条，而踢哪条，正是「工作集装得下」和「工作集在颠簸」的分界。切换策略，再比路数多加一条热行:
8 路的组里放 9 条 line,LRU 在每一次访问上都未命中 —— 它每次踢的正好是环里下一个要用的。FIFO 一样。随机做不到连续这么倒霉，只有 23% 未命中。
真实缓存两个都不用：精确 LRU 次序每组要 log₂(N!) 位，所以硬件用一棵位树或者每行一个「最近没用」位来近似 —— 这抹平了上面那个病态，却没有消掉它。
局部性就是全部的赌注
缓存是在赌：下一个地址要么是你刚用过的，要么挨着它。赌输的代价是 100 倍，而指令条数一样。
时间那一半有个可度量的形状：复用距离 —— 同一条 line 两次使用之间碰过的不同 line 的数量。容量为 C 的缓存，把距离小于 C 的每一次访问变成命中，别的都不变。
下面是一段 96 次访问的 trace 的距离直方图。把容量切线往右拖 —— 左边是命中，右边是未命中, 最远那列是每条 line 的第一次触碰：
注意回报有多不均匀。头 4 行容量买到44% 的访问；从 12 行加到 16 行什么也买不到，因为那个区间里本来就没东西。缓存定容是一条带拐点的曲线，而拐点是程序的属性，不是硬件的。
空间那一半由循环访问内存的顺序决定。C 的数组 M[N][N] 把 M[i][j] 放在 M[i][j+1] 旁边；这里每一行正好是一条 line。把遍历一步步推，再切换遍历顺序:
看左边那列 line。行优先时，8 个元素花 1 条 line; 列优先时，同样 8 个花 8 条。在 4096×4096 的 double 矩阵上，就是 2,097,152 条对 16,777,216 条 —— 一模一样的算术，8 倍的流量。 Fortran 按列优先存，所以同一个循环嵌套在那边是对的，在这边是错的。
同样的论证在一条记录内部也成立。一个带位置、速度、颜色的粒子是 9 个 float; 只读位置和速度的更新步骤要其中 6 个。拖动循环读几个字段，再切换布局：
只要循环读的少于全部 9 个，结构体数组这种布局就要搬 36 字节才用上 24, 而三分之一的带宽花在没人要的颜色上。数组结构体那种布局搬的正好是它读的，而且每个字段数组不用 gather 就能向量化。
两种效应汇成同一条曲线。下面这段区域被走了两遍：一遍按地址顺序，一遍作为指向它内部的依赖指针链。把区域的大小从 4 KB 拖到 1 GB:
顺序扫描几乎不动：到哪儿都不到 1 ns 一个元素，因为 16 个元素共享一条 line、10 条 line 同时在途。指针追逐到 1 GB 时爬到每步 103 ns —— 211 倍 —— 而执行的指令条数一样。
顺序那条曲线之所以平，是因为硬件在帮忙。连着两条 line 之后，流式预取器就咬住，并提前程序 8 条 line 发出 load。沿着带子拖动这次读，再把遍历切成随机顺序：
顺序时，读的前方那些 line已经在路上，真正的 load 命中。随机时没有跨步可探测，流根本形不成，每次读都付满 80 ns。这就是同样渐进复杂度下 vector 打赢链表的机械原因。
于是在查找结构里该优化的是扇出，不是深度。二叉树每层花一条 line; B 树的一个节点填满一整条 line 或一页，然后把整节点都比一遍。设定节点大小和键的数量:
4 KB 的节点配 16 字节的键，扇出是 256，所以 10 亿个键只要取 4 次，而不是 30 次。两个都是 O(log n)，对数的底由传输单位定。
它在哪儿掉下去，又掉得多安静
这里没有一样会抛异常。工作集大了 5%、2 的幂跨步、默认页大小 —— 每一样都给出正确答案，只是慢好几倍。
先说整个层级赖以运转的不变式。每一次访问，这条 line 都被某一级持有，代价就是持有它的最小那一级的延迟。未命中率不过是「那一级是哪一级」的分布。
对 W 字节工作集上的均匀随机访问，只要 W 超过 C, 容量 C 的缓存的命中率正好是 C/W。把工作集拖过那 3 个容量，从曲线上读平均值：
在 30 MB —— 正好是 L3 —— 平均访问是 15.1 ns。 60 MB 时是 47.6 ns。程序什么都没变：同一个循环、同样的指令条数、3 倍的墙上时间。这就是工作集悬崖，而它给出的唯一警告就是这个数字本身。
这条曲线不是魔法，它就是一个嵌套表达式。平均访存时间等于 L1 命中时间，加上未命中的那部分乘以 L2 时间，再加上又未命中的那部分乘以 L3 时间，以此类推。拖动L1 未命中率和L3 未命中率:
因为每一项都被它上面所有未命中率乘过，最深那一项杠杆最大：在每千次 30 次 L1 未命中时，把L3 未命中率从 20% 翻到 40%，平均值从 2.1 ns 变成 2.3 ns —— 对每一次访问都是。这就是「去量 LLC-load-misses 而不是猜」的全部论据。
还有第二个缓存，坏的方式一样，却更容易被忽略。每次访问同时要做地址翻译，而 TLB 缓存的正是这些翻译：本核上是 1536 条。拖动工作集，再换页大小：
4 KB 页时那是 6 MB 的覆盖 —— 不是民间说法里的 256 MB —— 所以 30 MB 的工作集会让80% 的访问在真正取数据之前先走一遍页表。换成 2 MB 页，覆盖乘以 512,整个工作集都装得进去。
最后一道悬崖专抓好工程师，因为代码看着是对的。沿着一个行距刚好是 2 的幂的矩阵往下走一列，每一行都落进同一个组。把每行的填充从 0 往上拖：
时，全部 64 行都 index 到同一个 8 路的组，每一轮把 64 条全部重新未命中一遍。, 这一列就摊到全部 64 个组上，未命中归零，数组只大了 1.6%。
double M[512][512]; /* 行距 4096 B：每个 */
/* M[i][0] 都落进 set 0 */
double M[512][512 + 8]; /* 每行 +64 B：这一列 */
/* 铺满全部 64 个 set */这 3 样没有一样会自报家门：没有异常、没有日志、没有断言失败 —— 只有正确答案，慢 20 倍，而且只在大到值得在意的输入上。
速查
3 个该张口就答的问题，以及 5 个危险信号，每个都带着它要花的那个数。
把不变式说出来。
每一次访问，这条 line 至少被某一级持有，代价是持有它的最小那一级的延迟。正确性从不取决于是哪一级 —— 命中和未命中返回的字节完全一样。这里所有故障都是性能 bug，从来不是错误答案。
我的程序现在在这条梯子的哪一档？
取热循环反复访问的数据大小 —— 不是分配量，是它真正碰到的那部分。拖动它，读出大多数访问由哪一级应答：
48 KB 以下，答案是 L1，平均 1.6 ns。过了 30 MB,DRAM 应答其中大多数，平均值朝 80 走。有用的读数不是端点而是占比：一旦 DRAM 应答的比例超过百分之几，那一项就主导了平均值，别的都是舍入误差。
为啥 line 是 64 字节而不是 256?
更大的 line 摊薄 tag 和 DRAM 突发更好，还白送预取。但它也搬来更多没人要的字节，并让伪共享更糟 —— 两个核写相隔 100 字节的变量会把同一条 line 来回抢。下面 5 种模式付的就是这笔账：
每一个都是同一笔交易换了身衣服：循环不读的东西，跟着要读的东西一起来了。链表搬 64 字节只用 8; 指针数组每个对象付两条 line；拉链法每次探测多付一条。
第 4 个在 review 里看不见，因为字节数全都是对的。动代码之前先用 perf stat -e cache-misses,LLC-load-misses,dTLB-load-misses 确认，改完再量一次。