Для чего используется выравнивание инструкций

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

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

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

Выводы

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

Кому предназначается данная статья

В этой статье я рассмотрю технику, с помощью которой можно уменьшить потребление памяти в программах на C путем реорганизации объявляемых структур. Вам потребуются базовые знания языка C.

Этот способ пригодится при написании программ для встроенных систем с ограниченным количеством памяти или компонентов ядра ОС. Также он полезен, если вы работаете с настолько большими структурами данных, что ваша программа постоянно упирается в лимит памяти. Кроме того, он пригодится в любом приложении, где действительно необходимо уменьшить промахи в кэше.

И, наконец, этот способ — первый шаг к некоторым магическим приемам в С. Вы не можете называть себя опытным C-программистом, если не овладели им. Вы не можете называться мастером C, пока не сможете написать подобную статью самостоятельно и грамотно ее критиковать.

Почему я написал эту статью

В 2013 мне пришлось использовать технику оптимизации, о которой я узнал более 20 лет назад и с тех пор практически не использовал. Мне понадобилось уменьшить потребление памяти программой, которая использовала тысячи, а иногда и десятки тысяч С-структур. Это был cvs-fast-export, и очень часто он рушился из-за недостатка памяти.

Существует способ значительно уменьшить потребление памяти в таких ситуациях путем грамотной реорганизации элементов структур. В моем случае программа стала потреблять на 40% меньше памяти и стала способна переработать бо́льшие репозитории без падений.

Однако в процессе работы я понял, что эта техника в наши дни почти забыта. Поиск в сети подтвердил мою догадку: сегодня в среде С-программистов мало кто пишет об этом, по крайней мере, в тех местах, которые индексируются поисковиком. Есть пара статей в Википедии, но нигде нет подробного разъяснения этой темы.

Этому есть вполне разумное объяснение. На всех курсах по информатике студентов приучают (и вполне обоснованно) избегать микрооптимизаций в пользу поиска лучшего алгоритма. Снижение цены на оборудование сделало охоту за байтами менее актуальной. И сегодня все реже встречается опыт глубокого погружения в различные архитектуры процессоров.

Однако описываемый трюк все еще имеет ценность в некоторых ситуациях и будет иметь ее до тех пор, пока количество памяти на машине конечно. Эта статья убережет С-программистов от изобретения велосипеда и поможет сконцентрироваться на более важных вещах.

Выравнивание

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

На процессорах x86 и ARM примитивные типы не могут находиться в произвольной ячейке памяти. Каждый тип, кроме char, требует выравнивания. char может начинаться с любого адреса, однако двухбайтовый short должен начинаться только с четного адреса, четырехбайтный int или float — с адреса, кратного 4, восьмибайтные long или double — с адреса, кратного 8. Наличие или отсутствие знака значения не имеет. Указатели — 32-битные (4 байта) или 64-битные (8 байт) — также выравниваются.

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

Я специально упомянул, что это происходит на современных процессорах, потому что на некоторых старых процессорах небезопасный код (например, приведение некратного адреса в указатель на int и его использование) не просто замедлит работу процессора, он упадет с ошибкой о невалидной инструкции. Так вел себя, например, Sun SPARK. На самом деле такое поведение можно воспроизвести на x86 с правильным флагом (e18) в детерминированной ситуации.

Иногда можно дать указание процессору не использовать выравнивание, к примеру, с помощью директивы #pragma pack. (Не делайте этого без серьезной необходимости, потому что результатом будет более ресурсоемкий и медленный код.) Обычно это позволяет сохранить почти столько же памяти, сколько и описываемый мной способ.

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

Заполнение

Давайте посмотрим на простой пример расположения переменных в памяти. Допустим, у нас есть следующие строки в C-коде:

Если вы не знакомы с выраниванием, вы можете предположить, что эти три значения располагаются в памяти последовательно. Таким образом, на 32-битной машине за четырьмя байтами указателя сразу расположится 1 байт char, а следом за ним четыре байта целого. На 64-битной машине отличие будет в размере указателя — 8 байт вместо 4.

А вот что происходит на самом деле (на x86, ARM или другом процессоре с выравниваением данных). Память для p начинается с адреса, кратного 4. Выравнивания указателя — самое строгое.

Следом за ним идет c. Но четырехбайтный x требует заполнения (padding) пустыми байтами. Происходит примерно то же самое, как если бы мы добавили еще одну переменную:

			char *p /* 4 or 8 байт */
char c /* 1 байт */
char pad[3] /* 3 байт */
int x /* 4 байт */
		

Массив символов pad[3] в данном случае указывает на то, что мы заполняем пространство тремя пустыми байтами. Раньше это называли «мусор» («slop»).

Если тип x будет short, который занимает 2 байта, данные будут располагаться так:

			char *p /* 4 or 8 байт */
char c /* 1 байт */
char pad[1] /* 1 байт */
short x /* 2 байт */
		

С другой стороны, на 64-битной машине эти данные расположатся в памяти следующим образом:

			char *p /* 8 байт */
char c /* 1 байт */
char pad[7] /* 7 байт */
long x /* 8 байт */
		

У вас наверняка уже возник вопрос: а что, если переменная с меньшим размером будет объявлена в начале:

Если мы представим расположение структуры в памяти как:

			char c;
char pad1[M];
char *p;
char pad2[N];
int x;
		

что мы можем сказать о M и N?

Для начала, N в данном случае будет равно 0. Адрес x гарантированно будет выравниваться по адресу указателя p, выравнивание которого, в свою очередь, более строгое.

