Оптимизация циклов Numba и Cython

Рассмотрим следующие четыре функции (python, numba, cython и smart), которые вычисляют одинаковые ответы при одинаковых целочисленных входных данных.

def python(n):
    total = 0
    for m in range(1,n+1):
        total += m
    return total

from numba import jit
numba = jit(python)

cpdef int cython(int n):
    cdef int total = 0
    cdef int m
    for m in range(1, n+1):
        total += m
    return total

def smart(n):
    return n * (n + 1) // 2

Рассчитав время их казни, я был несколько удивлен, обнаружив, что

  1. Время выполнения numba не зависит от n (в то время как cython линейно зависит от n)
  2. numba медленнее, чем smart

Сразу возникает два вопроса:

  1. Почему Numba, а не Cython, может превратить его в алгоритм с постоянным временем?
  2. Учитывая, что Numba удалось превратить его в алгоритм с постоянным временем, почему он медленнее, чем чистая функция постоянного времени Python smart?

Поскольку я не специалист по ассемблеру, просмотр сгенерированного кода на самом деле не дает мне большой подсказки, кроме того, что промежуточный код LLVM, сгенерированный Numba, все еще появляется (хотя я мог неправильно понять), чтобы содержать цикл ... и Я безнадежно теряюсь в x64, который в конечном итоге создается из этого. (Если кто-то не спросит, я не буду публиковать сгенерированные коды, так как они довольно длинные.)

Я запускаю это на x64 Linux в ноутбуке Jupyter, поэтому я подозреваю, что Cython использует GCC 4.4.7, который использовался для компиляции Python; и llvmlite 0.20.0, что подразумевает LLVM 4.0.x.

Редактировать:

я тоже засекал

smart_numba = jit(smart)

а также

cpdef int smart_cython(int n):
    return n * (n + 1) // 2

smart_numba и numba дают одинаковое время, которое на 25% медленнее, чем smart (чистый Python), и на 175% медленнее, чем smart_cython.

Означает ли это, что Cython очень хорошо справляется с преодолением границы между Python и низкоуровневым, а Numba справляется с этой задачей плохо? Или есть что-то еще?


python numba cython
person jacg    schedule 06.12.2017    source источник

Ответы (1)


arrow_upward
8
arrow_downward

  1. Похоже, это проблема LLVM и GCC — см. пример в проводнике компилятора здесь, который менее шумный, чем тот, что нумба выплевывает. Я немного запутался в сборке, но довольно ясно, что вывод GCC имеет цикл (от jge до .L6), а вывод clang — нет. См. также эту проблему в системе отслеживания ошибок GCC.

  2. На моей машине (Windows x64) numba не намного медленнее, чем smart, всего около 9 нс. Эти накладные расходы, по-видимому, связаны с механизмом диспетчеризации типов numba — если вы пропустите его, выбрав конкретную перегрузку, версия numba будет быстрее, чем версия python.

Вот мои тайминги

In [73]: %timeit numba_sum(10000)
182 ns ± 1.69 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

In [74]: %timeit smart(10000)
171 ns ± 2.26 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

# pick out int64 overload
i64_numba_sum = numba_sum.get_overload((numba.int64,))

In [75]: %timeit i64_numba_sum(10000)
94 ns ± 1.41 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
person chrisb    schedule 06.12.2017
comment
Да, godbolt делает отсутствие/наличие цикла довольно очевидным. Но меня смущает использование регистров, начинающихся с e, которые, как я понимаю, 32-битные. Numba определенно предположил int64. Если я изменю int на long int, вывод clang станет очень длинным и сложным, за пределами моей способности расшифровать. Интересно, что на вашей машине numba быстрее, чем smart: на моей на 25% медленнее. Numba также замедляет smart, чтобы соответствовать скорости numba (что неудивительно, если вы видели, что numba медленнее, чем smart). - person jacg; 07.12.2017
comment
Извините, я оговорился, я имел в виду не значительно медленнее. См. редактирование, кажется, что диспетчеризация типа на самом деле создает накладные расходы в версии numba. - person chrisb; 07.12.2017