Какие коды операций быстрее на уровне процессора? [закрыто]

19

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

  1. побитовое
  2. Целочисленное сложение / вычитание
  3. Целочисленное умножение / деление
  4. сравнение
  5. Контроль потока
  6. Поплавок сложение / вычитание
  7. Умножение поплавков / деление

Там, где вам нужен высокопроизводительный код, C ++ можно оптимизировать вручную при сборке, использовать SIMD-инструкции или более эффективный поток управления, типы данных и т. Д. Поэтому я пытаюсь понять, является ли тип данных (int32 / float32 / float64) или операция используется ( *, +, &) влияет на производительность на уровне процессора.

  1. Является ли одиночное умножение на процессоре медленнее, чем сложение?
  2. В теории MCU вы узнаете, что скорость кодов операций определяется количеством циклов ЦП, которое требуется для выполнения. Значит ли это, что умножение занимает 4 цикла, а сложение - 2?
  3. Каковы скоростные характеристики основных математических и управляющих кодов потока?
  4. Если два кода операции выполняют одинаковое количество циклов, то оба могут использоваться взаимозаменяемо без какого-либо увеличения / потери производительности?
  5. Любые другие технические детали, которые вы можете поделиться относительно производительности процессора x86, приветствуются
Robinicks
источник
17
Это звучит очень похоже на преждевременную оптимизацию, и помните, что компилятор не выводит то, что вы вводите, и вы действительно не хотите писать ассемблер, если вы действительно этого не делаете.
Рой Т.
3
Умножение и деление чисел с плавающей запятой - это совершенно разные вещи, их не следует относить к одной категории. Для n-битных чисел умножение - это процесс O (n), а деление - это процесс O (nlogn). Это делает деление примерно в 5 раз медленнее, чем умножение на современных процессорах.
Сэм Хочевар
1
Единственный реальный ответ - «профиль это».
Тетрад
1
Если продолжить ответ Роя, то сборка с ручной оптимизацией почти всегда будет чистым убытком, если вы действительно не исключительны. Современные процессоры - очень сложные звери, и хорошие оптимизирующие компиляторы осуществляют преобразования кода, которые совершенно неочевидны и не тривиальны для кода вручную. Даже для SSE / SIMD всегда используйте встроенные функции в C / C ++ и позвольте компилятору оптимизировать их использование для вас. Использование необработанной сборки отключает оптимизацию компилятора, и вы теряете большие деньги.
Шон Мидлдич
Вам не нужно вручную оптимизировать сборку, чтобы использовать SIMD. SIMD очень полезно оптимизировать в зависимости от ситуации, но в основном используется стандартное соглашение (по крайней мере, оно работает на GCC и MSVC) для использования SSE2. Что касается вашего списка, то на современном суперскалярном многопотоковом процессоре зависимость от данных и давление в регистрах вызывают больше проблем, чем целочисленная и иногда производительность с плавающей запятой; То же самое относится и к локальности данных. Кстати, целочисленное деление такое же, как умножение на современном x86
OrgnlDave

Ответы:

26

Руководства по оптимизации Agner Fog превосходны. У него есть руководства, таблицы сроков выполнения инструкций и документы по микроархитектуре всех последних моделей процессоров x86 (начиная с Intel Pentium). Смотрите также некоторые другие ресурсы, связанные с /programming//tags/x86/info

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

Является ли одиночное умножение на процессоре медленнее, чем сложение?

Да (если только не степенью 2). (Задержка в 3-4 раза при пропускной способности Intel на уровне тактовых импульсов только одна). Однако не пытайтесь избежать этого, так как он добавляет 2 или 3.

Каковы скоростные характеристики основных математических и управляющих кодов потока?

Обратитесь к таблицам инструкций Agner Fog и руководству по микроархитектуре, если вы хотите точно знать : P. Будьте осторожны с условными прыжками. Безусловные переходы (например, вызовы функций) имеют небольшие накладные расходы, но не очень.

Если два кода операции выполняют одинаковое количество циклов, то оба могут использоваться взаимозаменяемо без какого-либо увеличения / потери производительности?

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

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

Документы по микроарху Agner Fog описывают конвейеры процессоров Intel и AMD достаточно подробно, чтобы точно определить, сколько циклов должно пройти цикл на одну итерацию, и является ли узким местом пропускная способность uop, цепочка зависимостей или конкуренция за один порт выполнения. Посмотрите некоторые мои ответы на StackOverflow, например, этот или этот .

Кроме того, http://www.realworldtech.com/haswell-cpu/ (и аналогично для более ранних версий) интересно читать, если вам нравится дизайн процессора.

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

