Почему NumPy иногда медленнее, чем NumPy + обычный цикл Python?

Question

Это основано на этот вопрос задан 2018-10.

Рассмотрим следующий код.Три простые функции для подсчета ненулевых элементов в массиве NumPy 3D (1000 × 1000 × 1000).

import numpy as np

def f_1(arr):
    return np.sum(arr > 0)

def f_2(arr):
    ans = 0
    for val in range(arr.shape[0]):
        ans += np.sum(arr[val, :, :] > 0)
    return ans

def f_3(arr):
    return np.count_nonzero(arr)

if __name__ == '__main__':

    data = np.random.randint(0, 10, (1_000, 1_000, 1_000))
    print(f_1(data))
    print(f_2(data))
    print(f_3(data))

Время выполнения на моем компьютере (Python 3.7.?, Windows 10, NumPy 1.16.?):

%timeit f_1(data)
1.73 s ± 21.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit f_2(data)
1.4 s ± 1.36 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit f_3(data)
2.38 s ± 956 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

Итак, f_2() работает быстрее, чем f_1() и f_3().Однако дело обстоит не так с data меньшего размера.Вопрос - почему так?Это NumPy, Python или что-то еще?

Answer 1

Это связано с доступом к памяти и кэшированием. Каждая из этих функций делает две вещи, взяв в качестве примера первый код:

np.sum(arr > 0)

Сначала выполняется сравнение, чтобы найти, где arr больше нуля (или не равно нулю, поскольку arr содержит неотрицательные целые числа). Это создает промежуточный массив той же формы, что и arr. Затем он суммирует этот массив.

Прямо, верно? Ну, при использовании np.sum(arr > 0) это большой массив. Когда он достаточно большой, чтобы не помещаться в кэш, производительность снижается, поскольку, когда процессор начинает выполнять сумму, большинство элементов массива будет удалено из памяти и нуждается в перезагрузке.

Поскольку f_2 выполняет итерации по первому измерению, он имеет дело с меньшими подмассивами. То же самое копирование и сумма выполняются, но на этот раз промежуточный массив помещается в память. Он создан, использован и уничтожен, не покидая памяти. Это намного быстрее.

Теперь вы можете подумать, что f_3 будет самым быстрым (с использованием встроенного метода и всего), но, глядя на исходный код , вы увидите, что он использует следующие операции:

a_bool = a.astype(np.bool_, copy=False)
return a_bool.sum(axis=axis, dtype=np.intp

a_bool - это просто еще один способ найти ненулевые записи, который создает большой промежуточный массив.

Выводы

Эмпирические правила - только это, и они часто неправильны. Если вам нужен более быстрый код, профилируйте его и посмотрите, в чем проблемы (хорошо поработайте над этим здесь).

Python делает некоторые вещи очень хорошо. В случаях, когда он оптимизирован, он может быть быстрее, чем numpy. Не бойтесь использовать старый старый код Python или типы данных в сочетании с Numpy.

Если вам часто приходится вручную писать циклы для повышения производительности, вы можете захотеть взглянуть на numexpr - он автоматически делает это. Я сам этим не пользовался, но это должно обеспечить хорошее ускорение, если промежуточные массивы замедляют вашу программу.

Answer 2

Все зависит от того, как данные располагаются в памяти и как код обращается к ним. По сути, данные выбираются из памяти в блоках, которые затем кэшируются; если алгоритму удается использовать данные из блока, который находится в кеше, нет необходимости снова читать из памяти. Это может привести к значительной экономии времени, особенно когда кэш-память намного меньше данных, с которыми вы имеете дело.

Рассмотрим эти вариации, которые отличаются только тем, по какой оси мы итерируем:

def f_2_0(arr):
    ans = 0
    for val in range(arr.shape[0]):
        ans += np.sum(arr[val, :, :] > 0)
    return ans

def f_2_1(arr):
    ans = 0
    for val in range(arr.shape[1]):
        ans += np.sum(arr[:, val, :] > 0)
    return ans

def f_2_2(arr):
    ans = 0
    for val in range(arr.shape[2]):
        ans += np.sum(arr[:, :, val] > 0)
    return ans

И результаты на моем ноутбуке:

%timeit f_1(data)
2.31 s ± 47.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit f_2_0(data)
1.88 s ± 60 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit f_2_1(data)
2.65 s ± 142 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit f_2_2(data)
12.8 s ± 650 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Вы можете видеть, что f_2_1 почти так же быстро, как f_1, , что заставляет меня думать, что numpy не использует оптимальный шаблон доступа (тот, который используется f_2_0) . Объяснение того, как именно кэширование влияет на время, приведено в другом ответе .

Answer 3

Давайте полностью удалим временный массив

Как уже упоминал в своем ответе @ user2699, выделение и запись в большой массив, который не помещается в кэш, может значительно замедлить процесс.Чтобы продемонстрировать это поведение, я написал две маленькие функции с использованием Numba (JIT-Compiler).

В скомпилированных языках (C, Fortran, ..) вы обычно избегаете временных массивов.В интерпретируемом Python (без использования Cython или Numba) вам часто требуется вызывать скомпилированную функцию для большей части данных (векторизация), поскольку циклы в интерпретируемом коде чрезвычайно медленные.Но это также может иметь недостатки (например, временные массивы, неправильное использование кэша)

Функция без временного выделения массива

@nb.njit(fastmath=True,parallel=False)
def f_4(arr):
    sum=0
    for i in nb.prange(arr.shape[0]):
        for j in range(arr.shape[1]):
            for k in range(arr.shape[2]):
                if arr[i,j,k]>0:
                    sum+=1
    return sum

С временным массивом

Обратите внимание, что если вы включаете распараллеливание parallel=True, компилятор не только пытается распараллелить код, но и другие оптимизации, такие как слияние циклов, включаются.

@nb.njit(fastmath=True,parallel=False)
def f_5(arr):
    return np.sum(arr>0)

Сроки

%timeit f_1(data)
1.65 s ± 48.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit f_2(data)
1.27 s ± 5.66 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit f_3(data)
1.99 s ± 6.11 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit f_4(data) #parallel=false
216 ms ± 5.45 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit f_4(data) #parallel=true
121 ms ± 4.85 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit f_5(data) #parallel=False
1.12 s ± 19 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit f_5(data) #parallel=true Temp-Array is automatically optimized away
146 ms ± 12.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)