来源：https://root-11.codeberg.page/intro-book-python/

1 — 机器模型

大多数关于“计算机如何工作”的解释都会使用一个带有 CPU 和一个称为内存的大块的示意图。这个图是错的。内存是许多不同速度的东西，你的数据位于哪个部分决定了你的程序是快还是慢。

CPU 内部有 L1 缓存——很小，每核心有时只有 32 KB，但从它读取大约需要 1 纳秒。它周围是 L2——几百 KB，大约 3-4 纳秒。然后是 L3——以 MB 计量，大约 10 纳秒。CPU 外部是主内存 (RAM)——以 GB 计量，每次读取大约 100 纳秒。这些数字因芯片而异；但比率是稳定的。L1 大约比 RAM 快一百倍。

当你的代码读取 arr[17] 时，CPU 不只拉取第 17 个字节。它拉取一个完整的 64 字节块——一个缓存行——并将该行保存在 L1 中。随后读取 arr[18] 几乎是免费的。顺序读取很快，因为每个被加载的行在被驱逐之前大部分都被使用了。随机读取很慢，因为每次读取都需要一次新的 RAM 访问。

指针是内存中的一个地址。跟随一个指针就是一次内存读取，而 CPU 无法预测这个地址。如果该地址在缓存中，读取很快；如果不在，你需要等待完整的约 100 纳秒。一个拥有许多对象和它们之间许多指针的程序是一个充满了这些等待的程序。

为什么你以前不需要考虑这些

如果你上周用过 Python，上述这些都不会出现。解释器运行你的代码，操作系统给它分配内存，并且它工作了。你在 100 KB 或 100 MB 时感觉不到任何悬崖。你写了一个 for 循环，循环运行了，每个元素的成本就是它本来的样子。

这种体验是真实的，并且它在向你隐藏机器。一次 Python for 循环迭代的成本——PyObject_Add、引用计数递增、PyLong 装箱、字节码分发——在这台机器上每个元素大约 5 纳秒。这个数字高于 L3 缓存未命中的成本。所以当你在 Python 列表中迭代时，缓存层次结构对你来说是不可见的：你在每一步的解释器上花费了如此长的时间，以至于下一个字节是在 L1 中还是必须来自 RAM 都成了四舍五入的误差。

这就是 Python 中机器模型缺失的部分。层次结构仍然存在；只是瓶颈转移了。要看到机器，你必须查看解释器分发不占主导地位的地方。两个这样的地方，都可以在你的笔记本电脑上测量到：

1. 三种方式对一百万个 int64 求和。 code/measurement/cache_cliffs.py 将 N 从 1 万遍历到 1 亿，并对以下操作计时：对 Python 列表进行 sum(lst)，对连续的 numpy 数组进行 arr.sum()，以及对 arr[idx].sum() 其中 idx 是一个被打乱顺序的排列。在这台机器上：

N	Python 列表	numpy 顺序	numpy 收集	收集/顺序
10,000	4.85 ns	0.54 ns	1.47 ns	2.7×
100,000	4.60 ns	0.18 ns	2.88 ns	16.4×
1,000,000	4.60 ns	0.21 ns	3.51 ns	17.0×
10,000,000	4.62 ns	0.19 ns	10.33 ns	53.7×
100,000,000	4.60 ns	0.16 ns	11.80 ns	72.2×

阅读这些列。Python 列表在五个数量级上平坦地保持在约 4.6 纳秒/元素。从解释器内部看，缓存层次结构不存在。numpy 顺序列快 25-30 倍，揭示了带宽——内部循环是 C 语言，字节是类型化的，预取器工作正常。numpy 收集列是对相同数据以打乱顺序进行访问；一旦工作集离开 L1（在 1 万到 10 万之间），每个元素的成本就会攀升，到 1 亿时，与顺序访问的差距达到了 72 倍。这个比率就是这台机器上测量到的 L1 到 RAM 的成本差距。

2. 引发一次异常 vs 一百万次异常。 code/measurement/try_except.py 在命中率从 0.0001% 到 99.9999% 的范围内，比较了 try/except ZeroDivisionError 与显式的 if value != 0 检查。在 50/50 的情况下，try/except 形式慢 4 倍；在 99.9999%（几乎不引发异常）的情况下，try/except 形式比 if 还快。区别在于 CPU 的分支预测器：高频率下的跳转分支基本上是免费的；而一个预测错误的分支成本约为 10-20 个周期。教训不是“使用 try/except”或“使用 if”——而是常数因子是依赖于比率的，即使是 Python 也继承了这一点。

