Python 代码对 CPU 缓存敏感吗？(2024)

Is Python Code Sensitive to CPU Caching? (2024)

Source | HN Comments

文章通过实验验证了Python代码对CPU缓存的敏感性。实验比较了Python中顺序和随机访问列表元素的性能，结果表明随机访问明显慢于顺序访问，尤其是在数据量超过CPU缓存大小时。即使在CPython这样的解释型环境中，缓存效应也对性能有显著影响。文章还对比了使用Numpy的实现，Numpy由于其扁平数组的特性，性能优势明显，但两者都受到缓存压力的影响。结论是，虽然Python代码的CPU缓存敏感性不如C++或Rust，但在某些情况下，优化缓存访问可以提高性能。

Lukas Atkinson

Python 代码对 CPU 缓存敏感吗？

2024-07-07 12 分钟，作者：Lukas Atkinson Python (11) Algorithms (3)

免责声明：结果可能因不同的软件和硬件而异。用于这些测试的软件是 CPython 3.12。CPU 使用 x86-64 (amd64) 架构，Zen 2 微架构。由于将核心分组到单独的“核心复合体”中，部分共享它们的缓存，因此这一代 CPU 具有相当复杂的缓存层次结构。每个核心应该看到高达 32KB 的 L1，512KB 的 L2，16MB 的 L3。

背景

程序将数据存储在内存 (RAM) 中，但这很慢。CPU 缓存更快，但小得多。CPU 必须决定将 RAM 的哪些部分加载到缓存中。当然，显式访问的内存地址将被加载到缓存中。但是，加载数据的行为相对较慢，因此 CPU 将尝试预加载相关数据。

例如，我们可以期望 CPU 检测线性数组访问模式，并自动预加载数组的下一个块。因此，foreach 风格的循环遍历数组，其中所有相关数据都直接在数组内部，可以非常有利于缓存，而随机访问是无法预测的。

在实践中，许多数组包含指针。我们必须解引用指向不同内存位置的指针才能获得实际数据。也许指向的位置已经在缓存中，也许没有，我们将不得不等待——实际上也是一种随机访问。

在 Java (OpenJDK) 和 Python (CPython) 中，所有普通对象实际上都表示为指向更复杂数据结构的指针。用 C 表示法，数组不会包含 PyObject 值，而是 PyObject* 指针。

因此，显然，Python 数据结构不会像 C++ 或 Rust 中的数据结构那样有利于缓存。

但是，与本地编译的语言相比，Python 已经有大量的解释器开销，所以这可能并不重要？

以我的经验，解释器开销往往在 2× – 100× 范围内，通常至少 10×，如果可以进行有意义的编译器优化，则情况会更糟。
但是，访问主内存与访问 L1 缓存数据的典型成本值往往也在 100× 范围内。

所有这些都非常粗略，但表明解释器开销不会淹没缓存效应。

设计实验

我们的工作假设是：在 Python 程序中可以检测到缓存效应。

这是无法测试的，所以让我们根据上面的数组迭代示例来改进它。我们可以尝试观察到的是，当 indices = shuffled(range(len(values)))（“随机”访问）时，以下程序应该比按顺序访问元素 (indices = list(range(len(values)))) 花费更长的时间：

sum(values[i] for i in indices)

但是这里有很多不同的对象在起作用：

indices 是一个包含指向整数对象的指针的数组
i 实际上是指向这样一个整数对象的指针
values 是一个包含指向对象的指针的数组
values[i] 实际上是这样一个指针

用 C 表示法来说，这意味着我们有四种不同的内存位置：

indices[…] / i，包含一个指针
*i，包含实际的索引
values[*i]，包含一个指针
*values[*i]，包含实际的值

如果我们想正确地设计实验，我们必须考虑所有这些内存位置的缓存效应。

indices 数组可能没有问题，因为它将按顺序迭代。
但是，每个索引 *i 都需要一次内存访问。为了减少缓存效应的影响，如果这些值在内存中按顺序排列，那就太好了。Python 不允许我们控制这一点，但在实践中，对象很可能是一个接一个地分配的。因此，我们希望按照它们将被引用的顺序创建这些整数对象。这意味着我们不能在运行基准测试的 Python 进程中对索引进行洗牌，但可以读入已经洗牌的测试数据。
values 数组没有问题，因为它是我们想要测试的主要缓存效应。
*values[*i] 元素可能重要也可能不重要。要么 CPU 能够理解 values 实际上是指向值的指针，并且可以预加载指向的值。或者，缓存效应可能意味着如果这些值按照它们在 values 数组中被引用的相同顺序排列，则示例运行得更快。