Значение M менее предсказуемо. Если компилятор расположит c в последнем байте машинного слова, следующий за ним байт (первый байт p) будет находиться в начале следующего машинного слова. В этом случае M будет равен 0.

Более вероятно, что c расположится в первом байте машинного слова. В этом случае размер M будет таким, чтобы p был выровнен по началу следующего слова — 3 на 32-битной машине, 7 на 64-битной.

Возможны промежуточные ситуации. M может быть от 0 до 7 (от 0 до 3 на 32-битной машине), потому что char может начинаться на любом байте машинного слова.

Если вы хотите, чтобы эти переменные занимали меньше памяти, вы можете поменять местами x и c.

			char *p /* 8 байт */
long x /* 8 байт */
char c /* 1 байт */
		

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

Прежде чем мы коснемся структур, следует упомянуть массивы скалярных величин. На платформе с выравниванием данных массивы char/short/int/long или указателей располагаются в памяти последовательно, без заполнения.

В следующем разделе мы увидим, что это не всегда выполняется для массивов структур.

Выравнивание и заполнение структур

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

Также, в C адрес структуры совпадает с адресом ее первого элемента, без сдвига в начале. Осторожно: в C++ классы, которые выглядят как структуры, могут нарушать это правило. (Это зависит от того, как устроен базовый класс и реализованы виртуальные методы, и может отличаться в различных компиляторах.)

(В случае сомнений вы можете использовать макрос offsetof() из ANSI C, с помощью которого можно рассмотреть расположение элементов струтур в памяти.)

Давайте рассмотрим следующую структуру:

			struct foo1 {
    char *p; /* 8 байт */
    char c; /* 1 байт */
    char pad[7]; /* 7 байт */
    long x; /* 8 байт */
};
		

На 64-битной машине любой экземпляр foo1 будет выравниваться по 8 байтам. Расположение в памяти идентично тому, которое мы получили бы, если бы в памяти находились скалярные величины. Однако, если мы перенесем c в начало, все поменяется:

			struct foo2 {
    char c; /* 1 байт */
    char pad[7]; /* 7 байт */
    char *p; /* 8 байт */
    long x; /* 8 байт */
};
		

Если бы мы рассматривали отдельные переменные, c мог бы начинаться с произвольного байта и размер заполнения мог бы варьироваться. Но выравнивание структуры foo2 идет по указателю, c также должен быть выровнен по указателю. В итоге мы получаем фиксированное заполнение в 7 байт.

Рассмотрим теперь концевое заполнение структур. Общее правило такое: компилятор заполняет все место до адреса следующей структуры так, чтобы она была выровнена по самому длинному элементу структуры. sizeof() возвращает размер структуры с учетом заполнения.

Например, на 64-битном x86 процессоре или ARM:

			struct foo3 {
    char *p; /* 8 байт */
    char c; /* 1 байт */
};

struct foo3 singleton;
struct foo3 quad[4];
		

Вы можете подумать, что sizeof(struct foo3) вернет 9, однако верным ответом будет 16. Адрес следующей структуры будет (&p)[2]. Таким образом, в массиве из 4 элементов у каждого будет заполнение в 7 пустых байт, поскольку первые элементы каждой структуры должны быть выровнены в данном случае по 8 байтам. Расположение в памяти такое, какое было бы, если бы структура была объявлена следующим образом:

			struct foo3 {
    char *p; /* 8 байт */
    char c; /* 1 байт */
    char pad[7];
};
		

Для сравнения, рассмотрим такой пример:

			struct foo4 {
    short s; /* 2 байт */
    char c; /* 1 байт */
    char pad[1];
};
		

Поскольку s требует 2-байтового выравнивания, следующий адрес будет отстоять от c на один байт, вся структура foo4 будет заполнена одним пустым байтом в конце и sizeof(struct foo4) вернет 4.

Выравнивание битовых полей и вложенных структур

Битовые поля позволяют объявить переменные, занимающие меньшую, чем char память, вплоть до 1 бита. Например:

			struct foo5 {
    short s;
    char c;
    int flip:1;
    int nybble:4;
    int septet:7;
};
		

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

С точки зрения компилятора битовые поля структуры foo5 выглядят как двухбайтовые значения, из 16 бит которых используются только 12. Место после них заполняется так, чтобы размер структуры был кратен sizeof(short) — размеру наибольшего элемента.

			struct foo5 {
    short s; /* 2 байт */
    char c; /* 1 байт */
    int flip:1; /* всего 1 бит */
    int nybble:4; /* всего 5 бит */
    int septet:7; /* всего 12 бит */
    int pad1:4; /* всего 16 бит = 2 байт */
    char pad2; /* 1 байт */
};
		

Ограничения битового поля на выход за пределы машинного слова приведет к тому, что на 32-битной машине первые две структуры поместятся в одно или два слова, но третья (foo8) займет три слова, причем у последнего будет занят только первый бит. С другой стороны, структура foo8 поместится в одно 64-битное слово.

			struct foo6 {
    int bigfield:31; /* Начало первого 32-битного слова */
    int licodelefield:1;
};

struct foo7 {
    int bigfield1:31; /* Начало первого 32-битного слова */
    int licodelefield1:1;
    int bigfield2:31; /* Начало второго 32-битного слова */
    int licodelefield2:1;
};

