使用 numpy 函数时 C 连续数组和 Fortran 连续数组之间的性能差异

Question

我正在研究一本比较 C 连续数组和 Fortran 连续数组性能的书中的示例，其中我观察到，在使用 np.sum(axis 时，Fortran 连续数组在行操作方面比 C 连续数组表现更好=1) 即。与预期相反。当使用 np.cumsum(axis=1) 时，C 连续数组的性能比理论上预期的更好。可能是什么原因？

Jupyter Notebook 代码：

import numpy as np
arr_c=np.ones((1000,1000),order='C')
arr_f=np.ones((1000,1000),order='F')

使用 np.sum(axis=1) 时观察到的结果与理论上的预期相反。

%timeit arr_c.sum(axis=1)

每个循环 605 µs ± 40.8 µs（7 次运行的平均值 ± 标准偏差，每次 1,000 个循环）

%timeit arr_f.sum(axis=1)

每个循环 398 µs ± 25.3 µs（7 次运行的平均值 ± 标准偏差，每次 1,000 个循环）

但是使用 np.cumsum(axis=1) 时结果符合预期。

%timeit arr_c.cumsum(axis=1)

每个循环 4.01 ms ± 83 µs（7 次运行的平均值 ± 标准差，每次 100 个循环）

%timeit arr_f.cumsum(axis=1)

每个循环 15.6 ms ± 103 µs（7 次运行的平均值 ± 标准偏差，每次 100 个循环）

Answer 1

我不知道你指的是哪本书。但我认为要么这本书是错误的，要么是你误读了它（或者它是在特定的背景下，并且谈论的是我所想到的其他考虑因素）。但人们在 HPC 课程中通常被教导的是，当算法的内部部分迭代列时，C 顺序更好，而当内部部分迭代行时，C 顺序更好。

为什么订单会改变业绩

首先（我想这就是你的书所说的）理解为什么顺序很重要很重要。这是因为高速缓存。如果您的算法按照数据存储的顺序访问数据，那么大多数时候，数据已经在高速缓存中。如果没有，那么您将不得不更频繁地从内存中检索新块，这会产生成本。

因此，如果内存包含 M₀=0 M₁=1 M2=2 M₃=3 M₄=4 M₅=5 M₆=6 M₇=7 M₈=8 M₉=9 M₁₀=10 M₁₁=11 M₁2=12 M₁₃=13 M₁₄= 14 M₁₅=15，则算法

s=0
for i in range(4):
    for j in range(4):
        s+=Mᵢₓ₄₊ⱼ

比

更有效率

s=0
for i in range(4):
    for j in range(4):
        s+=Mⱼₓ₄₊ᵢ

因为第一个按顺序访问 M₀、M2、...、M₁₅，所以当第二个访问 M₀、M₄、M₈、M₁2、M₁、M₅、...

如果你的内存缓存只容纳 4 M 位置，那么第一个版本将只需要重新加载一个块 4 次，而第二个版本将不得不每 16 次获取一个新块。

当然，这是一个理论上的例子。缓存比那个大。但这就是原因。

现在，如果我们假设这 16 个内存位置是矩阵

M[row, colum]

的 16 个数据，如果您只对矩阵

M[row, colum]

的一列（“只有一列”在这里很重要）求和，比如说第 1 列，

def sumColumn(col):
    s=0
    for row in range(4):
        s+=M[row, col]
sumColumn(1)

将访问内存 M₄、M₅、M₆、M₇ 是 Fortran 顺序的矩阵（因此

M[i,j]

位于内存 Mᵢ₊₄ⱼ）

但是会访问内存 M₁,M₅,M₉,M₁₃ 矩阵是 C 阶的（所以

M[i,j]

位于内存 M₄ᵢ₊ⱼ）

为什么它不能直接应用于整个矩阵运算

如果实现

sum(axis=1)

相当于

result=np.zeros((4,))
for column in range(4):
    result[column] = sumColumn(column)

也就是说，如果我展开它

result=np.zeros((4,))
for column in range(4):
    for row in range(4):
        result[column] += M[row, column]

然后，这是同样的事情的4倍。因此，在 Fortran 顺序中高效的算法是 4 倍，在 C 顺序中效率较低

但没有说这就是实现

也可以是

result=np.zeros((4,))
for row in range(4):
    for column in range(4):
        result[column] += M[row, column]

然后你会得到一个在 C 顺序中比在 Fortran 顺序中更有效（缓存方面）的算法。

所以，重点是，它取决于实现。因此，当数据按 C 顺序排列时，实现会更好（因为它们首先迭代行，然后迭代列，即按内存顺序数据按 C 顺序排列）。当数据按 Fortran 顺序排列时，有些会更好（因为它们迭代第一列，第二行，如果数据按 Fortran 顺序，则按内存顺序）。 您可以打赌，numpy 在可能的情况下会为每个上下文使用最佳实现。

tl；博士

通常当人们谈论与订单相关的性能时，这是因为缓存。在缓存方面，如果数据采用 Fortran 顺序（并且该列的所有数据在内存中相邻），则对单个列求和会更快。

但这不适用于对所有列求和，就像

.sum(axis=1)

或

np.cumsum(axis=1)

那样，因为您不知道实现是否迭代第一行第二列。