Выравнивание инструкций кода

https://dendibakh.github.io/blog/2018/01/18/Code_alignment_issues
  • Перевод
Насколько трудно может быть измерить производительность простой функции, вроде вот этой?

// 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() располагается в коде в обоих случаях:

«базовый случай»:

image

«no_foo»:

image

Толстыми прямоугольниками на рисунках выше отмечены 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% прироста скорости. Забавно, правда?

Расположение функции для случая с выравниванием функции не сильно отличается от «базового» случая:

image

То есть мы имеем дело с какой-то проблемой с DSB, как и в «базовом» случае. Счётчики показывают даже ещё худшую эффективность использования DSB: DSB_MISS_PS 2600M vs 1800M. Что ещё важнее, так это сравнить показания счётчика IDQ_UOPS_NOT_DELIVERED,CYCLES_0_UOPS_DELIV: 330M vs 4100M. В конце концов, что для нас действительно важно — это обеспечить заполненность бекэнда декодированными микроинструкциями.

Теперь случай с выровненными базовыми блоками:

image

Он интересен тем, что в нём наблюдается как высокий уровень использования DSB, так и низкое количество тактов, в которых не было доставленных микроинструкций. Посмотрите на таблицу ниже с конкретными значениями счётчиков.

Использованные счётчики производительности


image

А вот объяснение заголовков столбцов этой таблицы:

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 инструкций не абсолютно беслатно — их всё же нужно прочитать из памяти и декодировать.

Выводы