struct foo8 {
    int bigfield1:31; /* Начало первого 32-битного слова */
    int bigfield2:31; /* Начало второго 32-битного слова */
    int licodelefield1:1;
    int licodelefield2:1; /* Начало третьего 32-битного слова */
};
		

Важная деталь: если элементом вашей структуры является структура, она также будет выравниваться по самому длинному скаляру. Например:

			struct foo9 {
    char c;
    
    struct foo9_inner {
        char *p;
        short x;
    } inner;
};
		

char *p во внутренней структуре требует выравнивания по указателю как во внутренней, так и во внешней структуре. Реальное расположение в памяти на 64-битной машине будет примерно такое:

			struct foo9 {
    char c; /* 1 байт*/
    char pad1[7]; /* 7 байт */

    struct foo9_inner {
        char *p; /* 8 байт */
        short x; /* 2 байт */
        char pad2[6]; /* 6 байт */
    } inner;
};
		

Эта структура дает нам подсказку, где и как мы можем сэкономить память переупаковкой. Из 24 байт 13 заполняющие. Это больше 50% потерянного места!

Реорганизация структур

Теперь, когда мы знаем как и зачем компилятор выравнивает данные в памяти, посмотрим, как мы можем уменьшить количество «мусора». Это и будет называться «искусство упаковки структур».

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

Наиболее простой способ избавиться от мусора — расположить элементы структуры по уменьшению размера. Таким образом, указатели будут располагаться в начале, поскольку на 64-битной машине они займут по 8 байт. Потом 4-битовые int; 2-байтовые short; затем char.

Рассмотрим, например, односвязный список:

			struct foo10 {
    char c;
    struct foo10 *p;
    short x;
};
		

Или, если мы явно укажем заполняющие байты:

			struct foo10 {
    char c; /* 1 byte */
    char pad1[7]; /* 7 bytes */
    struct foo10 *p; /* 8 bytes */
    short x; /* 2 bytes */
    char pad2[6]; /* 6 bytes */
};
		

Всего 24 байта. Однако, если мы перепишем следующим образом:

			struct foo11 {
    struct foo11 *p;
    short x;
    char c;
};
		

то, посмотрев на расположение структуры в памяти, мы увидим, что теперь данные не требуют заполнения, поскольку начало адреса более короткого элемента следует сразу после конца адреса более длинного. Все, что нам теперь требуется — концевое заполнение для выравнивания следующей структуры:

			struct foo11 {
    struct foo11 *p; /* 8 bytes */
    short x; /* 2 bytes */
    char c; /* 1 byte */
    char pad[5]; /* 5 bytes */
};
		

Переупаовкой мы добились сокращения занимаемого места с 24 до 16 байт. Это может показаться незначительным, но что, если у вас односвязный список из 200 тысяч элементов? Эффект растет быстро, особенно на встроенных системах с ограниченым объемом памяти или в критических участках ядра ОС.

Замечу, что реорганизация не всегда позволяет сохранить память. Если мы применим этот прием к нашей структуре foo9, мы получим следующее:

			struct foo12 {
    struct foo12_inner {
        char *p; /* 8 bytes */
        int x; /* 4 bytes */
    } inner;
    
    char c; /* 1 byte*/
};
		

Явно укажем заполнение:

			struct foo12 {
    struct foo12_inner {
        char *p; /* 8 bytes */
        int x; /* 4 bytes */
        char pad[4]; /* 4 bytes */
    } inner;

    char c; /* 1 byte*/
    char pad[7]; /* 7 bytes */
};
		

Размер foo12 — также 24 байта, потому что c выравнивается по внутренней структуре. Для уменьшения занимаемой памяти нам придется изменить дизайн самой структуры данных.

Когда я выложил первый вариант этой статьи, меня спросили почему, если реогранизация для уменьшения «мусора» настолько проста, компилятор не делает ее автоматически. Ответ: C изначально разрабатывался для написания ОС и низкоуровневого кода. Автоматическая реорганизация структур будет мешать программисту организовать структуру с учетом требований оборудования к расположению битов и байтов в памяти.

Выравнивания перечислений и целочисленных типов

Использование перечислений («enumerated types») вместо директивы #define — отличная идея, если отладчик может их отличить от целых чисел. Перечисления гарантировано совместимы с целочисленным типом, однако стадарт C не специфицирует, с помощью какого именно типа они реализованы.

Будьте осторожны: несмотря на то, что обычно в перечислениях используется int, в некоторых компиляторах по умолчанию может использоваться short, long или char. Также в компиляторе может быть предусмотрена директива или опция для явного указания размера.

Тип long double также может создавать некоторые проблемы. Некоторые платформы реализуют его с помощью 80 бит, некоторые — 128 бит, некоторые 80-битные реализации заполняют место после данных до 96 или 128 бит.

В обоих случаях лучше использовать sizeof() для проверки занимаемого места.

Наконец, иногда на x86 Linux-машинах double может быть исключением: 8-байтный double может требовать выравнивания по 4 байтам в структуре, несмотря на то, что стоящий отдельно выравнивается по 8 байтам. Это зависит от компилятора и его опций.

Читаемость кода и локальность кэша

Несмотря на то, что реорганизация структур — самый простой способ избавиться от мусора в памяти, он не всегда будет оптимальным. Необходимо также учесть читаемость кода и локальность кэша («cache locality»).

Следует помнить, что программы пишутся не только для компьютера, но и для людей. Читаемый код важен даже тогда, когда единственный, кто его будет читать — это вы в будущем.

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

