Выравнивание структур данных в памяти компьютера

Введение

Способ организации и доступа к данным в компьютерной памяти.

Выравнивание структуры данных – это способ организации и доступа к данным в компьютерной памяти. Оно включает в себя три отдельные, но взаимосвязанные аспекта: выравнивание данных, заполнение структуры данных (padding) и упаковку. Центральный процессор в современном компьютерном оборудовании наиболее эффективно выполняет операции чтения и записи в память, когда данные выровнены естественным образом, что обычно означает, что адрес памяти данных кратен размеру данных. Например, в 32-битной архитектуре данные считаются выровненными, если они хранятся в четырех последовательных байтах, и первый байт расположен по адресу, кратному четырем байтам. Выравнивание данных – это приведение элементов в соответствие с их естественным выравниванием. Для обеспечения естественного выравнивания может потребоваться вставка заполнения между элементами структуры или после последнего элемента структуры. Например, на 32-битной машине структура данных, содержащая 16-битное значение, за которым следует 32-битное значение, может содержать 16 бит заполнения между 16-битным и 32-битным значениями для выравнивания 32-битного значения по 32-битной границе. В качестве альтернативы можно упаковать структуру, исключив заполнение, что может привести к более медленному доступу, но позволит сэкономить примерно четверть памяти. Хотя выравнивание структуры данных является фундаментальной проблемой для всех современных компьютеров, многие языки программирования и их реализации обрабатывают выравнивание данных автоматически. Fortran, Ada, PL/I, Pascal, некоторые реализации C и C++, D, Rust, C# и язык ассемблера предоставляют, по крайней мере, частичный контроль над заполнением структуры данных, что может быть полезно в определенных специализированных случаях.

Определения

Адрес памяти a называется выровненным по n байтам, когда a кратно n (где n является степенью 2). В этом контексте байт является наименьшей единицей доступа к памяти, то есть каждый адрес памяти соответствует уникальному байту. Адрес, выровненный по n байтам, будет иметь минимум log2(n) младших значащих нулей при представлении в двоичном виде. Альтернативная формулировка "b бит выровнен" обозначает адрес, выровненный по b/8 байт (например, 64 бита выровнен – это 8 байт выровнен). Доступ к памяти считается выровненным, если обращаемые данные имеют длину n байт, а адрес данных выровнен по n байтам. Если доступ к памяти не выровнен, он называется невыровненным. Следует отметить, что по определению, байтовые доступы к памяти всегда выровнены. Указатель памяти, ссылающийся на примитивные данные длиной n байт, считается выровненным, если он может содержать только адреса, выровненные по n байтам, в противном случае он считается невыровненным. Указатель памяти, ссылающийся на агрегат данных (структуру данных или массив), считается выровненным, если и только если каждый примитивный элемент данных в агрегате выровнен. Следует отметить, что вышеуказанные определения предполагают, что каждый примитивный элемент данных имеет длину, равную степени двойки. Если это не так (например, для 80-битной чисел с плавающей точкой на x86), контекст определяет условия, при которых данные считаются выровненными или невыровненными. Структуры данных могут храниться в памяти на стеке с фиксированным размером, называемым ограниченным, или на куче с динамическим размером, называемым неограниченным.

Проблемы

