Скорости << >> умножения и деления

Вы можете использовать <<для умножения и >>деления чисел в Python, когда я их рассчитываю, я нахожу, используя способ двоичного сдвига, это в 10 раз быстрее, чем деление или умножение обычным способом.

Почему используется <<и >>намного быстрее, чем *и /?

Какие процессы за сценой происходят *и /так медленно?

Давайте посмотрим на две маленькие программы на C, которые делают сдвиг и деление.

#include <stdlib.h>

int main(int argc, char* argv[]) {
        int i = atoi(argv[0]);
        int b = i << 2;
}

#include <stdlib.h>

int main(int argc, char* argv[]) {
        int i = atoi(argv[0]);
        int d = i / 4;
}

Затем они скомпилированы, gcc -Sчтобы увидеть, какой будет фактическая сборка.

С версией битового сдвига, от вызова atoiдо возврата:

    callq   _atoi
    movl    $0, %ecx
    movl    %eax, -20(%rbp)
    movl    -20(%rbp), %eax
    shll    $2, %eax
    movl    %eax, -24(%rbp)
    movl    %ecx, %eax
    addq    $32, %rsp
    popq    %rbp
    ret

Пока делят версию:

    callq   _atoi
    movl    $0, %ecx
    movl    $4, %edx
    movl    %eax, -20(%rbp)
    movl    -20(%rbp), %eax
    movl    %edx, -28(%rbp)         ## 4-byte Spill
    cltd
    movl    -28(%rbp), %r8d         ## 4-byte Reload
    idivl   %r8d
    movl    %eax, -24(%rbp)
    movl    %ecx, %eax
    addq    $32, %rsp
    popq    %rbp
    ret

Просто взглянув на это, в разделенной версии есть еще несколько инструкций по сравнению со сдвигом битов.

Ключ, что они делают?

В версии с битовым сдвигом ключевая инструкция - shll $2, %eaxлогический сдвиг влево - есть разрыв, а все остальное - просто перемещение значений.

В версии с делением вы можете увидеть idivl %r8d- но чуть выше это cltd(конвертировать long в double) и некоторую дополнительную логику вокруг разлива и перезагрузки. Эта дополнительная работа, зная, что мы имеем дело с математикой, а не с битами, часто необходима, чтобы избежать различных ошибок, которые могут возникнуть при выполнении только битовой математики.

Давайте сделаем некоторое быстрое умножение:

#include <stdlib.h>

int main(int argc, char* argv[]) {
    int i = atoi(argv[0]);
    int b = i >> 2;
}

#include <stdlib.h>

int main(int argc, char* argv[]) {
    int i = atoi(argv[0]);
    int d = i * 4;
}

Вместо того, чтобы проходить через все это, есть еще одна строка:

$ diff mult.s bit.s
24c24
> 2 доллара, eax
---
<sarl $ 2,% eax

Здесь компилятор смог определить, что математика может быть выполнена со сдвигом, однако вместо логического сдвига он выполняет арифметический сдвиг. Разница между ними была бы очевидна, если бы мы запустили это - sarlсохраняет знак. Так что -2 * 4 = -8пока что shllнет.

Давайте посмотрим на это в быстром Perl-скрипте:

#!/usr/bin/perl

$foo = 4;
print $foo << 2, "\n";
print $foo * 4, "\n";

$foo = -4;
print $foo << 2, "\n";
print $foo * 4, "\n";

Вывод:

16
16
18446744073709551600
-16

Гм ... -4 << 2это 18446744073709551600не совсем то, что вы, вероятно, ожидаете, имея дело с умножением и делением. Это правильно, но не целочисленное умножение.

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

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

Например, верно, что умножение является более сложной операцией для реализации на аппаратном уровне, но это не всегда приводит к замедлению . Как оказалось, addтакже значительно сложнее в реализации, чем xor(или вообще любая битовая операция), но add(и sub) обычно получают достаточно транзисторов, предназначенных для их работы, которые в итоге оказываются такими же быстрыми, как битовые операторы. Таким образом, вы не можете просто рассматривать сложность аппаратной реализации как руководство по скорости.

Итак, давайте подробно рассмотрим сдвиг по сравнению с «полными» операторами, такими как умножение и сдвиг.

перевод

Почти на всех аппаратных средствах смещение на постоянную величину (т. Е. На величину, которую компилятор может определить во время компиляции) происходит быстро . В частности, это обычно происходит с задержкой одного цикла и с пропускной способностью 1 за цикл или лучше. На некоторых аппаратных средствах (например, на некоторых микросхемах Intel и ARM) некоторые сдвиги на константу могут даже быть «свободными», поскольку они могут быть встроены в другую инструкцию ( leaна Intel - специальные возможности сдвига первого источника в ARM).

Сдвиг на переменную величину - больше серой области. На старом оборудовании это иногда было очень медленно, и скорость менялась от поколения к поколению. Например, в начальном выпуске Intel P4 переключение на переменную величину было общеизвестно медленным - требовало времени, пропорционального величине смены! На этой платформе использование умножений для замены смен может быть выгодным (т. Е. Мир перевернулся). На предыдущих чипах Intel, а также на последующих поколениях переключение на переменную величину не было столь болезненным.