我不确定如何测试 values 顺序的影响，所以让我们坚持使用相同的技巧，即使用分配顺序来增加潜在的缓存友好型数据布局的机会。

我们可以生成如下格式的测试数据：

<size>,<iterations>,<expected sum>
<indices>,...
<values>,...

例如，以下将描述对 values 的按顺序访问（索引的顺序很重要，值的顺序不应该）：

4,1,10
0,1,2,3,4
3,2,4,0,1

我不想费心处理字符串和数字解析，所以让我们使用 Python 的 struct 和 array 模块将测试数据打包成二进制表示形式。

这是我们将要进行基准测试的主要程序：

import sys, struct, array
def parse_array(f, fmt, n):
  arr = array.array(fmt)
  arr.fromfile(f, n)
  return arr.tolist()
# parse the test case
header_layout = struct.Struct("=4sLLQ")
magic, size, iterations, expected_sum = \
  header_layout.unpack(sys.stdin.buffer.read(header_layout.size))
assert magic == b"cach", f"wrong magic number {magic}"
indices = parse_array(sys.stdin.buffer, "L", size)
values = parse_array(sys.stdin.buffer, "L", size)
# run the test case
for _ in range(iterations):
  s = sum(values[i] for i in indices)
  assert s == expected_sum

这是一个生成测试用例的程序：

import sys, struct, array, random, click
@click.command()
@click.option("--size", type=int, required=True)
@click.option("--iterations", type=int, required=True)
@click.option("--shuffle/--no-shuffle", required=True)
@click.option("--seed", type=int, required=True)
def cli(size: int, iterations: int, shuffle: bool, seed: int):
  rng = random.Random(seed)
  values = list(range(size))
  rng.shuffle(values) # should not affect benchmarks, but best randomize
  indices = list(range(size))
  if shuffle:
    rng.shuffle(indices)
  header_layout = struct.Struct("=4sLLQ")
  sys.stdout.buffer.write(header_layout.pack(b"cach", size, iterations, sum(values)))
  array.array("L", indices).tofile(sys.stdout.buffer)
  array.array("L", values).tofile(sys.stdout.buffer)
if __name__ == "__main__":
  cli()

顺便说一句，为什么我们不直接使用 array 而不是 Python list 进行测试呢？毕竟，一个数组可以让我们控制内存布局？

对于 values，我们想使用 list，因为我们对典型 Python 数据结构的缓存效应感兴趣。
对于 indices，因为访问 indices[…] 元素仍然必须创建一个 PyObject*。最好在运行实际测试之前消除所有这些分配。

对于特定的示例大小，实际上将使用多少内存？

虽然上面的布局将整数编码为 32 位或 64 位整数（4 或 8 字节），但内存中的表示将是一个 PyObject*。
指针需要一个指针（8 字节），
在其小整数模式下，PyObject 数据还需要 28 字节（3.5 个指针的值）（通过 sys.getsizeof() 计算）。
但是，对齐考虑可能会将其向上舍入为 32 字节（4 个指针的值）。
总共有 5 个指针的值（40 字节）用于 values 中的每个元素，加上 indices 相同的量。
为了观察有意义的结果，我们的问题规模应该比可用的缓存大小大得多。对于 16MB 缓存，这意味着 values 应该包含至少 420000 个条目，如果我们也考虑来自 indices 的缓存压力，则条目数量减半。

这使我们能够制定一些期望：

对于低于 200000 左右的问题规模，我们期望线性访问和随机访问的工作方式类似。
假设：对于高于 420000 的问题规模，我们期望线性数组访问比随机访问快得多。

我们可以使用 hyperfine 工具 (v1.18) 来运行单个基准测试。它支持参数化的基准测试。

所有实验都将使用以下形式，尽管我们将更改 --iterations 和 size 参数。

