Выравнивание структуры данных — это способ организации и доступа к данным в памяти компьютера . Оно состоит из трех отдельных, но связанных между собой вопросов: выравнивание данных , заполнение структуры данных и упаковка .
Процессор в современном компьютерном оборудовании выполняет чтение и запись в память наиболее эффективно , когда данные естественным образом выровнены , что обычно означает, что адрес памяти данных кратен размеру данных. Например, в 32-битной архитектуре данные могут быть выровнены, если данные хранятся в четырех последовательных байтах, а первый байт лежит на 4-байтовой границе.
Выравнивание данных — это выравнивание элементов в соответствии с их естественным выравниванием. Для обеспечения естественного выравнивания может потребоваться вставить некоторое заполнение между элементами структуры или после последнего элемента структуры. Например, на 32-битной машине структура данных, содержащая 16-битное значение, за которым следует 32-битное значение, может иметь 16 бит заполнения между 16-битным значением и 32-битным значением для выравнивания 32-битного значения по 32-битной границе. В качестве альтернативы можно упаковать структуру, опустив заполнение, что может привести к более медленному доступу, но использует на три четверти меньше памяти.
Хотя выравнивание структуры данных является фундаментальной проблемой для всех современных компьютеров, многие компьютерные языки и реализации компьютерных языков автоматически обрабатывают выравнивание данных. Fortran , Ada , [1] [2] PL/I , [3] Pascal , [4] некоторые реализации C и C++ , D , [5] Rust , [6] C# , [7] и язык ассемблера позволяют по крайней мере частично контролировать заполнение структуры данных, что может быть полезно в определенных особых обстоятельствах.
Адрес памяти a называется выровненным по n байтам , когда a кратно n (где n — степень числа 2). В этом контексте байт — это наименьшая единица доступа к памяти, т. е. каждый адрес памяти определяет другой байт. Адрес, выровненный по n байтам, будет иметь минимум log 2 ( n ) наименее значимых нулей при выражении в двоичном виде .
Альтернативная формулировка b-битовое выравнивание обозначает адрес , выровненный на b/8 байт (например, 64-битовое выравнивание означает выровненный на 8 байт).
Доступ к памяти называется выровненным , когда данные, к которым осуществляется доступ, имеют длину n байт, а адрес данных выровнен на n байт. Когда доступ к памяти не выровнен, он называется невыровненным . Обратите внимание, что по определению доступ к памяти по байтам всегда выровнен.
Указатель памяти, ссылающийся на примитивные данные длиной n байт, называется выровненным , если ему разрешено содержать только адреса, выровненные на n байт, в противном случае он называется невыровненным . Указатель памяти, ссылающийся на агрегат данных (структуру данных или массив), выровнен, если (и только если) каждый примитивный элемент данных в агрегате выровнен.
Обратите внимание, что определения выше предполагают, что каждый примитивный элемент данных имеет длину степени двух байтов. Когда это не так (как в случае с 80-битной плавающей точкой на x86 ), контекст влияет на условия, при которых элемент данных считается выровненным или нет.
Структуры данных могут храниться в памяти в стеке со статическим размером, известным как ограниченный , или в куче с динамическим размером, известным как неограниченный .
Процессор обращается к памяти по одному слову памяти за раз. Пока размер слова памяти по крайней мере такой же большой, как и самый большой примитивный тип данных , поддерживаемый компьютером, выровненный доступ всегда будет обращаться к одному слову памяти. Это может быть не так для невыровненного доступа к данным.
Если самые высокие и самые низкие байты в данных не находятся в одном и том же слове памяти, компьютер должен разделить доступ к данным на несколько доступов к памяти. Это требует множества сложных схем для генерации доступов к памяти и их координации. Чтобы обработать случай, когда слова памяти находятся на разных страницах памяти, процессор должен либо проверить, что обе страницы присутствуют, перед выполнением инструкции, либо иметь возможность обрабатывать пропуск TLB или ошибку страницы при любом доступе к памяти во время выполнения инструкции.
Некоторые конструкции процессоров намеренно избегают введения такой сложности и вместо этого обеспечивают альтернативное поведение в случае невыровненного доступа к памяти. Например, реализации архитектуры ARM до ARMv6 ISA требуют обязательного выровненного доступа к памяти для всех многобайтовых инструкций загрузки и сохранения. [8] В зависимости от того, какая конкретная инструкция была выдана, результатом попытки невыровненного доступа может быть округление младших битов нарушающего адреса, превращающее его в выровненный доступ (иногда с дополнительными оговорками), или вызов исключения MMU (если присутствует аппаратное обеспечение MMU), или молчаливое получение других потенциально непредсказуемых результатов. Архитектуры ARMv6 и более поздние поддерживают невыровненный доступ во многих обстоятельствах, но не обязательно во всех.
При доступе к одному слову памяти операция является атомарной, т. е. все слово памяти считывается или записывается сразу, и другие устройства должны ждать завершения операции чтения или записи, прежде чем они смогут получить к нему доступ. Это может быть не так для невыровненных доступов к нескольким словам памяти, например, первое слово может быть прочитано одним устройством, оба слова записаны другим устройством, а затем второе слово прочитано первым устройством, так что прочитанное значение не является ни исходным значением, ни обновленным значением. Хотя такие сбои редки, их может быть очень трудно идентифицировать.
Хотя компилятор (или интерпретатор ) обычно выделяет отдельные элементы данных на выровненных границах, структуры данных часто имеют элементы с различными требованиями к выравниванию. Для поддержания надлежащего выравнивания транслятор обычно вставляет дополнительные неименованные элементы данных, чтобы каждый элемент был правильно выровнен. Кроме того, структура данных в целом может быть дополнена конечным неименованным элементом. Это позволяет каждому элементу массива структур быть правильно выровненным.
Отступ вставляется только тогда, когда за элементом структуры следует элемент с большим требованием к выравниванию или в конце структуры. Изменяя порядок элементов в структуре, можно изменить объем отступа, необходимый для поддержания выравнивания. Например, если элементы отсортированы по убыванию требований к выравниванию, требуется минимальный объем отступа. Минимальный объем требуемого отступа всегда меньше максимального выравнивания в структуре. Вычисление максимального объема требуемого отступа сложнее, но он всегда меньше суммы требований к выравниванию для всех элементов за вычетом удвоенной суммы требований к выравниванию для наименее выровненной половины элементов структуры.
Хотя C и C++ не позволяют компилятору переупорядочивать элементы структуры для экономии места, другие языки могут. Также можно указать большинству компиляторов C и C++ "упаковывать" элементы структуры до определенного уровня выравнивания, например, "pack(2)" означает выравнивание элементов данных, больших, чем байт, до двухбайтовой границы, так что любые элементы заполнения будут иметь длину не более одного байта. Аналогично, в PL/I структура может быть объявлена UNALIGNEDдля устранения всего заполнения, за исключением битовых строк.
Одним из применений таких «упакованных» структур является экономия памяти. Например, структура, содержащая один байт (например, char) и четырехбайтовое целое число (например, uint32_t), потребует три дополнительных байта заполнения. Большой массив таких структур будет использовать на 37,5% меньше памяти, если они упакованы, хотя доступ к каждой структуре может занять больше времени. Этот компромисс можно считать формой компромисса между пространством и временем .
Хотя использование "упакованных" структур чаще всего используется для экономии памяти , их также можно использовать для форматирования структуры данных для передачи с использованием стандартного протокола. Однако при таком использовании необходимо также позаботиться о том, чтобы значения членов структуры сохранялись с порядком байтов, требуемым протоколом (часто сетевым порядком байтов ), который может отличаться от порядка байтов, используемого изначально хост-машиной.
Следующие формулы определяют количество байтов заполнения, необходимых для выравнивания начала структуры данных (где mod — оператор деления по модулю ):
отступ = (выравнивание - (смещение по модулю выравнивание)) по модулю выравниваниевыровненный = смещение + отступ = смещение + ((выравнивание - (смещение по модулю выравнивание)) по модулю выравнивание)
Например, заполнение, которое нужно добавить к смещению 0x59d для выровненной по 4 байтам структуры, равно 3. Тогда структура начнется с 0x5a0, что кратно 4. Однако, когда выравнивание offset уже равно выравниванию align , второй модуль в (align - (offset mod align)) mod align вернет ноль, поэтому исходное значение останется неизменным.
Поскольку выравнивание по определению является степенью двойки, [a] операцию по модулю можно свести к побитовой операции И.
Следующие формулы выдают правильные значения (где & — побитовое И, а ~ — побитовое НЕ ) — при условии, что смещение не имеет знака или система использует арифметику с дополнительным кодом :
отступ = (выравнивание - (смещение & (выравнивание - 1))) & (выравнивание - 1) = -смещение & (выравнивание - 1)выровнено = (смещение + (выравнивание - 1)) & ~(выравнивание - 1) = (смещение + (выравнивание - 1)) & -выравнивание
Элементы структуры данных хранятся в памяти последовательно, так что в приведенной ниже структуре элемент Data1 всегда будет предшествовать Data2, а элемент Data2 всегда будет предшествовать Data3:
структура MyData { короткие Данные1 ; короткие Данные2 ; короткие Данные3 ; }; Если тип "short" хранится в двух байтах памяти, то каждый член структуры данных, изображенной выше, будет выровнен по 2 байта. Data1 будет иметь смещение 0, Data2 — смещение 2, а Data3 — смещение 4. Размер этой структуры составит 6 байт.
Тип каждого члена структуры обычно имеет выравнивание по умолчанию, что означает, что он будет, если иное не запрошено программистом, выровнен по предопределенной границе. Следующие типичные выравнивания действительны для компиляторов от Microsoft ( Visual C++ ), Borland / CodeGear ( C++Builder ), Digital Mars ( DMC ) и GNU ( GCC ) при компиляции для 32-битной x86:
Единственными заметными различиями в выравнивании для 64-битной системы LP64 по сравнению с 32-битной системой являются:
Некоторые типы данных зависят от реализации.
Вот структура с членами различных типов, общая длина которой до компиляции составляет 8 байт :
struct MixedData { char Data1 ; short Data2 ; int Data3 ; char Data4 ; }; После компиляции структура данных будет дополнена байтами заполнения для обеспечения надлежащего выравнивания каждого из ее членов:
struct MixedData /* После компиляции на 32-битной машине x86 */ { char Data1 ; /* 1 байт */ char Padding1 [ 1 ]; /* 1 байт для следующего 'short' для выравнивания по 2-байтовой границе, предполагая, что адрес, где начинается структура, является четным числом */ short Data2 ; /* 2 байта */ int Data3 ; /* 4 байта - наибольший член структуры */ char Data4 ; /* 1 байт */ char Padding2 [ 3 ]; /* 3 байта, чтобы общий размер структуры составил 12 байт */ }; Скомпилированный размер структуры теперь составляет 12 байт.
Последний член дополняется необходимым количеством байтов, чтобы общий размер структуры был кратен наибольшему выравниванию любого члена структуры ( в данном случае alignof(int) , которое = 4 в linux-32bit/gcc) [ требуется ссылка ] .
В этом случае к последнему члену добавляется 3 байта, чтобы дополнить структуру до размера 12 байтов ( alignof(int) * 3 ).
структура FinalPad { float x ; char n [ 1 ]; }; В этом примере общий размер структуры sizeof (FinalPad) == 8 , а не 5 (так что размер кратен 4 ( alignof(float) )).
структура FinalPadShort { короткая с ; символ n [ 3 ]; }; В этом примере общий размер структуры sizeof (FinalPadShort) == 6 , а не 5 (и не 8) (так что размер кратен 2 ( alignof(short) == 2 в linux-32bit/gcc)).
Можно изменить выравнивание структур, чтобы уменьшить объем требуемой им памяти (или обеспечить соответствие существующему формату), переупорядочив элементы структуры или изменив выравнивание (или «упаковку») элементов структуры компилятором.
struct MixedData /* после переупорядочивания */ { char Data1 ; char Data4 ; /* переупорядочено */ short Data2 ; int Data3 ; }; Скомпилированный размер структуры теперь соответствует предварительно скомпилированному размеру 8 байт . Обратите внимание, что Padding1[1] был заменен (и, таким образом, исключен) на Data4 , а Padding2[3] больше не нужен, поскольку структура уже выровнена по размеру длинного слова.
Альтернативный метод принудительного выравнивания структуры MixedData по границе одного байта приведет к тому, что препроцессор отменит предопределенное выравнивание элементов структуры, и, таким образом, никакие байты заполнения не будут вставлены.
Хотя не существует стандартного способа определения выравнивания членов структуры (хотя C и C++ позволяют использовать спецификатор alignas для этой цели, его можно использовать только для указания более строгого выравнивания), некоторые компиляторы используют директивы #pragma для указания упаковки внутри исходных файлов. Вот пример:
#pragma pack(push) /* помещаем текущее выравнивание в стек */ #pragma pack(1) /* устанавливаем выравнивание по границе 1 байта */struct MyPackedData { char Data1 ; long Data2 ; char Data3 ; }; #pragma pack(pop) /* восстановить исходное выравнивание из стека */Эта структура будет иметь скомпилированный размер 6 байт на 32-битной системе. Вышеуказанные директивы доступны в компиляторах от Microsoft , [9] Borland , GNU , [10] и многих других.
Другой пример:
struct MyPackedData { char Data1 ; long Data2 ; char Data3 ; } __attribute__ (( упаковано )); В некоторых компиляторах Microsoft, особенно для процессоров RISC, существует неожиданная связь между упаковкой проекта по умолчанию (директива /Zp) и директивой #pragma pack . Директива #pragma pack может использоваться только для уменьшения размера упаковки структуры из упаковки проекта по умолчанию. [11] Это приводит к проблемам взаимодействия с заголовками библиотек, которые используют, например, #pragma pack(8) , если упаковка проекта меньше этого. По этой причине установка упаковки проекта на любое значение, отличное от значения по умолчанию в 8 байт, нарушит директивы #pragma pack, используемые в заголовках библиотек, и приведет к двоичной несовместимости между структурами. Это ограничение отсутствует при компиляции для x86.
Было бы полезно выделить память, выровненную по строкам кэша . Если массив разделен на разделы для работы более чем с одним потоком, то невыровненные по строкам кэша границы подмассива могут привести к снижению производительности. Вот пример выделения памяти (двойной массив размером 10), выровненной по кэшу размером 64 байта.
#include <stdlib.h> double * foo ( void ) { //создать массив размером 10 double * array ; if ( 0 == posix_memalign ( ( void ** ) & array , 64 , 10 * sizeof ( double ))) return array ; вернуть NULL ; } Проблемы выравнивания могут затрагивать области, значительно превышающие структуру C, когда целью является эффективное отображение этой области с помощью механизма аппаратной трансляции адресов (переотображение PCI, работа MMU ).
Например, в 32-разрядной операционной системе страница размером 4 КиБ (4096 байт) — это не просто произвольный фрагмент данных размером 4 КиБ. Вместо этого это обычно область памяти, выровненная по границе 4 КиБ. Это происходит потому, что выравнивание страницы по границе размером со страницу позволяет оборудованию сопоставлять виртуальный адрес с физическим адресом, заменяя старшие биты в адресе, а не выполняя сложную арифметику.
Пример: Предположим, что у нас есть отображение TLB виртуального адреса 0x2CFC7000 на физический адрес 0x12345000. (Обратите внимание, что оба этих адреса выровнены по границам 4 КиБ.) Доступ к данным, расположенным по виртуальному адресу va=0x2CFC7ABC, приводит к разрешению TLB 0x2CFC7 на 0x12345 для выдачи физического доступа к pa=0x12345ABC. Здесь 20/12-битное разделение, к счастью, соответствует шестнадцатеричному представлению, разделенному на 5/3 цифр. Аппаратное обеспечение может реализовать это преобразование, просто объединив первые 20 бит физического адреса (0x12345) и последние 12 бит виртуального адреса (0xABC). Это также называется виртуально индексированным (ABC) физически помеченным (12345).
Блок данных размером 2 (n+1) − 1 всегда имеет один подблок размером 2 n , выровненный по 2 n байтам.
Вот как динамический распределитель, не имеющий сведений о выравнивании, может использоваться для предоставления выровненных буферов ценой двукратной потери пространства.
// Пример: выровнять 4096 байтов по 4096-байтовому буферу с помощью malloc()// невыровненный указатель на большую область void * up = malloc (( 1 << 13 ) - 1 ); // хорошо выровненный указатель на 4 КБ void * ap = aligntonext ( up , 12 ); где aligntonext( p , r ) работает путем добавления выровненного приращения, а затем очистки r наименее значимых бит p . Возможная реализация —
// Предположим `uint32_t p, bits;` для удобства чтения #define alignto(p, bits) (((p) >> bits) << bits) #define aligntonext(p, bits) alignto(((p) + (1 << bits) - 1), bits)[…] Сегмент может иметь один (а в случае атрибута inpage — два) из пяти атрибутов выравнивания: […] Байт, что означает, что сегмент может быть расположен по любому адресу. […] Слово, что означает, что сегмент может быть расположен только по адресу, кратному двум, начиная с адреса 0H. […] Абзац, что означает, что сегмент может быть расположен только по адресу, кратному 16, начиная с адреса 0. […] Страница, что означает, что сегмент может быть расположен только по адресу, кратному 256, начиная с адреса 0. […] Входящая страница, что означает, что сегмент может быть расположен по любому из предыдущих атрибутов, а также должен быть расположен так, чтобы не пересекать границу страницы […] Коды выравнивания: […] B – байт […] W – слово […] G – абзац […] xR – входящая страница […] P – страница […] A – абсолютное […] x в коде выравнивания входящей страницы может быть любым другим кодом выравнивания. […] сегмент может иметь атрибут входящей страницы, что означает, что он должен находиться на странице размером 256 байт, и может иметь атрибут слова, что означает, что он должен находиться на четном байте. […]