При написании программы, которой требуется частый доступ к данным или их части, стоит помнить, что произволительность будет выше, если запрашиваемые данные помещяются в кэш — блок памяти, целиком читаемый процессором при доступе к адресу в нем. На 64-битной машине он обычно занимает 64 байта, на других платформах — обычно 32 байта.

Группировка связанных данных не только улучшает читаемость, но и способствует локализации данных в кэше. Это дополнительная причина реорганизовывать структуры с учетом особенностей доступа к данным в вашей программе.

Если в вашем коде есть конкурентный (concurrent) доступ к данным, появляется третья проблема: «cache line bouncing». Для минимизации трафика в шине следует располагать данные так, чтобы чтение из одного кэша и запись в другой производились с меньшим промежутком.

Да, это противоречит предыдущему замечанию, однако многопоточный код — это всегда сложно. Оптимизация многопоточного кода — тема, заслуживающая отдельной большой статьи. Все, что я могу здесь сказать, такая проблема существует.

Другие способы упаковки

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

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

В общем случае старайтесь уменьшить размер полей с данными. В cvs-fast-export, например, я воспользовался знанием от том, что CVS и RCS репозитории не существовали до 1982 года. Я заменил 64-битное Unix-время time_t (начинающееся с 1970) на 32-битное время с начальной точкой 1982-01-01T00:00:00; это должно покрыть даты до 2118 года. (Если вы применяете подобный трюк, не забудьте проверять границы устанавливаемого значения, чтобы избежать трудноуловимых багов.)

Каждое такое сокращение размера поля не только уменьшает размер структуры, но и уменьшает количество мусора или может создать дополнительные возможности для уменьшения структуры путем реорганизации элементов. Последовательно применяя эти шаги, мы можем добиться значительной экономии памяти.

Самый рискованый метод упаковки — использование union. Если вы уверены, что в вашей структуре данных поля никогда не будут использоваться совместно, можете рассмотреть этот вариант. Но будьте предельно осторожны, тщательно тестируйте свой код, потому что даже маленькая неточность может привести не только к трудноуловимым багам, но и к порче данных.

Инструменты

Компилятор clang имеет опцию -Wpadded, которая будет генерировать сообщения о заполнении.

Я слышал много хороших отзывов о программе pahole, хотя сам ее не использовал. Она работает вместе с компилятором и позволяет генерировать отчет, описывающий реальное расположение данных в памяти.

Доказательства и исключения

Исходный код небольшой программы, которая иллюстрирует вышеописанное можно скачать здесь: packtest.c.

Если вы используете экзотические сочетания компилятора, опций и оборудования, вы, возможно, найдете исключения из правил, который я привожу. Причем, чем старше процессор, тем чаще вы с ними будете сталкиваться.

Следующий уровень владения данной техникой — знать, где и когда ожидать, что правила будут нарушены. В то время, когда я изучал ее (ранние 80-е), людей, которые не освоили эту технику называли «жертвами VAX» («all-the-world’s-a-VAX syndrome»). Помните, что не все компьютеры в мире — PC.

Полезные ссылки

Здесь я привожу ссылки на статьи и эссе, которые я считаю хорошим дополнением к данному материалу.

A Guide to Undefined Behavior in C and C++
Time, Clock, and Calendar Programming In C

Источник: The Lost Art of C Structure Packing (Eric S. Raymond, esr@thyrsus.com)

Как-то раз, обсуждая с одногруппницей тему ее диплома, я посоветовал ей отличную статью Data alignment: Straighten up and fly right, посвященную выравниванию данных в оперативной памяти. Т. к. с английским у нее дела обстоят не очень хорошо, она попросила меня перевести статью на русский язык. Переведя статью, я решил, что незачем добру пропадать, и поэтому с разрешения автора выкладываю сюда перевод. Перевод довольно вольный, но в то же время достаточно точный. Вообщем, буду рад, если кому-нибудь пригодится.

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

Гранулярность доступа к памяти

Программисты привыкли думать о памяти, как о простом массиве байтов. В языке C и его языках-наследниках char* всегда означало «блок данных», и даже в Java™ есть тип byte[] для представления «сырых» данных в памяти.

Рис. 1. Как программисты видят память

Однако, процессор в вашем компьютере считывает данные из памяти блоками размером отнюдь не в одни байт. Считывание данных производится блоками по 2, 4, 8, 16 или даже 32 байта. Далее размер таких блоков мы будем называть гранулярностью доступа к памяти.

Рис. 2. Как эту же память видят процессоры

Разница в том, как программисты видят память, и как процессоры на самом деле с ней работают, приводит к интересным последствиям, которым и посвящена данная статья.

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

• Приложение будет работать медленнее.
• Приложение может «зависнуть».
• Операционная система может внезапно аварийно завершиться.
• Приложение будет работать непредсказуемо, что в итоге может привести к порче ваших данных.

Что такое выравнивание

Чтобы проиллюстрировать принципы, лежащие в основе выравнивания данных, выполним небольшую программу и посмотрим, какое влияние на нее будет оказывать гранулярность доступа к памяти. Программа предельно проста: сначала считываем в регистр 4 байта с адреса 0, а затем считываем в тот же регистр 4 байта с адреса 1.

Для начала посмотрим, как наша программа будет работать на процессоре с однобайтовой гранулярностью доступа к памяти:

Рис. 3. 1-байтовая гранулярность доступа к памяти

