PyPy в 17 раз быстрее Python. Можно ли ускорить Python?

В качестве основы для Python я написал это на C (а затем решил использовать C ++ для более удобного ввода-вывода массива). Он эффективно компилируется для x86-64 с помощью clang ++. Это работает в 82 раза быстрее, чем CPython3.6.2 с указанным в вопросе кодом, на Skylake x86, поэтому даже ваши более быстрые версии Python по-прежнему на пару факторов отстают от почти оптимального машинного кода. (Да, я посмотрел на вывод asm компилятора, чтобы убедиться, что он работает хорошо).

Разрешение хорошему JIT-компилятору или опережающему компилятору увидеть логику цикла является ключом к производительности здесь. Логика проблемы по своей сути последовательна, поэтому нет возможности заставить Python запускать уже скомпилированный C для выполнения что-то по всему массиву (например, NumPy), потому что для этой конкретной проблемы не будет скомпилирован C, если вы не используете Cython или что-то в этом роде. Возвращение каждого шага к решению проблемы интерпретатору CPython - смерть для производительности, когда его медлительность не скрывается узкими местами в памяти или чем-то еще.

Обновление: преобразование массива смещений в массив указателей ускоряет его еще в 1,5 раза (простой режим адресации + удаление add из цепочки зависимостей, переносимых циклом критического пути, что снижает его до просто 4-тактная задержка загрузки-использования L1D для простого режима адресации (когда указатель исходит из другая загрузка), а не 6c = 5c + 1c для режима индексированной адресации + add задержка).

Но я думаю, что мы можем проявить щедрость к Python и не ожидать, что он будет идти в ногу с преобразованиями алгоритмов, подходящими для современных процессоров: P (особенно потому, что я использовал 32-битные указатели даже в 64-битном режиме, чтобы убедиться, что массив элементов 4585 был по-прежнему только 18kiB, поэтому он умещается в кэш-памяти L1D 32kiB. Как Linux x32 ABI или AArch64 ILP32 ABI.)

Кроме того, альтернативное выражение для обновления получает команду gcc для его компиляции без ветвей, как это делает clang. (Закомментированный и исходный perf stat результат оставлен в этом ответе, потому что интересно увидеть эффект безветвия и ветвления с ошибочными прогнозами.)

unsigned jumps(int offset[], unsigned size) {
    unsigned location = 0;
    unsigned counter = 0;

    do {
          //location += offset[location]++;            // simple version
          // >=3 conditional version below

        int off = offset[location];

        offset[location] += (off>=3) ? -1 : 1;       // branchy with gcc
        // offset[location] = (off>=3) ? off-1 : off+1;  // branchless with gcc and clang.  

        location += off;

        counter++;
    } while (location < size);

    return counter;
}

#include <iostream>
#include <iterator>
#include <vector>

int main()
{
    std::ios::sync_with_stdio(false);     // makes cin faster
    std::istream_iterator<int> begin(std::cin), dummy;
    std::vector<int> values(begin, dummy);   // construct a dynamic array from reading stdin

    unsigned count = jumps(values.data(), values.size());
    std::cout << count << '\n';
}

В clang4.0.1 -O3 -march=skylake внутренний цикл не имеет ветвей; он использует условный ход для условия >=3. Я использовал ? :, потому что надеялся, что компилятор сделает именно это. Источник + asm на Обозреватель компилятора Godbolt

.LBB1_4:                                # =>This Inner Loop Header: Depth=1
    mov     ebx, edi               ; silly compiler: extra work inside the loop to save code outside
    mov     esi, dword ptr [rax + 4*rbx]  ; off = offset[location]
    cmp     esi, 2
    mov     ecx, 1
    cmovg   ecx, r8d               ; ecx = (off>=3) ? -1 : 1;  // r8d = -1 (set outside the loop)
    add     ecx, esi               ; off += -1 or 1
    mov     dword ptr [rax + 4*rbx], ecx  ; store back the updated off
    add     edi, esi               ; location += off  (original value)
    add     edx, 1                 ; counter++
    cmp     edi, r9d
    jb      .LBB1_4                ; unsigned compare against array size