3. 常数因子会泄露出来。 code/measurement/string_methods.py 针对相同的输出，比较了 %-格式化、f-strings 和 .format。在这台机器上，%-格式化比 f-strings 快约 20%，而 f-strings 比 .format 快约 5%。这些在一次性日志行中都不重要。但在紧凑循环中，它们都很重要。“现代惯用”的选择并不自动是廉价的选择。

本章要求你做什么

关于现代 CPU 的主要事实是，算术基本上是免费的；成本在于将数据送到算术单元。一个尊重这一点的程序是快速的。一个忽视这一点的程序，与一个做相同工作、相同加法次数、但布局符合缓存喜好的程序相比，可能会慢一百倍。

在 Python 中，这个事实披着一层伪装：解释器如此之慢，以至于机器看起来没有悬崖。一旦你离开纯 Python，伪装就会脱落——而本书教授的内容几乎都涉及离开纯 Python，转向类型化的连续列，在那里，悬崖就在它一直存在的地方。

这也是为什么仅凭“复杂度类”会产生误导。一个命中缓存很好的 O(N log N) 算法，可以胜过将读取分散到 RAM 各处的“更快”的 O(N) 算法。大 O 描述了成本随 N 增长的方式；而布局描述了被乘进去的常数因子。在本书所针对的规模下，常数因子往往胜出。

练习

这些练习是校准。在你的机器上运行它们并记下数字——本书的其余部分会引用它们。

1. 查找你的缓存大小。 在 Linux 上，lscpu | grep -i cache 列出每核心的 L1d、L1i、L2、L3。（在 macOS 上：sysctl -a | grep cache。）把它们写下来。这些是 §27 中会约束你的预算。
2. 运行缓存悬崖示例。 uv run code/measurement/cache_cliffs.py。读取输出。注意 numpy 收集列开始攀升的大小——那是你溢出 L1 的地方。注意它再次攀升的地方——L2、L3。
3. 确认解释器的掩蔽作用。 修改示例，使其在现有测量之外，在每个大小步骤同时打印 arr.tolist() 的总和。确认 Python 列表的成本仍然是平坦的——即使数据相同，悬崖也没有出现。
4. 运行 try/except 示例。 uv run code/measurement/try_except.py。注意交叉点：在什么命中率下，try/except 变得比 if 更快？在大多数机器上，它高于 99%。
5. 运行字符串格式化示例。 uv run code/measurement/string_methods.py。注意在你的机器上的排名。这个顺序可能随 CPython 版本而改变——请实际测量，不要死记硬背。
6. 一个指针链表。 使用 class Node: __slots__ = ("value", "next") 构建一个包含 1,000,000 个节点的链，然后通过从头部跟随 .next 遍历来对 value 求和。将其与对相同长度的 numpy int64 数组的相同求和进行比较。你看到的比率大致是在 Python 中一层间接寻址的 L1 到 RAM 的比率——请注意，当对象嵌套更深时，这个比率会复合增长。
7. （挑战） 将你的 lscpu 输出与你的基准测试关联起来。 使用练习 1 中的缓存大小和练习 2 中的计时，识别收集列中的每一步正在离开哪一级缓存。这些转换并不总是清晰的——标注出它们存在噪声的地方。

[!NOTE]
本章中的数字是在作者机器上测量的。Python 列表平坦、numpy 阶梯状、收集/顺序比率扩大的形态在不同的硬件上是稳健的。确切的比率会随 CPU 代次而变化：较旧或较小的芯片（Raspberry Pi 4、2012 时代的 Intel）显示跨 L1/L2/L3 的梯度阶梯，而现代桌面芯片通常在 L3 到 RAM 的边界处显示一个大悬崖。在你自己的机器上测量；重现形态，而不是具体数字。

这些练习的参考答案注释见 01_the_machine_model_solutions.md。

接下来是什么

你在练习 1 中记下的缓存大小和在练习 2 中找到的悬崖是整个书背后的常数。§2 — 数字及其如何适配 将采取下一步：每个数据单元有多大，以及一个缓存行中能容纳多少个？

2 — 数字及其如何适配

一个缓存行是 64 字节。这是 CPU 一次加载的内存单元。你与数据所做的一切，部分程度上都是关于 64 字节中能容纳多少东西的问题。

一个 int 的实际成本

你上周写了 x = 1，问题就结束了。内存中存放的是一个 PyLong 对象：一个头、一个引用计数、一个长度，以及一个或多个保存值的 32 位“数字”部分。即使是 0，最小大小也是 28 字节。当值增长超过一个数字时，对象每增加一个数字就增长 4 字节。在这台机器上，来自 code/measurement/number_footprint.py 的结果：