Здесь мы видим то, что и ожидает увидеть любой программист, руководствующийся базовыми представлениями о том, как работает оперативная память: при считывании 4 байт с адреса 1 процессор делает те же 4 операции доступа к памяти, что и при считывании данных с адреса 0. А теперь давайте посмотрим, как наша программа будет работать на процессоре с гранулярностью доступа к памяти в 2 байта (примером такого процессора является классический 68000):

Рис. 4. 2-байтовая гранулярность доступа к памяти

При чтении данных с адреса 0 процессору с 2-байтовой гранулярностью требуется в два раза меньше операций доступа к памяти, чем процессору с 1-байтовой гранулярностью. Считывание двух байтов за одну операцию доступа к памяти производится быстрее, чем считывание тех же двух байтов за две операции доступа к памяти (см. Разработка на PC и производительность — Memory Latency — прим. переводчика), так что производители процессоров могут добиться заметного увеличения производительности путем уменьшения операций доступа к памяти, увеличив при этом гранулярность.

Однако заметьте, что происходит, когда мы считываем данные с адреса 1. Т. к. адрес не кратен размеру считываемых данных, процессору приходится выполнять лишнюю работу, считывая при этом 6 байт вместо 4. Такой адрес называется невыровненным. При доступе к данным по невыровненным адресам процессору приходится делать лишние обращения к памяти, что в итоге приводит к снижению скорости работы программы.

Теперь же давайте посмотрим, что произойдет, если запустить нашу программу на процессоре с гранулярностью доступа к данным в 4 байта (таком как 68030 или PowerPC® 601):

Рис. 5. 4-байтовая гранулярность доступа к памяти

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

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

«Ленивые» процессоры

Процессор вынужден прибегать к некоторым дополнительным действиям при обработке инструкции на доступ к данным с невыровненного адреса. Вернемся к нашему примеру со считыванием 4 байт с адреса 1 на процессоре с гранулярностью в 4 байта:

Рис. 6. Обработка процессором команды на доступ к данным по невыровненному адресу

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

Некоторые процессоры просто не выполняют эту работу.

Классический 68000 был процессором с гранулярностью в 2 байта и не имел соответствующей логики обработки невыровненных данных. Если он сталкивался с командой на обращение к данным по невыровненному адресу, то просто генерировал исключение, а, к примеру, классическая Mac OS не обрабатывала данное исключение должным образом и выдавала пользователю сообщение с требованием перезагрузить систему.

Более поздние процессоры серии 680×0, к примеру 68020, утратили данное ограничение и выполняли всю необходимую работу. Это объясняет, почему некоторые старые программы, отлично работающие на 68020, аварийно завершались на 68000, и также объясняет тот факт, почему раньше программисты, писавшие программы для Mac OS, инициализировали указатели странными адресами — если на классической Mac OS управление доходило до разыменования указателя, которому не был присвоен адрес реально существующих данных, система немедленно передавала управление отладчику. Впоследствии они могли просмотреть стек вызова функций и определить, где произошла ошибка.

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

Примером процессора, который ради скорости жертвует поддержкой доступа к невыровненым данным, является MIPS. MIPS — отличный пример процессора, в котором не реализованы многие специфические возможности во имя обеспечения более высокого быстродействия.

PowerPC использует следующий подход: все современные PowerPC-процессоры имеют поддержку доступа к невыровненным 32-битовым целочисленным значениям, и хотя пользователям и приходится платить за доступ к невыровненным данным некоторым снижением производительности, оно довольно невелико.

С другой стороны, современные PowerPC-процессоры не включают в себя поддержку доступа к 64-битовым вещественным числам, и если процессор встречает команду на доступ к такому числу с невыровненного адреса, то он генерирует исключение, передавая тем самым управление операционной системе и давая ей возможность на софтверном уровне выполнить всю необходимую работу. Это решает проблему, но, естественно, выполняется значительно медленнее, чем если бы все необходимые операции выполнял процессор.

Скорость

Напишем несколько тестов, которые проиллюстрируют нам падение производительности при обращении к невыровненным данным. Тесты предельно простые: считываем число, изменяем его знак и записываем полученное значение обратно. Числа считываются из и записываются в 10 Мб буфер. При тестировании изменяются следующие значения:

1. Размер чисел, которыми обрабатывается буфер. Сначала буфер обрабатывается 1-байтовыми числами, затем 2-, 4- и 8-байтовыми.
2. Выравнивание буфера. Мы изменяем выравнивание буфера, увеличивая указатель на него, и запускаем тест снова.

Тесты выполнялись на 800 MHz PowerBook G4. Чтобы уменьшить влияние операционной системы и других программ на их результаты, каждый тест был запущен 10 раз, и было взято среднее значение от полученных результатов. Первый тест — работа с 1-байтовыми числами:

Листинг 1. Обработка 1-байтовыми числами

void Munge8( void *data, uint32_t size ) {
    uint8_t *data8 = (uint8_t*) data;
    uint8_t *data8End = data8 + size;while( data8 != data8End )
        *data8++ = -*data8;
}

Для выполнения данной функции в среднем потребовалось 67 364 микросекунды. Теперь изменим ее для работы с 2-байтовыми числами (в таком случае ей потребуется выполнить в два раза меньше операций доступа к данным):

Листинг 2. Обработка 2-байтовыми числами

