Почему введение бесполезных инструкций MOV ускоряет узкую петлю в сборке x86_64?
Фон:
При оптимизации некоторого Pascal кода со встроенным языком ассемблера я заметил ненужную инструкцию MOV и удалил ее.
К моему удивлению, удаление ненужной команды заставило мою программу замедлить работу.
Я обнаружил, что добавление произвольных, бесполезных команд MOV увеличивает производительность еще больше.
Эффект неустойчивый и изменения, основанные на порядке выполнения: те же самые старшие инструкции, перенесенные на вверх или вниз одной строкой , создают замедление.
Я понимаю, что процессор делает всевозможные оптимизации и оптимизацию, но это больше похоже на черную магию.
Данные:
Версия моего кода условно компилирует три нежелательных операции в середине цикла, который запускает 2**20==1048576 раз. (Окружающая программа просто вычисляет хэши SHA-256.
Результаты на моей довольно старой машине (Intel (R) Core (TM) 2 CPU 6400 @2.13 GHz):
avg time (ms) with -dJUNKOPS: 1822.84 ms
avg time (ms) without: 1836.44 ms
Программы выполнялись 25 раз в цикле, причем порядок выполнения каждый раз изменялся случайным образом.
Выдержки:
{$asmmode intel}
procedure example_junkop_in_sha256;
var s1, t2 : uint32;
begin
// Here are parts of the SHA-256 algorithm, in Pascal:
// s0 {r10d} := ror(a, 2) xor ror(a, 13) xor ror(a, 22)
// s1 {r11d} := ror(e, 6) xor ror(e, 11) xor ror(e, 25)
// Here is how I translated them (side by side to show symmetry):
asm
MOV r8d, a ; MOV r9d, e
ROR r8d, 2 ; ROR r9d, 6
MOV r10d, r8d ; MOV r11d, r9d
ROR r8d, 11 {13 total} ; ROR r9d, 5 {11 total}
XOR r10d, r8d ; XOR r11d, r9d
ROR r8d, 9 {22 total} ; ROR r9d, 14 {25 total}
XOR r10d, r8d ; XOR r11d, r9d
// Here is the extraneous operation that I removed, causing a speedup
// s1 is the uint32 variable declared at the start of the Pascal code.
//
// I had cleaned up the code, so I no longer needed this variable, and
// could just leave the value sitting in the r11d register until I needed
// it again later.
//
// Since copying to RAM seemed like a waste, I removed the instruction,
// only to discover that the code ran slower without it.
{$IFDEF JUNKOPS}
MOV s1, r11d
{$ENDIF}
// The next part of the code just moves on to another part of SHA-256,
// maj { r12d } := (a and b) xor (a and c) xor (b and c)
mov r8d, a
mov r9d, b
mov r13d, r9d // Set aside a copy of b
and r9d, r8d
mov r12d, c
and r8d, r12d { a and c }
xor r9d, r8d
and r12d, r13d { c and b }
xor r12d, r9d
// Copying the calculated value to the same s1 variable is another speedup.
// As far as I can tell, it doesn't actually matter what register is copied,
// but moving this line up or down makes a huge difference.
{$IFDEF JUNKOPS}
MOV s1, r9d // after mov r12d, c
{$ENDIF}
// And here is where the two calculated values above are actually used:
// T2 {r12d} := S0 {r10d} + Maj {r12d};
ADD r12d, r10d
MOV T2, r12d
end
end;
Попробуйте сами:
Код находится в режиме онлайн в GitHub, если вы хотите попробовать сами.
Мои вопросы:
- Почему бесполезное копирование содержимого регистра в RAM повышает производительность?
- Почему одна и та же бесполезная инструкция обеспечивает ускорение на некоторых строках и замедление на других?
- Является ли это поведение чем-то, что может быть предсказано компилятором?
Ответы
Ответ 1
Наиболее вероятной причиной улучшения скорости является то, что:
- Вставка MOV сдвигает последующие инструкции на разные адреса памяти
- одна из этих перемещенных инструкций была важной условной ветвью
- эта ветвь неверно предсказана из-за сглаживания в таблице прогноза ветвей
- перемещение ветки устраняло псевдоним и позволяло правильной предсказанию ветки.
У вашего Core2 не сохраняется отдельная запись истории для каждого условного перехода. Вместо этого он сохраняет общую историю всех условных прыжков. Один из недостатков глобального прогноза ветвления заключается в том, что история разбавляется нерелевантной информацией, если разные условные скачки некоррелированы.
Этот маленький учебник по прогнозированию ветвлений показывает, как работают буферы ветвления. Буфер кэша индексируется нижней частью адреса команды перехода. Это хорошо работает, если две важные некоррелированные ветки не имеют одинаковых младших бит. В этом случае вы получаете псевдонимы, которые вызывают много неверно предсказанных ветвей (которые останавливают конвейер команд и замедляют вашу программу).
Если вы хотите понять, как неверные представления отрасли влияют на производительность, взгляните на этот отличный ответ: fooobar.com/questions/1/...
У компиляторов обычно недостаточно информации, чтобы знать, какие ветки будут иметь псевдоним и будут ли эти псевдонимы значительными. Однако эту информацию можно определить во время выполнения с помощью таких инструментов, как Cachegrind и VTune.
Ответ 2
Вы можете прочитать http://research.google.com/pubs/pub37077.html
TL; DR: случайная вставка инструкций nop в программах может легко увеличить производительность на 5% и более, и нет, компиляторы не могут легко использовать это. Обычно это комбинация предсказателя ветвей и поведения кэша, но это может быть так же хорошо, как, например, остановка станции резервирования (даже в случае, если нет цепочек зависимостей, которые нарушены или очевидные перераспределения ресурсов вообще).
Ответ 3
Я считаю, что в современных процессорах инструкции по сборке, будучи последним видимым слоем для программиста для предоставления инструкций по выполнению процессору, фактически представляют собой несколько уровней от фактического выполнения CPU.
Современные процессоры RISC/CISC гибриды, которые переводят CISC x86 во внутренние инструкции, которые больше по RISC в поведении. Кроме того, существуют анализаторы исполнения вне очереди, отраслевые предсказатели, Intel "micro-ops fusion", которые пытаются группировать команды в более крупные партии одновременной работы (вроде VLIW/Itanium titanic). Существуют даже границы кэша, которые могли бы сделать код более быстрым для бог-знает - почему, если он больше (возможно, контроллер кэша имеет более интеллектуальное решение или поддерживает его дольше).
CISC всегда располагал слоем трансляции на уровне микрокода, но дело в том, что с современными процессорами ситуация намного сложнее. Со всей дополнительной транзисторной недвижимостью в современных заводах по производству полупроводников процессоры могут, вероятно, параллельно применять несколько подходов к оптимизации, а затем выбрать тот, который в конце обеспечит наилучшее ускорение. Дополнительные инструкции могут смещать процессор, чтобы использовать один путь оптимизации, который лучше других.
Эффект дополнительных инструкций, вероятно, зависит от модели/поколения CPU/производителя и вряд ли будет предсказуемым. Оптимизация языка ассемблера таким образом потребовала бы выполнения многих поколений архитектуры ЦП, возможно, используя пути выполнения конкретных процессоров, и было бы желательно только для действительно действительно важных разделов кода, хотя, если вы выполняете сборку, вы, вероятно, уже знаете это.
Ответ 4
Подготовка кеша
Перемещение операций в память может подготовить кэш и сделать последующие операции перемещения быстрее. Процессор обычно имеет два блока нагрузки и один блок хранения. Блок загрузки может считывать из памяти в регистр (один считывается за цикл), запоминающее устройство хранится из регистра в память. Существуют также другие блоки, которые выполняют операции между регистрами. Все блоки работают параллельно. Таким образом, в каждом цикле мы можем выполнять сразу несколько операций, но не более двух нагрузок, одного хранилища и нескольких операций с регистром. Обычно это до 4 простых операций с равными регистрами, до 3 простых операций с регистрами XMM/YMM и 1-2 комплексными операциями с любыми регистрами. В вашем коде есть много операций с регистрами, поэтому одна операция в хранилище свободной памяти бесплатна (поскольку в любом случае существует более 4 операций с регистром), но она готовит кэш памяти для последующей операции хранилища. Чтобы узнать, как работают хранилища памяти, обратитесь к Справочное руководство по оптимизации архитектуры Intel 64 и IA-32.
Нарушение ложных зависимостей
Хотя это не совсем относится к вашему делу, но иногда использование 32-битных операций mov под 64-разрядным процессором (как в вашем случае) используется для очистки более высоких бит (32-63) и разрыва цепей зависимостей.
Хорошо известно, что в x86-64, используя 32-разрядные операнды, удаляются более высокие биты 64-разрядного регистра. Просьба прочитать соответствующий раздел - 3.4.1.1 - Руководство разработчика программного обеспечения Intel® 64 и IA-32 Volume Volume 1:
32-разрядные операнды генерируют 32-битный результат, с нулевым расширением до 64-битного результата в целевом регистре общего назначения
Таким образом, команды mov, которые могут показаться бесполезными с первого взгляда, очищают более высокие разряды соответствующих регистров. Что это дает нам? Он разбивает цепи зависимостей и позволяет выполнять команды параллельно, в случайном порядке, с помощью алгоритм вне порядка, реализованного внутри процессора с момента Pentium Pro в 1995 году.
Цитата из Справочное руководство по оптимизации архитектуры Intel® 64 и IA-32, раздел 3.5.1.8:
Последовательности кодов, которые изменяют частичный регистр, могут испытывать некоторую задержку в своей цепочке зависимостей, но их можно избежать, используя идиомы нарушения зависимости. В процессорах на базе микроархитектуры Intel Core ряд инструкций может помочь устранить зависимость от выполнения, когда программное обеспечение использует эту инструкцию для очистки регистрационного содержимого до нуля. Разделите зависимости от частей регистров между инструкциями, работая на 32-битных регистрах вместо частичных регистров. Для ходов, это может быть выполнено с помощью 32-битных перемещений или с помощью MOVZX.
Правило сборки/компилятора. Правило 37. (M impact, MH generality). Разрывные зависимости от частей регистров между инструкциями, работающие на 32-разрядных регистрах вместо частичных регистров. Для ходов это может быть выполнено с помощью 32-битных перемещений или с помощью MOVZX.
MOVZX и MOV с 32-разрядными операндами для x64 эквивалентны - все они разбивают цепи зависимостей.
Вот почему ваш код выполняется быстрее. Если нет зависимостей, ЦП может внутренне переименовывать регистры, хотя на первый взгляд может показаться, что вторая команда изменяет регистр, используемый первой инструкцией, и два не могут выполняться параллельно. Но из-за переименования регистров они могут.
Регистрация переименования - это метод, используемый внутренним процессором, который устраняет ложные зависимости данных, возникающие в результате повторного использования регистров с помощью последовательных инструкций, которые делают не имеют реальных зависимостей данных между ними.
Думаю, теперь вы видите, что это слишком очевидно.