Процессор обращается к памяти по одному слову за раз. Пока размер слова памяти не меньше, чем наибольший примитивный тип данных, поддерживаемый компьютером, выровненные обращения всегда будут обращаться к одному слову памяти. Это может быть неверно для невыровненных обращений к данным. Если старший и младший байты данных не находятся в пределах одного и того же слова памяти, компьютеру необходимо разбить обращение к данным на несколько обращений к памяти. Это требует сложной схемы для генерации и координации этих обращений. Для обработки случая, когда слова памяти находятся на разных страницах памяти, процессор должен либо убедиться, что обе страницы присутствуют перед выполнением инструкции, либо уметь обрабатывать промах TLB или ошибку страницы при любом обращении к памяти во время выполнения инструкции. Некоторые процессорные архитектуры намеренно избегают такой сложности и вместо этого обеспечивают альтернативное поведение при невыровненном обращении к памяти. Например, реализации архитектуры ARM до ISA ARMv6 требуют обязательного выровненного доступа к памяти для всех многобайтовых инструкций загрузки и сохранения. В зависимости от конкретной выполненной инструкции, результатом попытки невыровненного доступа может быть округление младших значащих битов некорректного адреса в меньшую сторону, приводящее к выровненному доступу (иногда с дополнительными оговорками), генерация исключения MMU (если присутствует аппаратное обеспечение MMU) или молчаливое получение других потенциально непредсказуемых результатов. Архитектуры ARMv6 и более поздние поддерживают невыровненный доступ во многих случаях, но не обязательно во всех. Когда осуществляется доступ к одному слову памяти, операция является атомарной, то есть всё слово памяти считывается или записывается одновременно, и другие устройства должны ждать завершения операции чтения или записи, прежде чем получить к нему доступ. Это может быть неверно для невыровненных обращений к нескольким словам памяти, например, первое слово может быть прочитано одним устройством, оба слова записаны другим устройством, а затем второе слово прочитано первым устройством, так что прочитанное значение не является ни исходным, ни обновленным. Хотя такие сбои редки, их очень трудно обнаружить.

The CPU accesses memory by a single memory word at a time. As long as the memory word size is at least as large as the largest primitive data type supported by the computer, aligned accesses will always access a single memory word. This may not be true for misaligned data accesses. If the highest and lowest bytes in a datum are not within the same memory word the computer must split the datum access into multiple memory accesses. This requires a lot of complex circuitry to generate the memory accesses and coordinate them. To handle the case where the memory words are in different memory pages the processor must either verify that both pages are present before executing the instruction or be able to handle a TLB miss or a page fault on any memory access during the instruction execution. Some processor designs deliberately avoid introducing such complexity, and instead yield alternative behavior in the event of a misaligned memory access. For example, implementations of the ARM architecture prior to the ARMv6 ISA require mandatory aligned memory access for all multi byte load and store instructions. Depending on which specific instruction was issued, the result of attempted misaligned access might be to round down the least significant bits of the offending address turning it into an aligned access (sometimes with additional caveats), or to throw an MMU exception (if MMU hardware is present), or to silently yield other potentially unpredictable results. The ARMv6 and later architectures support unaligned access in many circumstances, but not necessarily all. When a single memory word is accessed the operation is atomic, i. e. the whole memory word is read or written at once and other devices must wait until the read or write operation completes before they can access it. This may not be true for unaligned accesses to multiple memory words, e. g. the first word might be read by one device, both words written by another device and then the second word read by the first device so that the value read is neither the original value nor the updated value. Although such failures are rare, they can be very difficult to identify.

Пополнение структуры данных

