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

288

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

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

и так далее.

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

экю
источник
8
На самом деле, возможное дешевое деление на константу, отличную от степени двойки, возможно, но сложная задача, к которой вы не относитесь справедливо с "/ Делением ... / делением" в вашем вопросе. Смотрите, например, hackersdelight.org/divcMore.pdf (или получите книгу « Восторг хакера», если можете).
Паскаль Куок
46
Это похоже на то, что можно легко проверить.
Juanchopanza
25
Как обычно - это зависит. Однажды я попробовал это на ассемблере на Intel 8088 (IBM PC / XT), где умножение заняло несколько миллиардов часов. Изменения и добавления выполняются намного быстрее, так что это кажется хорошей идеей. Тем не менее, при умножении шинного блока можно было свободно заполнять очередь команд, и затем следующая команда могла начаться немедленно. После серии сдвигов и добавлений очередь команд будет пуста, и ЦПУ придется ждать следующей инструкции, извлекаемой из памяти (по одному байту за раз!). Мера, мера, мера!
Бо Перссон
19
Также имейте в виду, что смещение вправо четко определено только для целых чисел без знака . Если у вас целое число со знаком, то не определено, дополняется ли 0 или старший бит слева. (И не забывайте,
сколько времени понадобится
29
На самом деле, хороший оптимизирующий компилятор будет реализовывать умножение и деление со сдвигами, когда они быстрее.
Питер Григорьевич

Ответы:

487

Краткий ответ: маловероятно.

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

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

Дрю Холл
источник
31
Да, как уже говорилось, возможная выгода почти для каждого приложения полностью перевесит введенную неизвестность. Не беспокойтесь об этом виде оптимизации преждевременно. Создайте то, что семантически ясно, определите узкие места и оптимизируйте оттуда ...
Дейв
4
Согласитесь, оптимизация для удобочитаемости и удобства обслуживания, вероятно, даст вам больше времени, чтобы потратить на оптимизацию того, что профилировщик называет « горячими путями» кода.
doug65536
5
Эти комментарии звучат так, будто вы разочаровываетесь в потенциальной производительности, рассказывая компилятору, как выполнять свою работу. Это не тот случай. На самом деле вы получаете лучший код из gcc -O3x86, return i*10чем из shift-версии . Как человек, который много смотрит на результаты компиляции (см. Многие из моих ответов по asm / оптимизация), я не удивлен. Есть моменты, когда это может помочь держать компилятор одним способом , но это не один из них. GCC хорош в целочисленной математике, потому что это важно.
Питер Кордес
Просто скачал набросок Arduino, который имеет millis() >> 2; Было бы слишком много просить просто разделить?
Пол Виланд
1
Я протестировал i / 32vs i >> 5и i / 4vs i >> 2на gcc для cortex-a9 (который не имеет аппаратного разделения) с оптимизацией -O3, и результирующая сборка была точно такой же. Сначала я не любил использовать деления, но это описывает мое намерение и результат тот же.
Робсн
91

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

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

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

Джеймс Канзе
источник
5
Возможно, вас заинтересует следующий пост в блоге, в котором автор отмечает, что современные оптимизирующие компиляторы, похоже, реконструируют общие шаблоны, которые программисты могли бы использовать, думая о них более эффективно в своих математических формах, чтобы действительно генерировать для них наиболее эффективную последовательность команд. , shape-of-code.coding-guidelines.com/2009/06/30/…
Паскаль Куок
@PascalCuoq Ничего особенного в этом нет. Я обнаружил почти то же самое для Sun CC около 20 лет назад.
Джеймс Канз
67

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

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

Эрик Липперт
источник
5
Избегать с простыми скобками?
Джоэл Б
21
@ Джоэл: Конечно. Если вы помните, что они вам нужны. Я хочу сказать, что легко забыть, что ты делаешь. Люди, которые приобретают умственную привычку читать «x << 1», как если бы это было «x * 2», приобретают умственную привычку думать, что << - это то же, что и умножение, чего не происходит.
Эрик Липперт
1
Ну, я нахожу выражение "(hi << 8) + lo" более показательным, чем "hi * 256 + lo". Вероятно, это дело вкуса, но иногда более понятно писать что-то сложное. В большинстве случаев я полностью согласен с вашей точкой зрения.
Иван Данилов
32
@Ivan: И "(привет << 8) | lo" еще яснее. Установка младших битов массива битов не является добавлением целых чисел . Это установка битов , поэтому напишите код, который устанавливает биты.
Эрик Липперт
1
Вот это да. Не думал об этом раньше. Спасибо.
Иван Данилов
50

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

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

Jens
источник
3
Просто добавим приблизительную оценку: на типичном 16-битном процессоре (80C166) добавление двух целых происходит с 1-2 циклами, умножением с 10 циклами и делением с 20 циклами. Плюс некоторые операции перемещения, если вы оптимизируете i * 10 на несколько операций (каждая перемещается еще на +1 цикл). Наиболее распространенные компиляторы (Keil / Tasking) не оптимизируют, за исключением случаев умножения / деления на степень 2.
Йенс
55
И вообще, компилятор оптимизирует код лучше, чем вы.
user703016
Я согласен с тем, что при умножении «количеств» оператор умножения, как правило, лучше, но при делении знаковых значений на степени 2 >>оператор работает быстрее, /и, если знаковые значения могут быть отрицательными, он часто также семантически превосходит их. Если нужно получить значение, которое x>>4было бы произведено, это намного яснее x < 0 ? -((-1-x)/16)-1 : x/16;, и я не представляю, как компилятор может оптимизировать это последнее выражение до чего-то приятного.
суперкат
38

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

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

Тематическое исследование - от 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 )

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