void Munge16( void *data, uint32_t size ) {
    uint16_t *data16 = (uint16_t*) data;
    uint16_t *data16End = data16 + (size >> 1); /* Divide size by 2. */
    uint8_t *data8 = (uint8_t*) data16End;
    uint8_t *data8End = data8 + (size & 0x00000001); /* Strip upper 31 bits. */while( data16 != data16End )
        *data16++ = -*data16;
    while( data8 != data8End )
        *data8++ = -*data8;
}

Этой функции в среднем потребовалось 48 765 микросекунд для обработки того же 10 Мб буфера, что на 38% быстрее чем в предыдущем примере. Однако, этот буфер был выровнен. Если же мы возьмем невыровненный буфер, то время работы функции увеличится до 66 385 микросекунд, т. е. 27% времени будет уходить на обеспечение работы с невыровненными данными. Следующий график демонстрирует, как меняется производительность при обработке выровненного и невыровненного буфера:

Рис. 7. Сравнение времени обработки 1-байтовыми числами с временем обработки 2-байтовыми числами

Как видно из графика, обработка 1-байтовыми числами заняла довольно много времени. В то же время на обработку 2-байтовыми числами требуется значительно меньше времени, но только до тех пор, пока буфер выровнен по 2-байтовой границе, в противном случае 27% времени мы будем тратить впустую.

А теперь посмотрим, что будет, если мы попробуем обрабатывать данные четырехбайтовыми числами:

Листинг 3. Обработка 4-байтовыми числами

void Munge32( void *data, uint32_t size ) {
    uint32_t *data32 = (uint32_t*) data;
    uint32_t *data32End = data32 + (size >> 2); /* Divide size by 4. */
    uint8_t *data8 = (uint8_t*) data32End;
    uint8_t *data8End = data8 + (size & 0x00000003); /* Strip upper 30 bits. */while( data32 != data32End )
        *data32++ = -*data32;
    while( data8 != data8End )
        *data8++ = -*data8;
}

Обработка выровненного буфера заняла 43 043 микросекунды. Невыровненный буфер обрабатывался 55 775 микросекунд. Таким образом, получается, что на данной тестовой машине невыровненные 4-байтовые числа обрабатываются медленнее выровненных 2-байтовых чисел:

Рис. 8. Сравнение времени обработки 1-байтовыми, 2-байтовыми и 4-байтовыми числами

А теперь плохая новость: попробуем обработать тот же буфер 8-байтовыми числами:

Листинг 4. Обработка 8-байтовыми числами

void Munge64( void *data, uint32_t size ) {
    double *data64 = (double*) data;
    double *data64End = data64 + (size >> 3); /* Divide size by 8. */
    uint8_t *data8 = (uint8_t*) data64End;
    uint8_t *data8End = data8 + (size & 0x00000007); /* Strip upper 29 bits. */while( data64 != data64End )
        *data64++ = -*data64;
    while( data8 != data8End )
        *data8++ = -*data8;
}

Munge64() обработала выровненный буфер за 39 085 микросекунд — это на 10% быстрее чем при обработке 4-байтовыми числами. Однако обработка 8-байтовыми числами невыровненного буфера заняла целых 1 841 155 микросекунд — на два порядка медленнее обработки выровненных данных!

Что произошло? Т. к. в современных PowerPC нет аппаратной поддержки доступа к невыровненным восьмибайтовым числам, процессор генерирует исключение при каждом обращении к такому числу. Операционная система перехватывает исключение и выполняет выравнивание вручную. Следующий график иллюстрирует падение производительности, и когда оно происходит:

Рис. 9. Сравнение времени работы при обработке числами различного размера

Падение быстродействия при обращении к невыровненным 2- и 4-байтовым числам просто меркнет на фоне падения быстродействия при обращении к невыровненным 8-байтовым числам, поэтому «отрежем» его верхнюю часть:

Рис. 10. Сравнение времени работы при обработке числами различного размера #2

А теперь более пристально посмотрим на график и сравним скорость выполнения программы при обращении к 8-байтовым числам, выровненным по 4-байтовой границе:

Рис. 11. Сравнение времени работы при обработке числами различного размера #3

Заметьте, что обращение к 8-байтовым числам, выровненным по 4-байтовой и 12-байтовой границе, медленнее, чем чтение тех же данных, 4- или даже 2-байтовыми числами. Несмотря на то, что PowerPC имеет аппаратную поддержку работы с 8-байтовыми числами, выровненными по 4-байтовой границе, вам все равно приходится платить временем выполнения программы за доступ по адресам, не кратным восьми. К счастью, эта плата не настолько велика, как при доступе к 8-байтовым числам, выровненным по 1-, 2-, 3-, 5-, 6- и 7-байтовым границам, но мораль в том, что доступ к невыровненной памяти быстрее при работе с числами меньшего размера.

Атомарность

Все современные процессоры предоставляют инструкции атомарного доступа к данным. Эти специальные инструкции являются ключевыми при реализации различных примитивов синхронизации, необходимых для контроля доступа к данным из нескольких одновременно выполняющихся программ (потоков). Как нетрудно догадаться по их имени, выполнение атомарных инструкций не должно прерываться во время их выполнения — именно это свойство делает их просто незаменимыми при реализации объектов синхронизации.

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

Если адрес не выровнен, то требуется как минимум две операции доступа к памяти. Но что произойдет, если требуемые нам данные находятся на границе двух страниц виртуальной памяти? Вполне вероятна ситуация, когда первая страница будет находиться в оперативной памяти, а вторая будет выгружена на диск. В таком случае при доступе к данным во время выполнения атомарной инструкции будет сгенерировано прерывание Page fault, что приведет к передаче управления подсистеме виртуальной памяти, отвечающей за подкачку выгруженных на диск страниц в память, а, следовательно, нарушению атомарности инструкции. Чтобы устранить возможность возникновения подобной ситуации, и 68K, и PowerPC требуют, чтобы все данные, к которым впоследствии будет производиться атомарный доступ, были выровнены по 4-байтовой границе.