int 0                          28 bytes
int 1                          28 bytes
int 256 (最后一个被驻留的)     28 bytes
int 257                        28 bytes
int 1_000                      28 bytes
int 2**31                      32 bytes
int 2**63                      36 bytes
int 2**127                     44 bytes
float 0.0                      24 bytes
float 3.14                     24 bytes
float 1e300                    24 bytes

一个 PyFloat 是 24 字节，固定大小。一个 PyLong 至少 28 字节，并且随数值大小增长。一个 bool 也是一个 PyLong。一个 complex 是 32 字节。在每种情况下，仅仅是头部就比数值本身还大。

这是本章问题的第一部分。选择能容纳你值范围的最窄类型——这种定义了缓存行是容纳 8 个东西还是 64 个东西的规范——在纯 Python 中不存在。没有 uint8。没有 int32。每个 Python int 都是同样昂贵的对象，无论它保存的是值 0 还是 2**63。你不能用范围来换取缓存行，因为你不能选择范围。

[!NOTE]
CPython 将 [-5, 256] 范围内的小整数作为单例缓存（小整数缓存）。一个包含零的列表并不会分配一百万个 PyLong(0) 对象——它分配一百万个指针，全都指向同一个对象。一旦值超出这个范围，每个值都是一个全新的分配。用 id(0) == id(0)（为真）与 id(257) == id(257)（有时为真，有时为假，取决于解析器在同一编译单元中对字面常量的缓存——但永远不可靠）来确认这一点。将小整数缓存视为你不能依赖的 CPython 实现细节。CPython 核心开发者 Terry Jan Reedy 确认，3.15.0b1 及更新版本将此上限从 256 提高到了 1024——这个边界在本书编写过程中移动了。持久的论点是机制本身，而不是数字。

numpy 还给你什么

numpy 让宽度预算重新存在。np.int8 是一个字节，范围 -128 到 127。np.int16 是两个字节，np.int32 是四个字节，np.int64 是八个字节。np.float32 是四个字节（约 7 位十进制数字精度）；np.float64 是八个字节（约 15 位）。有符号/无符号和整数/浮点变体可以自由组合。

一个 np.zeros(N, dtype=np.uint8) 是 N 个字节——平坦、连续、没有每个元素的头部。一个缓存行可以容纳 64 个它们。一个 np.zeros(N, dtype=np.int64) 是 8N 个字节；一个缓存行可以容纳 8 个。如果你的循环每缓存行访问一个元素，那么 int64 版本的内存加载次数是 uint8 版本的 8 倍。宽度预算回来了。

同样的示例，数据列讲述了 N=1,000,000 时的故事：

布局	数据大小	求和 (ms)
大整数的 Python 列表	38.25 MB	2.56
浮点数的 Python 列表	38.38 MB	4.27
numpy int8	0.95 MB	0.28
numpy int16	1.91 MB	0.34
numpy int32	3.81 MB	0.45
numpy int64	7.63 MB	0.42
numpy float32	3.81 MB	0.22
numpy float64	7.63 MB	0.36

在此规模下，Python 列表与 numpy 的比率：列表相比 numpy int8 多 40 倍的字节，相比 int16 多 20 倍，相比 int32 多 10 倍，相比 int64 多 5 倍。选择能容纳你值范围的最窄 numpy 宽度，在列表到 numpy 的基础上，还可以给你带来高达 8 倍的额外缩减。求和时间从毫秒下降到零点几毫秒——两个数量级。

选择能容纳你值范围的最窄类型，并写下原因。一副 52 张牌的花色需要 4 个值，点数需要 13 个，位置可能需要 8 个——所有这些都可以放在 np.uint8 中。一个生物的 pos 需要大约十公里的网格，分辨率到厘米级别；这可以放在 np.float32 中。一年模拟中微秒级的时间戳需要大约 3×10¹³，这装不进 np.uint32（4×10⁹），但可以舒适地放在 np.uint64 中。做出选择，并把选择写下来。

浮点数不是实数

它们看起来像实数，但并不是。float32 只有大约 40 亿个值；float64 只有大约 18 千万亿个值；这是有限的。操作有边缘情况：1.0 / 0.0 = inf，0.0 / 0.0 = nan，并且 nan != nan —— 是的，nan 的相等性是被故意破坏的，因为没有合理的答案。但是 == 对于普通浮点数也不可靠：0.1 + 0.2 == 0.3 是 False，因为 0.1 和 0.2 无法在二进制中精确表示，并且舍入误差刚好超过了 0.3。这就是为什么 math.isclose(a, b, rel_tol=1e-9, abs_tol=0.0) 存在的原因——这是标准库承认 == 是用于浮点数的错误工具，并且比较它们需要一个你特意选择的容差。两个几乎相等的浮点数相减会失去它们的大部分精度（这是灾难性抵消）。将一个很小的浮点数加到一个很大的浮点数上会悄悄地丢弃那个很小的浮点数（这是吸收）。如果你知道这些的存在，它们都不是问题；如果你假设浮点数就是数学，那么它们全都是问题。

