Что быстрее: x << 1 или x << 10?

84

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

x << 1;

и

x << 10;

И, пожалуйста, не ненавидьте меня за этот вопрос. :)

c++ c performance cpu low-level Армен Цирунян
источник
17
Омг, я взглянул на код и моей первой мыслью были «операторы потоковой печати». Мне нужен перерыв.
Кос,
4
Мне кажется, я слышу, как кто-то слабо говорит о «преждевременной оптимизации», или, может быть, просто в моем воображении.
tia
5
@tia он сказал, что не собирается ничего оптимизировать :)
1
@Grigory да, и поэтому мы не видим здесь никого, кто пропускает вопрос с этой фразой. : D
tia
1
В качестве примечания: недавно я понял, что сдвиг влево и вправо не обязательно требует одного и того же времени процессора. В моем случае переключение вправо происходило намного медленнее. Сначала я был удивлен, но я думаю, что ответ заключается в том, что сдвиг влево означает логический, а сдвиг вправо, возможно, означает арифметический: stackoverflow.com/questions/141525/…
Кристиан Аммер

Ответы:

84

Потенциально зависит от процессора.

Однако все современные процессоры (x86, ARM) используют «баррель-шифтер» - аппаратный модуль, специально разработанный для выполнения произвольных сдвигов за постоянное время.

Итак, суть в том ... нет. Нет разницы.

нимродм
источник
21
Отлично, теперь у меня есть образ, говорящий моему процессору сделать бочку, застрявшую у меня в голове ...
Игнасио Васкес-Абрамс
11
Errr - ОЧЕНЬ МНОГО зависит от процессора. На некоторых процессорах это постоянное время. В других случаях это может быть один цикл за смену (однажды я использовал сдвиг примерно на 60 000 позиций как способ измерения тактовой частоты процессора). А на других процессорах могут быть только инструкции для однобитового сдвига, и в этом случае многобитовый сдвиг делегируется библиотечной подпрограмме, которая находится в цикле, повторяющемся.
quick_now
4
@quickly_now: Конечно, это плохой способ измерения тактовой частоты. Ни один процессор не настолько глуп, чтобы на самом деле выполнять 60 000 смен; который будет просто преобразован в 60000 mod register_size. Например, 32-разрядный процессор будет использовать только 5 младших битов счетчика сдвига.
casablanca
4
Транспьютер inmos имел оператор сдвига, который считал количество сдвигов 32-битным операндом. Вы можете сделать 4 миллиарда смен, если хотите, по 1 такту каждая. «Никакой процессор не тупой». Извините - ошиблись. Этот сделал. Однако вам нужно было кодировать эту часть на ассемблере. Компиляторы сделали разумную модификацию / оптимизацию (просто выставили результат на 0, ничего не делайте).
quick_now
5
К сожалению, Pentium 4 лишился сдвоенного переключателя, что способствовало его общей низкой скорости выполнения инструкций за такт. Я предполагаю, что архитектура Core Blah вернула его.
Рассел Борогов
64

Некоторые встроенные процессоры имеют только команду «сдвиг на один». На таких процессорах компилятор изменится x << 3на ((x << 1) << 1) << 1.

Я думаю, что Motorola MC68HCxx была одним из самых популярных семейств с этим ограничением. К счастью, такие архитектуры сейчас довольно редки, в большинстве из них теперь есть баррель-шифтер с переменным размером сдвига.

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

Бен Фойгт
источник
12
По-прежнему часто встречается во встроенных микроконтроллерах.
Бен Джексон
4
Что вы имеете в виду под «редким»? По статистике количество проданных 8-битных микроконтроллеров превышает количество всех других типов MPU.
Вованиум
8-битные микроконтроллеры мало используются для новых разработок, когда вы можете получить 16-битные по той же цене за единицу (например, MSP430 от TI) с большим объемом ПЗУ для программ, большей рабочей RAM и большими возможностями. И даже в некоторых 8-битных микроконтроллерах есть баррель-шифтеры.
Ben Voigt
1
Размер слова микроконтроллера не имеет ничего общего с тем, есть ли у него баррель-сдвигатель, семейство MC68HCxx, о котором я упоминал, также имеет 16-битные процессоры, все они одновременно сдвигают только одну битовую позицию.
Ben Voigt
Факт, что большинство 8-битных микроконтроллеров не имеют барочечного переключателя, хотя вы правы, что есть такие, для которых это неправда, и есть не 8-битные без барочечного переключателя. Битность получена как надежное приближение для машин с переключателем [вне] ствола. Также тот факт, что ядро ​​процессора для MCU часто не определяет выбор модели, а внутренняя периферия - это выбор. А 8-битные часто выбирают для более богатой периферии по той же цене.
Вованиум
29

