Ускорение операций по модулю в CPython

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

Время работы PyPy больше похоже на то, что необходимо для 10 ^ 8 операций по модулю с C-целыми числами, поэтому он, вероятно, может использовать JIT, который не требует больших накладных расходов, и, таким образом, мы можем видеть ускорение арифметических операций. .

Возможный способ уменьшить накладные расходы — использовать Cython (здесь мое исследование того, как Cython может помочь уменьшить интерпретатор и диспетчерские-накладные расходы), и работает из коробки для генераторов:

%%cython
def gen_cy1(int a=783):
    while True:
        a = (a * 48271) % 0x7fffffff
        yield a
        
def gen_cy2(int a=783):
    while True:
        a *= 48271
        a = (a & 0x7fffffff) + (a >> 31)
        a = (a & 0x7fffffff) + (a >> 31)
        yield a

Я использую следующую функцию для тестирования:

def run(gen,N):
    for i in range(N): next(gen)

и тесты показывают:

N=10**6
%timeit run(gen1(),N)   #  246 ms
%timeit run(gen2(),N)   #  387 ms
%timeit run(gen_cy1(),N)   # 114 ms
%timeit run(gen_cy2(),N)   # 107 ms

Обе версии Cython одинаково быстры (и несколько быстрее, чем оригинал), потому что больше операций на самом деле не требует больших накладных расходов, поскольку арифметические операции выполняются с C-int, а не с Python-ints.

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

Просто чтобы дать представление, что было бы возможно, если бы не использовались Python-генераторы - функции, которые генерируют все числа (но не конвертируют их в Python-объекты и, следовательно, без накладных расходов):

%%cython
def gen_last_cy1(int n, int a=783):
    cdef int i
    for i in range(n):
        a = (a * 48271) % 0x7fffffff
    return a

def gen_last_cy2(int n, int a=783):
    cdef int i
    for i in range(n):
        a *= 48271
        a = (a & 0x7fffffff) + (a >> 31)
        a = (a & 0x7fffffff) + (a >> 31)
    return a

привести к следующим таймингам:

N=10**6
%timeit gen_last_cy1(N)  # 7.21 ms
%timeit gen_last_cy2(N)  # 2.59 ms

Это означает, что можно сэкономить более 90% рабочего времени, если генератор не используется!

Я был немного удивлен, что измененная вторая версия превзошла оригинальную первую. Обычно C-компиляторы не выполняют операции по модулю напрямую, а сами используют битовые трюки, если это возможно. Но здесь приемы Си-компилятора уступают по крайней мере на моей машине.

Ассемблер (доступен на gotbold.org), сгенерированный gcc (-O2) для оригинальной версии:

        imull   $48271, %edi, %edi
        movslq  %edi, %rdx
        movq    %rdx, %rax
        salq    $30, %rax
        addq    %rdx, %rax
        movl    %edi, %edx
        sarl    $31, %edx
        sarq    $61, %rax
        subl    %edx, %eax
        movl    %eax, %edx
        sall    $31, %edx
        subl    %eax, %edx
        movl    %edi, %eax
        subl    %edx, %eax

как видно, div нет.

А вот ассемблер для второй версии (с гораздо меньшим количеством операций):

        imull   $48271, %edi, %eax
        movl    %eax, %edx
        sarl    $31, %eax
        andl    $2147483647, %edx
        addl    %edx, %eax
        movl    %eax, %edx
        sarl    $31, %eax
        andl    $2147483647, %edx
        addl    %edx, %eax

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