Изменение представления массива numpy дважды в объединенной функции ускоряет выполнение функции - PullRequest
Новая
       11

Изменение представления массива numpy дважды в объединенной функции ускоряет выполнение функции

5 голосов
/ 21 сентября 2019

Итак, я тестировал скорости двух версий одной и той же функции;один с изменением вида массива numpy дважды и один без.Код выглядит следующим образом: 

import numpy as np
from numba import njit

@njit
def min_getter(arr):

    if len(arr) > 1:
        result = np.empty(len(arr), dtype = arr.dtype)
        local_min = arr[0]
        result[0] = local_min

        for i in range(1,len(arr)):
            if arr[i] < local_min:
                local_min = arr[i]
            result[i] = local_min
        return result

    else:
        return arr

@njit
def min_getter_rev1(arr1):

    if len(arr1) > 1:
        arr = arr1[::-1][::-1]
        result = np.empty(len(arr), dtype = arr.dtype)
        local_min = arr[0]
        result[0] = local_min

        for i in range(1,len(arr)):
            if arr[i] < local_min:
                local_min = arr[i]
            result[i] = local_min
        return result

    else:
        return arr1
size = 500000
x = np.arange(size)   
y = np.hstack((x[::-1], x))

y_min = min_getter(y)
yrev_min = min_getter_rev1(y)

Удивительно, но тот, у которого есть дополнительная операция, работает несколько быстрее несколько раз.Я использовал %timeit около 10 раз для обеих функций;пробовал разные размеры массива, и разница очевидна (по крайней мере на моем компьютере).Время выполнения min_getter составляет около:

2.35 ms ± 58.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) (иногда это 2,33, а иногда 2,37, но никогда не опускается ниже 2,30)

, а время выполнения min_getter_rev1 составляет около:

2.22 ms ± 23.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) (иногда это 2,25, а иногда 2,23, но редко превышает 2,30)

Есть идеи, почему и как это произошло?Разница в скорости увеличивается на 4-6%, что может иметь большое значение в некоторых приложениях.Базовый механизм ускорения может помочь ускорить некоторые кодовые соединения, потенциально

Примечание 1. Я пробовал size = 5000000 и тестировал 5-10 раз для каждой функции, а разница еще большеочевидный.Чем быстрее будет работать 23.2 ms ± 51.7 µs per loop (mean ± std. dev. of 7 runs, 10 loops each), тем медленнее будет 24.4 ms ± 234 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Примечание 2. Во время тестов версии numpy и numba: 1.16.5 и 0.45.1;версия Python 3.7.4;IPython версия 7.8.0;Python IDE используется spyder.Результаты теста могут отличаться в разных версиях.

1 Ответ

2 голосов
/ 22 сентября 2019

TL; DR: Вероятно, просто счастливое совпадение, что второй код был быстрее.

Проверка сгенерированных типов показывает, что есть одно важное отличие:

  • ВВ первом примере ваш arr набирается как array(int32, 1d, C) непрерывный массив C. 
min_getter.inspect_types()

min_getter (array(int32, 1d, C),)  <--- THIS IS THE IMPORTANT LINE
--------------------------------------------------------------------------------
# File: <>
# --- LINE 4 --- 
# label 0

@njit

# --- LINE 5 --- 

def min_getter(arr):

[...]
  • Во втором примере arr набирается как array(int32, 1d, A), массивбез знания, если это смежно.Это связано с тем, что [::-1] возвращает массив без информации о смежности, и после его потери он не может быть восстановлен за секунду [::-1]. 
>>> min_getter_rev1.inspect_types()