На этот счет много случаев.

  1. Многие высокоскоростные MPU имеют баррель-шифтер, электронную схему, подобную мультиплексору, которая выполняет любое переключение за постоянное время.

  2. Если MPU имеет только 1 бит, сдвиг x << 10обычно будет медленнее, как это обычно делается с помощью 10 смен или байтового копирования с 2 сменами.

  3. Но известен распространенный случай, когда x << 10было бы даже быстрее, чем x << 1. Если x равен 16 бит, заботятся только младшие 6 бит (все остальные будут сдвинуты), поэтому MPU должен загружать только младший байт, таким образом, сделать только один цикл доступа к 8-битной памяти, в то время как x << 10требуется два цикла доступа. Если цикл доступа медленнее, чем сдвиг (и очищает младший байт), x << 10будет быстрее. Это может относиться к микроконтроллерам с быстрым встроенным программным ПЗУ при доступе к медленной внешней памяти данных.

  4. В дополнение к случаю 3, компилятор может заботиться о количестве значимых битов x << 10и оптимизировать дальнейшие операции для операций с меньшей шириной, например, замену умножения 16x16 на единицу 16x8 (поскольку младший байт всегда равен нулю).

Обратите внимание, некоторые микроконтроллеры вообще не имеют инструкции сдвига влево, они ее используют add x,x.

Вованиум
источник
Я не понимаю, почему x << 10 быстрее, чем x << 8, где в x << 8 вам нужно выполнить загрузку из младшего байта из 16 бит, а не выполнять загрузку и две смены. я не понимаю.
нет
3
@none: я не утверждал, что x << 10 быстрее, чем x << 8.
Вованиум
9

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

односложный
источник
1
Выполняются ли инструкции за одинаковое количество циклов? На нескольких архитектурах одна и та же инструкция будет преобразована в несколько разных кодов операций на основе операндов и займет от 1 до 5 циклов.
Nick T
@Nick Инструкция ARM обычно занимает от 1 до 2 циклов. Не уверен, что с новыми архитектурами.
onemasse
2
@Nick T: Он говорит об ARM, у этого сдвига есть не специальная инструкция, а «особенность» многих инструкций по обработке данных. Т.е. ADD R0, R1, R2 ASL #3складывает R1 и сдвигает R2 на 3 бита влево.
Вованиум
7

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

Имейте в виду, что сдвиг чего-либо за пределы ширины в битах данных является «неопределенным поведением» в C и C ++. Правый сдвиг подписанных данных также «определяется реализацией». Вместо того, чтобы слишком беспокоиться о скорости, позаботьтесь о том, чтобы вы получили одинаковый ответ в разных реализациях.

Цитата из раздела 3.3.7 ANSI C:

3.3.7 Операторы побитового сдвига

Синтаксис

      shift-expression:
              additive-expression
              shift-expression <<  additive-expression
              shift-expression >>  additive-expression

Ограничения

Каждый из операндов должен иметь целочисленный тип.

Семантика

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

Результат E1 << E2 - E1 сдвинутые влево битовые позиции E2; освобожденные биты заполняются нулями. Если E1 имеет беззнаковый тип, значение результата - E1, умноженное на количество, 2, возведенное в степень E2, уменьшенное по модулю ULONG_MAX + 1, если E1 имеет тип unsigned long, в противном случае UINT_MAX + 1. (Константы ULONG_MAX и UINT_MAX определены в заголовке.)

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

Так:

x = y << z;

«<<»: y × 2 z ( не определено, если происходит переполнение);

x = y >> z;

">>": определено реализацией для подписи (чаще всего результат арифметического сдвига: y / 2 z ).

