Почему введение бесполезных инструкций MOV ускоряет сжатый цикл в сборке x86_64?

222

Задний план:

При оптимизации кода на Pascal со встроенным языком ассемблера я заметил ненужную MOVинструкцию и удалил ее.

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

Я обнаружил, что добавление произвольных, бесполезных MOVинструкций еще больше повышает производительность .

Эффект нестабилен и изменяется в зависимости от порядка выполнения: одни и те же ненужные инструкции, перемещаемые вверх или вниз на одну строку, вызывают замедление .

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

Данные:

Версия моего кода условно компилирует три ненужные операции в середине цикла, который выполняется 2**20==1048576раз. (Окружающая программа просто вычисляет хэши SHA-256 ).

Результаты на моей довольно старой машине (Intel® Core ™ 2 CPU 6400 @ 2,13 ГГц):

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, если вы хотите попробовать его сами.

Мои вопросы:

  • Зачем бесполезно копировать содержимое регистра в оперативную память, чтобы повысить производительность?
  • Почему одна и та же бесполезная инструкция может ускорить некоторые строки и замедлить работу других?
  • Это поведение может быть предсказуемо использовано компилятором?
tangentstorm
источник
7
Существуют всевозможные «бесполезные» инструкции, которые могут фактически служить для разрыва цепочек зависимостей, пометки физических регистров как вышедших из употребления и т. Д. Для использования этих операций требуется некоторое знание микроархитектуры . Ваш вопрос должен содержать краткую последовательность инструкций в качестве минимального примера, а не направлять людей на github.
Бретт Хейл
1
@BrettHale хороший момент, спасибо. Я добавил отрывок кода с некоторыми комментариями. Будет ли копирование значения регистра в оперативную память помечать регистр как удаленный, даже если значение в нем будет использовано позже?
тангентсторм
9
Можете ли вы указать стандартное отклонение для этих средних? В этом посте нет никаких реальных указаний на то, что есть реальная разница.
Starwed
2
Можете ли вы попробовать синхронизировать инструкции, используя инструкцию rdtscp, и проверить тактовые циклы для обеих версий?
Якобботч
2
Это также может быть связано с выравниванием памяти? Я не делал математику сам (ленивый: P), но добавление некоторых фиктивных инструкций может привести к выравниванию памяти в вашем коде ...
Лоренцо Дематте

Ответы:

144

Наиболее вероятной причиной улучшения скорости является то, что:

  • вставка MOV сдвигает последующие инструкции в разные адреса памяти
  • одна из этих перемещенных инструкций была важной условной ветвью
  • эта ветвь была неправильно предсказана из-за наложения в таблице предсказания ветвления
  • перемещение ветви исключило псевдоним и позволило правильно прогнозировать ветку

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

Этот небольшой учебник по предсказанию ветвлений показывает, как работают буферы предсказания ветвлений. Буфер кеша индексируется по нижней части адреса инструкции ветвления. Это работает хорошо, если две важные некоррелированные ветви не используют одни и те же младшие биты. В этом случае вы получаете псевдонимы, которые вызывают много непредсказуемых переходов (что приводит к остановке конвейера команд и замедлению вашей программы).

Если вы хотите понять, как неправильные прогнозы веток влияют на производительность, взгляните на этот превосходный ответ: https://stackoverflow.com/a/11227902/1001643

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

Раймонд Хеттингер
источник
2
Хм. Это звучит многообещающе. Единственными условными ветвями в этой реализации sha256 являются проверки конца цикла FOR. В то время я пометил эту ревизию как странность в git и продолжил оптимизацию. Одним из моих следующих шагов было переписать паскаль цикла FOR самостоятельно в сборке, после чего эти дополнительные инструкции больше не давали положительного эффекта. Возможно, сгенерированный код бесплатного паскаля для процессора было сложнее предсказать, чем простой счетчик, которым я его заменил.
тангентсторм
1
@tangentstorm Звучит как хорошее резюме. Таблица прогнозирования ветвлений не очень велика, поэтому одна запись таблицы может относиться к нескольким ветвям. Это может сделать некоторые прогнозы бесполезными. Проблема легко решается, если одна из конфликтующих ветвей перемещается в другую часть таблицы. Практически любое небольшое изменение может сделать это :-)
Рэймонд Хеттингер
1
Я думаю, что это наиболее разумное объяснение конкретного поведения, которое я наблюдал, поэтому я собираюсь отметить это как ответ. Спасибо. :)
tangentstorm
3
Существует совершенно превосходное обсуждение подобной проблемы, с которой столкнулся один из авторов Bochs, вы можете добавить это к своему ответу: emulators.com/docs/nx25_nostradamus.htm
leander
3
Выравнивание Insn имеет гораздо большее значение, чем просто цели ветвления. Узкие места декодирования - огромная проблема для Core2 и Nehalem: часто бывает сложно поддерживать занятость своих исполнительных блоков. Внедрение Sandybridge UOP-кэша значительно увеличило пропускную способность внешнего интерфейса. Из- за этой проблемы выполняется выравнивание целей ветвления , но это влияет на весь код.
Питер Кордес
80

Вы можете прочитать http://research.google.com/pubs/pub37077.html

