Выравнивание структуры данных - это способ организации данных и доступа к ним в памяти компьютера . Она состоит из трех отдельных , но взаимосвязанных вопросов: выравнивание данных , структура данных заполнения и упаковка .
Процессора в современных компьютерных аппаратных выполняет операции чтения и записи в память наиболее эффективно , когда данные , естественно выровнены , что обычно означает , что адрес памяти Данные , является кратным размеру данных. Например, в 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] и язык ассемблера позволяют хотя бы частично контроль заполнения структуры данных, который может быть полезен в определенных особых обстоятельствах.
Определения
Память адрес называется п-байтовое выровнены , когда кратно п байт (где п является степенью 2). В этом контексте байт - это наименьшая единица доступа к памяти, т. Е. Каждый адрес памяти определяет отдельный байт. П -байт выровнен адрес будет иметь минимум журнал 2 (п) наименее значимые нули при экспрессии в двоичном виде .
Альтернативная формулировка с выравниванием по b-битам обозначает адрес с выравниванием по b / 8 байтов (например, с выравниванием по 64 бита и выравниванием по 8 байтов).
Доступ к памяти называется выровнены , когда данные , к которому осуществляется доступ п байт в длину и адрес Датум п -байт выровнены. Когда доступ к памяти не выровнен, это называется криво . Обратите внимание, что по определению обращения к байтовой памяти всегда выровнены.
Указатель памяти , которая относится к примитивным данным, п байт длиной , как говорят, выровнено , если это разрешено только содержат адреса, которые п -байт выровненных, в противном случае она называется выровненными . Указатель памяти, который относится к агрегату данных (структуре данных или массиву), выравнивается, если (и только если) выровнены все примитивные данные в агрегате.
Обратите внимание, что приведенные выше определения предполагают, что каждый элемент данных имеет длину в два байта. Когда это не так (как в случае с 80-битной плавающей точкой на x86 ), контекст влияет на условия, при которых данные считаются выровненными или нет.
Структуры данных могут храниться в памяти в стеке со статическим размером, известным как ограниченный, или в куче с динамическим размером, известным как неограниченный .
Проблемы
ЦП обращается к памяти по одному слову памяти за раз. Пока размер слова памяти не меньше размера самого большого примитивного типа данных, поддерживаемого компьютером, выровненный доступ всегда будет обращаться к одному слову памяти. Это может быть неверно для несогласованного доступа к данным.
Если старший и младший байты в данных не находятся в одном и том же слове памяти, компьютер должен разделить доступ к данным на несколько обращений к памяти. Это требует множества сложных схем для генерации обращений к памяти и их координации. Чтобы справиться со случаем, когда слова памяти находятся на разных страницах памяти, процессор должен либо проверить наличие обеих страниц перед выполнением инструкции, либо уметь обрабатывать промах TLB или отказ страницы при любом доступе к памяти во время выполнения инструкции.
Некоторые конструкции процессоров намеренно избегают такой сложности и вместо этого дают альтернативное поведение в случае неправильного доступа к памяти. Например, реализации архитектуры ARM до ARMv6 ISA требуют обязательного согласованного доступа к памяти для всех многобайтовых инструкций загрузки и сохранения. [8] В зависимости от того, какая конкретная инструкция была выдана, результатом попытки несогласованного доступа может быть округление в меньшую сторону наименее значимых битов ошибочного адреса, превращающее его в согласованный доступ (иногда с дополнительными предостережениями), или выдача исключения MMU ( при наличии оборудования MMU), или для незаметного получения других потенциально непредсказуемых результатов. Архитектура ARMv6 и более поздние версии поддерживают невыровненный доступ во многих случаях, но не обязательно во всех.
Когда осуществляется доступ к одному слову памяти, операция является атомарной, то есть все слово памяти читается или записывается одновременно, и другие устройства должны ждать завершения операции чтения или записи, прежде чем они смогут получить к нему доступ. Это может быть неверно для невыровненных обращений к нескольким словам памяти, например, первое слово может быть прочитано одним устройством, оба слова записаны другим устройством, а затем второе слово прочитано первым устройством, так что считанное значение не является исходным значением. ни обновленное значение. Хотя такие сбои случаются редко, их бывает очень сложно идентифицировать.
Заполнение структуры данных
Хотя компилятор (или интерпретатор ) обычно выделяет отдельные элементы данных на выровненных границах, структуры данных часто имеют элементы с различными требованиями к выравниванию. Чтобы поддерживать правильное выравнивание, транслятор обычно вставляет дополнительные безымянные элементы данных, чтобы каждый член был правильно выровнен. Кроме того, структура данных в целом может быть дополнена последним безымянным членом. Это позволяет правильно выровнять каждый член массива структур .
Заполнение вставляется только тогда, когда за членом структуры следует член с более высокими требованиями к выравниванию или в конце структуры. Изменяя порядок элементов в структуре, можно изменить количество отступов, необходимых для сохранения выравнивания. Например, если элементы сортируются в соответствии с требованиями выравнивания по убыванию, требуется минимальное количество отступов. Требуемый минимальный объем заполнения всегда меньше максимального выравнивания в структуре. Вычислить максимальное требуемое заполнение сложнее, но оно всегда меньше суммы требований к выравниванию для всех элементов минус удвоенная сумма требований к выравниванию для наименее выровненной половины элементов структуры.
Хотя C и C ++ не позволяют компилятору переупорядочивать элементы структуры для экономии места, другие языки могут. Также можно указать большинству компиляторов C и C ++ «упаковать» элементы структуры до определенного уровня выравнивания, например, «pack (2)» означает выравнивание элементов данных размером более одного байта с двухбайтовой границей, чтобы любые элементы заполнения имеют длину не более одного байта.
Одно из применений таких «упакованных» структур - экономия памяти. Например, структура, содержащая один байт и четырехбайтовое целое число, потребует трех дополнительных байтов заполнения. Большой массив таких структур будет использовать на 37,5% меньше памяти, если они будут упакованы, хотя доступ к каждой структуре может занять больше времени. Этот компромисс можно рассматривать как форму компромисса между пространством и временем .
Хотя использование «упакованных» структур наиболее часто используется для экономии места в памяти , их также можно использовать для форматирования структуры данных для передачи с использованием стандартного протокола. Однако при таком использовании необходимо также позаботиться о том, чтобы значения элементов структуры сохранялись с порядком байтов, требуемым протоколом (часто сетевым порядком байтов ), который может отличаться от порядка байтов, изначально используемого хост-машиной.
Вычислительная набивка
Следующие формулы обеспечивают количество байтов заполнения, необходимых для выравнивания начала структуры данных (где mod - оператор по модулю ):
padding = (align - (смещение выравнивания по модулю)) выравнивание по модулювыровнено = смещение + отступ = смещение + ((выравнивание - (выравнивание смещения по модулю)) выравнивание по модулю)
Например, заполнение, добавляемое к смещению 0x59d для 4-байтовой выровненной структуры, равно 3. Затем структура будет начинаться с 0x5a0, что кратно 4. Однако, когда выравнивание смещения уже равно выравниванию выравнивания , второй модуль по модулю (align - (offset mod align)) mod align вернет ноль, поэтому исходное значение остается неизменным.
Поскольку выравнивание по определению является степенью двойки, [a] операция по модулю может быть сведена к побитовой логической операции И.
Следующие формулы производят выровненных смещение (где & является побитовое И и ~ побитовое НЕ ):
padding = (выровнять - (смещение & (выровнять - 1))) & (выровнять - 1) = (-смещение & (выровнять - 1))выровненный = (смещение + (выравнивание - 1)) & ~ (выравнивание - 1) = (смещение + (выравнивание - 1)) & -align
Типичное выравнивание структур C на x86
Члены структуры данных хранятся в памяти последовательно, так что в приведенной ниже структуре элемент Data1 всегда предшествует Data2; и Data2 всегда предшествует Data3:
struct MyData { короткие данные1 ; короткие Data2 ; короткие Data3 ; };
Если тип «короткий» хранится в двух байтах памяти, то каждый член структуры данных, изображенной выше, будет выровнен по 2 байта. Data1 будет со смещением 0, Data2 со смещением 2 и Data3 со смещением 4. Размер этой структуры будет 6 байтов.
Тип каждого члена структуры обычно имеет выравнивание по умолчанию, что означает, что, если программист не потребует иного, он будет выровнен по заранее определенной границе. Следующие типичные выравнивания действительны для компиляторов Microsoft ( Visual C ++ ), Borland / CodeGear ( C ++ Builder ), Digital Mars (DMC) и GNU ( GCC ) при компиляции для 32-разрядной системы x86:
- Символ (один байт) будет 1-байтовое выровнены.
- Короткий (два байта) будет 2-байтовое выровнены.
- Тип int (четыре байта) будет выровнен по 4 байта.
- Длиной (четыре байта) будет 4-байтовое выровнены.
- С плавающей точкой (четыре байта) будет 4-байтовое выровнены.
- А двойные (восемь байт) будет 8 байт выровнен по Windows , и 4 байта выровненной на Linux (8 байт с -malign-двойной вариант времени компиляции).
- Долго долго (восемь байт) будет 4-байтовое выровнены.
- А длинный двойные (десять байты с C ++ Builder и DMC, восемь байт с Visual C ++, двенадцать байт с GCC) будут 8-байтовыми выровненным с C ++ Builder, 2 байта в соответствии с DMC, 8-байтовые совмещены с Визуальным C ++ и 4 байта с выравниванием по GCC.
- Любой указатель (четыре байта) будет выровнен по 4 байта. (например: char *, int *)
Единственное заметное различие в выравнивании для LP64 64-битной системы , когда по сравнению с 32-битной системы являются:
- Длиной (восемь байт) будет 8-байтовое выровнены.
- А двойные (восемь байт) будет 8-байтовое выровнены.
- Долго долго (восемь байт) будет 8-байтовое выровнены.
- А длинный двойные (восемь байт с Visual C ++, шестнадцать байт с GCC) будут 8 байт в соответствии с Visual C ++ и 16-байт в соответствии с GCC.
- Любой указатель (восемь байтов) будет выровнен по 8 байтов.
Некоторые типы данных зависят от реализации.
Вот структура с элементами разных типов, всего 8 байтов до компиляции:
struct MixedData { char Data1 ; короткие Data2 ; int Data3 ; char Data4 ; };
После компиляции структура данных будет дополнена байтами заполнения, чтобы обеспечить правильное выравнивание для каждого из ее членов:
struct MixedData / * После компиляции на 32-битной машине x86 * / { char Data1 ; / * 1 байт * / char Padding1 [ 1 ]; / * 1 байт для следующего «короткого» значения, которое будет выровнено по 2-байтовой границе, предполагая, что адрес, с которого начинается структура, является четным числом * / short Data2 ; / * 2 байта * / int Data3 ; / * 4 байта - наибольший член структуры * / char Data4 ; / * 1 байт * / char Padding2 [ 3 ]; / * 3 байта, чтобы общий размер структуры составлял 12 байтов * / };
Скомпилированный размер структуры теперь составляет 12 байт. Важно отметить, что последний член дополняется количеством требуемых байтов, так что общий размер структуры должен быть кратным наибольшему выравниванию любого члена структуры (в данном случае выравнивание (int), которое = 4 на linux-32bit / gcc) [ необходима ссылка ] .
В этом случае 3 байта добавляются к последнему члену для заполнения структуры до размера 12 байтов (выравнивание (int) × 3).
struct FinalPad { float x ; char n [ 1 ]; };
В этом примере общий размер структуры sizeof (FinalPad) == 8 , а не 5 (так что размер кратен 4 (выравнивание float)).
struct FinalPadShort { короткие s ; char n [ 3 ]; };
В этом примере общий размер конструкции sizeof (FinalPadShort) == 6 , а не 5 (не 8) (так что размер кратен 2 (alignment (short) = 2 в linux-32bit / gcc)).
Можно изменить выравнивание структур, чтобы уменьшить требуемую память (или соответствовать существующему формату), переупорядочив элементы структуры или изменив выравнивание (или «упаковку») компилятором элементов структуры.
struct MixedData / * после переупорядочения * / { char Data1 ; char Data4 ; / * переупорядочен * / short Data2 ; int Data3 ; };
Скомпилированный размер структуры теперь соответствует предварительно скомпилированному размеру 8 байтов . Обратите внимание, что Padding1 [1] был заменен (и, таким образом, удален) на Data4 и Padding2 [3] больше не нужен, поскольку структура уже выровнена по размеру длинного слова.
Альтернативный метод обеспечения соблюдения Выравнивание структуры MixedData с однобайтовой границей заставит препроцессор отбросить заранее определенное выравнивание элементов структуры, и, таким образом, байты заполнения не будут вставлены.
Хотя стандартного способа определения выравнивания элементов структуры не существует, некоторые компиляторы используют #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__ (( упаковано ));
Упаковка по умолчанию и #pragma pack
В некоторых компиляторах Microsoft, особенно для процессоров RISC, существует неожиданная взаимосвязь между упаковкой проекта по умолчанию (директива / Zp) и Директива #pragma pack . В Директива #pragma pack может использоваться только для уменьшения размера упаковки структуры из упаковки проекта по умолчанию. [11] Это приводит к проблемам взаимодействия с заголовками библиотек, которые используют, например, #pragma pack (8) , если упаковка проекта меньше этой. По этой причине установка для упаковки проекта любого значения, кроме 8 байтов по умолчанию, нарушит Директивы #pragma pack используются в заголовках библиотек и приводят к двоичной несовместимости между структурами. Это ограничение отсутствует при компиляции для x86.
Выделение памяти, выровненной по строкам кеша
Было бы полезно выделить память, выровненную по строкам кеша . Если массив разделен для работы более чем одним потоком, невыравнивание границ подмассива по строкам кэша может привести к снижению производительности. Вот пример выделения памяти (двойной массив размером 10), выровненной с кешем размером 64 байта.
#include двойной * foo ( недействительно ) { двойной * var ; // создаем массив размером 10 int ok ; ok = posix_memalign (( void ** ) & var , 64 , 10 * sizeof ( double )); если ( ок ! = 0 ) вернуть NULL ; return var ; }
Аппаратное значение требований к выравниванию
Проблемы выравнивания могут влиять на области, намного большие, чем структура 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 << биты) - 1), биты)
Заметки
- ^ На современных компьютерах, где целевое выравнивание является степенью двойки. Это может быть неверно, например, в системе, использующей 9-битные байты или 60-битные слова.
Рекомендации
- ^ "Пункты представления Ada и прагмы" . Справочное руководство GNAT, документация по 7.4.0w . Проверено 30 августа 2015 .
- ^ «F.8 Положения о заверениях». Руководство программиста SPARCompiler Ada (PDF) . Проверено 30 августа 2015 .
- ^ Спецификации языка PL / I операционной системы IBM System / 360 (PDF) . IBM . Июль 1966. С. 55–56. C28-6571-3.
- ^ Никлаус Вирт (июль 1973 г.). «Язык программирования Паскаль (пересмотренный отчет)» (PDF) . п. 12.
- ^ «Атрибуты - язык программирования D: выровнять атрибут» . Проверено 13 апреля 2012 .
- ^ «Рустономикон - Альтернативные представления» . Проверено 19 июня 2016 .
- ^ "LayoutKind Enum (System.Runtime.InteropServices)" . docs.microsoft.com . Проверено 1 апреля 2019 .
- ^ Куруса, Левенте (27 декабря 2016 г.). «Любопытный случай невыровненного доступа на ARM» . Средний . Проверено 7 августа 2019 .
- ^ упаковка
- ^ 6.58.8 Прагмы упаковки структуры
- ^ «Работа с упаковочными конструкциями» . Библиотека MSDN . Microsoft. 2007-07-09 . Проверено 11 января 2011 .
дальнейшее чтение
- Брайант, Рэндал Э .; Дэвид, О'Халларон (2003). Компьютерные системы: взгляд программиста (издание 2003 г.). Река Аппер Сэдл, Нью-Джерси, США: Pearson Education . ISBN 0-13-034074-X.
- «1. Введение: Выравнивание сегментов». Утилиты семейства 8086 - Руководство пользователя систем разработки на базе 8080/8085 (PDF) . Редакция E (A620 / 5821 6K DD ed.). Санта-Клара, Калифорния, США: Intel Corporation . Май 1982 [1980, 1978]. С. 1-6, 3-5. Номер заказа: 9800639-04. Архивировано (PDF) из оригинала 29 февраля 2020 года . Проверено 29 февраля 2020 .
[…] Сегмент может иметь один (а в случае атрибута inpage - два) из пяти атрибутов выравнивания: […] Байт, что означает, что сегмент может располагаться по любому адресу. […] Слово, которое означает, что сегмент может быть расположен только по адресу, кратному двум, начиная с адреса 0H. […] Абзац, который означает, что сегмент может быть расположен только по адресу, кратному 16, начиная с адреса 0. […] Страница, что означает, что сегмент может быть расположен только по адресу, кратному 256 , начиная с адреса 0. […] Inpage, что означает, что сегмент может быть расположен в любом из предшествующих атрибутов, плюс должен быть расположен так, чтобы он не пересекал границу страницы […] Коды выравнивания: […] B - байт […] W - слово […] G - абзац […] xR - inpage […] P - page […] A - absolute […] x в коде выравнивания страницы может быть любым другим кодом выравнивания. […] Сегмент может иметь атрибут inpage, что означает, что он должен находиться в пределах 256-байтовой страницы и может иметь атрибут word, что означает, что он должен располагаться в байте с четным номером. […]
Внешние ссылки
- Статья IBM developerWorks о выравнивании данных
- Статья о согласовании и производительности данных
- Статья MSDN о выравнивании данных
- Статья о согласовании и переносимости данных
- Выравнивание и порядок байтов
- Выравнивание стека в 64-битных соглашениях о вызовах - обсуждает выравнивание стека для соглашений о вызовах x86-64.