Умножение и деление может быть достигнуто с помощью битовых операторов, например
i*2 = i<<1
i*3 = (i<<1) + i;
i*10 = (i<<3) + (i<<1)
и так далее.
Действительно ли быстрее использовать скажем (i<<3)+(i<<1)
умножить на 10, чем i*10
напрямую? Есть ли какие-либо входные данные, которые не могут быть умножены или разделены таким образом?
Ответы:
Краткий ответ: маловероятно.
Длинный ответ: в вашем компиляторе есть оптимизатор, который знает, как умножать настолько быстро, насколько позволяет ваша целевая архитектура процессора. Лучше всего четко сообщить компилятору о своем намерении (т.е. i * 2, а не i << 1) и позволить ему решить, какая последовательность сборки / машинного кода самая быстрая. Возможно даже, что сам процессор реализовал инструкцию умножения в виде последовательности сдвигов и добавлений в микрокоде.
Итог - не тратьте много времени на беспокойство по этому поводу. Если вы хотите сдвинуться, сдвиньтесь. Если вы хотите умножить, умножьте. Делайте то, что семантически ясно - ваши коллеги поблагодарят вас позже. Или, более вероятно, прокляну вас позже, если вы поступите иначе.
источник
gcc -O3
x86,return i*10
чем из shift-версии . Как человек, который много смотрит на результаты компиляции (см. Многие из моих ответов по asm / оптимизация), я не удивлен. Есть моменты, когда это может помочь держать компилятор одним способом , но это не один из них. GCC хорош в целочисленной математике, потому что это важно.millis() >> 2
; Было бы слишком много просить просто разделить?i / 32
vsi >> 5
иi / 4
vsi >> 2
на gcc для cortex-a9 (который не имеет аппаратного разделения) с оптимизацией -O3, и результирующая сборка была точно такой же. Сначала я не любил использовать деления, но это описывает мое намерение и результат тот же.Просто конкретная точка измерения: много лет назад я проверил две версии моего алгоритма хеширования:
и
На каждой машине, на которой я тестировал, первая была, по крайней мере, так же быстро, как и вторая. Несколько удивительно, но иногда это было быстрее (например, на Sun Sparc). Когда аппаратное обеспечение не поддерживало быстрое умножение (и большинство не поддерживало тогда), компилятор преобразовывал умножение в соответствующие комбинации сдвигов и добавления / саб. И поскольку он знал конечную цель, он мог иногда делать это в меньшем количестве инструкций, чем когда вы явно писали сдвиги и дополнения / сабы.
Обратите внимание, что это было что-то вроде 15 лет назад. Надеюсь, с тех пор компиляторы стали лучше, так что вы можете в значительной степени рассчитывать на то, что компилятор сделает правильные вещи, возможно, лучше, чем вы могли бы. (Кроме того, причина, по которой код выглядит так C'ish, в том, что это было более 15 лет назад. Я бы
std::string
сегодня использовал итераторы.)источник
В дополнение ко всем другим хорошим ответам здесь, позвольте мне указать еще одну причину не использовать сдвиг, когда вы имеете в виду делить или умножать. Я никогда не видел, чтобы кто-то вводил ошибку, забывая об относительном приоритете умножения и сложения. Я видел ошибки, возникающие, когда программисты по техническому обслуживанию забыли, что «умножение» посредством сдвига логически является умножением, но не синтаксически того же приоритета, что и умножение.
x * 2 + z
иx << 1 + z
очень разные!Если вы работаете с числами, используйте такие арифметические операторы, как
+ - * / %
. Если вы работаете с массивами битов, используйте операторы битового переворота, например& ^ | >>
. Не смешивайте их; Выражение, в котором есть как немного сложное, так и арифметическое, является ошибкой, ожидающей своего появления.источник
Это зависит от процессора и компилятора. Некоторые компиляторы уже оптимизируют код таким образом, другие - нет. Таким образом, вы должны проверять каждый раз, когда ваш код должен быть оптимизирован таким образом.
Если вам не нужно отчаянно оптимизировать, я не зашифрую свой исходный код только для того, чтобы сохранить инструкцию по сборке или цикл процессора.
источник
>>
оператор работает быстрее,/
и, если знаковые значения могут быть отрицательными, он часто также семантически превосходит их. Если нужно получить значение, котороеx>>4
было бы произведено, это намного яснееx < 0 ? -((-1-x)/16)-1 : x/16;
, и я не представляю, как компилятор может оптимизировать это последнее выражение до чего-то приятного.Это может быть или не быть на вашей машине - если вам все равно, измерьте в реальных условиях использования.
Тематическое исследование - от 486 до Core 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, так что даже с несколькими из них вместе выглядят поверхностно как победитель.
В эти дни с ядром i7:
(из http://software.intel.com/en-us/forums/showthread.php?t=61481 )
(из какого-то интеллара)
Это дает вам представление о том, как далеко все зашло. Оптимизация мелочи - как сдвиг битов по сравнению с
*
- к которым серьезно относились даже в 90-е годы, сейчас просто устарели. Сдвиг битов все еще быстрее, но для не-степени двух муль / дел к тому времени, когда вы делаете все свои смены и добавляете результаты, это снова медленнее. Затем, больше инструкций означает больше ошибок кэша, больше потенциальных проблем в конвейерной обработке, более широкое использование временных регистров может означать большее сохранение и восстановление содержимого регистра из стека ... это быстро становится слишком сложным, чтобы количественно определить все воздействия, но они преимущественно отрицательный.функциональность в исходном коде против реализации
В более общем плане, ваш вопрос помечен C и C ++. Как языки 3-го поколения, они специально разработаны, чтобы скрыть детали базового набора команд ЦП. Чтобы удовлетворить свои языковые стандарты, они должны поддерживать операции умножения и сдвига (и многие другие), даже если базовое оборудование этого не делает . В таких случаях они должны синтезировать требуемый результат, используя множество других инструкций. Точно так же они должны обеспечивать программную поддержку для операций с плавающей запятой, если в процессоре этого нет, а FPU нет. Все современные процессоры поддерживают
*
и<<
, так что это может показаться абсурдным теоретическим и историческим, но важно то, что свобода выбора реализации идет в обоих направлениях: даже если у процессора есть инструкция, которая реализует операцию, запрашиваемую в исходном коде в общем случае, компилятор может свободно выберите что-то еще, что он предпочитает, потому что это лучше для конкретного случая, с которым сталкивается компилятор.Примеры (с гипотетическим языком ассемблера)
Инструкции, такие как exclusive или (
xor
), не имеют отношения к исходному коду, но xoring что-либо само по себе очищает все биты, поэтому его можно использовать для установки чего-либо на 0. Исходный код, который подразумевает адреса памяти, может не повлечь за собой никакого использования.Такого рода хаки использовались до тех пор, пока компьютеры были рядом. В первые годы существования 3GL, чтобы обеспечить освоение разработчиками, выход компилятора должен был удовлетворять существующему хардкорному оптимизирующему руку разработчику на ассемблере. сообщество, которое произвело код, не было медленнее, более многословно или иначе хуже. Компиляторы быстро переняли много замечательных оптимизаций - они стали лучшим централизованным хранилищем, чем любой отдельный программист на языке ассемблера, хотя всегда есть шанс, что они пропустят определенную оптимизацию, которая оказывается критической в конкретном случае - люди могут иногда преуменьшить это и нащупать что-то лучшее, в то время как компиляторы просто делают, как им было сказано, пока кто-то не поделится этим опытом с ними.
Таким образом, даже если переключение и добавление по-прежнему происходит быстрее на каком-то конкретном оборудовании, тогда разработчик компилятора, вероятно, сработал именно тогда, когда это безопасно и выгодно.
Ремонтопригодность
Если ваше аппаратное обеспечение изменится, вы можете перекомпилировать его, и он будет смотреть на целевой ЦП и делать еще один лучший выбор, в то время как вы вряд ли когда-нибудь захотите пересмотреть свои «оптимизации» или перечислить, какие среды компиляции должны использовать умножение, а какие - сдвигаться. Подумайте обо всех «оптимизациях» со сдвигом битов со сдвигом в два, написанных более 10 лет назад, которые теперь замедляют код, в котором они работают, так как он работает на современных процессорах ...!
К счастью, хорошие компиляторы, такие как GCC, обычно могут заменить серию битовых сдвигов и арифметику прямым умножением, когда включена любая оптимизация (т.е.
...main(...) { return (argc << 4) + (argc << 2) + argc; }
->imull $21, 8(%ebp), %eax
), поэтому перекомпиляция может помочь даже без исправления кода, но это не гарантируется.Странный код со сдвигом битов, реализующий умножение или деление, гораздо менее выразителен, чем вы пытались достичь концептуально, поэтому другие разработчики будут смущены этим, а сбитый с толку программист с большей вероятностью введет ошибки или удалит что-то важное в попытке восстановить кажущееся здравомыслие. Если вы делаете неочевидные вещи, когда они действительно ощутимо полезны, а затем хорошо документируете их (но в любом случае не документируете другие интуитивные вещи), все будут счастливее.
Общие решения против частичных решений
Если у вас есть некоторые дополнительные знания, такие как то, что вы
int
действительно будете хранить только значенияx
,y
иz
, возможно, вы сможете выработать некоторые инструкции, которые работают с этими значениями, и получить результат быстрее, чем когда компилятор не имеет это понимание и нуждается в реализации, которая работает для всехint
ценностей. Например, рассмотрим ваш вопрос:Вы иллюстрируете умножение, но как насчет деления?
Согласно стандарту C ++ 5.8:
Таким образом, ваш битовый сдвиг имеет результат, определенный реализацией, когда
x
он отрицательный: он может не работать одинаково на разных машинах. Но/
работает гораздо более предсказуемо. (Это также может быть не вполне согласованным, поскольку разные машины могут иметь разные представления отрицательных чисел и, следовательно, разные диапазоны, даже если в представлении присутствует одинаковое количество битов.)Вы можете сказать: «Мне все равно ... это
int
хранит возраст сотрудника, он никогда не может быть отрицательным». Если у вас есть такая особая способность проникновения в суть, тогда да - ваша>>
безопасная оптимизация может быть передана компилятором, если вы явно не сделаете это в своем коде. Но это рискованно и редко полезно, так как большую часть времени у вас не будет такого понимания, и другие программисты, работающие над тем же кодом, не будут знать, что вы поставили на карту некоторые необычные ожидания данных, которые вы '' Я буду обрабатывать ... то, что кажется им абсолютно безопасным, может иметь неприятные последствия из-за вашей "оптимизации"Да ... как упомянуто выше, отрицательные числа имеют поведение, определяемое реализацией, когда они "разделены" сдвигом битов.
источник
intVal>>1
будет иметь одинаковую семантику, которая отличается от таковой,intVal/2
что иногда полезно. Если нужно вычислить переносимым образом значение, которое принесут обычные архитектурыintVal >> 1
, выражение должно быть несколько более сложным и трудным для чтения, и, скорее всего, будет генерировать существенно худший код по сравнению с тем, который был созданintVal >> 1
.Просто попробовал на моей машине компилировать это:
При разборке выдает результат:
Эта версия быстрее, чем ваш оптимизированный вручную код с чистым сдвигом и дополнением.
Вы действительно никогда не знаете, что собирается придумать компилятор, поэтому лучше просто написать нормальное умножение и позволить ему оптимизировать его так, как он хочет, за исключением очень точных случаев, когда вы знаете, что компилятор не может оптимизировать.
источник
vector<T>::size()
. Мой компилятор был довольно древним! :)Сдвиг, как правило, намного быстрее, чем умножение на уровне инструкций, но, возможно, вы тратите свое время на преждевременную оптимизацию. Компилятор вполне может выполнить эти оптимизации во время компиляции. Выполнение этого самостоятельно повлияет на читабельность и, возможно, не повлияет на производительность. Вероятно, стоит делать такие вещи, только если вы профилировали и обнаружили, что это узкое место.
На самом деле трюк с разделением, известный как «магическое разделение», может принести огромные выгоды. Опять же, вы должны сначала профиль, чтобы увидеть, если это необходимо. Но если вы его используете, есть полезные программы, которые помогут вам выяснить, какие инструкции необходимы для той же семантики деления. Вот пример: http://www.masm32.com/board/index.php?topic=12421.0
Пример, который я поднял из потока OP на MASM32:
Будет генерировать:
источник
Команды сдвига и целочисленного умножения имеют схожую производительность на большинстве современных процессоров - инструкции целочисленного умножения были относительно медленными еще в 1980-х годах, но в целом это уже не так. Команды для целочисленного умножения могут иметь большую задержку , поэтому могут быть случаи, когда сдвиг предпочтителен. То же самое относится к случаям, когда вы можете держать больше исполнительных блоков занятыми (хотя это может сократить оба пути).
Целочисленное деление все еще относительно медленное, поэтому использование сдвига вместо деления на степень 2 все еще является выигрышем, и большинство компиляторов будут реализовывать это как оптимизацию. Однако обратите внимание, что для того, чтобы эта оптимизация была действительной, дивиденд должен быть либо беззнаковым, либо должен быть известен как положительный. Для отрицательного дивиденда сдвиг и деление не эквивалентны!
Вывод:
Поэтому, если вы хотите помочь компилятору, убедитесь, что переменная или выражение в дивиденде явно без знака.
источник
Это полностью зависит от целевого устройства, языка, цели и т. Д.
Хруст пикселя в драйвере видеокарты? Очень вероятно, да!
.NET бизнес-приложение для вашего отдела? Абсолютно нет причин даже смотреть на это.
Возможно, стоит взглянуть на высокопроизводительную игру для мобильного устройства, но только после более легкой оптимизации.
источник
Не делайте этого, если только вам это абсолютно не нужно, и ваше намерение кода требует смещения, а не умножения / деления.
В обычный день - вы можете сэкономить несколько машинных циклов (или потерять, так как компилятор лучше знает, что оптимизировать), но затраты не стоят того - вы тратите время на мелкие детали, а не на реальную работу, поддерживая код труднее и ваши сотрудники будут проклинать вас.
Возможно, вам придется сделать это для вычислений с высокой нагрузкой, где каждый сохраненный цикл означает минуты времени выполнения. Но вы должны оптимизировать одно место за раз и делать тесты производительности каждый раз, чтобы увидеть, действительно ли вы сделали это быстрее или сломали логику компиляторов.
источник
Насколько я знаю, в некоторых машинах умножение может потребовать от 16 до 32 машинных циклов. Так что да , в зависимости от типа машины, операторы битового сдвига быстрее, чем умножение / деление.
Однако некоторые машины имеют математический процессор, который содержит специальные инструкции для умножения / деления.
источник
Я согласен с помеченным ответом Дрю Холла. Ответ может использовать некоторые дополнительные заметки, хотя.
Для подавляющего большинства разработчиков программного обеспечения процессор и компилятор больше не относятся к данному вопросу. Большинство из нас далеко за 8088 и MS-DOS. Это возможно только для тех, кто все еще разрабатывает для встроенных процессоров ...
В моей компании по разработке программного обеспечения Math (add / sub / mul / div) должен использоваться для всей математики. Хотя Shift следует использовать при преобразовании между типами данных, например. ushort для байта как n >> 8, а не n / 256.
источник
В случае целых чисел со знаком и сдвига вправо против деления это может иметь значение. Для отрицательных чисел сдвиг округляет до отрицательной бесконечности, а деление округляет до нуля. Конечно, компилятор изменит деление на что-то более дешевое, но обычно он изменит это на то, что имеет то же поведение округления, что и деление, потому что он либо не может доказать, что переменная не будет отрицательной, либо просто не будет забота. Поэтому, если вы можете доказать, что число не будет отрицательным, или если вам все равно, как оно будет округляться, вы можете выполнить эту оптимизацию таким образом, чтобы с большей вероятностью что-то изменить.
источник
unsigned
Тест Python, выполняющий одинаковое умножение 100 миллионов раз против одинаковых случайных чисел.
Так что при сдвиге, а не умножении / делении на степень два в python, есть небольшое улучшение (~ 10% для деления; ~ 1% для умножения). Если это не сила двух, вероятно, значительное замедление.
Опять же, эти # будут меняться в зависимости от вашего процессора, вашего компилятора (или интерпретатора - для простоты сделано в python).
Как и со всеми остальными, не оптимизируйте преждевременно. Напишите очень читаемый код, профиль, если он недостаточно быстр, а затем попытайтесь оптимизировать медленные части. Помните, ваш компилятор намного лучше в оптимизации, чем вы.
источник
Есть оптимизации, которые компилятор не может сделать, потому что они работают только для сокращенного набора входных данных.
Ниже приведен пример кода C ++, который может выполнить более быстрое деление, выполняя 64-битное «Умножение на обратную». Числитель и знаменатель должны быть ниже определенного порога. Обратите внимание, что он должен быть скомпилирован для использования 64-битных инструкций, чтобы быть на самом деле быстрее, чем обычное деление.
источник
Я думаю, что в одном случае, когда вы хотите умножить или разделить на степень два, вы не ошибетесь с использованием операторов битового сдвига, даже если компилятор преобразует их в MUL / DIV, потому что некоторые процессоры микрокодируют (на самом деле, макрос) их в любом случае, так что в этих случаях вы добьетесь улучшения, особенно если сдвиг больше 1. Или, более конкретно, если у ЦПУ нет операторов сдвига битов, это все равно будет MUL / DIV, но если ЦП имеет операторы bithift, вы избегаете ветки микрокода, и это на несколько инструкций меньше.
Я сейчас пишу некоторый код, который требует много операций удвоения / деления пополам, потому что он работает на плотном двоичном дереве, и есть еще одна операция, которая, я подозреваю, может быть более оптимальной, чем сложение - левая (степень двойного умножения) ) сдвиг с дополнением. Это можно заменить на сдвиг влево и xor, если сдвиг шире, чем количество бит, которое вы хотите добавить, простой пример (i << 1) ^ 1, который добавляет единицу к удвоенному значению. Это, конечно, не относится к сдвигу вправо (степень двойного деления), поскольку только сдвиг влево (с прямым порядком байтов) заполняет пробел нулями.
В моем коде эти умножения / деления на два и степени двух операций используются очень интенсивно, и поскольку формулы уже достаточно короткие, каждая команда, которая может быть исключена, может принести существенный выигрыш. Если процессор не поддерживает эти операторы битового сдвига, никакого усиления не произойдет, но и не будет потерь.
Кроме того, в алгоритмах, которые я пишу, они визуально представляют движения, которые происходят, поэтому в этом смысле они на самом деле более ясны. Левая часть бинарного дерева больше, а правая меньше. Кроме того, в моем коде нечетные и четные числа имеют особое значение, и все левые дочерние элементы в дереве являются нечетными, а все правые дочерние элементы и корень четными. В некоторых случаях, с которыми я еще не сталкивался, но, может, я даже и не думал об этом, x & 1 может быть более оптимальной операцией по сравнению с x% 2. x & 1 для четного числа будет давать ноль, но будет производить 1 для нечетного числа.
Пройдя немного дальше, чем просто нечетная / четная идентификация, если я получу ноль для x & 3, я знаю, что 4 является фактором нашего числа, и то же самое для x% 7 для 8 и так далее. Я знаю, что эти случаи, вероятно, имеют ограниченную полезность, но приятно знать, что вы можете избежать операции модуля и использовать вместо нее побитовую логическую операцию, потому что побитовые операции почти всегда самые быстрые и наименее вероятно будут неоднозначными для компилятора.
Я в значительной степени придумываю область плотных бинарных деревьев, поэтому я ожидаю, что люди могут не понять значение этого комментария, поскольку очень редко люди хотят выполнять факторизацию только на степени двух или только умножать / делить степени двух.
источник
Является ли это на самом деле быстрее , зависит от аппаратного обеспечения и компилятор на самом деле используется.
источник
Если вы сравните выходные данные для синтаксиса x + x, x * 2 и x << 1 в компиляторе gcc, то вы получите тот же результат в сборке x86: https://godbolt.org/z/JLpp0j
Таким образом, вы можете считать gcc умным, чтобы определить свое лучшее решение независимо от того, что вы ввели.
источник
Я тоже хотел посмотреть, смогу ли я победить дом. это более общее побитовое значение для любого числа путем умножения любого числа. макросы, которые я сделал, примерно на 25% больше, чем в два раза медленнее, чем обычно * умножение. как говорят другие, если он близок к кратному 2 или состоит из нескольких кратных 2, вы можете выиграть. как X * 23 состоит из (X << 4) + (X << 2) + (X << 1) + X будет медленнее, чем X * 65 состоит из (X << 6) + X.
источник