К сожалению, PowerPC не генерирует исключение, когда встречает инструкцию атомарной записи по невыровненному адресу. Вместо этого, он просто оставляет данные без изменения. Это может привести к довольно неприятным последствиям, т. к. многие атомарные функции написаны так, что после неудачной записи повторяют свою попытку снова и снова в предположении, что в данном случае ресурсом завладел кто-то другой, что в итоге приводит к «зависанию» программы.

Выравнивание в структурах

Рассмотрим следующую структуру:

Листинг 5. Обычная структура

typedef struct {
    char    a;
    long    b;
    char    c;
} Struct;

Как вы думаете, какой размер данная структура занимает в памяти компьютера? Многие программисты ответят «6 байт». Это вполне логично: один байт для a, четыре байта для b и еще один байт для c. 1 + 4 + 1 = 6. Если следовать данным рассуждениям, то такая структура должна располагаться в памяти следующим образом:

Однако, если вы «попросите» ваш компилятор выдать размер данной структуры при помощи sizeof( Struct ), то, скорее всего, получите величину больше чем 6, вероятнее всего 8, а возможно даже и целых 24 байта. Этому есть две причины: обратная совместимость и эффективность.

Итак, обратная совместимость. Помните 68000-процессор с гранулярностью доступа к памяти в два байта, который генерировал исключение при обращении к невыровненным адресам? Если бы при такой организации структуры вы попытались обратиться к полю b, то вы обратились бы по невыровненному адресу. В итоге, если отладчик у вас не установлен, Mac OS отобразила бы вам диалог с сообщением о критической ошибке и всего одной кнопкой «Перезагрузиться». Вряд ли такое сообщение доставит много радости пользователю, особенно если у него остались несохраненные данные!

Поэтому, вместо того, чтобы располагать поля в структурах так, как программист видит их в описании структуры, компилятор вставляет «лишние» данные между ее полями, чтобы все поля располагались по выравненным адресам:

Сегодня, когда 68020 производится с поддержкой доступа к невыровненным данным, это может показаться излишним, но не надо забывать про производительность.

А вторая причина — как раз производительность. Сегодня PowerPC хорошо работает с данными, выравненными по 2-байтовой границе, но еще лучше он работает с данными, выравненными по 4-байтовой границе. Вам, возможно, и нет необходимости заботиться о классическом 68000, но о потенциальном снижении производительности на два порядка при доступе к невыровненным полям типа double явно стоит! Именно поэтому компиляторы в обязательном порядке самостоятельно выравнивают все поля внутри структур.

Заключение

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

• Ваши программы могут работать значительно медленнее, чем могли бы, если они делают много обращений к невыровненным данным, т. к. при их выполнении процессор будет вынужден выполнять лишнюю работу.
• Ваши программы могут «зависать», если вы размещаете объекты синхронизации по невыровненным адресам.
• Есть вероятность, что вы не оптимально размещаете поля внутри структур, что приводит к некоторому снижению скорости работы программы, а также может быть критично в случае большого дефицита оперативной памяти (прим. переводчика).

Выравнивание

Последнее обновление: 02.07.2023

Для ускорения доступа объектам в памяти в архитектуре x86-64 может применяться выравнивание.
Выравнивание данных не всегда необходимо, так как кэш-архитектура современных процессоров x86-64 на самом деле обрабатывает большинство невыровненных данных.
Тем не менее иногда доступ к данным, которые не выровнены по соответствующему адресу, может потребовать дополнительного времени. И если скорость доступа к подобным данным
критична, то можно использовать выравнивание.

Выравнивание означает, что адрес объекта является четным и кратен определенному размеру. В качестве такого размера обычно выбирают размер объекта, если он не более 32 байт и является степенью двойки.
Для объектов размером более 32 байт обычно достаточно выравнивание объекта по 8-, 16- или 32-байтовой адресной границе. Для установки выравнивания применяется директива align

align выравнивание

В качестве операнда директиве передается целочисленное значение: 1, 2, 4, 8 или 16. Как правило, если нужен максимально быстрый доступ, то необходимо выбирать значение, равное размеру объекта, по которому надо выровнять. То есть для выравнивания по слову (16 бит)
применяется выражение align 2, для выравнивания по двойному слову (4 байта) применяется выражение align 4, по четверным словам —
align 8 и т.д. Если размер объекта не является степенью числа 2, то обычно для выравнивания используется первая ближайщая степень числа 2 (максимум до 16 байт), большее размера объекта.
При этом объекты real80 (и tbyte) выравниваются только по 8 байтам. Например:

.data
    d1 dword 33
    w1 word 22
    b1 byte 11
align 2
    w2 word 10

Если MASM встречает директиву align в разделе .data, он выравняет последующую переменную по адресу, который кратен указанному выравниванию.
Если MASM определяет, что текущий адрес директивы align не является целым числом, кратным указанному значению, то после предыдущей переменной добавляются дополнительные байты
до тех пор, пока текущий адрес в разделе .data не станет кратен указанному значению.

