Как бессмысленное изменение оператора проверки влияет на скорость кода 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

Ответ

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