На современных чипах Intel сдвиг на переменную величину не особенно быстрый, но и не страшный. Архитектура x86 затруднена, когда дело доходит до переменных сдвигов, потому что они определили операцию необычным образом: значения сдвигов, равные 0, не изменяют флаги условия, но все другие сдвиги делают. Это препятствует эффективному переименованию регистра флагов, так как это не может быть определено, пока сдвиг не выполнит, должны ли последующие инструкции читать коды условий, записанные сдвигом, или некоторую предыдущую инструкцию. Кроме того, сдвиги записывают только часть регистра флагов, что может привести к частичной остановке флагов.

В результате на последних архитектурах Intel сдвиг на переменную величину занимает три «микрооперации», в то время как большинство других простых операций (сложение, побитовые операции, даже умножение) занимают только 1. Такие сдвиги могут выполняться не чаще, чем раз в 2 цикла. ,

умножение

Тенденция в современном оборудовании для настольных компьютеров и ноутбуков - сделать умножение быстрой операцией. На последних чипах Intel и AMD фактически каждое цикл может выполняться по одному умножению (мы называем это обратной пропускной способностью ). Латентность , однако, умножения 3 циклов. Таким образом, это означает, что вы получаете результат любого заданного умножения 3 цикла после его запуска, но вы можете начинать новое умножение каждый цикл. Какое значение (1 цикл или 3 цикла) является более важным, зависит от структуры вашего алгоритма. Если умножение является частью цепочки критических зависимостей, важна задержка. Если нет, взаимная пропускная способность или другие факторы могут быть более важными.

Ключевым моментом для них является то, что на современных чипах для ноутбуков (или лучше) умножение - это быстрая операция, и, вероятно, она будет быстрее, чем последовательность команд из 3 или 4, которую компилятор выдаст, чтобы «получить округление» для снижения нагрузки. Для переменных смещений в Intel, как правило, также предпочтительнее умножение из-за вышеупомянутых проблем.

На меньших платформах форм-фактора умножение может все еще быть медленным, так как создание полного и быстрого 32-разрядного или особенно 64-разрядного умножителя требует много транзисторов и мощности. Если кто-то может заполнить подробности о производительности умножения на последних мобильных чипах, это будет очень цениться.

Делить

Разделение - это более сложная операция с аппаратной точки зрения, чем умножение, и оно также гораздо реже встречается в реальном коде - это означает, что для него, вероятно, выделено меньше ресурсов. Тенденция в современных чипах по-прежнему направлена ​​на более быстрые делители, но даже современные топовые чипы занимают 10-40 циклов, чтобы разделить, и они только частично конвейерны. В целом, 64-битные деления даже медленнее, чем 32-битные. В отличие от большинства других операций, деление может занять разное количество циклов в зависимости от аргументов.

Избегайте делений и заменяйте их на сдвиги (или пусть компилятор сделает это, но вам может понадобиться проверить сборку), если можете!

BINARY_LSHIFT и BINARY_RSHIFT являются алгоритмически более простыми процессами, чем BINARY_MULTIPLY и BINARY_FLOOR_DIVIDE, и могут занимать меньше тактов. То есть, если у вас есть какое-либо двоичное число и вам нужно сдвинуть биты на N, все, что вам нужно сделать, это сдвинуть цифры на это количество пробелов и заменить их нулями. Двоичное умножение в целом более сложное , хотя такие методы, как множитель Дадды, делают его довольно быстрым.

Конечно, оптимизирующий компилятор может распознать случаи, когда вы умножаете / делите на степени два и заменяете соответствующим сдвигом влево / вправо. Глядя на дизассемблированный байт-код, Python явно не делает этого:

>>> dis.dis(lambda x: x*4)
  1           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (4)
              6 BINARY_MULTIPLY     
              7 RETURN_VALUE        

>>> dis.dis(lambda x: x<<2)
  1           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (2)
              6 BINARY_LSHIFT       
              7 RETURN_VALUE        


>>> dis.dis(lambda x: x//2)
  1           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (2)
              6 BINARY_FLOOR_DIVIDE 
              7 RETURN_VALUE        

>>> dis.dis(lambda x: x>>1)
  1           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (1)
              6 BINARY_RSHIFT       
              7 RETURN_VALUE        

Тем не менее, на моем процессоре я нахожу, что умножение и сдвиг влево / вправо имеют одинаковую синхронизацию, а деление по полу (на степень два) медленнее примерно на 25%:

>>> import timeit

>>> timeit.repeat("z=a + 4", setup="a = 37")
[0.03717184066772461, 0.03291916847229004, 0.03287005424499512]

>>> timeit.repeat("z=a - 4", setup="a = 37")
[0.03534698486328125, 0.03207516670227051, 0.03196907043457031]

>>> timeit.repeat("z=a * 4", setup="a = 37")
[0.04594111442565918, 0.0408930778503418, 0.045324087142944336]

>>> timeit.repeat("z=a // 4", setup="a = 37")
[0.05412912368774414, 0.05091404914855957, 0.04910898208618164]

>>> timeit.repeat("z=a << 2", setup="a = 37")
[0.04751706123352051, 0.04259490966796875, 0.041903018951416016]

>>> timeit.repeat("z=a >> 2", setup="a = 37")
[0.04719185829162598, 0.04201006889343262, 0.042105913162231445]