(из какого-то интеллара)

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

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

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

В более общем плане, ваш вопрос помечен C и C ++. Как языки 3-го поколения, они специально разработаны, чтобы скрыть детали базового набора команд ЦП. Чтобы удовлетворить свои языковые стандарты, они должны поддерживать операции умножения и сдвига (и многие другие), даже если базовое оборудование этого не делает . В таких случаях они должны синтезировать требуемый результат, используя множество других инструкций. Точно так же они должны обеспечивать программную поддержку для операций с плавающей запятой, если в процессоре этого нет, а 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...............

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

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

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

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

Если ваше аппаратное обеспечение изменится, вы можете перекомпилировать его, и он будет смотреть на целевой ЦП и делать еще один лучший выбор, в то время как вы вряд ли когда-нибудь захотите пересмотреть свои «оптимизации» или перечислить, какие среды компиляции должны использовать умножение, а какие - сдвигаться. Подумайте обо всех «оптимизациях» со сдвигом битов со сдвигом в два, написанных более 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 - это биты E2, сдвинутые вправо E1. Если E1 имеет тип без знака или E1 имеет тип со знаком и неотрицательное значение, значение результата является неотъемлемой частью отношения E1, деленного на величину 2, возведенную в степень E2. Если E1 имеет тип со знаком и отрицательное значение, результирующее значение определяется реализацией.

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

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

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

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

Тони Делрой
источник
2
Очень хороший ответ. Сравнение Core i7 и 486 поучительно!
Дрю Холл
На всех распространенных архитектурах intVal>>1будет иметь одинаковую семантику, которая отличается от таковой, intVal/2что иногда полезно. Если нужно вычислить переносимым образом значение, которое принесут обычные архитектуры intVal >> 1, выражение должно быть несколько более сложным и трудным для чтения, и, скорее всего, будет генерировать существенно худший код по сравнению с тем, который был создан intVal >> 1.
суперкат
35

Просто попробовал на моей машине компилировать это:

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

При разборке выдает результат:

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

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

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

user703016
источник
1
Вы бы получили большое преимущество за это, если бы пропустили часть о векторе. Если компилятор может исправить умножение, он также может видеть, что вектор не изменяется.
Бо Перссон
Как компилятор может знать, что размер вектора не изменится без каких-либо действительно опасных предположений? Или вы никогда не слышали о параллелизме ...
Чарльз Гудвин
1
Итак, вы перебираете глобальный вектор без блокировок? И я зацикливаюсь на локальном векторе, адрес которого не был взят, и вызываю только константные функции-члены. По крайней мере, мой компилятор понимает, что размер вектора не изменится. (и скоро кто-то, вероятно, пометит нас для чата :-).
Бо Перссон
1
@BoPersson Наконец, по прошествии всего этого времени я удалил свое утверждение о том, что компилятор не может оптимизироваться vector<T>::size(). Мой компилятор был довольно древним! :)
user703016
21

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

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

Пример, который я поднял из потока 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
Майк Кван
источник
7
@ По какой-то причине твой комментарий заставил меня рассмеяться и пролить кофе. Спасибо.
asawyer
30
Там нет случайных тем на форуме о симпатии математике. Любой, кто любит математику, знает, как трудно создать настоящую «случайную» ветку форума.
Джоэл Б
1
Вероятно, стоит делать подобные вещи, только если вы профилировали и обнаружили, что это узкое место, и снова применили альтернативы и профиль и получили как минимум 10-кратное преимущество в производительности .
Ли Райан
12

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

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

#include <stdio.h>

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

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

Пол Р
источник
4
Целочисленные умножения микрокодируются, например, на PPU PlayStation 3, и останавливают весь конвейер. Рекомендуется избегать целочисленных умножений на некоторых платформах :)
Maister
2
Многие беззнаковые деления - при условии, что компилятор знает, как - реализованы с использованием умножения без знака. Один или два умножения на несколько тактовых циклов каждый может выполнять ту же работу, что и деление на 40 тактов и более.
Олоф Форшелл
1
@Olof: правда, но действителен только для деления на константу времени компиляции, конечно
Пол Р.
4

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

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

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

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

