Насколько трудно может быть измерить производительность простой функции, вроде вот этой?

// 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 

Мы можем заметить, что код выровнен по границе кеш-линии (0x406c0 mod 0x40 == 0x0). Это хорошо. Но есть ещё кое-что, что нам нужно знать об архитектуре процессоров 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 инструкций не абсолютно беслатно — их всё же нужно прочитать из памяти и декодировать.

Выводы

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