Как вы можете заметить, даже столь небольшое количество кода может вызвать затруднение. Я не думаю, что все мы должны быть экспертами в архитектуре микропроцессоров, но стоит хотя бы знать, что подобные проблемы могут существовать. Будьте в курсе того, что однажды измеренная производительность функции может измениться в будущем даже без изменения кода этой функции. Если это является важным для вас моментом — не забывайте делать дополнительные измерения производительности для выявления проблем, подобных описанной в данной статье.
Инфопульс Украина 164,74
Creating Value, Delivering Excellence
Поделиться публикацией
Комментарии 22
  • +4

    имхо, подобные детали лучше вынести из зоны ответственности разработчика прикладного софта в зону ответственности разработчика компиляторов, а точнее оптимизаторов.

    • 0
      Она и есть там, компиляторы это давно учитывают. Просто тут компилятор недостаточно выровнял код, либо из-за просчёта, либо просто решил, что в этом нет смысла.
    • +1
      Есть компиляторы которые не перестают удивлять rsdn.org/forum/cpp/6722631.1
      … компилятор способный по не объяснимым причинам замедлить исполнение куска кода более чем в 100 раз...
      • 0
        Я бы сказал «по непредсказуемым причинам», а не «по необьяснимым».

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

        Вот родственный пример для GCC:

        $ gcc -O1 test2.cc test1.cc -o test
        $ time ./test
            0m51.66s real     0m51.47s user     0m00.02s system
        $ gcc -O3 test2.cc test1.cc -o test
        $ time ./test
            1m11.64s real     1m11.30s user     0m00.04s system
        $ cat /proc/cpuinfo  | grep name
        model name	: Intel(R) Atom(TM) CPU  Z3560  @ 1.00GHz
        model name	: Intel(R) Atom(TM) CPU  Z3560  @ 1.00GHz
        model name	: Intel(R) Atom(TM) CPU  Z3560  @ 1.00GHz
        model name	: Intel(R) Atom(TM) CPU  Z3560  @ 1.00GHz
        

        Переход от -O1 к -O3 = замедление, причём заметно большее, чем описываемое в статье!

        Исходники
        test.h:
        #include <inttypes.h>
        
        struct pair {
          uint64_t low;
          uint64_t hi;
        };
        
        pair add(pair& a, pair& b);
        

        test1.c:
        #include "test.h"
        
        pair add(pair& a, pair& b) {
         pair s;
         s.low = a.low + b.low;
         s.hi = a.hi + b.hi + (s.low < a.low); //carry
         return s;
        }
        

        test2.c:
        #include <stdio.h>
        
        #include "test.h"
        
        int main() {
          pair a = { 0x4243444546474849, 0x4243444546474849 };
          pair b = { 0x5758595a5b5c5d5e, 0x5758595a5b5c5d5e };
          for (uint64_t i=0;i<10000000000;++i) {
            a = add(a, b);
          }
        }
        


        Если взглянуть на сгенерированный код — то сразу понятно, откуда замедление, но совершенно непонятно, как переход от -O1 к -O3 его провоцировал…

        Просто в GCC производительностью занились много лет назад и замедление в 100 раз всегда считалось чем-то ужасным, так что такие катастрофы, как в MSVC уже подвыловлены. А разработчики MSVC занялись производительностью не так и давно, так что…
        • +3
          >> но совершенно непонятно, как переход от -O1 к -O3 его провоцировал
          Лечится ключом -fno-expensive-optimizations
          Какой-то проход видимо посчитал, что вероятность (s.low >= a.low) крайне низка.
          Правильно предсказанный бранч занимает 0 тактов, а adc на интел целых 2.
          Это можно увидеть используя
          pair add(pair& a, pair& b) __attribute__((hot));
          pair add(pair& a, pair& b) __attribute__((cold));
          Во втором случае он перемещает mov ecx, 1 прямо за переход, не оптимизируя fetch, так сказать.

          Кроме того, лишь x86 бэкенд генерит переход — на других процах такой фигни я не обнаружил.
          • 0
            * вероятность (s.low >= a.low) крайне высока
            • –1
              Правильно предсказанный бранч занимает 0 тактов, а adc на интел целых 2.
              Однако add таки один такт занимает, а потому замена связки add+adc на add+jc+add+add — это в чистом виде пессимизация. Независимо от вероятностей код занимает либо 3 тракта, либо ещё больше. А в оригинале — он только 3 такта всегда занимал…
              • 0
                >> add+jc+add+add
                В этой связке первые две команды add не являются зависимыми (и они могут быть исполнены параллельно).
                Цепочка зависимости это лишь последние add+add вместо add + adc.
                На процах Интел до Skylake (IIRC), латентность ADC 2 такта.
                _возможно_ этот такт и перевешивает. Я лишь предпогаю, как вы понимаете.
                • 0
                  В этой связке первые две команды add не являются зависимыми (и они могут быть исполнены параллельно).
                  Это если вы эту команду отдельно, не в цикле исполняете. Но там — это не так важно. А в цикле — вы займёте больше исполняемых устройств, задержка тут не так важна. Особенно если у вас иногда всё же предстказание переходов не срабатывает (в 25% случаев, ага), и вы получаете хорошую-такую задержку…
                  • +1
                    Короче всё намного проще.
                    Всё решается даже до преобразования в p-code.

                    При -O1 -fexpensive-optimizations срабатывает стадия 188t.widening_mul
                    (при обычном -O1 её нет)

                    godbolt.org/g/vDfnVb

                    Происходит преобразование

                    <bb 2> [100.00%]:
                    _1 = a_11(D)->low;
                    _2 = b_12(D)->low;
                    _3 = _1 + _2;
                    # DEBUG s$low => _3
                    _4 = a_11(D)->hi;
                    _5 = b_12(D)->hi;
                    _6 = _4 + _5;
                    _7 = _1 > _3;
                    _8 = (long unsigned int) _7;
                    _9 = _6 + _8;
                    # DEBUG s$hi => _9
                    MEM[(struct pair *)&D.2410] = _3;
                    MEM[(struct pair *)&D.2410 + 8B] = _9;

                    вот в это

                    <bb 2> [100.00%]:
                    _1 = a_11(D)->low;
                    _2 = b_12(D)->low;
                    _15 = ADD_OVERFLOW (_1, _2);
                    _3 = REALPART_EXPR <_15>;
                    _16 = IMAGPART_EXPR <_15>;
                    # DEBUG s$low => _3
                    _4 = a_11(D)->hi;
                    _5 = b_12(D)->hi;
                    _6 = _4 + _5;
                    _7 = _16 != 0;
                    _8 = (long unsigned int) _7;
                    _9 = _6 + _8;
                    # DEBUG s$hi => _9
                    MEM[(struct pair *)&D.2410] = _3;
                    MEM[(struct pair *)&D.2410 + 8B] = _9;

                    Имеем

                    _7 = _1 > _3;
                    _8 = (long unsigned int) _7;
                    _9 = _6 + _8;
                    vs.
                    _7 = _16 != 0;
                    _8 = (long unsigned int) _7;
                    _9 = _6 + _8;
                    не тут ли потерялся перенос?

                    Также если открыть 311t.statistics, то можно заметить что
                    266 combine «three-insn combine» «pair add(pair&, pair&)» 1
                    не применяется. Возможно это следствие.
                    • –1
                      Возможно. Но я просто о том, что странные эффекты могут возникать в любом компиляторе. В случае с этой конкретной проблемой мы просто «забили», так как наш проект (по многим причинам, но в основном чтобы использовать libc++, а не libstdc++) переехал на clang. Соответственно «ездить по мозгам» разработчикам GCC оказалось некому…
        • 0

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

          • 0
            Вполне достаточно почитать/посмотреть умопянутую в тексте презентацию Zia Ansari:
            «Causes of Performance Instability due to Code Placement in X86»
          • 0
            было бы все так очевидно,

            в свое время пытался максимально оптимизировать, выработались некоторые практики, типо: такие структуры лучше обходить через for, другие — foreach, для больших структур в некоторых местах применить указатели и т.д. и т.п… потом столкнулся с проблемой: желание выработать «культуру письма» кончилось сломаной головой =)…

            в результате: усложнение алгоритмов желанием минимум использования хеш-таблиц, пытаться обходить структуру не так как задумали разработчики языка и.т.п, куча головной боли себе придумал, и все ради нескольких мс к скорости выполнения программы… и в некоторых случаях применяемые методы давали сбой, и кроме сложности кода прога замедлялась в несколько раз)

            больше такой херней не занимаюсь, и как в первом комменте написали: оптимизацию оставить разработчикам компиляторов, программисту нужно логику программы описывать, а не средствами ЯП пытаться залезть под капот компилятору =)

            PS: занимательная статья
            • 0
              Всё так, я своего нерадивого коллегу пытаюсь убедить, что использование ассемблерных вставок для матрасчётов в современном C++ — это моветон. Успехи так себе, конечно, с восклицаниями «Видишь? ВИДИШЬ!?» меня парировали тем, что при -O1 и -O3 перемешивание операндов в выражении позволяло уменьшить выражение на две инструкции, а на асме — ещё на одну. «С ПЛАВАЮЩЕЙ ЗАПЯТОЙ!!!»

              Но мы ведь не про это, а про использование компилятора, который имеет просто неприличное множество настроек оптимизации (даже если это MSVC). Раз они есть и даются нам, будет глупо их игнорировать. Да, поиск оптимальных настроек полным перебором — это через чур, но потеребонькать основные оптимизирующие опции всё же стоит. Задачи мы решаем разные, платформы у нас разные и цели у нас разные, а компилятор один на всех — и не очень смышлёный. Нужно давать ему подсказки.
              • +5
                >> Всё так, я своего нерадивого коллегу пытаюсь убедить, что использование ассемблерных вставок для матрасчётов в современном C++ — это моветон.
                Инлайн-асмом что-ли? Зачем, когда есть инстринсики?
                Так что либо интринсики, либо нормальный асм (если заставить компилятор генерить внятный код не получается).
                • 0
                  > Успехи так себе
                  За это надо сразу бить Кнутом
                  «premature optimization is the root of all evil»
              • 0

                А можно ссылку на оригинал? Хочется поделиться с иностранными коллегами

              • +1
                Я удивлен что clang не применяет выравнивание по умолчанию. Тем более что его реккомендуют делать сами производители процессоров (например читал про такое в cortex-a57 optimization guide).
                В gcc такие выравнивания делаются автоматически на -О2 и выше.
                gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

                Флаги -falign-…

                Скорее всего это баг в clang. Возможно его стоит зарепортить разработчикам.
                • 0
                  Тогда уж это в LLVM баг, clang же не занимается генерацией машинного кода самостоятельно.
                  • 0
                    По умолчанию выравнивает на 16 байт — размер instruction fetch (у intel).
                    Это видно в первом же листинге
                    4046c0: entry
                    4046d0: loop start

                    Если каждый цикл на 32 байта выравнивать, вырастет размер кода + что-то может наоборот не влезть в DSB или сместиться и вызвать замедление. В презентации Zia Ansari про это говорилось.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое