31

У меня есть следующие два варианта кода для Cython:

Вариант 1:

cpdef prime(int n):
    cdef int i
    if n < 2: return False
    for i in xrange(3, int(n**0.5) + 2, 2):
        if not n % i: return False
    return True

Вариант 2:

cpdef prime(int n):
    cdef int i
    if n < -1: return False
    for i in xrange(3, int(n**0.5) + 2, 2):
        if not n % i: return False
    return True

Как видно, единственная разница в строке:

if n < -1: return False

Вызывается один из вариантов этого кода из Python самым обычным образом:

for i in xrange(10000):
    result = prime(1007963447)

Проверяю только на этом числе, никаких n < 2, а тем более n < -1.

Время выполнения для каждого варианта:

Вариант 1: 1.20464787483
Вариант 2: 0.90665817260
  • Если заменить строку if n < 2: return False на if False: return или if n < 0: pass, время выполнения опять возрастает до ~1.10sec.
  • Если заменить на if n < 0: return False или if n < 0: return, то время выполнения не меняется (~0.9sec).
  • Если вообще убрать эту строку, то время выполнения возрастает до ~1.10sec.

Пробовал разные варианты. Среда разработки, кодировки и фазы луны не влияют на результат, влияет только эта строка.

Вопрос: почему такие бессмысленные изменения ускоряют\змедляют работу кода? Или я чего-то не понимаю?

UPD. Вот наглядная разница в сгенерированных файлах "*.c": Diff Online

Единственная разница в соответствующих строках:

pyx_t_1 = ((__pyx_v_n < -1) != 0);

и

pyx_t_1 = ((__pyx_v_n < 2) != 0);

UPD2. Также добавил сравнение ассемблерных листингов (слева n<2): Assembler listing

22
  • 3
    попробуйте посмотреть полученный C-код 6 сен 2015 в 7:27
  • 1
    @dizballanze, хорошая идея. Добавил разницу между сгенерированными файлами.
    – anatolii
    6 сен 2015 в 10:31
  • 2
    Возможно, компилятор как-то оптимизирует код, предполагая, что если по условию n<2 происходит выход, то в цикл попадают только положительные n. Попробуйте вывести ассемблерный листинг и сравнить )
    – insolor
    6 сен 2015 в 19:18
  • 2
    что происходит, если использовать unsigned тип для n, i?
    – jfs
    7 сен 2015 в 20:00
  • 1
    в сторону: если необходимо отфильтровать простые числа из какого-либо диапазона, то можно использовать решето Эратосфена -- простой и эффективный алгоритм (или для больших чисел решето Аткина). Если отдельные числа хочется проверить, то Тест Миллера — Рабина является эффективным решением.
    – jfs
    7 сен 2015 в 20:08

2 ответа 2

26

В этом вопросе сразу бросается в глаза то, что на результаты бенчмарка влияет константа, работающая за пределами цикла. При наличии цикла, длинной около sqrt(1007963447), ничто за его пределами не должно сколь-нибудь заметно влиять на результат (код довольно прозрачен и возможные сторонние эффекты почти исключены).

Я провел небольшое расследование и обнаружил что ассемблерные листинги обоих версий довольно сильно отличаются как раз внутри цикла на месте операции взятия остатка деления. Вместо двух инструкций в быстрой версии:

idivl   %esi
testl   %edx, %edx

В медленной версии присутствует целый кусок кода:

idivl   %esi
movl    %edx, %esi
xorl    %ecx, %esi
shrl    $31, %esi
testl   %edx, %edx
setne   %dil
andl    %edi, %esi
imull   %ecx, %esi
addq    $2, %rcx
addl    %esi, %edx

Среди прочего тут присутствует относительно "тяжелая" операция умножения imull. Видимо, именно этот кусок ответственен за разницу в скоростях на бенчмарке. На появление этого куска влияет значение константы с которой в исходнике сравнивается переменная n совсем в другом месте, выше по тексту за пределами цикла.