hyperfine \
 --setup 'python generate_data.py --seed 1234 --iterations {iterations} --size {size} --{shuffle} >example_{size}_{shuffle}.bin' \
 --command-name 'size={size} iters={iterations} {shuffle}' \
 -L size 100,1000,10000,100000 \
 -L iterations 5 \
 -L shuffle shuffle,no-shuffle \
 'python run_benchmark.py <example_{size}_{shuffle}.bin'

结果

我们现在可以进行几个实验来研究缓存的影响。

小数据集

我们上面的分析表明，低于 200000 左右的问题规模不应受到缓存的影响。让我们让 hyperfine 比较 for size in {50_000, 100_000, 200_000} 的洗牌访问。请注意，我们还在调整迭代次数，以便数组访问的总数保持恒定在 1000 万次，这使我们还可以比较不同大小的结果。

size=50_000 的结果 ``` Benchmark 1: size=50000 iters=200 shuffle (iterations = 200) Time (mean ± σ): 462.0 ms ± 13.4 ms [User: 456.7 ms, System: 5.2 ms] Range (min … max): 439.5 ms … 477.5 ms 10 runs Benchmark 2: size=50000 iters=200 no-shuffle (iterations = 200) Time (mean ± σ): 374.1 ms ± 17.3 ms [User: 369.2 ms, System: 4.8 ms] Range (min … max): 350.0 ms … 394.3 ms 10 runs Summary size=50000 iters=200 no-shuffle (iterations = 200) ran 1.23 ± 0.07 times faster than size=50000 iters=200 shuffle (iterations = 200)

size=100_000 的结果: ```
Benchmark 1: size=100000 iters=100 shuffle (iterations = 100)
 Time (mean ± σ):   479.6 ms ± 19.6 ms  [User: 470.2 ms, System: 9.3 ms]
 Range (min … max):  453.7 ms … 519.8 ms  10 runs
Benchmark 2: size=100000 iters=100 no-shuffle (iterations = 100)
 Time (mean ± σ):   384.4 ms ± 14.0 ms  [User: 376.0 ms, System: 8.3 ms]
 Range (min … max):  361.4 ms … 405.8 ms  10 runs
Summary
 size=100000 iters=100 no-shuffle (iterations = 100) ran
  1.25 ± 0.07 times faster than size=100000 iters=100 shuffle (iterations = 100)

size=200_000 的结果: ``` Benchmark 1: size=200000 iters=50 shuffle (iterations = 50) Time (mean ± σ): 567.8 ms ± 35.4 ms [User: 557.7 ms, System: 9.9 ms] Range (min … max): 501.0 ms … 634.4 ms 10 runs Benchmark 2: size=200000 iters=50 no-shuffle (iterations = 50) Time (mean ± σ): 385.2 ms ± 13.8 ms [User: 377.3 ms, System: 7.8 ms] Range (min … max): 371.4 ms … 407.8 ms 10 runs Summary size=200000 iters=50 no-shuffle (iterations = 50) ran 1.47 ± 0.11 times faster than size=200000 iters=50 shuffle (iterations = 50)


解释：

对于所有测试的问题规模，我们看到随机化 (`shuffle`) 访问明显慢于线性数组访问 (`no-shuffle`)。对于大小 `50_000` 和 `100_000`，我们看到大约 1.24 的因子。但是对于大小 `200_000`，我们已经高达 `1.47` 的因子。

我们可以重新格式化数据，以比较不同问题规模中 `shuffle` 和 `no-shuffle` 因子的平均运行时间：

size| no-shuffle| shuffle| 相对减速
---|---|---|---
`50_000`| 374.1 ms ± 17.3 ms| 462.0 ms ± 13.4 ms| 1.23 ± 0.07
`100_000`| 384.4 ms ± 14.0 ms| 479.6 ms ± 19.6 ms| 1.25 ± 0.07
`200_000`| 385.2 ms ± 13.8 ms| 567.8 ms ± 35.4 ms| 1.47 ± 0.11
我们可以看到 `no-shuffle` 线性模式（左列）在不同问题规模中保持恒定的速度。所有这些时间都在彼此的误差范围内。

但是对于 `shuffle` 模式，我们看到了差异。虽然两个较小的问题规模的速度在彼此的误差范围内，但 `size = 200_000` 运行明显较慢。

这与我们的期望大致相符。

  * 我们看到线性数组访问在不同问题规模中提供了非常一致的性能。
  * 我们看到随机访问始终较慢，但开销并不算太糟（在较小的问题规模下仅约为 `1.24` 的因子）。
  * 当我们接近问题不再适合缓存的区域时，随机访问的性能开始下降。

### 大数据集

接下来，让我们测量当我们进入问题规模无法放入缓存的区域时的性能。为了保持一个好的 2 的幂序列，`iterations` 稍微增加了一些，保持了索引操作的恒定量在 1280 万次。

  * `size= 200_000 iters=64`（大小与“小数据集”轮次中最大的实验匹配）
  * `size= 400_000 iters=32`
  * `size= 800_000 iters=16`
  * `size=1600_000 iters= 8`

size=200_000 的结果: ```
Benchmark 1: size=200000 iters=64 shuffle (iterations = 64)
 Time (mean ± σ):   693.9 ms ± 40.1 ms  [User: 684.6 ms, System: 9.1 ms]
 Range (min … max):  641.0 ms … 751.8 ms  10 runs
