Решил поднять неактуальную для молодежи тему и перевести отличную статью. Оригинал – http://www.catb.org/esr/structure-packing/
1. Для кого предназначен документ
Данный текст посвящен технике уменьшения объема занимаемой памяти, за счет корректировки объявлений структур Си. Для усвоения материала, потребуются базовые знания языка программирования Си.
Необходимо знать о технике упаковки структур, если вы намеренны писать код для встраиваемых систем с ограниченной памятью или ядра операционной системы. Техника так же полезна если вы работаете с ресурсами приложения, ставшими настолько большими, что ваши программы регулярно сталкиваются с нехваткой памяти. Упаковка структур полезна в любом приложении, где вам по-настоящему надо заботиться о минимизации промахов кэша.
В конце концов, знание данной техники послужит мостом к другим эзотерическим темам языка Си. Вы не являетесь продвинутым программистом на Си, пока не освоите её. Вы не являетесь мастером языка Си, пока не сможете написать данный документ самостоятельно и разумно критиковать его.
2. Цель написание данного документа
Данная веб страница (http://www.catb.org/esr/structure-packing/. – прим.пер.) существует по причине моего активного применения оптимизационных техник на Си в конце 2013 года, которые я изучил более двух десятилетий назад и не использовал с тех пор так часто.
Мне необходимо было уменьшить объем занимаемой памяти программы, которая использовала тысячи, иногда сотни тысяч экземляров структур Си. Программа называлась cvs-fast-export (экспортирует RCS или CVS историю, как быстро импортируемый поток. Данная программа анализирует коллекцию RCS файлов в CVS репозитории и по возможности выделяет эквивалентную историю в форме быстро импортированного потока. – прим.пер.) и проблема заключалась в том, что она завершалась с ошибками о нехватки памяти на больших репозиториях.
Существуют способы значительного уменьшения использования памяти в ситуациях схожих с моей с помощью аккуратной реорганизации порядка членов в структурах. Это может привести к впечатляющему выйгрышу – в моем случае, я смог добиться уменьшения размера рабочего набора (working-set.- прим.пер) примерно на 40%, позволяя программе справляться с еще большими репозиториями, без аварийного завершения работы.
Но по мере того, как я работал и размышлял о том, что делал, я приходил к выводу, что техника упаковки структур, которую я использовал, в последние дни была позабыта. Небольшой поиск в сети подтвердил, что похоже программисты на Си больше не обсуждают эту тему, по крайней мере там, где поисковик смог бы найти данные обсуждения (? ПОДКОРРЕКТИРОВАТЬ!). Пара статей на Википедии касаются упаковки структур, но я не нашел никого, кто полностью бы раскрыл данную тему.
На самом деле есть обоснованные причины для этого. Курсы Computer Science (справедливо) держат людей подальше от микрооптимизации по отношению к нахождению лучшего алгоритма. Снижение цен на ресурсы ЭВМ сделало экономию использования памяти менее приоритетным. И способ, который хакеры использовали для обучения этому ранее, заключался в работе со странными аппаратными архитектурами – менее распространенный опыт на данный момент.
Но техника упаковки структур все еще имеет вес в важных ситуациях, и будет иметь, пока память является конечным ресурсом. Цель этого документа заключается в экономии времени программистов на Си, в связи с повторным открытием данной техники, позволяя сконцентрировать усилия на более важных вещах.
3. Требования к выравниванию
Первым делом необходимо понять, что на современных процессорах, способ, с помощью которого ваш компилятор Си размещает базовые структуры в памяти, является на первый взгляд неочевидным для того, чтобы сделать доступ к памяти быстрее.
Хранилище для базовых типов данных Си, на процессорах архитектуры x86 или ARM, обычно не начинается с произвольного адреса в ячейки памяти. Напротив, каждый тип, за исключением символьного, обладает требованием к выравниванию; символы могут располагаться, начиная с произвольного адреса байта, но 2 байтовый тип short обязан начинаться с четного адреса, 4 байтовый int или float обязаны начинаться с адреса кратного 4, и 8 байтовый long или double обязаны начинаться с адреса кратного 8. Является ли тип знаковым или безнаковым не имеет значения.
Предпосылкой к этому является то, что базовые типы языка Си на архитектурах x86 и ARM являются самовыравнивающимися (self-aligned.-прим.пер.). Указатели, 32-битные или 64-битные так же обладают свойством самовыравнивания.
Самовыравнивание обеспечивает более скоростной доступ к памяти, потому что способствует выполнению операций извлечения и вставки типизированных данных с помощью одной инструкции. Отсутствие ограничений к выравниванию, с другой стороны, заставит процессор делать два и более обращений к данным, нарушающих границы машинного слова. Для переменных символьного типа существет исключение, они достижимы из любой позиции в машином слове за константное время. Поэтому выравнивание на них не распространяется.
I said “on modern processors” because on some older ones forcing your C program to violate alignment rules (say, by casting an odd address into an int pointer and trying to use it) didn’t just slow your code down, it caused an illegal instruction fault. This was the behavior, for example, on Sun SPARC chips. In fact, with sufficient determination and the right (e18) hardware flag set on the processor, you can still trigger this on x86.
Я сказал “на современных процессорах”, потому что на старых, нарушение вашей программы на Си правил выравнивания (например приведение нечетного адреса к указателю на целое и попытка его использования) не просто понижает скорость выполнения кода, но и является причиной генерации исключения, в связи с недопустимой инструкцией. Такое поведение можно было наблюдать например на чипах Sun SPARC. В действительности, с (?) и правильно установленном аппаратном флаге (e18) процессора, проблема воспроизводится и на арихтектуре x86.
Also, self-alignment is not the only possible rule. Historically, some processors (especially those lacking barrel shifters (устройство быстрого сдвига) ) have had more restrictive ones. If you do embedded systems, you might trip over one of these lurking in the underbrush. Be aware this is possible.
К тому же, самовыравнивание не единственно возможное правило. Исторически, некоторые процессоры (особенно те, у кого отстутсвует устройство быстрого сдвига (barrel shifters.-прим.пер.)) имели намного значительные ограничения. Если вы имеете дело со встроенными системами, вы рискуете столкнуться с их неявным влиянием. Будьте внимательны, это вполне возможный сценарий.
Sometimes you can coerce your compiler into not using the processor’s normal alignment rules by using a pragma, usually #pragma pack. Do not do this casually, as it forces the generation of more expensive and slower code. Usually you can save as much memory, or almost as much, with the techniques I describe here.
Иногда вы можете в принудительном порядке указать компилятору не использовать правила выравнивания, используемые процессором, с помощью директивы pragma, обычно #pragma pack. Не делайте этого не подумав дважды, так как результатом является генерации медленного и неэффективного кода. Обычно вы можете сэкономить значительное количество памяти, используя техники описаные здесь.
The only good reason for #pragma pack is if you have to exactly match your C data layout to some kind of bit-level hardware or protocol requirement, like a memory-mapped hardware port, and violating normal alignment is required for that to work. If you’re in that situation, and you don’t already know everything else I’m writing about here, you’re in deep trouble and I wish you luck.
Единственная весомая причина для использования директивы #pragma pack, когда ваше размещение данных обязано соответствовать определенным требованиям протокола или аппаратному обеспечению на уровне битов, например аппаратный порт, отображаемый в память (?), и нарушение естественного выравнивания необходимо для корректной работы. Если это ваш случай, и вы не знаете о других способах решения проблемы, которые я описываю здесь, значит у вас большие неприятности и я могу лишь пожелать вам удачи.
4.Выравнивание
Ознакомимся с небольшим примером расположения переменных в памяти. Все последующие примеры объявления переменных происходят в верхней части Си модуля.
char *p;
char c;
int x;
If you didn’t know anything about data alignment, you might assume that these three variables would occupy a continuous span of bytes in memory. That is, on a 32-bit machine 4 bytes of pointer would be immediately followed by 1 byte of char and that immediately followed by 4 bytes of int. And a 64-bit machine would be different only in that the pointer would be 8 bytes.
Если вы не знаете ничего о выравнивании данных, вы могли предположить, что данные переменные находятся в памяти последовательно, одна за другой (occupy a continuous span of bytes in memory. -прим.пер.). В этом случае ваш ход размышлений таков: на 32-битной ЭВМ, 4 байта занимаемых указателем, предшествуют 1 байту, принадлежащего символьному типу, за ним в свою очередь располагаются 4 байта целого типа. И на 64-битной машине ситуация аналогичная, отличие лишь в том, что указатель будет занимает 8 байт.
Here’s what actually happens (on an x86 or ARM or anything else with self-aligned types). The storage for p starts on a self-aligned 4- or 8-byte boundary depending on the machine word size. This is pointer alignment – the strictest possible.
Что же происходит на самом деле (на архитектурах x86,ARM и т.д. с самовыравнивающимися типами)? Область памяти с переменной p, начинается на выравненой 4 или 8 байтной границе, в зависимости от размера машинного слова. Это выравнивание указателя – самое строгое из возможных.
The storage for c follows immediately. But the 4-byte alignment requirement of x forces a gap in the layout; it comes out as though there were a fourth intervening variable, like this:
Далее следует область памяти для переменной c. Но 4 байтное выравнивание для x, подразумевает разрыв в размещении. Он будет выглядить, как четвертая переменная:
char *p; /* 4 или 8 байт */
char c; /* 1 байт */
char pad[3]; /* 3 байт */
int x; /* 4 байт */
The pad[3] character array represents the fact that there are three bytes of waste space in the structure. The old-school term for this was “slop”.
Символьный массив pad[3] демонстрирует, что имеет место быть 3-ех байтовое,”лишнее” пространство в структуре. Олдскульнйы термин для этого – “slop”.
Compare what happens if x is a 2-byte short:
Посмотрим, что будет, если x – 2-ух байтовый short:
char *p;
char c;
short x;
In that case, the actual layout will be this:
В таком случае, реальное размещение будет выглядеть так:
char *p; /* 4 или 8 байт */
char c; /* 1 байт */
char pad[1]; /* 1 байт */
short x; /* 2 байта */
On the other hand, if x is a long on a 64-bit machine
Если x имеет тип long на 64-битной машине:
char *p;
char c;
long x;
we end up with this:
результат следующий:
char *p; /* 8 байт */
char c; /* 1 байт */
char pad[7]; /* 7 байт */
long x; /* 8 байт */
If you have been following carefully, you are probably now wondering about the case where the shorter variable declaration comes first:
Если вы читали внимательно, вас возможно интересует случай, где переменная с наименьшим типом объявлется первой:
char c;
char *p;
int x;
If the actual memory layout were written like this
Распределение памяти в таком случае:
char c;
char pad1[M];
char *p;
char pad2[N];
int x;
what can we say about M and N?
Что мы можем сказать о M и N?
First, in this case N will be zero. The address of x, coming right after p, is guaranteed to be pointer-aligned, which is never less strict than int-aligned.
Во-первых,
The value of M is less predictable. If the compiler happened to map c to the last byte of a machine word, the next byte (the first of p) would be the first byte of the next one and properly pointer-aligned. M would be zero.
It is more likely that c will be mapped to the first byte of a machine word. In that case M will be whatever padding is needed to ensure that p has pointer alignment – 3 on a 32-bit machine, 7 on a 64-bit machine.
Intermediate cases are possible. M can be anything from 0 to 7 (0 to 3 on 32-bit) because a char can start on any byte boundary in a machine word.
If you wanted to make those variables take up less space, you could get that effect by swapping x with c in the original sequence.
char *p; /* 8 bytes */
long x; /* 8 bytes */
char c; /* 1 byte
Usually, for the small number of scalar variables in your C programs, bumming out the few bytes you can get by changing the order of declaration won’t save you enough to be significant. The technique becomes more interesting when applied to nonscalar variables – especially structs.
Before we get to those, let’s dispose of arrays of scalars. On a platform with self-aligned types, arrays of char/short/int/long/pointer have no internal padding; each member is automatically self-aligned at the end of the next one.
In the next section we will see that the same is not necessarily true of structure arrays.
thatskriptkid 