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

Здравствуйте! Наткнулся на термин Выравнивание данных в статье «Оптимизация кода на C++ (C++11) на примере конкретной задачи». В той статье код оптимизируется путем изменения порядка расположения переменных в структуре.
Почему происходит оптимизация кода, только из-за изменения порядка расположения переменных?

Ответ

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

Итак, смотрите, в чём дело.
Память компьютера работает следующим образом. Память программы можно представить себе как большой массив байт, а адрес — индекс в этом массиве.
[байт 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/