Вот что я выяснил:

Интересное поведение компилятора является следствием действия нескольких факторов:

  1. Особенность работы оператора % на python. Он призван обеспечивать тождество x == (x//y)*y + (x%y), то есть знак частного соответствует знаку делителя (второго операнда), что противоречит стандарту C. Такое поведение не просто реализуется на x86 архитектуре и на каждую инструкцию idiv приходится вставлять дополнительный код на проверку отритцательных операндов и корректировку результата. Cython поумолчанию также следует "питоновому" стандарту.

  2. Особенность генерации кода Cython, при которой простые арифметические операции в некоторых случаях реализованы как inline фунций, что, впрочем, не сильно сказывается на производительности по причине (3). Например, "питоновое" взятие остатка деления реализовано через вызов __Pyx_mod_int.

  3. На этапе компиляции в машинный код происходит чудо: Мощный оптимизатор gcc снасначала раскручивает inline фунции, потом анализирует все условия и перерассчитывает типы данных и математические области определения каждой переменной на каждой ветке алгоритма. Например, переменная n объявленная в коде как int, после прохождения ветвления на условии if (n < 0) return; дальше становится ограниченной областью определения [0; INT_MAX], т.е. фактически беззнаковой. При выполнении инструкции idiv область определения частного и остатка также можно рассчитать зная области определения делимого и делителя. Остаток, в нашем случае, также попадает в [0; INT_MAX] и все дальнейшие проверки на неотрицательность и идущие от них ветки алгоритма просто удаляются как unreachable code. В __Pyx_mod_int происходит как раз такая проверка с последующий корректировкой остатка (в случае отрицательного). Поэтому наличие/отсутствие всего этого куска в скомпилированном коде полностью зависит от значения константы с которой сравнивается переменная n выше по тексту. Условие n >= -1 не гарантирует неотрицательности остатка и проверка/корректировка из __Pyx_mod_int выполняется, но n >= 0 - гарантирует неотрицательность и функция взятия остатка сводится почти к одной инструкции процессора - idiv.

Хорошей новостью является то, что поведение Cython в отношении следования "питоновым" стандартам деления и взятия остатка можно легко переопределить. Для этого надо поставить декоратор @cython.cdivision(True) перед функцией или в сверху в заголовке модуля (перед первой строкой) вставить:

#!python
#cython: cdivision=True

Можно замерить скорость и убедится, что в этом случае остаток деления будет работает одинаково быстро вне зависимости от контекста. Операция % будет вести себя по С стандарту, компилироваться в одну процессорную инструкцию и __Pyx_mod_int не будет даже появляться в *.c исходниках на выходе Cython-компиляции.

Подробнее об этом от авторов Cython можно почитать в CEP 516 - Division Semantics.

2
  • 3
    Отличное исследование, особенно для первого ответа!
    – VladD
    25 окт 2015 в 18:37
  • 1
    кратко: Cython реализует Python семантику для % (modulo), которая компилируется в неэффективный код по сравнению с C % (remainder). Для положительных чисел обе операции совпадают и gcc способен сгенерировать эффективный код. gcc "умный" и if n < 2: return False (С аналог) перед циклом достаточны для него чтобы определить что n всегда положительно и поэтому генерируется быстрый код. if n < -1: return False разрешает отрицательные значения и поэтому медленный более общий код генерируется.
    – jfs
    26 окт 2015 в 18:56
2

Рекомендую использовать модуль dis для получения байт-кода Пайтон. https://docs.python.org/3.4/library/dis.html В нем Вы увидите разницу, я полагаю. Само собой оптимизация может проходить и на стадии компиляции при одинаковом байт-коде Пайтон.

1
  • Постарайтесь писать более развернутые ответы. Поясните, на чем основано ваше утверждение? 21 сен 2015 в 14:08

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.