Как бессмысленное изменение оператора проверки влияет на скорость кода Cython?

У меня есть следующие два варианта кода для 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
    

Ответы

Ответ 1

В этом вопросе сразу бросается в глаза то, что на результаты бенчмарка влияет константа
работающая за пределами цикла. При наличии цикла, длинной около 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 совсем в другом месте, выше по тексту за пределами цикла.

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

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


Особенность работы оператора % на python. Он призван обеспечивать тождество x =
(x//y)*y + (x%y), то есть знак частного соответствует знаку делителя (второго операнда)
что противоречит стандарту C. Такое поведение не просто реализуется на x86 архитектуре и на каждую инструкцию idiv приходится вставлять дополнительный код на проверку отритцательных операндов и корректировку результата. Cython поумолчанию также следует "питоновому" стандарту.
Особенность генерации кода Cython, при которой простые арифметические операции 
некоторых случаях реализованы как inline фунций, что, впрочем, не сильно сказывается на производительности по причине (3). Например, "питоновое" взятие остатка деления реализовано через вызов __Pyx_mod_int.
На этапе компиляции в машинный код происходит чудо: Мощный оптимизатор gcc снасначал
раскручивает inline фунции, потом анализирует все условия и перерассчитывает типы данны
и математические области определения каждой переменной на каждой ветке алгоритма. Например
переменная n объявленная в коде как int, после прохождения ветвления на условии if (
< 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

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