[Перевод] Выравнивание инструкций кода
Насколько трудно может быть измерить производительность простой функции, вроде вот этой?
// func.cpp
void benchmark_func(int* a)
{
for (int i = 0; i < 32; ++i)
a[i] += 1;
}Ну, давайте просто завернём её в какой-нибудь микробенчмарк, вызовем её много-много раз (для усреднения результатов) и посмотрим, что получится, да? Ну ладно, мы можем ещё посмотреть на сгенерированные инструкции просто чтобы убедиться, что компилятор чего-то там не «наоптимизировал». Мы можем также провести несколько разных тестов, чтобы убедиться, что именно цикл является узким местом. Ну и всё. Мы понимаем, что мы измеряем, да?
Давайте представим, что в нашем файле есть ещё одна функция, скорость работы который вы тоже замеряете, но в отдельных тестах. Т.е. файл выглядит как-то так:
// func.cpp
void foo(int* a)
{
for (int i = 0; i < 32; ++i)
a[i] += 1;
}
void benchmark_func(int* a)
{
for (int i = 0; i < 32; ++i)
a[i] += 1;
}И вот однажды ваш менеджер приходит к вам и показывает претензию от пользователя вашей библиотеки, которая заключается в том, что она не работает настолько быстро, как вы обещали. Но постойте, мы ведь хорошо измерили производительность и обещали ровно то, что получили по результатам тестов. Что же пошло не так?
Пользователь говорит, что был заинтересован лишь в тестировании функции benchmark_func (), так что он запускал тесты производительности только для неё.
Цифры
Я собирал этот код последним Clang со следующими опциями:
-O2 -march=skylake -fno-unroll-loops Я запускал этот код на процессоре Intel Core i7–6700 Skylake
Весь код вместе со скриптами для сборки можно скачать здесь. Вам также понадобится библиотека google benchmark.
Давайте назовём версию кода с двумя функциями «базовой», а вариант с одной лишь функцией benchmark_func — «no_foo». И вот результаты:
$ ./baseline.sh
---------------------------------------------------------
Benchmark CPU Iterations Throughput Clockticks/iter
---------------------------------------------------------
func_bench_median 4 ns 191481954 32.5626GB/s 74.73
$ ./no_foo.sh
---------------------------------------------------------
Benchmark CPU Iterations Throughput Clockticks/iter
---------------------------------------------------------
func_bench_median 4 ns 173214907 29.5699GB/s 84.54Я рассчитал метрику «Clockticks/iter» самостоятельно, поделив количество тиков выполнения функции benchmark_func () на количество итераций.
Как ни странно, удаление вообще не вызываемой в тесте функции foo () из файла с исходным кодом снизило производительность оставшейся функции на ~10%.
Давайте попробуем понять, что здесь происходит
Немного забегая наперёд, я скажу, что сгенерированный ассемблерный код для функции benchmark_func () идентичен в обоих случаях, и единственная разница в его расположении в бинарнике и выравнивании внутреннего цикла.
Давайте сначала посмотрим на сгенерированный код для «базовой» версии:
$ objdump -d a.out -M intel | grep "<_Z14benchmark_funcPi>:" -A15
00000000004046c0 <_Z14benchmark_funcPi>:
4046c0: 48 c7 c0 80 ff ff ff mov rax,0xffffffffffffff80
4046c7: c5 fd 76 c0 vpcmpeqd ymm0,ymm0,ymm0
4046cb: 0f 1f 44 00 00 nop DWORD PTR [rax+rax*1+0x0]
4046d0: c5 fe 6f 8c 07 80 00 vmovdqu ymm1,YMMWORD PTR [rdi+rax*1+0x80]
4046d7: 00 00
4046d9: c5 f5 fa c8 vpsubd ymm1,ymm1,ymm0
4046dd: c5 fe 7f 8c 07 80 00 vmovdqu YMMWORD PTR [rdi+rax*1+0x80],ymm1
4046e4: 00 00
4046e6: 48 83 c0 20 add rax,0x20
4046ea: 75 e4 jne 4046d0 <_Z14benchmark_funcPi+0x10>
4046ec: c5 f8 77 vzeroupper
4046ef: c3 ret Мы можем заметить, что код выровнен по границе кеш-линии (0×406c0 mod 0×40 == 0×0). Это хорошо. Но есть ещё кое-что, что нам нужно знать об архитектуре процессоров Intel. В используемом мною процессоре семейства Skylake существует движок трансляции микроинструкций, MITE (Micro-instruction Translation Engine), который выбирает инструкции по 16 байт за один проход. Важным моментом здесь является то, что это не просто какие-нибудь 16 байт, а именно 16 байт из выровненного по 16-байтному интервалу окна. После того, как эти инструкции были выбраны, декодер преобразовывает их в последовательность более мелких микроопераций (uops). Дальше эти микрооперации передаются на следующие этапы выполнения.
Но существует и ещё один аппаратный блок, который называется DSB (Decoded Stream Buffer), который, как следует из его названия, является кешом микроопераций. Если мы хотим выполнить какой-то набор инструкций, который уже недавно выполняли, то мы сначала проверяем, нет ли соответствующих ему микроопераций в DSB. Если они там найдутся — это спасёт нас не только от повторной трансляции их MITE, но даже и от их чтения из оперативной памяти (что вообще отлично). Однако, есть определённые ограничения, влияющие на то, как микроинструкции могут попасть (или не попасть) в DSB, мы поговорим об этом ниже.
В ассемблерных коммандах выше вы можете заметить, что код был векторизирован и у нас фактически есть всего 4 итерации цикла, что хорошо для данного примера, поскольку в противном случае LSD (Loop Stream Detector) обнаружил бы цикл и прекратил бы выборку инструкций из памяти.
Больше информации о всех этих нюансах интеловской архитектуры можно почитать в документе «Intel 64 and IA-32 Architectures Optimization Reference Manual». Также можно посмотреть хорошую презентацию Zia Ansari на эту тему.
Выравнивание инструкций кода имеет значение
Я думаю вы уже догадываетесь, о чём пойдёт речь далее. Давайте посмотрим, как функция benchmark_func () располагается в коде в обоих случаях:
«базовый случай»: 
«no_foo»: 
Толстыми прямоугольниками на рисунках выше отмечены 32-байтные окна, а желтым фоном — инструкции тела цикла. Первым наблюдением может быть то, что во втором случае весь код цикла попадает в одно 32-байтное окно, а в первом он распределён между двумя. И действительно, во втором случае у нас вдвое меньше промахов при обращении к DSB (DSB_MISS_PS 1800M vs 888M) и ровно нулевой оверхед на переключение DSB-MITE (DSB2MITE_SWITCHES, PENALTY_CYCLES 888M vs 0). Но почему же в этом случае всё работает на 10% хуже? Наверное, есть какая-то другая архитектурная особенность, которую я ещё не учёл.
Я провёл несколько экспериментов, проверяя разные свои гипотезы о том, как декодированные инструкции помещаются в DSB, но всё же я не на 100% уверен, что полностью это понял. Мои эксперименты я выложил вот здесь.
Счётчики производительности не показали никакой аномалии. Единственное, на что можно обратить внимание, это различие между двумя случаями по параметру
IDQ_UOPS_NOT_DELIVERED, CYCLES_0_UOPS_DELIV (4100M vs 5200M). Если вы не знаете, что это — посмотрите в конец статьи, там есть объяснения всех использованных счётчиков.
Идём ещё дальше
Я сделал ещё два эксперимента, явно задав выравнивание: -mllvm -align-all-functions=5 и -mllvm -align-all-blocks=5:
$ ./aligned_functions.sh
---------------------------------------------------------
Benchmark CPU Iterations Throughput Clockticks/iter
---------------------------------------------------------
func_bench_median 3 ns 218294614 36.8538GB/s 63.37
$ ./aligned_blocks.sh
---------------------------------------------------------
Benchmark CPU Iterations Throughput Clockticks/iter
---------------------------------------------------------
func_bench_median 3 ns 262104631 44.3106GB/s 46.25При выравнивании benchmark_func () по границе в 32 байта я получил +13% к производительности, а при выравнивании всех базовых блоков (включая начало функции) в функции benchmark_func () по границе в 32 байта я получил +36% прироста скорости. Забавно, правда?
Расположение функции для случая с выравниванием функции не сильно отличается от «базового» случая: 
То есть мы имеем дело с какой-то проблемой с DSB, как и в «базовом» случае. Счётчики показывают даже ещё худшую эффективность использования DSB: DSB_MISS_PS 2600M vs 1800M. Что ещё важнее, так это сравнить показания счётчика IDQ_UOPS_NOT_DELIVERED, CYCLES_0_UOPS_DELIV: 330M vs 4100M. В конце концов, что для нас действительно важно — это обеспечить заполненность бекэнда декодированными микроинструкциями.
Теперь случай с выровненными базовыми блоками: 
Он интересен тем, что в нём наблюдается как высокий уровень использования DSB, так и низкое количество тактов, в которых не было доставленных микроинструкций. Посмотрите на таблицу ниже с конкретными значениями счётчиков.
Использованные счётчики производительности
А вот объяснение заголовков столбцов этой таблицы:
FRONTEND_RETIRED.DSB_MISS_PS — считает инструкции, для которых произошел промах поиска в DSB (Decode Stream Buffer)
DSB2MITE_SWITCHES.PENALTY_CYCLES — считает штрафные такты при переключении между DSB и MITE. Обращение к DSB, при котором не нашлось требуемых инструкций и пришлось обращаться к MITE может в худшем случае стоить до 6 тактов, в которых никакие микрооперации не передаются в IDQ. Как правило, на это уходит до 2 тактов.
IDQ.ALL_DSB_CYCLES_4_UOPS — считает количество тактов, в которых ровно 4 микроинструкции было доставлено в Instruction Decode Queue (IDQ) из Decode Stream Buffer (DSB)
IDQ.ALL_DSB_CYCLES_ANY_UOPS — считает количество тактов, в которых микроинструкции были доставлены в Instruction Decode Queue (IDQ) из Decode Stream Buffer (DSB)
IDQ_UOPS_NOT_DELIVERED.CORE — считает количество микроопераций, не доставленных в Resource Allocation Table (RAT) для каждого потока, добавляя »4 — х» когда Instruction Decode Queue (IDQ) доставляет х микроопераций в Resource Allocation Table (RAT) (х принадлежит множеству {0,1,2,3})
IDQ_UOPS_NOT_DELIVERED.CYCLES_0_UOPS_DELIV.CORE — считает, для каждого потока, количество тактов, в которых микрооперации не были доставлены в Resource Allocation Table (RAT). IDQ_Uops_Not_Delivered.core =4.
Предостережения
Для данного конкретного случая все эти проблемы с выравниванием исчезнут, если мы, например, увеличим количество итераций до 1024. В этот момент сработает детектор циклов (LSD). Он поймёт, что мы находимся в цикле и выполняем одни и те же инструкции снова и снова. Тогда он просто запретит чтение инструкций из памяти и запустит их выполнение из своего внутреннего буфера. В этот момент становится уже совершенно не важно, как там наши инструкции расположены и выровнены в памяти.
Другим интересным примером может быть то, что я получил падения производительности ещё на 10% когда использовал компоновщик gold. Это не потому, что он какой-то плохой, а опять-таки, из-за выравнивания кода.
Почему бы не выравнивать код всегда?
Выравнивание означает, что компилятор вставляет в код инструкции NOP. Это увеличивает размер бинарника и также может ударить по производительности, если эти NOP-инструкции попадут в какой-то часто используемый цикл. Выполнение NOP инструкций не абсолютно беслатно — их всё же нужно прочитать из памяти и декодировать.
Выводы
Как вы можете заметить, даже столь небольшое количество кода может вызвать затруднение. Я не думаю, что все мы должны быть экспертами в архитектуре микропроцессоров, но стоит хотя бы знать, что подобные проблемы могут существовать. Будьте в курсе того, что однажды измеренная производительность функции может измениться в будущем даже без изменения кода этой функции. Если это является важным для вас моментом — не забывайте делать дополнительные измерения производительности для выявления проблем, подобных описанной в данной статье.
