Остальная функция (%) времени выполнения на массивах numpy намного длиннее, чем вычисление остатка вручную
В последние несколько дней я работал над улучшением времени выполнения функции python, которая требует многого использования функции остатка (%) между прочим. Мой основной тестовый пример - это массив с размером в 80 000 элементов (монотонно возрастающий), с 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.5x время исполнения тоже недостаточно), и если бы это было так, я бы подумал, что существование функция 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, верно обратное.
Ответы
Ответ 1
Моя лучшая гипотеза состоит в том, что ваш NumPy установить, используя неоптимизированную fmod внутри % расчета. Вот почему.
Во-первых, я не могу воспроизвести ваши результаты на обычной версии установленного NumPy 1.15.1. Я получаю только около 10% разницы в производительности (asdf.py содержит ваш временной код):
$ python3.6 asdf.py
0.0006543657302856445
0.0006025806903839111
Я могу воспроизвести существенное несоответствие производительности с помощью ручной сборки (python3.6 setup.py build_ext --inplace -j 4) из v1.15.1 из клона репозитория NumPy Git, хотя:
$ python3.6 asdf.py
0.00242799973487854
0.0006397026300430298
Это говорит о том, что мой пипе установлена сборка % лучше оптимизировано, чем моя ручная сборка или что вы установили.
Заглянув под капот, это заманчиво посмотреть на осуществление операций с плавающей точкой % в NumPy и винят замедление на расчет ненужную floordiv ([email protected]@ вычисляет как // и %):
NPY_NO_EXPORT void
@[email protected]_remainder(char **args, npy_intp *dimensions, npy_intp *steps, void *NPY_UNUSED(func))
{
BINARY_LOOP {
const @[email protected] in1 = *(@[email protected] *)ip1;
const @[email protected] in2 = *(@[email protected] *)ip2;
[email protected]@(in1, in2, (@[email protected] *)op1);
}
}
но в моих экспериментах удаление флордива не принесло пользы. Это выглядит достаточно легко для компилятора, чтобы оптимизировать его, поэтому, возможно, он был оптимизирован, или, возможно, это была всего лишь незначительная часть времени выполнения.
Вместо того, чтобы floordiv, пусть сосредоточиться только на одну строку в [email protected]@, в fmod вызова:
mod = [email protected]@(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 кажется довольно вероятным преступником.
