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

Question

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

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

и т. Д.

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

Answer 1

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

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

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

Answer 2

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

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 лет назад. Надеюсь, компиляторы с тех пор стало только лучше, так что вы можете в значительной степени рассчитывать на Компилятор делает правильные вещи, вероятно, лучше, чем вы могли бы. (Также, причина, по которой код выглядит так, потому что это было более 15 лет назад. Очевидно, я бы сегодня использовал std::string и итераторы.)

Answer 3

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

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

Answer 4

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

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

Answer 5

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

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

Пример использования - от 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, так что даже если несколько из них вместе смещаются поверхностно как победитель.

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

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

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

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

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

Answer 6

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

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

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

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

Answer 7

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

На самом деле трюк с разделением, известный как «магическое разделение», может принести огромные выгоды. Опять же, вы должны сначала профиль, чтобы увидеть, если это необходимо. Но если вы используете его, то есть полезные программы, которые помогут вам выяснить, какие инструкции необходимы для той же семантики деления. Вот пример: 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

Будет генерировать:

* * 1010

Answer 8

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

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

Answer 9

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

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

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

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

Answer 10

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

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

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