NumPy на небольших массивах: производительность элементарных арифметических операций

Я не на 100% уверен, что у этого вопроса есть решение, кроме «это накладные расходы, живите с этим», но кто знает.

Как правило, Numpy не оптимизирован для вычислений небольших массивов (а также для вычислений массивов, в которых последняя целевая ось тоже мала). Например, создание массивов, их сбор, анализ типов и т. д. — это довольно затратно.

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

Это действительно обычный способ исправить это. Обратите внимание, что Cython может быть лучше для упаковки. Однако Numba может легко ускорить создание массивов Numpy (без полного исправления), тогда как в Cython это сделать сложнее. Основная причина заключается в том, что Numba использует собственную реализацию Numpy и может оптимизировать свой код благодаря JIT-компилятору, в то время как Cpython и Cython этого не делают. Способ ускорения операций Numpy в Cython обычно заключается в создании представлений для него. Создание новых небольших массивов и функций Numpy по-прежнему обходится дорого.

Альтернатива включает прямой вызов собственных функций (C, C++, Fortran, Rust и т. д.), возможно, с помощью какой-либо библиотеки/инструмента привязки. Такую встроенную функцию можно вызывать из Cython, Ctypes, CFFI и т. д.

Поэтому я подумал, что сделаю простую подпрограмму на Фортране.

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

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

Numpy необходимо выполнить значительно больше операций, чем ваша функция Fortran. Numpy спроектирован как общий, в то время как ваша функция Fortran решает конкретно одну проблему. NumPyFunc выполняет как минимум 6 вызовов функций Numpy, и Numpy не может это оптимизировать из-за интерпретатора CPython. Интерпретаторы работают мучительно медленно (особенно CPython из-за очень динамичных свойств языка и его многочисленных высокоуровневых функций). Он также создает 6 временных массивов (некоторые из них сейчас могут быть переработаны для ускорения операций с большими массивами, но такая оптимизация приводит к еще большим накладным расходам). Каждый массив (который на самом деле представляет собой представление необработанного буфера памяти с динамическим подсчетом ссылок) представляет собой объект CPython, который необходимо выделить, подсчитать ссылки и освободить. Во время каждой операции Numpy необходимо динамически проверять тип, форму, размер, шаг, целевую ось объектов входного массива. Также необходимо проверить/выполнить некоторые функции высокого уровня, такие как циклическое воспроизведение, трансляция (для каждого измерения). Из-за множества возможных входных параметров Numpy выполняет это, создавая общие внутренние многомерные генераторы (по одному на входной массив). Эта часть кода Numpy неоптимальна (поэтому ее можно оптимизировать, хотя, ИМХО, она довольно сложна, поэтому еще мало что было сделано). Например, каждый из них динамически выделяется/освобождается по AFAIK. Вдобавок ко всему, Numpy спроектирован так, чтобы быть довольно удобным для пользователя, поэтому он проверяет/сообщает о проблемах, таких как деление на нули, поддерживает специальные значения, такие как NaN, Inf и т. д. (при этом пытаясь максимально снизить связанные с этим накладные расходы). И последнее, но не менее важное: необходимо освободить и снова получить GIL CPython (глобальную блокировку интерпретатора). Все это не исчерпывающий список: есть еще (технические) операции, которые я здесь не упомянул (например, выбор лучшей функции для запуска, чтобы операция выполнялась SIMD-дружественным способом, выборка CPython переменных модуля Numpy и т. д.).

Почти ничего из этого не делается вашим кодом на Фортране во время выполнения, а когда это происходит, то это делается только один раз вместо 6 раз. Большинство операций либо не выполняются, либо просто выполняются во время компиляции. В основном это возможно потому, что код специализирован. Это разумно оправдывает «в 5 раз более быстрый» код с такой степенью детализации (тем более, что один промах в кэше, требующий выборки из DRAM, обычно занимает 50–100 нс).

Возможно также, что нет ничего, что можно было бы сделать, чтобы сократить разрыв между NumPy и Fortran, а накладные расходы на операции с массивами NumPy - это то, что есть.

Хотя, безусловно, существуют способы микрооптимизации кода Numpy, это не приведет к значительному повышению производительности. Ключ в том, чтобы просто не использовать Numpy для массивов, содержащих всего 6-10 элементов. На самом деле вызов нативной функции для этого обходится уже очень дорого. Действительно, современные процессоры x86-64 могут добавлять 6-10 элементов между двумя массивами всего за **всего несколько циклов процессора благодаря инструкциям SIMD! Самая медленная чисто вычислительная часть, безусловно, заключается в проверке размера массива и поддержке размеров, не превышающих степень двойки, без каких-либо внешних обращений. Вычислительная часть вашей функции на Фортране должна занимать очень небольшую часть заявленного времени! Если не учитывать возможные промахи в кэше или доступ к DRAM, это, безусловно, должно занять не более 5–30 нс! Все остальное (90-98%) — это на самом деле чистые накладные расходы! В этом масштабе даже (не встроенный) вызов встроенной функции может быть дорогостоящим, поэтому у Numpy/CPython даже нет шансов сделать это так быстро.

Чтобы подчеркнуть, насколько быстрым может быть ваш код на Фортране, вот его ассемблерный код (скомпилированный с использованием gfortran и оптимизаций -O2):

f90_small_arrays_:
        mov     r11, rdi
        mov     rax, rcx
        movss   xmm1, DWORD PTR [r8]
        mov     rdi, rdx
        movss   xmm2, DWORD PTR [rax]
        movsx   rdx, DWORD PTR [r11]
        mov     rcx, QWORD PTR [rsp+8]
        mov     r10, QWORD PTR [rsp+16]
        subss   xmm1, xmm2
        test    edx, edx
        jle     .L1
        sal     rdx, 2
        xor     eax, eax
