Почему введение бесполезных инструкций MOV ускоряет жесткий цикл в сборке x86 64?
Справочная информация:
при оптимизации некоторых Паскаль код со встроенным языком ассемблера, я заметил ненужный 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 когда-нибудь прирост производительности?
- почему одна и та же бесполезная инструкция обеспечивает ускорение на одних линиях и замедление на других?
- является ли это поведение чем-то, что может быть предсказуемо использовано компилятором?
4 ответа:
наиболее вероятной причиной повышения скорости является то, что:
- вставка MOV сдвигает последующие инструкции на разные адреса памяти
- один из тех, кто переехал инструкции является важным условное ветвление
- эта ветвь была неправильно предсказана из-за сглаживания в таблице предсказания ветвей
- перемещение ветви устранило псевдоним и позволило правильно предсказать ветвь
ваш Core2 не хранит отдельную запись истории для каждого условного перехода. Вместо этого он сохраняет общую историю всех условных прыжков. Один недостаток глобальные предсказания ветвлений заключается в том, что история разбавляется нерелевантной информацией, если различные условные скачки некоррелированы.
этот учебник по прогнозированию ветвей показывает, как работают буферы прогнозирования ветвей. Буфер кэша индексируется нижней частью адреса инструкция филиала. Это хорошо работает, если две важные некоррелированные ветви не имеют одинаковых младших битов. В этом случае вы получаете псевдоним, который вызывает много неверно предсказанных ветвей (которые останавливают конвейер инструкций и замедляют вашу программу).
Если вы хотите понять, как неверные предсказания ветвей влияют на производительность, взгляните на этот отличный ответ:https://stackoverflow.com/a/11227902/1001643
компиляторы обычно не хватает информация, чтобы знать, какие ветви будут псевдонимы и будут ли эти псевдонимы значимыми. Однако эта информация может быть определена во время выполнения с помощью таких инструментов, как Cachegrind и VTune.
вы можете прочитать http://research.google.com/pubs/pub37077.html
TL;DR: случайная вставка инструкций nop в программы может легко увеличить производительность на 5% или более, и нет, компиляторы не могут легко использовать это. Обычно это комбинация предиктора ветвления и поведения кэша, но она также может быть, например, остановкой станции резервирования (даже в случае отсутствия цепочек зависимостей, которые нарушены или очевидны избыточные подписки на ресурсы любой.)
Я верю в современные процессоры инструкции по сборке, будучи последним видимым слоем для программиста для предоставления инструкций выполнения процессору, на самом деле являются несколькими слоями от фактического выполнения процессором.
современные процессоры RISC/ CISC гибриды, которые переводят инструкции CISC x86 во внутренние инструкции, которые являются более рискованными в поведении. Кроме того, из-за того, газоанализаторов исполнения, предикторы филиал, корпорации Intel "микро-ОПС fusion", которые пытаются группировать инструкции в большие партии одновременной работы (вроде как VLIW/ Itanium "Титаник"). Есть даже границы кэша, которые могут заставить код работать быстрее для бог знает почему, если он больше (возможно, контроллер кэша прорезает его более разумно или держит его дольше).
У CISC всегда был слой перевода сборки в микрокод, но дело в том, что с современными процессорами все намного намного больше сложный. Со всей дополнительной транзисторной недвижимостью в современных заводах по производству полупроводников процессоры, вероятно, могут применять несколько подходов к оптимизации параллельно, а затем выбрать тот, который обеспечивает лучшее ускорение. Дополнительные инструкции могут смещать процессор, чтобы использовать один путь оптимизации, который лучше других.
эффект дополнительных инструкций, вероятно, зависит от модели / поколения / производителя процессора и вряд ли будет предсказуемым. Оптимизация языка ассемблера таким образом потребует выполнения для многих поколений архитектуры ЦП, возможно, с использованием специфичных для ЦП путей выполнения, и будет желательна только для действительно важных разделов кода, хотя если вы делаете сборку, вы, вероятно, уже знаете это.
подготовка кэша
перемещение операций в память может подготовить кэш и сделать последующие операции перемещения быстрее. Процессор обычно имеет два блока загрузки и один блок хранения. Блок нагрузки может прочитать от памяти в регистр (одно прочитанное в цикл), блок магазина хранит от регистра к памяти. Есть также другие единицы, которые выполняют операции между регистрами. Все блоки работают параллельно. Таким образом, на каждом цикле мы можем выполнять сразу несколько операций, но не более двух нагрузок, одной хранить и несколько операций регистрации. Обычно это до 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 архитектуры руководство разработчика программного обеспечения Том 1:
алгоритм выхода из строя реализовано внутри процессоров с Pentium Pro в 1995 году.32-разрядные операнды генерируют 32-разрядный результат, нулевое расширение до 64-разрядного результата в целевом регистре общего назначения
цитата справочное руководство по оптимизации архитектур Intel® 64 и IA-32 раздел 3.5.1.8:
кодовые последовательности, которые изменяют частичный регистр, могут испытывать некоторую задержку в своей цепочке зависимостей, но их можно избежать, используя идиомы разрыва зависимостей. В процессорах на базе Intel Core микроархитектура, ряд инструкций может помочь очистить зависимость выполнения, когда программное обеспечение использует эти инструкции для очистки содержимого регистра до нуля. Разбейте зависимости на части регистров между инструкциями, работая на 32-разрядных регистрах вместо частичных регистров. Для ходы, это может быть достигнуто с помощью 32-битных ходов или с помощью MOVZX.
Правило Кодирования Сборки / Компилятора 37. (М ударе, МН общности): разбить зависимости на части регистры между инструкциями путем работы на 32-разрядных регистрах вместо частичных регистров. Для ходов это можно сделать с помощью 32-битных ходов или с помощью MOVZX.
MOVZX и MOV с 32-битными операндами для x64 эквивалентны - все они разрывают цепочки зависимостей.
вот почему ваш код выполняется быстрее. Если нет зависимостей, ЦП может внутренне переименовать регистры, хотя на первый взгляд может показаться, что вторая инструкция изменяет регистр, используемый первой инструкцией, и они не могут выполняться параллельно. Но из-за регистрации переименования они могут.
зарегистрировать переименование это метод, используемый внутренне процессором, который устраняет ложные зависимости данных, возникающие при повторном использовании регистров последовательными инструкциями, которые не имеют никаких реальных зависимостей данных между ними.
Я думаю, теперь вы видите, что это слишком очевидно.