Benchmark 2: size=200000 iters=64 no-shuffle (iterations = 64)
 Time (mean ± σ):   496.8 ms ± 10.3 ms  [User: 483.1 ms, System: 13.6 ms]
 Range (min … max):  482.2 ms … 515.4 ms  10 runs
Summary
 size=200000 iters=64 no-shuffle (iterations = 64) ran
  1.40 ± 0.09 times faster than size=200000 iters=64 shuffle (iterations = 64)

size=400_000 的结果: ``` Benchmark 1: size=400000 iters=32 shuffle (iterations = 32) Time (mean ± σ): 1.293 s ± 0.071 s [User: 1.275 s, System: 0.018 s] Range (min … max): 1.217 s … 1.452 s 10 runs Benchmark 2: size=400000 iters=32 no-shuffle (iterations = 32) Time (mean ± σ): 515.2 ms ± 16.2 ms [User: 497.3 ms, System: 17.7 ms] Range (min … max): 485.7 ms … 541.0 ms 10 runs Summary size=400000 iters=32 no-shuffle (iterations = 32) ran 2.51 ± 0.16 times faster than size=400000 iters=32 shuffle (iterations = 32)

size=800_000 的结果: ```
Benchmark 1: size=800000 iters=16 shuffle (iterations = 16)
 Time (mean ± σ):   1.855 s ± 0.036 s  [User: 1.824 s, System: 0.030 s]
 Range (min … max):  1.805 s … 1.926 s  10 runs
Benchmark 2: size=800000 iters=16 no-shuffle (iterations = 16)
 Time (mean ± σ):   550.0 ms ± 11.8 ms  [User: 521.5 ms, System: 28.4 ms]
 Range (min … max):  532.4 ms … 563.1 ms  10 runs
Summary
 size=800000 iters=16 no-shuffle (iterations = 16) ran
  3.37 ± 0.10 times faster than size=800000 iters=16 shuffle (iterations = 16)