Вот результат perf stat ./a.out < input.txt (для версии clang) на моем процессоре Skylake i7-6700k:

21841249        # correct total, matches Python

 Performance counter stats for './a.out':

         36.843436      task-clock (msec)         #    0.997 CPUs utilized          
                 0      context-switches          #    0.000 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
               119      page-faults               #    0.003 M/sec                  
       143,680,934      cycles                    #    3.900 GHz                    
       245,059,492      instructions              #    1.71  insn per cycle         
        22,654,670      branches                  #  614.890 M/sec                  
            20,171      branch-misses             #    0.09% of all branches        

       0.036953258 seconds time elapsed

Среднее число инструкций за такт намного ниже 4 из-за зависимости данных в цикле. Адрес загрузки для следующей итерации зависит от нагрузки + добавления для этой итерации, и выполнение вне очереди не может это скрыть. Однако он может перекрывать всю работу по обновлению значения текущего местоположения.

Переход с int на short не приводит к снижению производительности (как и ожидалось; _ 13_ имеет ту же задержку, что и mov в Skylake), но снижает потребление памяти вдвое, поэтому больший массив может поместиться в кеш L1D если нужно.

Я попытался скомпилировать массив в программу (как int offsets[] = { file contents with commas added };, чтобы его не нужно было читать и анализировать. Он также сделал размер константой времени компиляции. Это сократило время выполнения до ~ 36,2 +/- 0,1 миллисекунды по сравнению с ~ 36.8, поэтому версия, которая читает из файла, по-прежнему тратила большую часть своего времени на решение реальной проблемы, а не на синтаксический анализ ввода (в отличие от Python, у C ++ незначительные накладные расходы на запуск, а мой процессор Skylake хорошо разгоняется до максимальной тактовой частоты. менее чем за миллисекунду благодаря аппаратному управлению P-состоянием в Skylake.)

gcc использует ветвь, и это примерно в 2 раза медленнее. (14% ветвей прогнозируются неверно в соответствии с perf stat по всей программе. Это только ветвление как часть обновления значений, но пропуски ветвления останавливают конвейер, поэтому они также влияют на критический путь таким образом, что зависимости данных не не здесь. Оптимизатор решил, что это плохое решение.)

Переписывание условного выражения как offset[location] = (off>=3) ? off-1 : off+1; убеждает gcc отказаться от использования asm, что выглядит неплохо.

gcc7.1.1 -O3 -march = skylake (для исходного источника, который компилируется с веткой для (off <= 3) ? : -1 : +1).

vs. CPython (Python3.6.2 в Arch Linux):

Performance counter stats for './ec-gcc':

     70.032162      task-clock (msec)         #    0.998 CPUs utilized          
             0      context-switches          #    0.000 K/sec                  
             0      cpu-migrations            #    0.000 K/sec                  
           118      page-faults               #    0.002 M/sec                  
   273,115,485      cycles                    #    3.900 GHz                    
   255,088,412      instructions              #    0.93  insn per cycle         
    44,382,466      branches                  #  633.744 M/sec                  
     6,230,137      branch-misses             #   14.04% of all branches        

   0.070181924 seconds time elapsed

У меня не установлен PyPy или другие реализации Python, извините.

perf stat python ./orig-v2.e.py
21841249

 Performance counter stats for 'python ./orig-v2.e.py':

       3046.703831      task-clock (msec)         #    1.000 CPUs utilized          
                10      context-switches          #    0.003 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
               923      page-faults               #    0.303 K/sec                  
    11,880,130,860      cycles                    #    3.899 GHz                    
    38,731,286,195      instructions              #    3.26  insn per cycle         
     8,489,399,768      branches                  # 2786.421 M/sec                  
        18,666,459      branch-misses             #    0.22% of all branches        

       3.046819579 seconds time elapsed

Вы можете улучшить мелочи, но pypy (скорее всего) всегда будет быстрее в этой задаче.

И для CPython, и для Cython:

Для Cython:

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

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

• Из постановки задачи: Срочное прерывание поступает от ЦП: оно застряло в лабиринте инструкций перехода. Очевидно, бойкий ответ таков: не пишите обработчики IRQ на Python: P