code/measurement/sums.py 使用六种求和算法（sum、math.fsum、Kahan、Neumaier、pairwise、decimal 参考），在五个病态数据集（随机平衡、大数加许多小数、交替符号、微小增量以及包含 NaN 的数组）上演示了后果。运行它；阅读其中的差异。相同的输入数据以不同的顺序求和会得到不同的答案，而“天真”的答案有时会偏差几个数量级。解决方法不是“使用 float64 而不是 float32”——而是选择一种能感知数据形状的求和算法。对于无法限定输入的单次求和，math.fsum 和 Neumaier 通常是正确的默认选择。

本书大部分内容使用 np.uint8、np.uint16、np.uint32、np.float32 和用于时间的 np.uint64。int* 和 float64 仅在范围或精度真正需要时才出现。选择在每个列声明时都有记录。

练习

1. 每个值的成本。 打印 sys.getsizeof(0)、sys.getsizeof(2**31)、sys.getsizeof(2**127)、sys.getsizeof(0.0)、sys.getsizeof(True)。确认即使是一个 bool 也花费 28 字节（bool 是 int 的子类）。然后打印 np.array([0, 2**31, 0], dtype=np.int64).nbytes。三个 int64 总共 24 字节，没有头部，没有每个值的指针。
2. 缓存行填充。 对于每个 numpy dtype——int8、int16、int32、int64、float32、float64——计算一个 64 字节缓存行中可以容纳多少个。一个包含 16 个元素的 np.array(_, dtype=np.int32) 恰好是一行；一个包含 8 个元素的 np.array(_, dtype=np.float64) 恰好是一行。
3. 宽度与速度。 对 np.ones(100_000_000, dtype=np.int8) 求和，然后对 np.ones(100_000_000, dtype=np.int64) 求和。时间的比率应该小于字节的比率（8 倍），因为计算不是瓶颈——内存带宽才是。还要注意 int8 求和会溢出；这提示了为什么本书在选择宽度时要考虑最大值。
4. 浮点怪异。 计算 0.0 / 0.0、1.0 / 0.0、(-1.0) ** 0.5、math.sqrt(-1.0)。打印它们。然后执行 nan = float("nan"); assert nan != nan —— 确认它不会引发异常。
5. == 是错误的工具。 打印 0.1 + 0.2 == 0.3。观察到 False。打印 0.1 + 0.2 来查看舍入误差：0.30000000000000004。然后使用 math.isclose(0.1 + 0.2, 0.3) 并观察到 True。阅读 math.isclose 文档 —— 注意默认的 rel_tol=1e-9 是一个选择，当问题需要更紧或更松的容差时，你应该显式地进行选择。标准库提供 isclose 是因为语言设计者知道 == 在这里不可靠；依靠它。
6. 灾难性抵消。 计算 np.float32(1e10) - (np.float32(1e10) - np.float32(1.0))。结果应该是 1.0；在 float32 上通常不是。用 np.float64 重复，观察到它更接近（但并不总是精确地等于 1.0）。
7. 运行求和示例。 uv run code/measurement/sums.py。阅读五个数据集上不同算法之间的差异。注意哪个数据集的差异最大。这个数据集决定了你在生产中应该选用哪个求和例程。
8. 选择一个宽度。 对于以下每一列，写下你会选择的 dtype 以及原因：一年模拟中，以 30 Hz 频率运行的生物滴答年龄；纸牌的花色；4K 屏幕的像素数；拥有最多 1 亿用户的系统中的用户 ID；16 位 PCM 中的音频样本值。
9. （挑战） 浮点数的 eps。 np.finfo(np.float32).eps 是满足 1.0 + x != 1.0 的最小 x。计算该值，然后计算 np.float32(1.0) + np.float32(0.5) * np.finfo(np.float32).eps —— 结果是 1.0 还是 1.0 + eps/2？这对于一次将一个小的数字加到一个大的运行总计上意味着什么？

接下来是什么

§3 — Vec 是一个表 将采取下一步：既然你知道元素有多大，np.array 对它们做了什么，以及本书的其余部分期望它们呈现什么形状？