Python、numpy 和缓存行

Question

我尝试在Python中使用numpy遵循

https://igoro.com/archive/gallery-of-processor-cache-effects/

。 虽然它不起作用，而且我不太明白为什么......

numpy

具有固定大小的数据类型，例如

np.int64

占用8个字节。 因此，对于 64 字节的缓存行，缓存中应保存 8 个数组值。

因此，在进行计时时，访问缓存行内的值时，我不应该看到所需时间的显着变化，因为需要相同数量的缓存行传输。

基于这个SO答案，我还尝试禁用垃圾收集，这没有改变任何东西。

# import gc
import time
import numpy as np

def update_kth_entries(arr, k):
    arr[k] = 0
    start = time.perf_counter_ns()
    for idx in range(0, len(arr), k):
        arr[idx] = 0
    end = time.perf_counter_ns()
    print(f"Updated every {k:4} th entry ({len(arr)//k:7} elements) in {(end - start)*1e-9:.5f}s")
    return arr

# gc.disable()
arr = np.arange(8*1024*1024, dtype=np.int64)
print(
    f"(Data) size of array: {arr.nbytes/1024/1024:.2f} MiB "
    f"(based on {arr.dtype})"
)

for k in np.power(2, np.arange(0,11)):
    update_kth_entries(arr, k)
# gc.enable()

这给出了类似的东西

(Data) size of array: 64.00 MiB (based on int64)
Updated every    1 th entry (8388608 elements) in 0.72061s
Updated every    2 th entry (4194304 elements) in 0.32783s
Updated every    4 th entry (2097152 elements) in 0.14810s
Updated every    8 th entry (1048576 elements) in 0.07622s
Updated every   16 th entry ( 524288 elements) in 0.04409s
Updated every   32 th entry ( 262144 elements) in 0.01891s
Updated every   64 th entry ( 131072 elements) in 0.00930s
Updated every  128 th entry (  65536 elements) in 0.00434s
Updated every  256 th entry (  32768 elements) in 0.00234s
Updated every  512 th entry (  16384 elements) in 0.00129s
Updated every 1024 th entry (   8192 elements) in 0.00057s

这是

lscpu -C

的输出

NAME ONE-SIZE ALL-SIZE WAYS TYPE        LEVEL  SETS PHY-LINE COHERENCY-SIZE
L1d       32K     384K    8 Data            1    64        1             64
L1i       32K     384K    8 Instruction     1    64        1             64
L2       256K       3M    4 Unified         2  1024        1             64
L3        16M      16M   16 Unified         3 16384        1             64

此时我对我所观察到的东西感到非常困惑。

• 一方面，我无法使用上面的代码看到缓存行。
• 另一方面，我可以使用类似在这个答案中和足够大的2D数组来展示某种CPU缓存效果。

我在 Mac 上的容器中进行了上述测试。 在我的 Mac 上进行的快速测试显示了相同的行为。

这种奇怪的行为是由于 python 解释器造成的吗？

我在这里缺少什么？

Answer 1

我对我所观察到的东西感到很困惑。

您主要观察解释器和 Numpy 的开销。 事实上，

arr[idx] = 0

被解释并调用

arr

对象的函数，该函数执行类型检查、引用计数，当然会创建一个内部 Numpy 生成器和许多其他昂贵的东西。 这些开销比 CPU 缓存的延迟要大得多（至少是 L1 和 L2，甚至可能是关于确切目标 CPU 的 L3）。

事实上，

0.00057s

所以更新 8192 条缓存线是相当巨大的：这意味着每次访问大约需要 70 ns！ RAM 的延迟通常与此类似，而 CPU 缓存的延迟通常不超过几十纳秒（对于 L3），而在运行频率 >= 2GHz 的现代 CPU 上，L1/L2 则不超过几纳秒。因此，观察到的开销至少比您想要观察的效果高一到两个数量级。 Numpy 函数（包括已知非常慢的直接索引）的开销通常为几微秒（至少数百纳秒）。

您可以通过执行矢量化操作来减轻这种开销。这就是高效使用 Numpy 的方法。更具体地说，您可以将循环替换为

arr[0:arr.size:k] = 0

。在我的 Intel Skylake (Xeon) CPU 上，此操作的开销约为 300-400 ns。这仍然远高于缓存行访问的开销，但足够小，足以在

k

不太大时看到缓存效果。请注意，在我的机器上访问

arr.size

已经需要 30-40 ns，因此最好将其移到定时部分之外（并将结果存储在临时变量中）。

以下是初步结果：

(Data) size of array: 64.00 MiB (based on int64)
Updated every    1 th entry (8388608 elements) in 0.56829s
Updated every    2 th entry (4194304 elements) in 0.28489s
Updated every    4 th entry (2097152 elements) in 0.14076s
Updated every    8 th entry (1048576 elements) in 0.07060s
Updated every   16 th entry ( 524288 elements) in 0.03604s
Updated every   32 th entry ( 262144 elements) in 0.01799s
Updated every   64 th entry ( 131072 elements) in 0.00923s
Updated every  128 th entry (  65536 elements) in 0.00476s
Updated every  256 th entry (  32768 elements) in 0.00278s
Updated every  512 th entry (  16384 elements) in 0.00136s
Updated every 1024 th entry (   8192 elements) in 0.00062s

这是矢量化操作的：

Updated every    1 th entry (8388608 elements) in 0.00308s
Updated every    2 th entry (4194304 elements) in 0.00466s
Updated every    4 th entry (2097152 elements) in 0.00518s
Updated every    8 th entry (1048576 elements) in 0.00515s
Updated every   16 th entry ( 524288 elements) in 0.00391s
Updated every   32 th entry ( 262144 elements) in 0.00242s
Updated every   64 th entry ( 131072 elements) in 0.00129s
Updated every  128 th entry (  65536 elements) in 0.00064s
Updated every  256 th entry (  32768 elements) in 0.00039s
Updated every  512 th entry (  16384 elements) in 0.00024s
Updated every 1024 th entry (   8192 elements) in 0.00011s

我们可以看到 CPython 和 Numpy 开销占用了超过 80% 的时间。新的计时更加准确（尽管并不完美，因为最后一行仍然有一些可见的开销——当然是 3~15%）。 CPython 不太适合这样的基准测试。您应该使用本机语言（例如 C、C++、Rust），或者至少使用 JIT/AOT 编译器，以避免解释器开销并避免 Numpy/Python 开销。 Cython（仅具有内存视图）和 Numba 可以帮助大大减少此类开销。后面的应该就够了。

例如，我们可以看到，以 1024 的步幅访问缓存行大约需要 13 ns/缓存行，这是现实的（类似于 L3 缓存的延迟，这在这里是有意义的）。