Может ли MOV x86 действительно быть "свободным"? Почему я не могу воспроизвести это вообще?
Я продолжаю видеть, как люди утверждают, что инструкция MOV может быть бесплатной в x86 из-за переименования регистров.
На всю жизнь я не могу проверить это ни в одном тестовом случае. Каждый тестовый пример, который я пробую, развенчивает это.
Например, вот код, который я компилирую с Visual C++:
#include <limits.h>
#include <stdio.h>
#include <time.h>
int main(void)
{
unsigned int k, l, j;
clock_t tstart = clock();
for (k = 0, j = 0, l = 0; j < UINT_MAX; ++j)
{
++k;
k = j; // <-- comment out this line to remove the MOV instruction
l += j;
}
fprintf(stderr, "%d ms\n", (int)((clock() - tstart) * 1000 / CLOCKS_PER_SEC));
fflush(stderr);
return (int)(k + j + l);
}
Это приводит к следующему ассемблерному коду для цикла (не стесняйтесь создавать его так, как вы хотите; вам, очевидно, не нужен Visual C++):
LOOP:
add edi,esi
mov ebx,esi
inc esi
cmp esi,FFFFFFFFh
jc LOOP
Теперь я запускаю эту программу несколько раз и наблюдаю довольно постоянную разницу в 2% при удалении инструкции MOV:
Without MOV With MOV
1303 ms 1358 ms
1324 ms 1363 ms
1310 ms 1345 ms
1304 ms 1343 ms
1309 ms 1334 ms
1312 ms 1336 ms
1320 ms 1311 ms
1302 ms 1350 ms
1319 ms 1339 ms
1324 ms 1338 ms
Так что же дает? Почему MOV не "бесплатно"? Этот цикл слишком сложен для x86?
Есть ли один пример, который может продемонстрировать, что MOV свободен, как утверждают люди?
Если так, то, что это? И если нет, то почему все продолжают утверждать, что MOV является бесплатным?
2 ответа
Пропускная способность рассматриваемого цикла не зависит от задержки MOV или (от Haswell) преимущества неиспользования исполнительного блока.
Цикл все еще только 4 мопа для внешнего интерфейса, чтобы выдать в ядро не в порядке. (mov все еще должен отслеживаться неработающим ядром, даже если ему не нужен исполнительный блок, но cmp/jc макроплавки в один моп).
У процессоров Intel начиная с Core2 была проблема ширины 4 мопа за такт, поэтому mov не мешает ему выполнять (близко к) один итер в час на Haswell. Это также будет работать по одному за часы на Ivybridge (с устранением mov), но не на Sandybridge (без устранения mov). На SnB это будет около одного итера на циклы 1.333c, узкое место в пропускной способности ALU, потому что mov всегда будет нужен (У SnB/IvB есть только три порта ALU, в то время как у Haswell четыре).
Обратите внимание, что специальная обработка на этапе переименования была для x87 FXCHG (swap st0 с st1) гораздо дольше чем мов. Agner Fog перечисляет FXCHG как 0 латентности на PPro/PII/PIII (ядро P6 первого поколения).
Цикл в вопросе имеет две взаимосвязанные цепочки зависимостей (add edi,esi зависит от EDI и счетчика циклов ESI), что делает его более чувствительным к несовершенному планированию. Замедление на 2% по сравнению с теоретическим прогнозом из-за, казалось бы, несвязанных инструкций не является необычным, и небольшие различия в порядке инструкций могут иметь такого рода различие. Чтобы работать с точностью ровно 1 с на итерацию, в каждом цикле необходимо запускать INC и ADD. Поскольку все INC и ADD зависят от предыдущей итерации, выполнение не по порядку не может наверстать упущенное при запуске двух за один цикл. Хуже того, ADD зависит от INC в предыдущем цикле, что я и имел в виду под "блокировкой", поэтому потеря цикла в депо-цепочке INC также останавливает депо-цепочку ADD.
Кроме того, предсказанные ветки могут выполняться только на порту 6, поэтому любой цикл, когда порт 6 не выполняет cmp/jc, является циклом с потерянной пропускной способностью. Это происходит каждый раз, когда INC или ADD крадет цикл на порту 6 вместо того, чтобы работать на портах 0, 1 или 5. IDK, если это является причиной, или если потеря циклов в самих цепочках депозита INC/ADD является проблемой, или, возможно, некоторые из обоих.
Добавление дополнительного MOV не добавляет никакого давления на порт выполнения, предполагая, что оно устранено на 100%, но оно останавливает запуск внешнего интерфейса перед ядром выполнения. (Только 3 из 4 мопов в цикле нуждаются в исполнительном модуле, и ваш процессор Haswell может запускать INC и ADD на любом из своих 4 портов ALU: 0, 1, 5 и 6. Таким образом, узкими местами являются:
- максимальная пропускная способность переднего конца 4 мопов за такт. (Цикл без MOV составляет всего 3 мопа, поэтому интерфейс может работать впереди).
- Пропускная способность по одному на такт.
- цепочка зависимостей, включающая
esi(Задержка INC 1 в час) - цепочка зависимостей, включающая
edi(Задержка при добавлении 1 за такт, а также зависит от INC из предыдущей итерации)
Без MOV клиентский интерфейс может выдавать три мопа цикла по 4 за такт, пока ядро не выйдет из строя. (AFAICT, он "разворачивает" крошечные петли в буфере петель (Loop Stream Detector: LSD), поэтому цикл с мопами ABC может выдавать паттерн ABCA BCAB CABC .... Счетчик перфокарт для lsd.cycles_4_uops подтверждает, что это в основном проблемы в группах по 4, когда он выпускает любые мопс.)
Процессоры Intel присваивают порты мопам по мере их выхода в неработающее ядро. Решение основано на счетчиках, которые отслеживают, сколько мопов для каждого порта уже находится в планировщике (или Reservation Station, RS). Когда в RS имеется много мопов, ожидающих выполнения, это работает хорошо, и обычно следует избегать планирования INC или ADD для port6. И я предполагаю также избегать планирования INC и ADD таким образом, чтобы время было потеряно из любой из этих цепочек деп. Но если RS пуст или почти пуст, счетчики не остановят ADD или INC от кражи цикла на порту6.
Я думал, что я на что-то здесь, но любое неоптимальное планирование должно позволить переднему концу нагнать и поддерживать задний конец полный. Я не думаю, что мы должны ожидать, что внешний интерфейс вызовет достаточно пузырьков в конвейере, чтобы объяснить падение на 2% ниже максимальной пропускной способности, поскольку крошечный цикл должен работать из буфера цикла с очень постоянной пропускной способностью 4 на такт. Может быть, что-то еще происходит.
Реальный пример пользы mov устранение.
я использовал lea построить цикл, который имеет только один mov за час, создавая идеальную демонстрацию, где устранение MOV успешно 100%, или 0% времени с mov same,same продемонстрировать латентное узкое место, которое производит.
Так как макрос слиты dec/jnz является частью цепочки зависимостей, включающей счетчик цикла, несовершенное планирование не может задержать его. Это отличается от случая, когда cmp/jc "разветвляется" из цепочки зависимостей критического пути на каждой итерации.
_start:
mov ecx, 2000000000 ; each iteration decrements by 2, so this is 1G iters
align 16 ; really align 32 makes more sense in case the uop-cache comes into play, but alignment is actually irrelevant for loops that fit in the loop buffer.
.loop:
mov eax, ecx
lea ecx, [rax-1] ; we vary these two instructions
dec ecx ; dec/jnz macro-fuses into one uop in the decoders, on Intel
jnz .loop
.end:
xor edi,edi ; edi=0
mov eax,231 ; __NR_exit_group from /usr/include/asm/unistd_64.h
syscall ; sys_exit_group(0)
В семействе Intel SnB LEA с одним или двумя компонентами в режиме адресации работает с задержкой 1с (см. http://agner.org/optimize/ и другие ссылки в вики-теге x86).
Я построил и запустил это как статический двоичный файл в Linux, поэтому счетчики перфектов в пользовательском пространстве для всего процесса измеряют только цикл с незначительными накладными расходами при запуске / завершении работы. (perf stat это действительно легко по сравнению с помещением запросов perf-counter в саму программу)
$ yasm -felf64 -Worphan-labels -gdwarf2 mov-elimination.asm && ld -o mov-elimination mov-elimination.o &&
objdump -Mintel -drwC mov-elimination &&
taskset -c 1 ocperf.py stat -etask-clock,context-switches,page-faults,cycles,instructions,branches,uops_issued.any,uops_executed.thread -r2 ./mov-elimination
Disassembly of section .text:
00000000004000b0 <_start>:
4000b0: b9 00 94 35 77 mov ecx,0x77359400
4000b5: 66 66 2e 0f 1f 84 00 00 00 00 00 data16 nop WORD PTR cs:[rax+rax*1+0x0]
00000000004000c0 <_start.loop>:
4000c0: 89 c8 mov eax,ecx
4000c2: 8d 48 ff lea ecx,[rax-0x1]
4000c5: ff c9 dec ecx
4000c7: 75 f7 jne 4000c0 <_start.loop>
00000000004000c9 <_start.end>:
4000c9: 31 ff xor edi,edi
4000cb: b8 e7 00 00 00 mov eax,0xe7
4000d0: 0f 05 syscall
perf stat -etask-clock,context-switches,page-faults,cycles,instructions,branches,cpu/event=0xe,umask=0x1,name=uops_issued_any/,cpu/event=0xb1,umask=0x1,name=uops_executed_thread/ -r2 ./mov-elimination
Performance counter stats for './mov-elimination' (2 runs):
513.242841 task-clock:u (msec) # 1.000 CPUs utilized ( +- 0.05% )
0 context-switches:u # 0.000 K/sec
1 page-faults:u # 0.002 K/sec
2,000,111,934 cycles:u # 3.897 GHz ( +- 0.00% )
4,000,000,161 instructions:u # 2.00 insn per cycle ( +- 0.00% )
1,000,000,157 branches:u # 1948.396 M/sec ( +- 0.00% )
3,000,058,589 uops_issued_any:u # 5845.300 M/sec ( +- 0.00% )
2,000,037,900 uops_executed_thread:u # 3896.865 M/sec ( +- 0.00% )
0.513402352 seconds time elapsed ( +- 0.05% )
Как и ожидалось, цикл запускается 1G раз (branches ~ = 1 миллиард). "Дополнительные" 111k циклов после 2G - это издержки, которые присутствуют и в других тестах, в том числе и без mov, Это не случайный сбой mov-elission, но он масштабируется с счетчиком итераций, так что это не просто накладные расходы при запуске. Это, вероятно, от прерывания по таймеру, так как IIRC Linux perf не возиться с счетчиками перфораторов при обработке прерываний, а просто позволяет им продолжать считать. (perf виртуализирует аппаратные счетчики производительности, чтобы вы могли получать счетчики для каждого процесса, даже когда поток мигрирует между процессорами.) Кроме того, прерывания по таймеру на логическом ядре, принадлежащем к одному и тому же физическому ядру, будут немного мешать.
Узким местом является цепочка зависимостей, переносимая циклами, включающая счетчик циклов. Циклы 2G для 1G iters - 2 такта на итерацию или 1 такт на декремент. Это подтверждает, что длина цепи dep составляет 2 цикла. Это возможно только если mov имеет нулевую задержку. (Я знаю, что это не доказывает, что не существует какого-то другого узкого места. Это действительно только доказывает, что задержка составляет не более 2 циклов, если вы не верите моему утверждению, что задержка является единственным узким местом. resource_stalls.any счетчик перфектов, но у него не так много вариантов разбить, какой микроархитектурный ресурс был исчерпан.)
Цикл имеет 3 мопа слитых доменов: mov, lea и слитый макрос dec/jnz, 3G uops_issued.any count подтверждает, что: он считает в объединенном домене, который является всем конвейером от декодеров до выхода на пенсию, за исключением планировщика (RS) и исполнительных блоков. (Пары команд с макросами остаются повсеместно единичными мопами. Только для микро-слияния хранилищ или загрузки ALU+ 1 моп с слитыми доменами в ROB отслеживает ход двух мопов с не слитыми доменами.)
2G uops_executed.thread (unsused-domain) говорит нам, что все mov Мопы были устранены (т.е. обработаны этапом выпуска / переименования и помещены в ROB в уже выполненном состоянии). Они по-прежнему занимают проблему пропускания / удаления, а также пространство в кэше UOP и размер кода. Они занимают место в ROB, ограничивая размер окна не по порядку. mov инструкция никогда не бывает бесплатной. Существует много возможных узких мест в микроархитектуре, помимо портов с задержкой и портами выполнения, наиболее важными из которых являются скорость выдачи внешнего интерфейса в 4 раза.
На процессорах Intel нулевая задержка часто является более сложной задачей, чем отсутствие необходимости в исполнительном устройстве, особенно в Haswell и более поздних версиях, где имеется 4 порта ALU. (Но только 3 из них могут обрабатывать векторные мопы, поэтому неисчерпываемые векторные перемещения были бы более узким местом, особенно в коде без многих нагрузок или хранилищ, забирающих входную полосу пропускания (4 мопа слитых доменов за такт) от мопов ALU Кроме того, планирование мопов на исполнительные блоки не является идеальным (больше похоже на то, что сначала готово к самым старым), поэтому мопы, которые не находятся на критическом пути, могут украсть циклы с критического пути.)
Если мы поставим nop или xor edx,edx в цикле, они также будут выпускать, но не выполнять на процессорах семейства Intel SnB.
Устранение движения с нулевой задержкой может быть полезно для расширения нуля от 32 до 64 бит и от 8 до 64. (movzx eax, bl устранен, movzx eax, bx не)
Без мов-устранения
mov ecx, ecx # Intel can't eliminate mov same,same
lea ecx, [rcx-1]
dec ecx
jnz .loop
3,000,320,972 cycles:u # 3.898 GHz ( +- 0.00% )
4,000,000,238 instructions:u # 1.33 insn per cycle ( +- 0.00% )
1,000,000,234 branches:u # 1299.225 M/sec ( +- 0.00% )
3,000,084,446 uops_issued_any:u # 3897.783 M/sec ( +- 0.00% )
3,000,058,661 uops_executed_thread:u # 3897.750 M/sec ( +- 0.00% )
Это требует 3G циклов для 1G итераций, потому что длина цепочки зависимостей теперь составляет 3 цикла.
Число uop в слитых доменах не изменилось, все еще 3G.
Что изменилось, так это то, что теперь число мопов в неиспользованном домене совпадает со значением в fused-domain. Все мопы нуждались в исполнительном блоке; ни один из mov инструкции были исключены, поэтому все они добавили задержку 1с в цепочку депонирования с переносом цикла.
(Когда есть микроплавкие мопы, как add eax, [rsi], uops_executed количество может быть выше, чем uops_issued, Но у нас этого нет.)
Без mov совсем:
lea ecx, [rcx-1]
dec ecx
jnz .loop
2,000,131,323 cycles:u # 3.896 GHz ( +- 0.00% )
3,000,000,161 instructions:u # 1.50 insn per cycle
1,000,000,157 branches:u # 1947.876 M/sec
2,000,055,428 uops_issued_any:u # 3895.859 M/sec ( +- 0.00% )
2,000,039,061 uops_executed_thread:u # 3895.828 M/sec ( +- 0.00% )
Теперь мы возвращаемся к задержке в 2 цикла для переносимой по петле цепи dep.
Ничто не устранено.
Я тестировал на 3,9 ГГц i7-6700k Skylake. Я получаю идентичные результаты на Haswell i5-4210U (с точностью до 40 КБ из 1G) для всех событий perf. Это примерно тот же предел погрешности, что и при повторном запуске в той же системе.
Обратите внимание, что если я побежал perf как корень и считается cycles вместо cycles:u (только пользовательское пространство), он измеряет частоту процессора как ровно 3.900 ГГц. (IDK, почему Linux подчиняется только настройкам bios для max turbo сразу после перезагрузки, но затем падает до 3,9 ГГц, если я оставляю его без дела на пару минут. Asus Z170 Pro Gaming mobo, Arch Linux с ядром 4.10.11-1-ARCH Видел то же самое с Ubuntu. balance_performance каждому из /sys/devices/system/cpu/cpufreq/policy[0-9]*/energy_performance_preference от /etc/rc.local исправляет, но пишет balance_power позже он снова падает до 3,9 ГГц.)
Вы должны получить те же результаты на AMD Ryzen, так как он может устранить целое число mov, Семейство AMD Bulldozer может исключать только копии регистра xmm. (По словам Агнера Фога, ymm копии регистров - это исключенная нижняя половина и ОП ALU для верхней половины.)
Например, AMD Bulldozer и Intel Ivybridge могут поддерживать пропускную способность 1 на тактовую частоту для
movaps xmm0, xmm1
movaps xmm2, xmm3
movaps xmm4, xmm5
dec
jnz .loop
Но Intel Sandybridge не может устранить ходы, поэтому он будет узким местом на 4 мегапикселях ALU для 3 портов выполнения. Если бы это было pxor xmm0,xmm0 вместо movaps SnB также может выдерживать одну итерацию за такт. (Но семейство Bulldozer не могло этого сделать, потому что для обнуления xor по-прежнему требуется исполнительный модуль на AMD, хотя он не зависит от старого значения регистра. А для семейства Bulldozer для PXOR пропускная способность составляет всего 0,5 с.)
Ограничения мов-устранения
Две зависимые инструкции MOV подряд показывают разницу между Haswell и Skylake.
.loop:
mov eax, ecx
mov ecx, eax
sub ecx, 2
jnz .loop
Haswell: незначительная межпроизводственная изменчивость (от 1,746 до 1,749 с / iter), но это типично:
1,749,102,925 cycles:u # 2.690 GHz
4,000,000,212 instructions:u # 2.29 insn per cycle
1,000,000,208 branches:u # 1538.062 M/sec
3,000,079,561 uops_issued_any:u # 4614.308 M/sec
1,746,698,502 uops_executed_core:u # 2686.531 M/sec
745,676,067 lsd_cycles_4_uops:u # 1146.896 M/sec
Не все инструкции MOV исключены: около 0,75 из 2 на итерацию использовали порт выполнения. Каждый MOV, который выполняется вместо того, чтобы быть удаленным, добавляет 1с задержки в цепочку депонирования с переносом цикла, так что это не случайно, что uops_executed а также cycles очень похожи Все мопы являются частью одной цепочки зависимостей, поэтому параллелизм невозможен. cycles всегда около 5М выше, чем uops_executed независимо от различий между циклами, так что я предполагаю, что где-то еще используется всего 5 миллионов циклов.
Skylake: более стабильный, чем результаты HSW, и большее устранение mov: только 0,6666 MOV из каждых 2 нуждались в исполнительной единице.
1,666,716,605 cycles:u # 3.897 GHz
4,000,000,136 instructions:u # 2.40 insn per cycle
1,000,000,132 branches:u # 2338.050 M/sec
3,000,059,008 uops_issued_any:u # 7014.288 M/sec
1,666,548,206 uops_executed_thread:u # 3896.473 M/sec
666,683,358 lsd_cycles_4_uops:u # 1558.739 M/sec
На Haswell, lsd.cycles_4_uops приходилось все мопы. (0,745 * 4 ~= 3). Таким образом, почти в каждом цикле, где выдаются любые мопы, выдается полная группа из 4 (из буфера цикла. Мне, вероятно, следовало бы взглянуть на другой счетчик, которому все равно, откуда они взялись, например, uops_issued.stall_cycles подсчитывать циклы, когда не было выполнено моп)
Но на SKL, 0.66666 * 4 = 2.66664 меньше 3, поэтому в некоторых циклах интерфейс выдаёт меньше 4 моп. (Обычно он останавливается, пока в ядре не по порядку есть место для выпуска полной группы из 4, вместо выпуска неполных групп).
Странно, IDK, каково точное микроархитектурное ограничение. Поскольку цикл состоит всего из 3 мопов, каждая группа выпусков из 4 мопов - это больше, чем полная итерация. Таким образом, группа проблем может содержать до 3 зависимых MOV. Возможно, Skylake предназначен для того, чтобы иногда это разрушать, чтобы допустить большее устранение mov?
обновление: на самом деле это нормально для 3-х циклов на Skylake. uops_issued.stall_cycles показывает, что HSW и SKL выдают простой цикл по 3 мопа без устранения mov, так же, как они выдают этот. Таким образом, лучшая устранение mov является побочным эффектом разделения групп вопросов по какой-то другой причине. (Это не узкое место, потому что взятые ветви не могут работать быстрее, чем 1 за такт, независимо от того, насколько быстро они выдают). Я до сих пор не знаю, почему SKL отличается, но я не думаю, что стоит о чем-то беспокоиться.
В менее экстремальном случае SKL и HSW одинаковы, и оба не смогли устранить 0,3333 из каждых 2 инструкций MOV:
.loop:
mov eax, ecx
dec eax
mov ecx, eax
sub ecx, 1
jnz .loop
2,333,434,710 cycles:u # 3.897 GHz
5,000,000,185 instructions:u # 2.14 insn per cycle
1,000,000,181 branches:u # 1669.905 M/sec
4,000,061,152 uops_issued_any:u # 6679.720 M/sec
2,333,374,781 uops_executed_thread:u # 3896.513 M/sec
1,000,000,942 lsd_cycles_4_uops:u # 1669.906 M/sec
Все мопы выпускаются в группах по 4. Любая непрерывная группа из 4 мопов будет содержать ровно два мопа MOV, которые являются кандидатами на исключение. Поскольку он явно преуспевает в устранении обоих в некоторых циклах, IDK почему не всегда может это сделать.
Руководство по оптимизации Intel гласит, что перезапись результата удаления mov как можно раньше освобождает микроархитектурные ресурсы, что позволяет добиться успеха чаще, по крайней мере, для movzx, Смотрите пример 3-25. Последовательность переупорядочения для повышения эффективности инструкций MOV с нулевой задержкой.
Так, может быть, это отслеживается внутри с помощью таблицы подсчетов рефитов ограниченного размера? Что-то должно помешать освобождению записи физического регистра, если она больше не нужна в качестве значения исходного архитектурного регистра, если она все еще необходима в качестве значения места назначения mov. Ключевым моментом является освобождение записей PRF как можно скорее, поскольку размер PRF может ограничить размер окна, выходящего за рамки порядка, меньшим, чем размер ROB.
Я попробовал примеры на Haswell и Skylake, и обнаружил, что удаление mov на самом деле работало значительно больше времени при этом, но на самом деле оно было немного медленнее в общих циклах, чем быстрее. Этот пример был призван продемонстрировать преимущества IvyBridge, который, вероятно, является узким местом на его 3 портах ALU, но HSW/SKL является лишь узким местом при конфликтах ресурсов в цепочках dep и, похоже, не беспокоит необходимость использования порта ALU для большей части movzx инструкции.
См. Также Почему XCHG reg, reg 3 микрооперационная инструкция по современным архитектурам Intel? для дополнительного исследования + догадки о том, как работает mov-elission и может ли оно работать для xchg eax, ecx, (На практике xchg reg,reg на Intel 3 ALU мопов, а на Ryzen 2 Интересно догадаться, могла ли Intel реализовать это более эффективно.)
Кстати, в качестве обходного пути для ошибки в Haswell, Linux не предоставляет uops_executed.thread когда включена гиперпоточность, только uops_executed.core, Другое ядро определенно бездействовало все время, даже не прерывая таймера, потому что я перевел его в автономный режим с echo 0 > /sys/devices/system/cpu/cpu3/online, К сожалению, этого нельзя сделать раньше perf решает, что HT включен, а на моем ноутбуке Dell нет опции BIOS для отключения HT. Так что я не могу получить perf использовать все 8 аппаратных счетчиков PMU одновременно в этой системе, только 4.:/
Вот два небольших теста, которые, я считаю, убедительно показывают доказательства устранения mov:
__loop1:
add edx, 1
add edx, 1
add ecx, 1
jnc __loop1
против
__loop2:
mov eax, edx
add eax, 1
mov edx, eax
add edx, 1
add ecx, 1
jnc __loop2
Если mov добавив цикл в цепочку зависимостей, можно ожидать, что вторая версия занимает около 4 циклов за итерацию. На моем Haswell оба требуют около 2 циклов на итерацию, что не может произойти без удаления mov.