Первое объявление .data в программе (на Windows) размещает свои переменные по адресу, который кратен 4096 байтам.
Какая бы переменная ни появилась первой в этом объявлении .data, она гарантированно будет выровнена. Каждая последующая переменная размещается по адресу,
который представляет собой сумму размеров всех предыдущих переменных плюс начальный адрес этой секции .data.

Например:

.data
    d1 dword 33
    w1 word 22
    b1 byte 11
align 2
    w2 word 10
.code
main proc
    mov rax, 0
    mov ax, [w2 - 4]    ; смещаемся назад на 4 байта - [w2-4] = [w1]
    ret
main endp
end

Здесь первые три переменных в сумме занимают 7 байт (4 + 2 + 1):

d1 dword 33
w1 word 22
b1 byte 11

Но за ними идет еще одна переменная с выравниванием по 2 байтам:

align 2
w2 word 10

Поэтому после переменной b1 добавляется еще один байт, чтобы последующая переменная w2 располагалась по четному адресу, который кратен 2. Соотвественно, чтобы перейти от
адреса переменной w2 к адресу переменной w1, надо вычесть 4 байта (размер переменной w1 + размер переменной b1 + 1 байт для установки выравнивания). И в данном случае в регистре AX окажется значение переменной w1.

mov ax, [w2 - 2]    ; [w2-2] = [b1]

Без выравнивания для перехода от адреса переменной w2 к адресу переменной w1 потребовалось бы смещение назад на 3 байта:

.data
    d1 word 33
    w1 word 22
    b1 byte 11
    w2 word 10  ; переменная w2 не выравнена
.code
main proc
    mov rax, 0
    mov ax, [w2-3]    ; смещаемся назад на 3 байта
    ret
main endp
end

Выравнивание делает программу немного больше (на несколько байтов), однако в обмен получаем более быстрый доступ к данным. Учитывая, что программа увеличится всего на несколько байтов, то это может быть неплохим решением.

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

Итак, смотрите, в чём дело.

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

[байт 0] [байт 1] [байт 2] [байт 3] [байт 4] [байт 5] [байт 6] [байт 7]...

(Ну или иногда легче представлять так:

... [байт 7] [байт 6] [байт 5] [байт 4] [байт 3] [байт 2] [байт 1] [байт 0]

— вам ещё предстоит узнать про разницу между Big Endian и Little Endian.)

Байт, как минимально адресуемую единицу памяти, можно адресовать как угодно. Но обычно вы работаете с более крупными единицами. Например, это машинное слово: размер регистра процессора. Для 32-битной архитектуры это четырёхбайтовая структура.

Теперь, байты прекрасно организовываются в четвёрки:

[байт 0] [байт 1] [байт 2] [байт 3] [байт 4] [байт 5] [байт 6] [байт 7]...
[        машинное слово 0         ] [        машинное слово 1         ]...

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

[байт 0] [байт 1] [байт 2] [байт 3] [байт 4] [байт 5] [байт 6] [байт 7] [байт 8]...
         [          машинное слово         ] [     ещё одно машинное слово     ]...

— машинное слово может начинаться по любому адресу!

Так вот, большинство компьютеров устроено так, что машинные слова, скомбинированные в четвёрки верхним образом читаются быстро, а вот машинные слова второго типа (то есть, те, которые не получаются шагами по 4 от нуля) — медленно. (Хотя требования по выравниванию могут быть и сложнее, и не совпадать с кратностью машинного слова.) Хуже того, очень многие архитектуры вовсе не позволяют читать такие слова, и для того, чтобы прочитать вот такое слово:

[байт 0] [байт 1] [байт 2] [байт 3] [байт 4] [байт 5] [байт 6] [байт 7]...
         [          машинное слово         ]

приходится читать машинные слова по адресу 0 и 4

[байт 0] [байт 1] [байт 2] [байт 3] [байт 4] [байт 5] [байт 6] [байт 7]...
         [    нужно это машинное слово     ]
[     но приходится читать это    ] [              и это              ]

выбирать из них нужные байты, перетасовывать и собирать «вручную» в нужное машинное слово! Понятно, что это сложная и сравнительно дорогостоящая операция.

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

Пример: для такой структуры:

struct
{
    char x; // 1 байт
    int y;  // 4 байта
    char z; // 1 байт
};

память выделяется так:

[    ] [    ] [    ] [    ] [    ] [    ] [    ] [    ] [    ] [    ] [    ] [    ]
[  x ] { потерянные байты } [             y           ] [  z ] { потерянные байты }

Если сама структура будет выровнена в памяти (об этом компилятор тоже заботится), то y будет выровнено, и доступ к нему будет быстрым (а на некоторых платформах, напомню, вообще только в этом случае возможен).

Но в этом случае наша структура занимает больше памяти, чем если бы порядок переменных был таким:

[    ] [    ] [    ] [    ] [    ] [    ] [    ] [    ]
[  x ] [  z ] {  потеряно } [             y           ]

Бóльшая структура означает бóльший расход памяти и бóльшие затраты на копирование, чтение этой структуры и тому подобное. Таким образом, переставив поля структуры, мы можем сэкономить.

Обратите внимание, что на самом деле универсальной оптимизации не существует. Например, для разных архитектур компьютера размер машинного слова будет отличаться. Кроме того, и размеры сколько-нибудь сложных данных могут отличаться тоже, а значит вычисленный оптимальный порядок на одной системе может оказаться очень неоптимальным на другой системе.

Дополнительное чтение по теме (на английском): http://www.catb.org/esr/structure-packing/