size=1600_000 的结果: ``` Benchmark 1: size=1600000 iters=8 shuffle (iterations = 8) Time (mean ± σ): 2.379 s ± 0.034 s [User: 2.327 s, System: 0.052 s] Range (min … max): 2.336 s … 2.428 s 10 runs Benchmark 2: size=1600000 iters=8 no-shuffle (iterations = 8) Time (mean ± σ): 628.4 ms ± 12.2 ms [User: 570.3 ms, System: 57.9 ms] Range (min … max): 606.3 ms … 647.2 ms 10 runs Summary size=1600000 iters=8 no-shuffle (iterations = 8) ran 3.79 ± 0.09 times faster than size=1600000 iters=8 shuffle (iterations = 8)


用于比较平均经过时间和随机访问的相对减速的表格：

size| no-shuffle| shuffle| 相对减速
---|---|---|---
`200_000`| 496.8 ms ± 10.3 ms| 693.9 ms ± 40.1 ms| 1.40 ± 0.09
`400_000`| 515.2 ms ± 16.2 ms| 1.293 s ± 0.071 s| 2.51 ± 0.16
`800_000`| 550.0 ms ± 11.8 ms| 1.855 s ± 0.036 s| 3.37 ± 0.10
`1600_000`| 628.4 ms ± 12.2 ms| 2.379 s ± 0.034 s| 3.79 ± 0.09
解释：

  * 对于线性访问（`no-shuffle` 模式），随着问题规模的增加，我们现在看到性能下降。部分原因是迭代次数较少，因此初始化开销（Python 解释器启动，解析输入数据）变得更加明显。
  * 对于随机访问（`shuffle` 模式），随着问题规模的增加，我们看到性能急剧下降。这些不能仅用初始化开销来解释。
  * 线性访问与随机访问对之间的相对减速随着问题规模的增加而增加。在 160 万个元素时（`values` 列表总共重约 60MB，加上 `indices` 中相同数量的数据），我们高达约 3.8 的相对减速。这意味着随机访问慢 280%，或者说线性访问只需要 26% 的时间。

由于线性访问和随机访问变体之间的数据集是等效的，这似乎证实了我们的实验假设，即线性访问明显更快，这反过来为我们的实际假设提供了证据，即缓存效应可以对 Python 代码产生重大影响。

## 额外环节：间接寻址的开销

纯 Python 的一个问题是 `PyObject*` 指针间接寻址，以及 `PyObject` 结构本身的开销。但是，Python 确实提供了规避此问题的方法。我们可以使用 `numpy` 模块来获得 C 风格的扁平数组，并在本机代码中执行索引和求和：

import sys, struct, numpy as np

parse the test case

header_layout = struct.Struct("=4sLLQ") magic, size, iterations, expected_sum =
header_layout.unpack(sys.stdin.buffer.read(header_layout.size)) assert magic == b"cach", f"wrong magic number {magic}" indices = np.fromfile(sys.stdin.buffer, dtype="L", count=size) values = np.fromfile(sys.stdin.buffer, dtype="L", count=size) assert sys.stdin.buffer.read() == b"" # EOF

run the test case

for _ in range(iterations): s = np.sum(values[indices], dtype=int) assert s == expected_sum


我们现在可以使用 Hyperfine 将基于 Numpy 的实现与固定问题规模的纯 Python 进行比较：

hyperfine
--setup 'python generate_data.py --seed 1234 --iterations {iterations} --size {size} --{shuffle} >example_{size}{shuffle}.bin'
--command-name 'size={size} iters={iterations} {shuffle} {implementation}'
-L size 1600000
-L iterations 8
-L shuffle shuffle,no-shuffle
-L implementation benchmark,benchmark_numpy
'python run{implementation}.py <example_{size}_{shuffle}.bin'

结果: ```
Benchmark 1: size=1600000 iters=8 shuffle benchmark (iterations = 8)
 Time (mean ± σ):   2.354 s ± 0.029 s  [User: 2.298 s, System: 0.055 s]
 Range (min … max):  2.315 s … 2.405 s  10 runs
Benchmark 2: size=1600000 iters=8 no-shuffle benchmark (iterations = 8)
 Time (mean ± σ):   618.1 ms ± 17.7 ms  [User: 567.3 ms, System: 50.6 ms]
 Range (min … max):  585.9 ms … 641.5 ms  10 runs
Benchmark 3: size=1600000 iters=8 shuffle benchmark_numpy (iterations = 8)
 Time (mean ± σ):   214.8 ms ± 17.5 ms  [User: 1782.5 ms, System: 19.9 ms]
 Range (min … max):  195.8 ms … 255.0 ms  14 runs
Benchmark 4: size=1600000 iters=8 no-shuffle benchmark_numpy (iterations = 8)
 Time (mean ± σ):   137.1 ms ± 11.0 ms  [User: 1726.8 ms, System: 18.6 ms]
 Range (min … max):  128.8 ms … 163.1 ms  18 runs
Summary
 size=1600000 iters=8 no-shuffle benchmark_numpy (iterations = 8) ran
  1.57 ± 0.18 times faster than size=1600000 iters=8 shuffle benchmark_numpy (iterations = 8)
  4.51 ± 0.38 times faster than size=1600000 iters=8 no-shuffle benchmark (iterations = 8)
  17.17 ± 1.39 times faster than size=1600000 iters=8 shuffle benchmark (iterations = 8)