Брейди мориц
источник
2

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

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

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

Kromster
источник
1

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

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

iammilind
источник
7
Люди, пишущие компиляторы для этих машин, также, вероятно, читали «Восторг хакеров» и оптимизировали его соответствующим образом.
Бо Перссон
1

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

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

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

deegee
источник
Я тоже с тобой согласен. Я подсознательно следую той же рекомендации, хотя у меня никогда не было формального требования сделать это.
Дрю Холл
0

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

Гарольд
источник
или приведи число кunsigned
Ли Райан
4
Вы уверены, что поведение переключения стандартизировано? У меня сложилось впечатление, что сдвиг вправо по отрицательным значениям определяется реализацией.
Kerrek SB
1
Хотя, возможно, следует упомянуть, что код, который полагается на любое конкретное поведение для смещения вправо отрицательных чисел, должен документировать это требование, преимущество смещения вправо огромно в тех случаях, когда оно естественным образом дает правильное значение, а оператор деления будет генерировать код, чтобы тратить его впустую. время вычисления нежелательного значения, которое пользовательскому коду затем пришлось бы тратить дополнительное время на настройку, чтобы получить то, что сдвиг дал бы в первую очередь. На самом деле, если бы у меня были мои барабанщики, у компиляторов была бы возможность кричать при попытках выполнить подписанное деление, так как ...
суперкат
1
... код, который знает, что операнды положительны, может улучшить оптимизацию, если он приведен к unsigned перед делением (возможно, приведение обратно к знаку позже), а код, который знает, что операнды могут быть отрицательными, должен в любом случае явно иметь дело с этим случаем (в этом случае с тем же успехом можно считать их позитивными).
суперкат
0

Тест 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).

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

доктор джимбоб
источник
0

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

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

#include <stdio.h>
#include <chrono>

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;
}
user2044859
источник
0

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

Я сейчас пишу некоторый код, который требует много операций удвоения / деления пополам, потому что он работает на плотном двоичном дереве, и есть еще одна операция, которая, я подозреваю, может быть более оптимальной, чем сложение - левая (степень двойного умножения) ) сдвиг с дополнением. Это можно заменить на сдвиг влево и xor, если сдвиг шире, чем количество бит, которое вы хотите добавить, простой пример (i << 1) ^ 1, который добавляет единицу к удвоенному значению. Это, конечно, не относится к сдвигу вправо (степень двойного деления), поскольку только сдвиг влево (с прямым порядком байтов) заполняет пробел нулями.

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

Кроме того, в алгоритмах, которые я пишу, они визуально представляют движения, которые происходят, поэтому в этом смысле они на самом деле более ясны. Левая часть бинарного дерева больше, а правая меньше. Кроме того, в моем коде нечетные и четные числа имеют особое значение, и все левые дочерние элементы в дереве являются нечетными, а все правые дочерние элементы и корень четными. В некоторых случаях, с которыми я еще не сталкивался, но, может, я даже и не думал об этом, x & 1 может быть более оптимальной операцией по сравнению с x% 2. x & 1 для четного числа будет давать ноль, но будет производить 1 для нечетного числа.

Пройдя немного дальше, чем просто нечетная / четная идентификация, если я получу ноль для x & 3, я знаю, что 4 является фактором нашего числа, и то же самое для x% 7 для 8 и так далее. Я знаю, что эти случаи, вероятно, имеют ограниченную полезность, но приятно знать, что вы можете избежать операции модуля и использовать вместо нее побитовую логическую операцию, потому что побитовые операции почти всегда самые быстрые и наименее вероятно будут неоднозначными для компилятора.

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

Луки Сумирный
источник
0

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

Альберт ван дер Хорст
источник
0

Если вы сравните выходные данные для синтаксиса x + x, x * 2 и x << 1 в компиляторе gcc, то вы получите тот же результат в сборке x86: https://godbolt.org/z/JLpp0j

        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        mov     eax, DWORD PTR [rbp-4]
        add     eax, eax
        pop     rbp
        ret

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

Буридан
источник
0

Я тоже хотел посмотреть, смогу ли я победить дом. это более общее побитовое значение для любого числа путем умножения любого числа. макросы, которые я сделал, примерно на 25% больше, чем в два раза медленнее, чем обычно * умножение. как говорят другие, если он близок к кратному 2 или состоит из нескольких кратных 2, вы можете выиграть. как X * 23 состоит из (X << 4) + (X << 2) + (X << 1) + X будет медленнее, чем X * 65 состоит из (X << 6) + X.

#include <stdio.h>
#include <time.h>