TL: DR, эти числа составлены на основе того, что я представляю для «типичного» варианта использования, в качестве компромисса между задержкой, узкими местами порта выполнения и пропускной способностью внешнего интерфейса (или останавливается для таких вещей, как пропущенные переходы ). Пожалуйста, не используйте эти цифры для какого-либо серьезного анализа .

  • От 0,5 до 1 побитовое / целочисленное сложение / вычитание /
    сдвиг и вращение (счетчик времени компиляции) /
    векторные версии всех этих (от 1 до 4 на пропускную способность цикла, задержка 1 цикла)
  • 1 вектор min, max, сравнение-равно, сравнение-больше (для создания маски)
  • 1,5 векторных тасовок. У Haswell и новее есть только один порт для случайного воспроизведения, и мне кажется, что если вам нужен какой-то большой объем перетасовки, то, как правило, требуется больше, так что я взвешиваю его немного выше, чтобы побудить задуматься об использовании меньшего количества случайных комбинаций. Они не бесплатны, особенно если вам нужна маска управления pshufb из памяти.
  • Загрузка / хранение 1,5 (попадание в кэш L1. Пропускная способность лучше, чем задержка)
  • 1,75 целочисленного умножения (задержка 3c / один на 1c tput на Intel, 4c lat на AMD и только одна на 2c tput). Маленькие константы даже дешевле, используя LEA и / или ADD / SUB / shift . Но, конечно, константы времени компиляции всегда хороши и могут часто оптимизироваться в другие вещи. (И умножение в цикле часто может быть уменьшено силой компилятором до tmp += 7цикла вместо tmp = i*7)
  • 1.75 некоторая 256-битная векторная перестановка (дополнительная задержка для insns, которая может перемещать данные между 128-битными полосами вектора AVX). (Или от 3 до 7 на Райзене, где переулки, пересекающие переулок, нуждаются во многих мопах)
  • 2 fp add / sub (и векторные версии одного и того же) (1 или 2 на тактовую пропускную способность, задержка от 3 до 5 тактов). Может быть медленным, если вы ограничиваете время ожидания, например, суммируете массив только с 1 sumпеременной. (Я мог бы взвесить это и fp mul до 1 или до 5 в зависимости от варианта использования).
  • 2 векторных фп мул или FMA. (x * y + z такой же дешевый, как mul или add, если вы компилируете с включенной поддержкой FMA).
  • 2 вставка / извлечение регистров общего назначения в векторные элементы ( _mm_insert_epi8и т. Д.)
  • 2.25 vector int mul (16-битные элементы или pmaddubsw, выполняющие 8 * 8 -> 16-битные). Дешевле на Skylake, с лучшей пропускной способностью, чем скалярный муль
  • 2.25 сдвиг / поворот по переменному количеству (задержка 2c, пропускная способность один на 2c в Intel, быстрее в AMD или с BMI2)
  • 2.5 Сравнение без разветвления ( y = x ? a : b, или y = x >= 0) ( test / setccили cmov)
  • 3 int-> float преобразование
  • 3 отлично предсказанных потока управления (предсказанное ветвление, вызов, возврат).
  • 4 вектора int mul (32-битные элементы) (2 мопа, задержка 10 с на Haswell)
  • 4 целочисленное деление или %по константе времени компиляции (не степень 2).
  • 7 векторных горизонтальных операций (например, PHADDдобавление значений внутри вектора)
  • 11 (вектор) деление FP (задержка 10-13c, по одному на пропускную способность 7c или хуже). (Может быть дешевым, если используется редко, но пропускная способность в 6-40 раз хуже, чем у FP mul)
  • 13? Поток управления (плохо предсказанная ветвь, возможно, предсказуемая на 75%)
  • 13 int Division ( да, действительно , это медленнее, чем деление FP, и не может векторизовать). (обратите внимание, что компиляторы делят на константу, используя mul / shift / add с магической константой , а div / mod степенями 2 очень дешево.)
  • 16 (вектор) FP sqrt
  • 25? загрузка (попадание в кэш L3). (магазины с отсутствующим кэшем дешевле, чем загружаемые.)
  • 50? FP trig / exp / log. Если вам нужно много опыта / журнала и вам не нужна полная точность, вы можете обменять точность на скорость с более коротким полиномом и / или таблицей. Вы также можете SIMD векторизации.
  • 50-80? всегда -mispredicted ветвь, стоимость 15-20 циклов
  • 200-400? загрузить / сохранить (отсутствует кеш)
  • 3000 ??? чтение страницы из файла (попадание в дисковый кеш ОС) (здесь цифры составляют)
  • 20000 ??? страница чтения с диска (отсутствие дискового кэша в ОС, быстрый SSD) (полностью подготовленный номер)

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

Относительная стоимость вещей на процессорах AMD будет одинаковой, за исключением того, что они имеют более быстрые целочисленные сдвиги, когда число сдвигов является переменным. Процессоры семейства AMD Bulldozer, разумеется, работают медленнее в большинстве программ по ряду причин. (Ryzen довольно хорош во многих вещах).

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

