Почему мой l oop намного быстрее, когда он содержится в одной строке кэша?

Question

Когда я запускаю эту маленькую программу сборки на своем Ryzen 9 3900X:

_start:   xor       rax, rax
          xor       rcx, rcx
loop0:    add       rax, 1
          mov       rdx, rax
          and       rdx, 1
          add       rcx, rdx
          cmp       rcx, 1000000000
          jne       loop0

Она завершается за 450 мс, если все инструкции между loop0 и до jne включительно полностью содержатся в одной кэш-строке , То есть, если:

round ((адрес цикла 0) / 64) == round ((адрес конца jne-инструкции) / 64)

Однако, если вышеуказанное условие не удерживается, вместо l oop требуется 900 мс.

Я сделал репо с кодом https://github.com/avl/strange_performance_repro.

Почему внутренний l oop намного медленнее в некоторых конкретных c случаях?

Редактировать: Удалено утверждение с выводом из-за ошибки при тестировании.

Answer 1

Ваша проблема заключается в переменной стоимости инструкции jne.

Прежде всего, чтобы понять влияние эффекта, нам нужно проанализировать сам полный l oop. Архитектура Ryzen 9 3900X - это Zen2. Мы можем получить информацию об этом на веб-сайте AMD или также WikiChip . Эта архитектура имеет 4 ALU и 3 AGU. Это примерно означает, что он может выполнять до 4 инструкций, таких как add / и / cmp за цикл.

Здесь указана стоимость каждой инструкции l oop (на основе таблицы команд Agner Fog для Zen1 ):

                                        # Reciprocal throughput
loop0:    add       rax, 1              # 0.25
          mov       rdx, rax            # 0.2
          and       rdx, 1              # 0.25
          add       rcx, rdx            # 0.25
          cmp       rcx, 1000000000     # 0.25  | Fused  0.5-2 (2 if jumping)
          jne       loop0               # 0.5-2 |

Как видите, 4 первые инструкции по вычислению l oop могут выполняться за ~ 1 цикл. Две последние инструкции могут быть объединены вашим процессором в более быструю. Ваша главная проблема в том, что эта последняя инструкция jne может быть довольно медленной по сравнению с остальной частью l oop. Таким образом, вы, скорее всего, будете измерять только издержки этой инструкции. С этого момента, вещи начинают быть сложными.

1019 * инженер и исследователь работал жесткий последние десятилетия снизить стоимость таких указаний на (почти) любой ценой. В настоящее время процессоры (например, Ryzen 9 3900X) используют планирование команд вне очереди для выполнения зависимых инструкций , требуемых инструкцией jne, как можно скорее. Большинство процессоров также могут прогнозировать адрес следующей инструкции, которая будет выполнена после jne и извлечения новых инструкций (например, одной из следующей итерации l oop), пока выполняется другая инструкция текущей итерации l oop. Выполнение выборки в кратчайшие сроки важно для предотвращения любого зависания при выполнении конвейера процессора (особенно в вашем случае).

Из документа AMD "Руководство по оптимизации программного обеспечения для семейств AMD 17h для моделей 30h и процессоров Greater " мы можем читать:

• 2.8.3 L oop Выравнивание:

  Для процессора l oop выравнивание обычно не является существенной проблемой. Однако для горячих циклов могут быть полезны некоторые дополнительные знания о компромиссах. Поскольку процессор может считывать выровненный 64-байтовый блок выборки каждый цикл, лучше всего по возможности выровнять конец l oop с последним байтом 64-байтовой строки кэша.

• 2.8.1.1 Logi следующего адреса c

  Logi следующего адреса c определяет адреса для выборки команд. [...]. Когда ветви идентифицированы, логика следующего адреса c перенаправляется аппаратным средством назначения и прогнозирования направления ветвления для генерации непоследовательного адреса блока выборки. Средства процессора, предназначенные для прогнозирования следующей инструкции, которая будет выполнена после перехода, подробно описаны в следующих разделах.

Таким образом, выполняя условное переход к инструкциям, расположенным в другой Строка кэша вводит дополнительные издержки задержки из-за выборки Op Cache (кэш команд быстрее, чем L1), который не требуется, если весь l oop помещается в 1 строку кэша. Действительно, если al oop пересекает строку кэша, требуется 2 выборки из кэша строки, что занимает не менее 2 циклов. Если все l oop помещается в строку кэша, требуется только одна выборка из 1 строки в кэше, которая занимает всего 1 цикл. В результате, поскольку ваши итерации l oop очень быстрые, оплата одного дополнительного цикла приводит к значительному замедлению. Но сколько?

Вы говорите, что программа занимает около 450 мс. Поскольку турбо частота Ryzen 9 3900X составляет 4,6 ГГц, а ваша l oop выполняется 2e9 раз, число циклов на одну итерацию l oop составляет 1,035. Обратите внимание, что это лучше, чем мы могли ожидать раньше (я думаю, этот процессор может переименовывать регистры, игнорировать инструкцию mov, выполнять инструкцию jne параллельно всего за 1 цикл, тогда как другие инструкции l oop идеально конвейерные, что поразительно). Это также показывает, что оплата дополнительных накладных расходов на 1 цикл удвоит количество циклов, необходимых для выполнения каждой итерации l oop, и, следовательно, общее время выполнения .

Если вы этого не сделаете Если вы хотите оплатить эти накладные расходы, рассмотрите вариант , развернув свой l oop, чтобы значительно сократить количество условных ветвлений и непоследовательных выборок.

Эта проблема может возникать на других архитектурах например на Intel Skylake. Действительно, тот же самый l oop на i5-9600KF занимает 0,70 с с выравниванием l oop и 0,90 без (также из-за дополнительной задержки в 1 цикле выборки). При 8-кратном развертывании результат равен 0,53 с (независимо от выравнивания).