#define MULTIPLYINTBYMINUS(X,Y) (-((X >> 30) & 1)&(Y<<30))+(-((X >> 29) & 1)&(Y<<29))+(-((X >> 28) & 1)&(Y<<28))+(-((X >> 27) & 1)&(Y<<27))+(-((X >> 26) & 1)&(Y<<26))+(-((X >> 25) & 1)&(Y<<25))+(-((X >> 24) & 1)&(Y<<24))+(-((X >> 23) & 1)&(Y<<23))+(-((X >> 22) & 1)&(Y<<22))+(-((X >> 21) & 1)&(Y<<21))+(-((X >> 20) & 1)&(Y<<20))+(-((X >> 19) & 1)&(Y<<19))+(-((X >> 18) & 1)&(Y<<18))+(-((X >> 17) & 1)&(Y<<17))+(-((X >> 16) & 1)&(Y<<16))+(-((X >> 15) & 1)&(Y<<15))+(-((X >> 14) & 1)&(Y<<14))+(-((X >> 13) & 1)&(Y<<13))+(-((X >> 12) & 1)&(Y<<12))+(-((X >> 11) & 1)&(Y<<11))+(-((X >> 10) & 1)&(Y<<10))+(-((X >> 9) & 1)&(Y<<9))+(-((X >> 8) & 1)&(Y<<8))+(-((X >> 7) & 1)&(Y<<7))+(-((X >> 6) & 1)&(Y<<6))+(-((X >> 5) & 1)&(Y<<5))+(-((X >> 4) & 1)&(Y<<4))+(-((X >> 3) & 1)&(Y<<3))+(-((X >> 2) & 1)&(Y<<2))+(-((X >> 1) & 1)&(Y<<1))+(-((X >> 0) & 1)&(Y<<0))
#define MULTIPLYINTBYSHIFT(X,Y) (((((X >> 30) & 1)<<31)>>31)&(Y<<30))+(((((X >> 29) & 1)<<31)>>31)&(Y<<29))+(((((X >> 28) & 1)<<31)>>31)&(Y<<28))+(((((X >> 27) & 1)<<31)>>31)&(Y<<27))+(((((X >> 26) & 1)<<31)>>31)&(Y<<26))+(((((X >> 25) & 1)<<31)>>31)&(Y<<25))+(((((X >> 24) & 1)<<31)>>31)&(Y<<24))+(((((X >> 23) & 1)<<31)>>31)&(Y<<23))+(((((X >> 22) & 1)<<31)>>31)&(Y<<22))+(((((X >> 21) & 1)<<31)>>31)&(Y<<21))+(((((X >> 20) & 1)<<31)>>31)&(Y<<20))+(((((X >> 19) & 1)<<31)>>31)&(Y<<19))+(((((X >> 18) & 1)<<31)>>31)&(Y<<18))+(((((X >> 17) & 1)<<31)>>31)&(Y<<17))+(((((X >> 16) & 1)<<31)>>31)&(Y<<16))+(((((X >> 15) & 1)<<31)>>31)&(Y<<15))+(((((X >> 14) & 1)<<31)>>31)&(Y<<14))+(((((X >> 13) & 1)<<31)>>31)&(Y<<13))+(((((X >> 12) & 1)<<31)>>31)&(Y<<12))+(((((X >> 11) & 1)<<31)>>31)&(Y<<11))+(((((X >> 10) & 1)<<31)>>31)&(Y<<10))+(((((X >> 9) & 1)<<31)>>31)&(Y<<9))+(((((X >> 8) & 1)<<31)>>31)&(Y<<8))+(((((X >> 7) & 1)<<31)>>31)&(Y<<7))+(((((X >> 6) & 1)<<31)>>31)&(Y<<6))+(((((X >> 5) & 1)<<31)>>31)&(Y<<5))+(((((X >> 4) & 1)<<31)>>31)&(Y<<4))+(((((X >> 3) & 1)<<31)>>31)&(Y<<3))+(((((X >> 2) & 1)<<31)>>31)&(Y<<2))+(((((X >> 1) & 1)<<31)>>31)&(Y<<1))+(((((X >> 0) & 1)<<31)>>31)&(Y<<0))
int main()
{
    int randomnumber=23;
    int randomnumber2=23;
    int checknum=23;
    clock_t start, diff;
    srand(time(0));
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum=MULTIPLYINTBYMINUS(randomnumber,randomnumber2);
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    int msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("MULTIPLYINTBYMINUS Time %d milliseconds", msec);
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum=MULTIPLYINTBYSHIFT(randomnumber,randomnumber2);
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("MULTIPLYINTBYSHIFT Time %d milliseconds", msec);
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum= randomnumber*randomnumber2;
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("normal * Time %d milliseconds", msec);
    return 0;
}
AlexanderLife
источник