Является ли умножение и деление с использованием операторов сдвига в C на самом деле быстрее?

Умножение и разделение могут быть достигнуты с использованием битовых операторов, например

i*2 = i<<1 i*3 = (i<<1) + i; i*10 = (i<<3) + (i<<1) 

и так далее.

Действительно ли быстрее использовать say (i<<3)+(i<<1) чтобы умножить на 10, чем непосредственно на i*10 ? Есть ли какие-либо входные данные, которые нельзя размножать или разделять таким образом?

    Короткий ответ: Скорее.

    Длинный ответ: у вашего компилятора есть оптимизатор, который знает, как умножаться так быстро, как ваша целевая архитектура процессора способна. Лучше всего сказать компилятору свое намерение четко (т.е. i * 2, а не i << 1), и пусть оно решит, какая самая быстрая последовательность сборки / машинного кода. Даже возможно, что сам процессор реализовал инструкцию умножения как последовательность сдвигов и добавлений в микрокод.

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

    Только конкретная точка измерения: много лет назад я сравнивал две версии своего алгоритма хеширования:

     unsigned hash( char const* s ) { unsigned h = 0; while ( *s != '\0' ) { h = 127 * h + (unsigned char)*s; ++ s; } return h; } 

    а также

     unsigned hash( char const* s ) { unsigned h = 0; while ( *s != '\0' ) { h = (h << 7) - h + (unsigned char)*s; ++ s; } return h; } 

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

    Обратите внимание, что это было что-то вроде 15 лет назад. Надеюсь, компиляторы только улучшились с тех пор, так что вы можете в значительной степени рассчитывать на то, что компилятор делает правильные вещи, возможно, лучше, чем вы могли. (Кроме того, причина, по которой код выглядит так C'ish, потому что это было более 15 лет назад. Я бы, очевидно, использовал std::string и iteratorы сегодня.)

    В дополнение ко всем остальным хорошим ответам здесь, позвольте мне указать еще одну причину не использовать сдвиг, когда вы имеете в виду разделить или размножить. Я никогда не видел, чтобы кто-то вводил ошибку, забывая о относительном преимуществе умножения и добавления. Я видел ошибки, введенные, когда программисты-программисты забывали, что «умножение» через сдвиг логически является умножением, но не синтаксически с тем же приоритетом, что и умножение. x * 2 + z и x << 1 + z очень разные!

    Если вы работаете с числами, используйте арифметические операторы типа + - * / % . Если вы работаете с массивами битов, используйте операторы бит twiddling, такие как & ^ | >> & ^ | >> . Не смешивайте их; выражение, которое имеет как бит, так и арифметику, является ошибкой, ожидающей появления.

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

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

    Действительно ли быстрее использовать say (i << 3) + (i << 1), чтобы умножить на 10, чем непосредственно на i * 10?

    Это может быть или не быть на вашей машине – если вам интересно, измерьте в своем реальном использовании.

    Пример исследования – от 486 до ядра i7

    Бенчмаркинг очень трудно сделать значимо, но мы можем посмотреть на несколько фактов. С http://www.penguin.cz/~literakl/intel/s.html#SAL и http://www.penguin.cz/~literakl/intel/i.html#IMUL мы получаем представление о тактовых тактах x86 необходимых для арифметического сдвига и умножения. Скажем, мы придерживаемся «486» (самый новый из перечисленных), 32-битных регистров и сразу же, IMUL занимает 13-42 цикла и IDIV 44. Каждая SAL занимает 2 и добавляет 1, поэтому даже с несколькими из них, как победитель.

    В эти дни с kernelм i7:

    (от http://software.intel.com/en-us/forums/showthread.php?t=61481 )

    Задержка составляет 1 цикл для целочисленного сложения и 3 цикла для целочисленного умножения . Вы можете найти задержки и скорость в Приложении C «Справочного руководства по оптимизации архитектуры Intel® 64 и IA-32», которое находится по адресу http://www.intel.com/products/processor/manuals/ .

    (из некоторых выпусков Intel)

    Используя SSE, Core i7 может выпускать одновременные команды добавления и умножения, что приводит к пиковой скорости 8 операций с плавающей запятой (FLOP) за такт

    Это дает вам представление о том, как далеко продвинулись. Оптимизация мелочей – как бит сдвига по сравнению с * -, которая была воспринята всерьез даже в 90-е годы, сейчас устарела. Бит-сдвиг по-прежнему быстрее, но для не-power-of-two mul / div к тому времени, когда вы делаете все свои смены и добавляете результаты, он медленнее снова. Затем больше инструкций означает больше ошибок кэша, больше потенциальных проблем при конвейерной обработке, больше использования временных регистров может означать больше сохранения и восстановления содержимого регистра из стека … он быстро становится слишком сложным, чтобы количественно оценить все воздействия окончательно, но они преимущественно отрицательный.

    функциональность в исходном коде и реализации

    В более общем плане на ваш вопрос помечены C и C ++. Как языки третьего поколения, они специально разработаны, чтобы скрыть детали базового набора инструкций процессора. Чтобы удовлетворить свои языковые стандарты, они должны поддерживать операции умножения и сдвига (и многие другие), даже если базовое оборудование не работает . В таких случаях они должны синтезировать требуемый результат, используя множество других инструкций. Точно так же они должны обеспечивать поддержку программного обеспечения для операций с плавающей запятой, если у CPU нет этого, и нет FPU. Современные процессоры поддерживают * и << , поэтому это может показаться абсурдно теоретическим и историческим, но важно то, что свобода выбора реализации идет в обоих направлениях: даже если у процессора есть инструкция, которая реализует операцию, запрошенную в исходном коде в в общем случае, компилятор может выбрать что-то другое, что он предпочитает, потому что это лучше для конкретного случая, с которым столкнулся компилятор.

    Примеры (с гипотетическим языком ассемблера)

     source literal approach optimised approach #define N 0 int x; .word x xor registerA, registerA x *= N; move x -> registerA move x -> registerB A = B * immediate(0) store registerA -> x ...............do something more with x............... 

    Инструкции, подобные эксклюзивным или ( xor ), не имеют отношения к исходному коду, но xor-ing ничего с собой очищает все биты, поэтому его можно использовать, чтобы установить что-то в 0. Исходный код, который подразумевает адреса памяти, может не повлечь за собой никакого использования ,

    Такие хаки использовались до тех пор, пока вокруг были компьютеры. В первые дни 3GLs, чтобы обеспечить захват разработчиков, выход компилятора должен был удовлетворить существующий хардкор-русификатор для ассемблера. сообществу, что полученный код не был медленнее, более подробным или иным образом хуже. Компиляторы быстро приняли множество отличных оптимизаций - они стали лучше централизованным хранилищем, чем мог быть любой программист на ассемблере, хотя всегда есть вероятность, что они упустит определенную оптимизацию, которая имеет решающее значение в конкретном случае - иногда люди могут орех его и нащупать что-то лучше, в то время как компиляторы просто делают, как им сказали, до тех пор, пока кто-то не вернет им это.

    Таким образом, даже если перемещение и добавление еще быстрее на каком-то конкретном оборудовании, тогда автор сценария, вероятно, разработал именно тогда, когда он будет безопасным и полезным.

    Ремонтопригодность

    Если ваши аппаратные изменения вы можете перекомпилировать, и он посмотрит на целевой процессор и сделает еще один лучший выбор, тогда как вы вряд ли когда-либо захотите вернуться к своим «оптимизациям» или перечислить, какие среды компиляции должны использовать умножение и которые должны сдвигаться. Подумайте обо всех «оптимизациях», не связанных с двумя бит-битами, написанных еще 10 лет назад, которые теперь замедляют работу кода, когда они работают на современных процессорах ...!

    К счастью, хорошие компиляторы, такие как GCC, обычно могут заменять ряд бит-сдвигов и арифметику прямым умножением, когда включена любая оптимизация (т. Е. ...main(...) { return (argc << 4) + (argc << 2) + argc; } -> imull $21, 8(%ebp), %eax ), поэтому перекомпиляция может помочь даже без исправления кода, но это не гарантируется.

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

    Общие решения и частичные решения

    Если у вас есть дополнительные знания, например, что ваш int действительно будет хранить только значения x , y и z , тогда вы сможете разработать некоторые инструкции, которые работают для этих значений, и получить ваш результат быстрее, чем когда компилятор не имеет такого понимания и нуждается в реализации, которая работает для всех значений int . Например, рассмотрите свой вопрос:

    Умножение и разделение могут быть достигнуты с помощью бит-операторов ...

    Вы проиллюстрируете умножение, но как насчет деления?

     int x; x >> 1; // divide by 2? 

    Согласно стандарту C ++ 5.8:

    -3- Значение E1 >> E2 равно E1 поправочным позициям E2. Если E1 имеет неподписанный тип, или если E1 имеет подписанный тип и неотрицательное значение, значение результата является неотъемлемой частью частного E1, деленной на величину 2, поднятую до мощности E2. Если E1 имеет подписанный тип и отрицательное значение, результирующее значение определяется реализацией.

    Таким образом, ваш сдвиг бит имеет определенный результат реализации, когда x отрицательный: он может работать не так на разных машинах. Но, / работает намного более предсказуемо. (Это может быть и совершенно несовместимым, так как разные машины могут иметь разные представления отрицательных чисел и, следовательно, разные диапазоны, даже если есть такое же количество бит, составляющих представление.)

    Вы можете сказать: «Мне все равно ... что int хранит возраст сотрудника, он никогда не может быть отрицательным». Если у вас есть такое особое понимание, то да - ваша >> безопасная оптимизация может быть передана компилятором, если вы явно не сделаете это в своем коде. Но это рискованно и редко полезно, поскольку вы не будете иметь такого понимания, и другие программисты, работающие над одним и тем же кодом, не будут знать, что вы поставили на дом некоторые необычные ожидания от данных, будет обрабатывать ... то, что кажется абсолютно безопасным изменением для них, может иметь неприятные последствия из-за вашей «оптимизации».

    Есть ли какие-либо входные данные, которые нельзя размножать или разделять таким образом?

    Да ... как упоминалось выше, отрицательные числа имеют поведение, определенное реализацией, когда «разделено» на бит-сдвиг.

    Просто попробовал на моей машине компиляцию:

     int a = ...; int b = a * 10; 

    При parsingке он производит выход:

     MOV EAX,DWORD PTR SS:[ESP+1C] ; Move a into EAX LEA EAX,DWORD PTR DS:[EAX+EAX*4] ; Multiply by 5 without shift ! SHL EAX, 1 ; Multiply by 2 using shift 

    Эта версия быстрее, чем ваш оптимизированный вручную код с чистым сдвигом и добавлением.

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

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

    На самом деле дивизионный трюк, известный как «магическое деление», действительно может дать огромные выигрыши. Опять же, вы должны сначала определить профиль, если это необходимо. Но если вы его используете, есть полезные программы, чтобы помочь вам понять, какие инструкции необходимы для одной семантики разделения. Вот пример: http://www.masm32.com/board/index.php?topic=12421.0

    Пример, который я снял с streamа OP на MASM32:

     include ConstDiv.inc ... mov eax,9999999 ; divide eax by 100000 cdiv 100000 ; edx = quotient 

    Генерирует:

     mov eax,9999999 mov edx,0A7C5AC47h add eax,1 .if !CARRY? mul edx .endif shr edx,16 

    Инструкции Shift и целочисленные умножения имеют сходную производительность на большинстве современных процессоров. В 1980-х годах команды с множественным умножением были относительно медленными, но в целом это уже не так. Целочисленные команды умножения могут иметь более высокую задержку , поэтому могут быть случаи, когда сдвиг предпочтительнее. То же самое можно сказать о случаях, когда вы можете увеличить количество задействованных блоков выполнения (хотя это может сократить оба пути).

    Целочисленное разделение по-прежнему относительно медленное, хотя использование сдвига вместо деления на мощность 2 по-прежнему является победой, и большинство компиляторов будут реализовывать это как оптимизацию. Обратите внимание, однако, что для того, чтобы эта оптимизация была действительной, дивиденд должен быть либо без знака, либо должен быть известен как положительный. Для отрицательного дивиденда сдвиг и деление не эквивалентны!

     #include  int main(void) { int i; for (i = 5; i >= -5; --i) { printf("%d / 2 = %d, %d >> 1 = %d\n", i, i / 2, i, i >> 1); } return 0; } 

    Вывод:

     5 / 2 = 2, 5 >> 1 = 2 4 / 2 = 2, 4 >> 1 = 2 3 / 2 = 1, 3 >> 1 = 1 2 / 2 = 1, 2 >> 1 = 1 1 / 2 = 0, 1 >> 1 = 0 0 / 2 = 0, 0 >> 1 = 0 -1 / 2 = 0, -1 >> 1 = -1 -2 / 2 = -1, -2 >> 1 = -1 -3 / 2 = -1, -3 >> 1 = -2 -4 / 2 = -2, -4 >> 1 = -2 -5 / 2 = -2, -5 >> 1 = -3 

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

    Это полностью зависит от целевого устройства, языка, цели и т. Д.

    Пиксельный хруст в драйвере видеокарты? Очень вероятно, да!

    .NET бизнес-приложение для вашего отдела? Абсолютно нет причин даже смотреть на это.

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

    Не делайте этого, если вам абсолютно не нужно, и ваш код требует изменения, а не умножения / деления.

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

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

    Насколько мне известно, в некоторых машинах для умножения может потребоваться от 16 до 32 машинных циклов. Итак, да , в зависимости от типа машины операторы с битрейтом быстрее, чем умножение / деление.

    Однако у определенной машины есть свой математический процессор, который содержит специальные инструкции для умножения / деления.

    Я согласен с отмеченным ответом Дрю Холла. Однако ответ мог бы использовать некоторые дополнительные примечания.

    Для подавляющего большинства разработчиков программного обеспечения процессор и компилятор больше не имеют отношения к вопросу. Большинство из нас далеко за пределами 8088 и MS-DOS. Возможно, это относится только к тем, кто все еще разрабатывает встроенные процессоры …

    В моей программной компании Math (add / sub / mul / div) следует использовать для всей математики. Хотя Shift следует использовать при преобразовании между типами данных, например. ushort to byte при n >> 8, а не n / 256.

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

    Тест Python, выполняющий то же умножение 100 миллионов раз по тем же случайным числам.

     >>> from timeit import timeit >>> setup_str = 'import scipy; from scipy import random; scipy.random.seed(0)' >>> N = 10*1000*1000 >>> timeit('x=random.randint(65536);', setup=setup_str, number=N) 1.894096851348877 # Time from generating the random #s and no opperati >>> timeit('x=random.randint(65536); x*2', setup=setup_str, number=N) 2.2799630165100098 >>> timeit('x=random.randint(65536); x << 1', setup=setup_str, number=N) 2.2616429328918457 >>> timeit('x=random.randint(65536); x*10', setup=setup_str, number=N) 2.2799630165100098 >>> timeit('x=random.randint(65536); (x << 3) + (x<<1)', setup=setup_str, number=N) 2.9485139846801758 >>> timeit('x=random.randint(65536); x // 2', setup=setup_str, number=N) 2.490908145904541 >>> timeit('x=random.randint(65536); x / 2', setup=setup_str, number=N) 2.4757170677185059 >>> timeit('x=random.randint(65536); x >> 1', setup=setup_str, number=N) 2.2316000461578369 

    Таким образом, при выполнении сдвига, а не умножения / деления на две пары в python, наблюдается небольшое улучшение (~ 10% для деления, ~ 1% для умножения). Если это не сила двух, то, вероятно, произойдет значительное замедление.

    Опять же, эти # будут меняться в зависимости от вашего процессора, ваш компилятор (или интерпретатор – в python для простоты).

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

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

    Ниже приведен пример кода c ++, который может выполнять более быстрое деление на 64 бит «Умножение на ответное». Как числитель, так и знаменатель должны быть ниже определенного порога. Обратите внимание, что он должен быть скомпилирован для использования 64-битных инструкций на самом деле быстрее обычного деления.

     #include  #include  static const unsigned s_bc = 32; static const unsigned long long s_p = 1ULL << s_bc; static const unsigned long long s_hp = s_p / 2; static unsigned long long s_f; static unsigned long long s_fr; static void fastDivInitialize(const unsigned d) { s_f = s_p / d; s_fr = s_f * (s_p - (s_f * d)); } static unsigned fastDiv(const unsigned n) { return (s_f * n + ((s_fr * n + s_hp) >> s_bc)) >> s_bc; } static bool fastDivCheck(const unsigned n, const unsigned d) { // 32 to 64 cycles latency on modern cpus const unsigned expected = n / d; // At least 10 cycles latency on modern cpus const unsigned result = fastDiv(n); if (result != expected) { printf("Failed for: %u/%u != %u\n", n, d, expected); return false; } return true; } int main() { unsigned result = 0; // Make sure to verify it works for your expected set of inputs const unsigned MAX_N = 65535; const unsigned MAX_D = 40000; const double ONE_SECOND_COUNT = 1000000000.0; auto t0 = std::chrono::steady_clock::now(); unsigned count = 0; printf("Verifying...\n"); for (unsigned d = 1; d <= MAX_D; ++d) { fastDivInitialize(d); for (unsigned n = 0; n <= MAX_N; ++n) { count += !fastDivCheck(n, d); } } auto t1 = std::chrono::steady_clock::now(); printf("Errors: %u / %u (%.4fs)\n", count, MAX_D * (MAX_N + 1), (t1 - t0).count() / ONE_SECOND_COUNT); t0 = t1; for (unsigned d = 1; d <= MAX_D; ++d) { fastDivInitialize(d); for (unsigned n = 0; n <= MAX_N; ++n) { result += fastDiv(n); } } t1 = std::chrono::steady_clock::now(); printf("Fast division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT); t0 = t1; count = 0; for (unsigned d = 1; d <= MAX_D; ++d) { for (unsigned n = 0; n <= MAX_N; ++n) { result += n / d; } } t1 = std::chrono::steady_clock::now(); printf("Normal division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT); getchar(); return result; } 

    Я думаю, что в одном случае, который вы хотите размножить или разделить на две силы, вы не ошибетесь в использовании операторов бит-сдвига, даже если компилятор преобразует их в MUL / DIV, потому что некоторые микрокоды процессоров (действительно, макро) в любом случае, поэтому для тех случаев вы достигнете улучшения, особенно если сдвиг больше 1. Или более явно, если у ЦП нет операторов с битрейтом, это будет MUL / DIV в любом случае, но если процессор имеет операторы с битрейтом, вы избегаете ветви микрокода, и это меньше инструкций.

    Я сейчас пишу код, который требует много операций удвоения / сокращения пополам, потому что он работает с плотным двоичным деревом, и есть еще одна операция, которая, как я подозреваю, может быть более оптимальной, чем добавление – левая (мощность двух умножить ) сдвиг с добавлением. This can be replaced with a left shift and an xor if the shift is wider than the number of bits you want to add, easy example is (i<<1)^1, which adds one to a doubled value. This does not of course apply to a right shift (power of two divide) because only a left (little endian) shift fills the gap with zeros.

    In my code, these multiply/divide by two and powers of two operations are very intensively used and because the formulae are quite short already, each instruction that can be eliminated can be a substantial gain. If the processor does not support these bitshift operators, no gain will happen but neither will there be a loss.

    Also, in the algorithms I am writing, they visually represent the movements that occur so in that sense they are in fact more clear. The left hand side of a binary tree is bigger, and the right is smaller. As well as that, in my code, odd and even numbers have a special significance, and all left-hand children in the tree are odd and all right hand children, and the root, are even. In some cases, which I haven’t encountered yet, but may, oh, actually, I didn’t even think of this, x&1 may be a more optimal operation compared to x%2. x&1 on an even number will produce zero, but will produce 1 for an odd number.

    Going a bit further than just odd/even identification, if I get zero for x&3 I know that 4 is a factor of our number, and same for x%7 for 8, and so on. I know that these cases have probably got limited utility but it’s nice to know that you can avoid a modulus operation and use a bitwise logic operation instead, because bitwise operations are almost always the fastest, and least likely to be ambiguous to the compiler.

    I am pretty much inventing the field of dense binary trees so I expect that people may not grasp the value of this comment, as very rarely do people want to only perform factorisations on only powers of two, or only multiply/divide powers of two.

    Давайте будем гением компьютера.