TL; DR: произвольная вставка nop-инструкций в программы может легко увеличить производительность на 5% и более, и нет, компиляторы не могут легко это использовать. Обычно это комбинация предиктора ветвления и поведения кэша, но это также может быть, например, остановка станции резервирования (даже в том случае, если нет цепочек зависимостей, которые нарушены, или явная переоценка ресурсов вообще).

Джонас Мейбе
источник
1
Интересный. Но достаточно ли умен процессор (или FPC), чтобы видеть, что запись в оперативную память в данном случае является NOP?
тангентсторм
8
Ассемблер не оптимизирован.
Марко ван де Воорт
5
Компиляторы могут использовать его, выполняя невероятно дорогие оптимизации, такие как многократное построение и профилирование, а затем изменяя выходные данные компилятора с помощью имитированного отжига или генетического алгоритма. Я читал о некоторых работах в этой области. Но мы говорим минимум о 5-10 минутах 100% загрузки процессора для компиляции, и в результате оптимизация, вероятно, будет зависеть от модели ядра процессора и даже от конкретной версии ядра или микрокода.
Адам Иерименко
Я бы не назвал это случайным NOP, они объясняют, почему NOP могут положительно влиять на производительность (tl; dr: stackoverflow.com/a/5901856/357198 ), а случайное добавление NOP приводило к снижению производительности. Интересно, что удаление «стратегического» NOP GCC не повлияло на производительность в целом!
PuercoPop
15

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

Современные процессоры - это гибриды RISC / CISC, которые переводят инструкции CISC x86 во внутренние инструкции, которые в большей степени соответствуют RISC. Кроме того, существуют анализаторы выполнения вне очереди, предсказатели ветвлений, Intel 'micro-ops fusion', которые пытаются сгруппировать инструкции в более крупные партии одновременной работы (вроде VLIW / Itanium titanic). Есть даже границы кеша, которые могут заставить код работать быстрее, если уж бог знает почему, если он больше (возможно, контроллер кеша размещает его более разумно или дольше удерживает).

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

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

cowarldlydragon
источник
6
Ваш ответ немного запутанный. Во многих местах кажется, что вы догадались, хотя большинство из того, что вы говорите, верно.
Alcuadrado
2
Может быть, я должен уточнить. Что меня смущает, так это отсутствие уверенности
alcuadrado
3
гадание, которое имеет смысл и с хорошей аргументацией, полностью обоснованно.
Jturolla
7
Никто не может точно знать, почему OP наблюдает за этим странным поведением, если только у инженера Intel нет доступа к специальному диагностическому оборудованию. Так что все остальные могут сделать, это угадать. Это не вина @ cowarldlydragon.
Алекс Д
2
Downvote; Ничто из того, что вы говорите, не объясняет поведение, которое видит OP. Ваш ответ бесполезен.
fuz
0

Подготовка кеша

Операции перемещения в память могут подготовить кэш и ускорить последующие операции перемещения. Процессор обычно имеет две единицы нагрузки и одну единицу хранения. Модуль загрузки может считывать данные из памяти в регистр (одно чтение за цикл), а модуль хранения сохраняет данные из регистра в память. Есть и другие устройства, которые выполняют операции между регистрами. Все подразделения работают параллельно. Таким образом, в каждом цикле мы можем выполнять несколько операций одновременно, но не более двух загрузок, одного хранилища и нескольких операций регистра. Обычно это до 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 :

32-битные операнды генерируют 32-битный результат, расширенный от нуля до 64-битного результата в целевом регистре назначения

Таким образом, инструкции mov, которые на первый взгляд могут показаться бесполезными, очищают старшие биты соответствующих регистров. Что это нам дает? Он разрывает цепочки зависимостей и позволяет выполнять инструкции параллельно, в произвольном порядке, с помощью алгоритма Out-of-Order, реализованного внутренне процессорами начиная с Pentium Pro в 1995 году.

Цитата из Справочного руководства по оптимизации архитектур Intel® 64 и IA-32 , раздел 3.5.1.8:

Последовательности кода, которые модифицируют частичный регистр, могут испытывать некоторую задержку в своей цепочке зависимостей, но этого можно избежать, используя идиомы разрыва зависимостей. В процессорах, основанных на микроархитектуре Intel Core, ряд инструкций может помочь очистить зависимость выполнения, когда программное обеспечение использует эти инструкции для очистки содержимого регистра до нуля. Разрывать зависимости между частями регистров между инструкциями, используя 32-битные регистры вместо частичных регистров. Для ходов это можно сделать с помощью 32-битных ходов или с помощью MOVZX.

Правило 37 кодирования ассемблера / компилятора (влияние M, универсальность MH) : Разрывать зависимости между частями регистров между инструкциями, используя 32-битные регистры вместо частичных регистров. Для ходов это можно сделать с помощью 32-битных ходов или с помощью MOVZX.

MOVZX и MOV с 32-разрядными операндами для x64 эквивалентны - все они разрывают цепочки зависимостей.

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

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

Я думаю, вы теперь видите, что это слишком очевидно.

Максим Масютин
источник
Это все верно, но не имеет ничего общего с кодом, представленным в вопросе.
Коди Грей
@CodyGray - спасибо за ваш отзыв. Я отредактировал ответ и добавил главу о том, что перемещение в память, окруженное операциями регистра, подготавливает кэш, и он свободен, так как хранилище в любом случае не используется. Таким образом, последующая операция магазина будет быстрее.
Максим Масютин