Хотя компилятор (или интерпретатор) обычно выделяет отдельные элементы данных по выровненным границам, структуры данных часто содержат члены с различными требованиями к выравниванию. Для обеспечения правильного выравнивания транслятор обычно вставляет дополнительные неименованные члены данных, чтобы каждый член был выровнен должным образом. Кроме того, сама структура данных может быть дополнена конечным неименованным членом. Это позволяет правильно выравнивать каждый член массива структур. Дополнение вставляется только тогда, когда за членом структуры следует член с более высоким требованием к выравниванию или в конце структуры. Изменяя порядок членов в структуре, можно изменить объем необходимого дополнения для поддержания выравнивания. Например, если члены отсортированы по убыванию требований к выравниванию, потребуется минимальное количество дополнения. Минимальный объем необходимого дополнения всегда меньше, чем максимальное выравнивание в структуре. Вычисление максимального объема необходимого дополнения более сложно, но всегда меньше суммы требований к выравниванию для всех членов минус удвоенную сумму требований к выравниванию для наименее выровненной половины членов структуры. Хотя C и C++ не позволяют компилятору переупорядочивать члены структуры для экономии места, другие языки могут это делать. Также можно указать большинству компиляторов C и C++ "упаковывать" члены структуры до определенного уровня выравнивания, например, "pack(2)" означает выравнивать члены данных, размер которых больше одного байта, по границе в два байта, так что любые члены дополнения будут не более одного байта. Аналогично, в PL/I структуру можно объявить UNALIGNED, чтобы исключить все дополнения, кроме дополнений вокруг битовых строк. Одно из применений таких "упакованных" структур — экономия памяти. Например, структура, содержащая один байт (например, char) и четырехбайтовое целое число (например, uint32_t), потребует трех дополнительных байтов дополнения. Большой массив таких структур будет использовать на 37,5% меньше памяти, если он упакован, хотя доступ к каждой структуре может занять больше времени. Этот компромисс можно рассматривать как форму компромисса между пространством и временем. Хотя использование "упакованных" структур чаще всего используется для экономии памяти, оно также может использоваться для форматирования структуры данных для передачи с использованием стандартного протокола. Однако в этом случае необходимо также следить за тем, чтобы значения членов структуры хранились с порядком байтов (эндианностью), требуемым протоколом (часто сетевым порядком байтов), который может отличаться от порядка байтов, используемого хост-машиной.

Although the compiler (or interpreter) normally allocates individual data items on aligned boundaries, data structures often have members with different alignment requirements. To maintain proper alignment the translator normally inserts additional unnamed data members so that each member is properly aligned. In addition, the data structure as a whole may be padded with a final unnamed member. This allows each member of an array of structures to be properly aligned. Padding is only inserted when a structure member is followed by a member with a larger alignment requirement or at the end of the structure. By changing the ordering of members in a structure, it is possible to change the amount of padding required to maintain alignment. For example, if members are sorted by descending alignment requirements a minimal amount of padding is required. The minimal amount of padding required is always less than the largest alignment in the structure. Computing the maximum amount of padding required is more complicated, but is always less than the sum of the alignment requirements for all members minus twice the sum of the alignment requirements for the least aligned half of the structure members. Although C and C++ do not allow the compiler to reorder structure members to save space, other languages might. It is also possible to tell most C and C++ compilers to "pack" the members of a structure to a certain level of alignment, e. g. "pack(2)" means align data members larger than a byte to a two byte boundary so that any padding members are at most one byte long. Likewise, in PL/I a structure may be declared UNALIGNED to eliminate all padding except around bit strings. One use for such "packed" structures is to conserve memory. For example, a structure containing a single byte (such as a char) and a four byte integer (such as uint32 t) would require three additional bytes of padding. A large array of such structures would use 37.5% less memory if they are packed, although accessing each structure might take longer. This compromise may be considered a form of space–time tradeoff. Although use of "packed" structures is most frequently used to conserve memory space, it may also be used to format a data structure for transmission using a standard protocol. However, in this usage, care must also be taken to ensure that the values of the struct members are stored with the endianness required by the protocol (often network byte order), which may be different from the endianness used natively by the host machine.

Упаковка по умолчанию и

На некоторых компиляторах Microsoft, особенно для процессоров RISC, существует неожиданная взаимосвязь между настройкой упаковки по умолчанию в проекте (директива /Zp) и директивой `#pragma pack`. Директива `#pragma pack` может использоваться только для уменьшения размера упаковки структуры относительно настройки упаковки по умолчанию в проекте. Это может приводить к проблемам совместимости с заголовочными файлами библиотек, использующими, например, `#pragma pack(push, 1)`, если настройка упаковки в проекте меньше, чем 1. Поэтому установка упаковки проекта на значение, отличное от значения по умолчанию в 8 байт, нарушит работу директив `#pragma pack`, используемых в заголовочных файлах библиотек, и вызовет двоичную несовместимость структур. Это ограничение не возникает при компиляции для x86.