волк
источник
Я не думаю, что 1u << 100это УБ. Это всего лишь 0.
Армен Цирунян
@Armen Tsirunyan: Битовый сдвиг 1u << 100как битовый сдвиг может быть переполнением; 1u << 100поскольку арифметический сдвиг равен 0. Согласно ANSI C, <<это битовый сдвиг. en.wikipedia.org/wiki/Arithmetic_shift
волк
2
@Armen Tsirunyan: См. Раздел 3.3.7 ANSI - Если значение правого операнда отрицательное или больше или равно ширине в битах продвинутого левого операнда, поведение не определено. Таким образом, ваш пример - UB в любой системе ANSI C, если нет типа 101+ бит.
волк
@ carrot-pot: Хорошо, ты меня убедил :)
Армен Цирунян
Связанный: x << (y & 31)все еще может компилироваться в одну инструкцию сдвига без инструкции И, если компилятор знает, что инструкция сдвига целевой архитектуры маскирует счетчик (как это делает x86). (Желательно не кодировать маску жестко; получить ее CHAR_BIT * sizeof(x) - 1или что-то в этом роде.) Это полезно для написания идиомы поворота, которая компилируется в одну инструкцию без C UB независимо от входных данных. ( stackoverflow.com/questions/776508/… ).
Питер Кордес
7

Вполне возможно, что на 8-битном процессоре это x<<1может быть намного медленнее, чем x<<10для 16-битного значения.

Например, разумным переводом x<<1может быть:

byte1 = (byte1 << 1) | (byte2 >> 7)
byte2 = (byte2 << 1)

тогда как x<<10было бы проще:

byte1 = (byte2 << 2)
byte2 = 0

Обратите внимание, как x<<1смещается чаще и даже дальше чем x<<10. Кроме того, результат x<<10не зависит от содержимого байта1. Это может дополнительно ускорить операцию.

Роберт
источник
5

На некоторых поколениях процессоров Intel (P2 или P3? Не AMD, если я правильно помню) операции сдвига битов до смешного медленные. Битовый сдвиг на 1 бит всегда должен быть быстрым, поскольку он может просто использовать сложение. Другой вопрос, который следует рассмотреть, заключается в том, являются ли сдвиги на постоянное количество бит быстрее, чем сдвиги переменной длины. Даже если коды операций имеют одинаковую скорость, на x86 непостоянный правый операнд битового сдвига должен занимать регистр CL, что накладывает дополнительные ограничения на выделение регистров и может замедлять работу программы.

R .. GitHub НЕ ПОМОГАЕТ ICE
источник
1
Это Pentium 4. Процессоры на базе PPro (такие как P2 и P3) имеют быструю смену. И да, изменение количества переменных на x86 происходит медленнее, чем могло бы быть, если только вы не можете использовать BMI2 shlx/ shrx/ sarx(Haswell и более поздние версии , и Ryzen). Семантика CISC (флаги не изменяются, если count = 0) вредит x86 здесь. shl r32, clсоставляет 3 мопа на семействе Sandybridge (хотя Intel утверждает, что может отменить один из мопов, если результат флага не используется). AMD имеет одинарную опцию shl r32, cl(но медленную двойную смену для повышенной точности shld r32, r32, cl),
Питер Кордес,
1
Сдвиги (даже с переменным числом) - это только один элемент в семействе P6, но чтение флага-результата shl r32, clили с немедленным, отличным от 1, останавливает интерфейс до тех пор, пока смена не прекратится ! ( stackoverflow.com/questions/36510095/… ). Компиляторы знают это и используют отдельную testинструкцию вместо использования флага результата сдвига. (Но это тратит впустую инструкции для процессоров, где это не проблема, см. Stackoverflow.com/questions/40354978/… )
Питер Кордес
3

Как всегда, это зависит от контекста окружающего кода : например, вы используете x<<1в качестве индекса массива? Или добавить что-то еще? В любом случае небольшое количество сдвигов (1 или 2) часто может оптимизировать даже больше, чем если бы компилятору пришлось просто сдвигать. Не говоря уже о компромиссе между пропускной способностью, задержкой и узкими местами интерфейса. Выполнение крошечного фрагмента не одномерно.

Инструкции аппаратного сдвига - не единственный вариант компиляции для компиляции x<<1, но другие ответы в основном предполагают это.

x << 1в точности эквивалентенx+x для беззнаковых и для целых чисел со знаком дополнения до 2. Компиляторы всегда знают, на какое оборудование они нацелены во время компиляции, поэтому они могут воспользоваться подобными уловками.