«Медленная» операция, такая как деление на FP, может быть очень дешевой, если окружающий код заставляет процессор загружаться другой работой . (вектор FP или sqrt равен 1 моп каждый, у них просто плохая задержка и пропускная способность. Они блокируют только блок деления, а не весь порт выполнения, на котором он находится. Целочисленный div - это несколько моп.) Так что, если у вас только один делитель FP на каждые ~ 20 муль и сложение, и для ЦП есть другая работа (например, независимая итерация цикла), тогда «стоимость» div FP может быть примерно такой же, как муль FP. Вероятно, это лучший пример чего-то, что имеет низкую пропускную способность, когда все, что вы делаете, но очень хорошо сочетается с другим кодом (когда задержка не имеет значения), из-за низкого общего числа мопов.

Обратите внимание, что целочисленное деление не так дружелюбно по отношению к окружающему коду: в Haswell это 9 моп, с пропускной способностью 8-11c и задержкой 22-29c. (64-битное деление намного медленнее, даже на Skylake.) Таким образом, задержки и числа пропускной способности несколько похожи на FP div, но FP div - это всего лишь один шаг.

Для примеров анализа короткой последовательности insns для пропускной способности, задержки и общего числа мопов см. Некоторые из моих ответов SO:

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

Питер Кордес
источник
«Предсказанная ветвь» в 4 имеет смысл - какой должна быть «предсказанная ветвь» в 20-25? (Я думал, что неправильно предсказанные ветви (их было около 13) гораздо дороже, но именно поэтому я на этой странице, чтобы узнать что-то ближе к истине - спасибо за отличный стол!)
Мэтт
@Matt: я думаю, что это была ошибка редактирования, и она должна была быть "непредсказуемой ветвью". Спасибо что подметил это. Обратите внимание, что 13 - для ветки с непредсказуемым прогнозом, а не для ветки с неправильным прогнозом, поэтому я пояснил это. Я заново сделал ручную завивку и внес некоторые правки. : P
Питер Кордес
16

Это зависит от рассматриваемого процессора, но для современного процессора список выглядит примерно так:

  1. Побит, сложение, вычитание, сравнение, умножение
  2. разделение
  3. Контроль потока (см. Ответ 3)

В зависимости от ЦП может быть значительная плата за работу с 64-битными типами данных.

Ваши вопросы:

  1. Совсем нет или не заметно на современном процессоре. Зависит от процессора.
  2. Эта информация устарела на 20-30 лет (школа отстой, теперь у вас есть доказательства), современные процессоры обрабатывают различное количество инструкций за такт, сколько зависит от того, что придумал планировщик.
  3. Деление немного медленнее, чем остальные, поток управления очень быстрый, если прогноз ветвления правильный, и очень медленный, если он неправильный (что-то вроде 20 циклов, зависит от процессора). В результате большая часть кода ограничена главным образом потоком управления. Не делайте с ifтем, что вы можете разумно делать с арифметикой.
  4. Не существует фиксированного числа для того, сколько циклов занимает любая инструкция, но иногда две разные инструкции могут работать одинаково, помещать их в другой контекст и, возможно, нет, запускать их на другом процессоре, и вы, вероятно, увидите третий результат.
  5. Помимо потока управления другая большая трата времени - это потеря кеша, всякий раз, когда вы пытаетесь прочитать данные, которых нет в кеше, ЦПУ придется ждать, пока они будут извлечены из памяти. В общем, вы должны пытаться обрабатывать данные рядом друг с другом, а не собирать данные повсюду.

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

AAAAAAAAAAAA
источник
Я также хотел бы отметить, что FPU чертовски быстр: особенно на Intel - поэтому фиксированная точка действительно нужна, только если вы хотите получить детерминированные результаты.
Джонатан Дикинсон
2
Я бы просто сделал больший акцент на последней части - сделаю хорошую игру. Это помогает иметь ясный код - вот почему 3. применяется только тогда, когда вы действительно измеряете проблему производительности. Всегда легко превратить эти if в нечто лучшее, если возникнет такая необходимость. С другой стороны, 5. сложнее - я определенно согласен, что это тот случай, когда вы действительно хотите сначала подумать, поскольку обычно это означает изменение архитектуры.
Луаан
3

Я сделал тест на целочисленные операции, которые зациклились миллион раз на x64_64, и пришел к краткому выводу, как показано ниже:

добавить --- 116 микросекунд

суб ---- 116 микросекунд

мул ---- 1036 микросекунд

Div ---- 13037 микросекунд

приведенные выше данные уже уменьшили накладные расходы, вызванные циклом,

hxiao
источник
2

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

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

Zoner
источник
+1, зависимые нагрузки (погоня за указателем) это большое дело. Отсутствие кэша заблокирует будущие загрузки даже от начала работы. Наличие большого количества загрузок из основной памяти в полете одновременно дает гораздо лучшую пропускную способность, чем при выполнении одной операции, требующей полной завершения предыдущего.
Питер Кордес