[...]

    # --- LINE 18 --- 
    #   arr1 = arg(0, name=arr1)  :: array(int32, 1d, C)
    #   $const0.2 = const(NoneType, None)  :: none
    #   $const0.3 = const(NoneType, None)  :: none
    #   $const0.4 = const(int, -1)  :: Literal[int](-1)
    #   $0.5 = global(slice: <class 'slice'>)  :: Function(<class 'slice'>)
    #   $0.6 = call $0.5($const0.2, $const0.3, $const0.4, func=$0.5, args=(Var($const0.2, <> (18)), Var($const0.3, <> (18)), Var($const0.4, <> (18))), kws=(), vararg=None)  :: (none, none, int64) -> slice<a:b:c>
    #   del $const0.4
    #   del $const0.3
    #   del $const0.2
    #   del $0.5
    #   $0.7 = static_getitem(value=arr1, index=slice(None, None, -1), index_var=$0.6)  :: array(int32, 1d, A)
    #   del arr1
    #   del $0.6
    #   $const0.8 = const(NoneType, None)  :: none
    #   $const0.9 = const(NoneType, None)  :: none
    #   $const0.10 = const(int, -1)  :: Literal[int](-1)
    #   $0.11 = global(slice: <class 'slice'>)  :: Function(<class 'slice'>)
    #   $0.12 = call $0.11($const0.8, $const0.9, $const0.10, func=$0.11, args=(Var($const0.8, <> (18)), Var($const0.9, <> (18)), Var($const0.10, <> (18))), kws=(), vararg=None)  :: (none, none, int64) -> slice<a:b:c>
    #   del $const0.9
    #   del $const0.8
    #   del $const0.10
    #   del $0.11
    #   $0.13 = static_getitem(value=$0.7, index=slice(None, None, -1), index_var=$0.12)  :: array(int32, 1d, A)
    #   del $0.7
    #   del $0.12
    #   arr = $0.13  :: array(int32, 1d, A)  <---- THIS IS THE IMPORTANT LINE
    #   del $0.13

    arr = arr1[::-1][::-1]

[...]

(Остальная часть сгенерированного кода практически идентична)

Индексирование и повторение должны выполняться быстрее, если известно, что массив является смежным.Но это не то, что мы наблюдаем в этом случае - скорее наоборот.

Так в чем же причина?

Сама Numba использует LLVM для «компиляции» приведенного кода.Таким образом, задействован фактический компилятор, и компиляторы могут выполнять оптимизацию.Несмотря на то, что код, проверенный inspect_types(), практически идентичен, фактический код LLVM / ASM довольно сильно отличается inspect_llvm() и inspect_asm().Таким образом, компилятор (или numba) смог выполнить какую-то оптимизацию во втором случае, что было невозможно в первом случае.Или некоторая оптимизация, которая была применена к первому случаю, фактически ухудшала код.

Однако это означает, что нам просто «повезло» во втором случае.Возможно, это не то, чем можно управлять, потому что оно зависит от:

  • типов, которые Numba создает на основе вашего источника,
  • исходного кода, который Numba использует для работы с этими типами.
  • сгенерированный LLVM из этих типов и источника numba и
  • сгенерированный ASM из этого LLVM.

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

Интересный факт: если вы выбросите внешние if s: 

import numpy as np
from numba import njit

@njit
def min_getter(arr):
    result = np.empty(len(arr), dtype = arr.dtype)
    local_min = arr[0]
    result[0] = local_min

    for i in range(1,len(arr)):
        if arr[i] < local_min:
            local_min = arr[i]
        result[i] = local_min
    return result

@njit
def min_getter_rev1(arr1):
    arr = arr1[::-1][::-1]
    result = np.empty(len(arr), dtype = arr.dtype)
    local_min = arr[0]
    result[0] = local_min

    for i in range(1,len(arr)):
        if arr[i] < local_min:
            local_min = arr[i]
        result[i] = local_min
    return result

size = 500000
x = np.arange(size)   
y = np.hstack((x[::-1], x))

y_min = min_getter(y)
yrev_min = min_getter_rev1(y)

%timeit min_getter(y)      # 2.29 ms ± 86.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit min_getter_rev1(y) # 2.37 ms ± 212 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

В этом случае тот, у кого нет [::-1][::-1], быстрее.

Итак, если вы хотите сделать это надежно быстрее: переместите флажок if len(arr) > 1 за пределы функции и не используйте [::-1][::-1], потому что в большинстве случаев это сделает работу медленнее (и менее читаемой)!

...