.L3:
        movss   xmm0, DWORD PTR [rdi+rax]
        subss   xmm0, DWORD PTR [rsi+rax]
        divss   xmm0, xmm1
        movss   DWORD PTR [rcx+rax], xmm0
        add     rax, 4
        cmp     rdx, rax
        jne     .L3
        movss   xmm1, DWORD PTR [r9]
        xor     eax, eax
        subss   xmm1, xmm2
.L4:
        movss   xmm0, DWORD PTR [rcx+rax]
        mulss   xmm0, xmm1
        addss   xmm0, DWORD PTR [rsi+rax]
        movss   DWORD PTR [r10+rax], xmm0
        add     rax, 4
        cmp     rdx, rax
        jne     .L4
.L1:
        ret

На моем процессоре i5-9600KF создание нижнего колонтитула занимает 5–20 циклов. Первый цикл занимает 3 цикла/элемент, а второй — 1,5 цикла/элемент. Обратите внимание, что количество циклов настолько мало, потому что инструкции конвейеризированы и выполняются параллельно . В итоге вся функция на моей машине должна занять 50-100 тактов для 10 элементов, то есть меньше 10-20 нс! На практике этот код не использует инструкции SIMD. Это может быть даже быстрее с -O3 (создание 128-битного SIMD-кода), поскольку 4 элемента можно вычислить одновременно почти за ту же стоимость, что и 1. На практике массивы настолько малы, что это не должно привести к увеличению более чем в два раза. более быстрое (~ 10 нс) выполнение, и большую часть времени даже не следует тратить на основной цикл SIMD (<5 нс на моем процессоре). Более того, эти две петли можно объединить. В этом случае я ожидаю, что основные вычислительные затраты на самом деле будут связаны с неверным прогнозированием итераций цикла (поскольку ЦП не знает размер массива, если только этот код не запускается очень часто с одним и тем же размером массива), а не не говоря уже о вызове этой функции CPython, который занимает сотни наносекунд.

Таким образом, если вы действительно заботитесь о производительности, вам следует избегать многократного вызова Fortran и вкладывать как можно больше работы в свои собственные функции (в настоящее время это делается в CPython). Более того, указание размера массивов во время компиляции в этом случае также может значительно повысить производительность. Использование -ffast-math может улучшить это еще больше (за счет использования инструкции быстрого обратного деления вместо медленного деления), хотя вам следует быть осторожным с ее последствиями. В последнем случае код генерирует 36 инструкций, что занимает всего 5-10 нс на моем процессоре (по сравнению с ~300 нс для вызова функции Fortran из CPython и ~3000 нс для кода Numpy). Он настолько быстр, что производительность собственного кода ограничивается задержкой инструкций ЦП. Таким образом, мой процессор может одновременно обрабатывать множество массивов (по 10 элементов), тратя при этом всего 2 нс на массив! Новые процессоры могут достигать даже 1 нс/массив! Это намного быстрее, чем выполнение любого оператора CPython (включая базовое присвоение переменных), а также намного быстрее, чем даже вызов встроенной функции. Не говоря уже о том, что подсчет ссылок на один объект CPython/операции Numpy-массива или GIL также выполняются намного медленнее (выполняемые атомарные операции обычно занимают десятки нс). Вот почему почти все модули CPython не могут вам помочь (модули на основе компилятора — лучшее решение, если вы хотите сохранить свой основной код в CPython, несмотря на огромные накладные расходы, необходимые для преобразования типов CPython в собственные и вызова собственных функций из интерпретатора. ).

Вопрос :
" (...) это накладные расходы, живите с этим", но кто знает ( ? ) "

Раз вы уже стремитесь сэкономить наносекунды и, помимо отличной работы, которую Жером Ришар уже проделал, давайте рассмотрим все накладные расходы, которые не нужно оплачивать, прежде чем добавлять в игру новые, хорошо?

Код — это не окончательное решение по производительности, а, скорее, основа для сравнения затрат, которые вам придется заплатить, и попыток их устранения (вам нет необходимости) на аппаратном обеспечении ваших машин для сравнительного анализа (никто не хочет сравнивать яблоки с апельсинами, не так ли? )

Поскольку все затраты, связанные с Numpy, уже были оплачены во внешних экземплярах (там были оплачены затраты на выделение памяти, преобразование типов и генератор случайных чисел), давайте попробуем лишь немного изменить код, который вычисляет так мало крошечных операций. (так что на самом деле не так много места для ускорения, скорее может произойти замедление, как объясняет закон Амдала; раздел о дополнительных накладных расходах и разделах атомарности работы и задержки процессора),

что мы могли бы попытаться:

• избегать любых новых выделений памяти и
• использовать режим вычислений на месте, где можно избавить Numpy от дополнительных, если одноразовых, накладных расходов

def NumPyFunc(array1, array2, float1, float2, float3):

    #utput1 = (array2 - array1) / (float2 - float1)
    array2 -= array1                # in-place SUB, hope Numpy can go into SIMD uops
    array2 /= ( float2 - float1 )   # in-place DIV, MUL by inverse ought be faster
                                    #          factor best pre-computed in call-signature
                                    #          and pray the Randomness  to deliver DIV!0 
    #utput2 = array1 + output1 * (float3 - float1)
    array1 += ( ( float3 - float1 ) #          factor best pre-computed in call-signature
              * array2
                )                   # in-place ADD
    #eturn output1, output2
    return  array2,  array1         # in-place modified results RET as ref-only passing

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

Спасибо и удачи в подсчете чисел