看起来 Numpy 具有相当大的性能优势，这并不奇怪。但是，在缓存效应方面，这是一个苹果与橘子的比较。由于 Numpy 数组是密集打包的，没有指针间接寻址，也没有每个项目的对象开销，因此它们占用的内存更少。在这里，我们只需要每个项目 8 字节的 Numpy，而纯 Python 中每个项目大约需要 40 字节——相差 5 倍。

相反，我们可以运行一个具有相同内存使用量的实验，但使用不同的 iterations 来实现可比较的索引操作次数。这可以说不是一个有效的比较，但这是一个很好的说明。在这里，让我们以 2000 万次操作的目标量为目标，分为

Numpy 为 400 万个值，迭代 5 次
纯 Python 为 80 万个值，迭代 25 次

python generate_data.py --seed 1234 --size 800000 --iterations 25 --shuffle  >example_vanilla_shuffle.bin
python generate_data.py --seed 1234 --size 800000 --iterations 25 --no-shuffle >example_vanilla_no-shuffle.bin
python generate_data.py --seed 1234 --size 4000000 --iterations 5 --shuffle  >example_numpy_shuffle.bin
python generate_data.py --seed 1234 --size 4000000 --iterations 5 --no-shuffle >example_numpy_no-shuffle.bin
hyperfine \
  --command-name '{implementation} {shuffle}' \
  -L implementation vanilla,numpy \
  -L shuffle shuffle,no-shuffle \
  'python run_benchmark_{implementation}.py <example_{implementation}_{shuffle}.bin'

结果: ``` Benchmark 1: vanilla shuffle Time (mean ± σ): 2.864 s ± 0.016 s [User: 2.828 s, System: 0.035 s] Range (min … max): 2.832 s … 2.884 s 10 runs Benchmark 2: numpy shuffle Time (mean ± σ): 336.8 ms ± 14.9 ms [User: 1918.3 ms, System: 27.0 ms] Range (min … max): 319.3 ms … 369.8 ms 10 runs Benchmark 3: vanilla no-shuffle Time (mean ± σ): 791.2 ms ± 21.7 ms [User: 758.6 ms, System: 32.2 ms] Range (min … max): 758.3 ms … 822.7 ms 10 runs Benchmark 4: numpy no-shuffle Time (mean ± σ): 167.8 ms ± 9.0 ms [User: 1745.3 ms, System: 30.2 ms] Range (min … max): 152.7 ms … 187.6 ms 17 runs Summary numpy no-shuffle ran 2.01 ± 0.14 times faster than numpy shuffle 4.71 ± 0.28 times faster than vanilla no-shuffle 17.06 ± 0.92 times faster than vanilla shuffle


每种实现的成对比较表：

implementation| no-shuffle| shuffle| 相对减速
---|---|---|---
numpy| 167.8 ms ± 9.0 ms| 336.8 ms ± 14.9 ms| 2.01 ± 0.14
vanilla| 791.2 ms ± 21.7 ms| 2.864 s ± 0.016 s| 3.62 ± 0.10
现在，我们可以清楚地看到 Numpy 和纯 Python 实现都受到缓存压力的影响，缓存友好的版本分别快 2× 和 3.6×。纯 Python 版本遭受更大的减速可能表明更复杂的 `PyObject*` 布局对缓存更加不利，但我有一种预感，这可能不是全部，例如，因为这些测量还包括输入解析开销。未来的工作可能涉及使用像 Valgrind 的 `cachegrind` 这样的工具来更详细地了解这些程序如何与 CPU 缓存交互，或者可以使用 Numpy 数组进行两种实现，并且仅比较求和和索引是在 C 代码还是 Python 代码中发生。

## 结论

在这些实验中，我们证明了即使 Python 与本机代码相比可能很慢，但缓存效应确实对性能有可衡量的影响。我们使用了相当大的列表来比较顺序元素访问和随机访问。我们发现，根据列表的大小，随机访问慢了 23% 到 280% 不等。这是值得优化的重要开销，至少对于受 CPU 限制的 Python 代码而言。

但是，这种实际效果应该可以忽略不计，因为使用长度在 10⁴+ 范围内的列表的受 CPU 限制的 Python 代码应该相当少见。

## 进一步阅读

[Agner Fog 的优化手册](https://