numpy数组上的剩余函数(%)运行时间远远长于手动余数计算

Question

在过去的几天里,我一直在努力改进python函数的运行时间,这需要使用余数函数(%)等等.我的主要测试案例是超过80,000个元素的numpy数组(单调增加),有10000次迭代,尽管我也尝试过各种其他大小.

最终我达到了剩余功能是一个主要瓶颈的地步,并尝试了各种解决方案.这是我在运行以下代码时发现的行为:

import numpy as np
import time

a = np.random.rand(80000)
a = np.cumsum(a)
d = 3
start_time1 = time.time()
for i in range(10000):
    b = a % d
    d += 0.001
end_time1 = time.time()
d = 3
start_time2 = time.time()
for i in range(10000):
    b = a - (d * np.floor(a / d))
    d += 0.001
end_time2 = time.time()
print((end_time1 - start_time1) / 10000)
print((end_time2 - start_time2) / 10000)

输出是:

0.0031344462633132934
0.00022937238216400147

当将数组大小增加到800,000时:

0.014903099656105041
0.010498356819152833

(对于这篇文章,我只为实际输出运行了一次代码,同时试图理解这个问题我已经得到了这些结果.)

虽然这解决了我的运行时问题 - 但我很难理解为什么.我错过了什么吗？我能想到的唯一区别是额外函数调用的开销,但第一种情况非常极端(并且运行时间的1.5倍也不够好),如果是这种情况,我会认为存在该np.remainder功能是没有意义的.

编辑: 我尝试使用非numpy循环测试相同的代码:

import numpy as np
import time


def pythonic_remainder(array, d):
    b = np.zeros(len(array))
    for i in range(len(array)):
        b[i] = array[i] % d

def split_pythonic_remainder(array, d):
    b = np.zeros(len(array))
    for i in range(len(array)):
        b[i] = array[i] - (d * np.floor(array[i] / d))

def split_remainder(a, d):
    return a - (d * np.floor(a / d))

def divide(array, iterations, action):
    d = 3
    for i in range(iterations):
        b = action(array, d)
        d += 0.001

a = np.random.rand(80000)
a = np.cumsum(a)
start_time = time.time()
divide(a, 10000, split_remainder)
print((time.time() - start_time) / 10000)

start_time = time.time()
divide(a, 10000, np.remainder)
print((time.time() - start_time) / 10000)
start_time = time.time()
divide(a, 10000, pythonic_remainder)
print((time.time() - start_time) / 10000)

start_time = time.time()
divide(a, 10000, split_pythonic_remainder)
print((time.time() - start_time) / 10000)

我得到的结果是:

0.0003770533800125122
0.003932329940795899
0.018835473942756652
0.10940513386726379

我觉得有趣的是,在非numpy情况下情况正好相反.

Answer 1

我最好的假设是你的NumPy安装fmod在%计算中使用了未经优化的.这就是原因.

首先,我无法在普通的pip安装版本的NumPy 1.15.1上重现您的结果.我只获得大约10%的性能差异(asdf.py包含您的计时代码):

$ python3.6 asdf.py
0.0006543657302856445
0.0006025806903839111

我可以python3.6 setup.py build_ext --inplace -j 4通过NumPy Git存储库的克隆从v1.15.1 的手动build()重现主要的性能差异,但是:

$ python3.6 asdf.py
0.00242799973487854
0.0006397026300430298

这表明我的pip安装版本%比我的手动版本或你安装的内容更好.

在引擎盖下看,很容易看到NumPy 中浮点的实现,%并将速度归咎于不必要的floordiv计算(npy_divmod@c@计算两者//和%):

NPY_NO_EXPORT void
@TYPE@_remainder(char **args, npy_intp *dimensions, npy_intp *steps, void *NPY_UNUSED(func))
{
    BINARY_LOOP {
        const @type@ in1 = *(@type@ *)ip1;
        const @type@ in2 = *(@type@ *)ip2;
        npy_divmod@c@(in1, in2, (@type@ *)op1);
    }
}

但在我的实验中,删除floordiv没有任何好处.对于编译器来说,它看起来很容易进行优化,因此它可能已经过优化,或者它可能只是运行时中可忽略不计的一小部分.

而不是floordiv,让我们只关注一行npy_divmod@c@,即fmod:

mod = npy_fmod@c@(a, b);

这是初始余数计算,在特殊情况处理和调整结果以匹配右侧操作数的符号之前.如果我们比较的表现%与numpy.fmod我的手工打造:

>>> import timeit
>>> import numpy
>>> a = numpy.arange(1, 8000, dtype=float)
>>> timeit.timeit('a % 3', globals=globals(), number=1000)
0.3510419335216284
>>> timeit.timeit('numpy.fmod(a, 3)', globals=globals(), number=1000)
0.33593094255775213
>>> timeit.timeit('a - 3*numpy.floor(a/3)', globals=globals(), number=1000)
0.07980139832943678

我们看到它fmod似乎对几乎整个运行时负责%.

我没有反汇编生成的二进制文件或在指令级调试器中逐步执行它以查看确切执行的内容,当然,我无法访问您的计算机或NumPy副本.不过,从上述证据来看,fmod似乎很可能是罪魁祸首.