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

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

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

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

1. Является ли одиночное умножение на процессоре медленнее, чем сложение?
2. В теории MCU вы узнаете, что скорость кодов операций определяется количеством циклов ЦП, которое требуется для выполнения. Значит ли это, что умножение занимает 4 цикла, а сложение - 2?
3. Каковы скоростные характеристики основных математических и управляющих кодов потока?
4. Если два кода операции выполняют одинаковое количество циклов, то оба могут использоваться взаимозаменяемо без какого-либо увеличения / потери производительности?
5. Любые другие технические детали, которые вы можете поделиться относительно производительности процессора x86, приветствуются

Руководства по оптимизации 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:

• Раздел «Анализ производительности» этого ответа суммирует вещи. Остальная часть ответа посвящена оптимизации цикла, который заключаетсяsum += x[i] * y[i]в развертывании с несколькими векторными аккумуляторами, чтобы скрыть задержку FMA. Он довольно технический и низкоуровневый, но показывает тип вывода на ассемблере, который вы хотите получить от компилятора, и почему это важно.
• Почему этот код C ++ быстрее, чем моя рукописная сборка для проверки гипотезы Коллатца? Этот популярный ответ, который я написал, объясняет, как держать компилятор в руках, чтобы по возможности сделать лучше asm. Также некоторые детали оптимизации asm, которые позволят вам опередить компилятор для небольших функций / циклов в этом случае. ИДК, почему у него гораздо больше откликов, чем у любого другого моего ответа.
• Каков эффективный способ подсчета установленных битов в позиции или ниже? : Тщательный анализ последовательности из 6 insns для интересной проблемы, когда некоторые ручные операции в исходном коде C привели к тому, что gcc сделал лучший код. Некоторые из моих других ответов предназначены для еще более коротких последовательностей инструкций.
• Самый быстрый калькулятор абсолютного значения с использованием SSE
• Проблемы с ADC / SBB и INC / DEC в тесных циклах на некоторых процессорах
• Быстрая векторизация rsqrt и обратная с SSE / AVX в зависимости от точности
• Сортировка 64-битных структур с использованием AVX?
• /programming//search?q=user%3A224132+throughput+latency+cycles

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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