内存层次与延迟数字

处理器把两个数相加只要不到一纳秒，但取一个不在任何缓存里的数却可能要80 ns。本讲把这些延迟数字合成一个数，也就是一次内存访问的平均代价，并指出是哪一级内存在吃掉你的时间。

交易程序的大部分时间都在等数据：一个价格、一个订单、表里的一行。对这些数据做算术几乎是免费的，但数据得先从内存运到处理器，离得越远越慢。想想书桌、书架、图书馆的某一层和城另一头的仓库：桌上那几张纸瞬间就到，书架要几秒，图书馆要一分钟，仓库要一下午。计算机把最常用的数据复制到处理器旁边小而快的存储里，叫作缓存，这样大多数请求在“书桌”上就能得到回答。

典型的服务器核心在主内存前有三级缓存。我们把它们叫作 L1、L2、L3，把主内存叫作 RAM。被某级缓存回答的请求是一次命中，必须继续去下一级的请求是一次缺失。下面的代码把四个延迟并排放在一起。

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}for level, ns in LATENCY_NS.items():    print(level, ns, "ns", ns / LATENCY_NS["L1"], "x L1")

L1 1.0 ns 1.0 x L1
L2 4.0 ns 4.0 x L1
L3 15.0 ns 15.0 x L1
RAM 80.0 ns 80.0 x L1

每一级都比上一级慢好几倍，RAM 比 L1 慢80 倍。整个技能就是要保证大多数访问在靠上的层级就得到回答。

访问从 L1 开始。值在那里，就只花 L1 的延迟，访问结束。不在，处理器就依次问 L2、L3，再到总有这个值的 RAM。问过的每一级不管命不命中都要花时间，所以在 L3 找到值的访问已经付了 L1、L2、L3 三级的钱。

1. 1
   先问 L1花 1 ns。命中就结束。
2. 2
   未命中再问 L2再花 4 ns。命中就结束。
3. 3
   未命中再问 L3再花 15 ns。命中就结束。
4. 4
   未命中就去 RAM再花 80 ns。RAM 总是有这个值。

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}cost_found_in_l3 = LATENCY_NS["L1"] + LATENCY_NS["L2"] + LATENCY_NS["L3"]print(cost_found_in_l3, "ns")

20.0 ns

由 L3 回答的访问花 20 ns，不是 15：前两次未命中花掉的 1 ns 和 4 ns 也要算进账里。

没有哪一次访问是“典型”的，所以我们求许多次访问的平均。按每条路径出现的频率给它的代价加权：每次访问都付 L1 的延迟，只有在 L1 未命中的那部分才付 L2，两级都未命中的那部分才付 L3，依此类推。写成一个表达式，括号像层级一样层层嵌套：

这就是平均内存访问时间。括号要从里往外读：最里面一层是在 L3 未命中的代价，往外一层加上访问 L3 的时间，一直到每次访问都要付的 L1。

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}h1, h2, h3 = 0.9, 0.8, 0.7t = LATENCY_NSamat = t["L1"] + (1 - h1) * (t["L2"] + (1 - h2) * (t["L3"] + (1 - h3) * t["RAM"]))1print(round(amat, 2), "ns")

2.18 ns

1. 11 - h 是未命中的访问所占比例，所以每一层括号都乘上能走到这一步的比例。

即使 90% 的访问在 L1 命中，平均仍是 2.18 ns，超过 L1 延迟的两倍。少数走到深处的访问太贵，把平均值拉了上去。所以一个看起来很棒的命中率，背后仍可能是一个慢程序。

有两个看似相同、答案却不同的问题：哪一级回答了这些访问？哪一级占用了时间？前者数访问，后者数等待。每一级只会被一部分访问到达，每次到达都要付它的延迟，所以一个很少被到达但很慢的层级，仍然可能主宰等待时间。

h1, h2, h3 = 0.9, 0.8, 0.7served = [h1, (1 - h1) * h2, (1 - h1) * (1 - h2) * h3, (1 - h1) * (1 - h2) * (1 - h3)]reach = [1.0, 1 - h1, (1 - h1) * (1 - h2), (1 - h1) * (1 - h2) * (1 - h3)]1cost = [r * ns for r, ns in zip(reach, [1.0, 4.0, 15.0, 80.0])]2print([round(x, 3) for x in served])print([round(c / sum(cost), 3) for c in cost])

[0.9, 0.08, 0.014, 0.006]
[0.459, 0.183, 0.138, 0.22]

1. 1reach 是访问到每一级的比例：所有访问都会到 L1。
2. 2sum(cost) 就是平均访问时间：和前面一样是 2.18 ns。

RAM 只回答 0.6% 的访问，却占了 22% 的等待时间，而 L1 回答了 90% 的访问，只占 46% 的时间。这是本技能里所有优化背后的关键事实：不要数访问次数，要数时间花在了哪里。

这对一张真实的表有多重要？实验里 SPY 日线表有 5,405 行、五列（开、高、低、收、成交量），共 27,025 个值。把每个值读一遍，分三种条件：几乎全部命中的热缓存、温缓存，以及每一级都有一半访问未命中的冷缓存。

实验把这一讲变成六个小函数，每个都建立在前面的基础上，最后估算读取真实 SPY 表的代价。下面列出它们，以及各自回答的问题。

• 函数 · 问题依赖
• average_access_time(hit_rates)一次访问平均花多少？延迟表
• slowdown(hit_rates)比总在 L1 命中慢多少倍？average_access_time
• levels_served(hit_rates)哪一级回答了访问？局部命中率
• time_shares(hit_rates)哪一级占用了时间？average_access_time
• scan_time_us(n_accesses, hit_rates)n 次访问要多久？average_access_time
• study(bars)读完整张 SPY 表要花多少？scan_time_ustime_shares

下一个主题：本讲把命中率当作已知量。在缓存行与空间局部性里，你要自己搭出产生这些命中率的缓存，并弄清为什么读紧挨着刚读过的值几乎不要钱。