На Intel Haswell , addимеет 4 за такт пропускной способности , но shlс немедленным графа имеет только 2 за тактовый пропускную способность . (См. Http://agner.org/optimize/ для таблиц инструкций и других ссылок вx86тег вики). Сдвиги вектора SIMD равны 1 за такт (2 в Skylake), но целочисленные добавления вектора SIMD равны 2 за такт (3 в Skylake). Хотя задержка такая же: 1 цикл.

Также существует специальная пошаговая кодировка, в shlкоторой счетчик неявно указывается в коде операции. У 8086 не было сдвигов с немедленным подсчетом, только по одному и по clрегистрам. Это в основном актуально для сдвигов вправо, потому что вы можете просто добавить сдвиги влево, если вы не сдвигаете операнд памяти. Но если значение понадобится позже, лучше сначала загрузить в регистр. Но в любом случае, shl eax,1или add eax,eaxон на один байт короче shl eax,10, и размер кода может напрямую (узкие места декодирования / внешнего интерфейса) или косвенно (промахи в кэше кода L1I) влиять на производительность.

В более общем смысле, небольшое количество сдвигов иногда можно оптимизировать в масштабируемый индекс в режиме адресации на x86. Большинство других широко используемых в наши дни архитектур - это RISC, и они не имеют режимов адресации с масштабируемым индексом, но x86 является достаточно распространенной архитектурой, чтобы об этом стоит упомянуть. (яйцо, если вы индексируете массив из 4-байтовых элементов, есть место для увеличения масштабного коэффициента на 1 int arr[]; arr[x<<1]).

Необходимость копирования + сдвига обычна в ситуациях, когда xвсе еще необходимо исходное значение . Но большинство целочисленных инструкций x86 работают на месте. (Назначение является одним из источников для таких инструкций, как addили shl.) Соглашение о вызовах x86-64 System V передает аргументы в регистры, с первым аргументом ediи возвращаемым значением eax, поэтому функция, которая возвращает, x<<10также заставляет компилятор испускать копирование + сдвиг код.

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

gcc и clang оптимизируют эти функции одинаково, как вы можете видеть в проводнике компилятора Godbolt :

int shl1(int x) { return x<<1; }
    lea     eax, [rdi+rdi]   # 1 cycle latency, 1 uop
    ret

int shl2(int x) { return x<<2; }
    lea     eax, [4*rdi]    # longer encoding: needs a disp32 of 0 because there's no base register, only scaled-index.
    ret

int times5(int x) { return x * 5; }
    lea     eax, [rdi + 4*rdi]
    ret

int shl10(int x) { return x<<10; }
    mov     eax, edi         # 1 uop, 0 or 1 cycle latency
    shl     eax, 10          # 1 uop, 1 cycle latency
    ret

LEA с 2 компонентами имеет задержку в 1 цикл и пропускную способность 2 на такт на последних процессорах Intel и AMD. (Семейство Sandybridge и Bulldozer / Ryzen). На Intel это только 1 пропускная способность на такт с задержкой 3с для lea eax, [rdi + rsi + 123]. (Связано: почему этот код C ++ быстрее, чем моя рукописная сборка для проверки гипотезы Коллатца? Подробно рассматривается.)

В любом случае, для копирования + сдвига на 10 нужна отдельная movинструкция. На многих последних процессорах может быть нулевая задержка, но для этого по-прежнему требуется пропускная способность внешнего интерфейса и размер кода. ( Может ли x86 MOV действительно быть «бесплатным»? Почему я вообще не могу воспроизвести его? )

Также по теме: как умножить регистр на 37, используя только 2 последовательные инструкции leal в x86? .

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

Например, if(x<<1) { }можно использовать andдля проверки всех битов, кроме старшего. На x86 вы должны использовать testинструкцию, например test eax, 0x7fffffff/ jz .falseвместо shl eax,1 / jz. Эта оптимизация работает для любого количества сдвигов, а также работает на машинах, где большие сдвиги выполняются медленно (например, Pentium 4) или отсутствуют (некоторые микроконтроллеры).

Многие ISA имеют инструкции по манипулированию битами, помимо сдвига. например, PowerPC имеет множество инструкций по извлечению / вставке битовых полей. Или ARM имеет сдвиги исходных операндов как часть любой другой инструкции. (Таким образом, инструкции сдвига / поворота - это просто особая форма moveиспользования смещенного источника.)

Помните, что C не является языком ассемблера . Всегда смотрите на оптимизированный вывод компилятора, когда настраиваете исходный код для эффективной компиляции.

Питер Кордес
источник