✖


Jump to content

Выравнивание структуры данных

(Перенаправлено из упакованного массива )

Выравнивание структуры данных – это способ организации данных и доступа к ним в памяти компьютера . Он состоит из трех отдельных, но связанных между собой вопросов: выравнивание данных , заполнение структуры данных и упаковка .

Процессор в современном компьютерном оборудовании наиболее эффективно выполняет чтение и запись в память , когда данные естественно выровнены , что обычно означает, что адрес памяти данных кратен размеру данных. Например, в 32-битной архитектуре данные могут быть выровнены, если данные хранятся в четырех последовательных байтах и ​​первый байт находится на границе 4 байтов.

Выравнивание данных — это выравнивание элементов в соответствии с их естественным выравниванием. Чтобы обеспечить естественное выравнивание, может потребоваться вставить некоторые отступы между элементами структуры или после последнего элемента структуры. Например, на 32-битной машине структура данных, содержащая 16-битное значение, за которым следует 32-битное значение, может иметь 16 бит заполнения между 16-битным значением и 32-битным значением для выравнивания 32-битного значения. значение на 32-битной границе. В качестве альтернативы можно упаковать структуру, опустив заполнение, что может привести к более медленному доступу, но использует на три четверти больше памяти.

Хотя выравнивание структур данных является фундаментальной проблемой для всех современных компьютеров, многие компьютерные языки и их реализации автоматически выполняют выравнивание данных. Фортран , Ада , [1] [2] ПЛ/Я , [3] Паскаль , [4] некоторые реализации C и C++ , D , [5] Ржавчина , [6] С# , [7] и язык ассемблера позволяют, по крайней мере, частично контролировать заполнение структуры данных, что может быть полезно в определенных особых обстоятельствах.

Определения [ править ]

Адрес памяти a называется по n байтам выровненным , если a кратен n (где n — степень двойки). В этом контексте байт — это наименьшая единица доступа к памяти, т. е. каждый адрес памяти определяет отдельный байт. Адрес , выровненный по n -байтам, будет иметь минимум log 2 ( n ) младших нулей, если он выражен в двоичном формате .

Альтернативная формулировка с выравниванием по битам обозначает адрес , выровненный по 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 — оператор по модулю ): 

padding = (align - (offset mod align)) mod align
aligned = offset + padding
        = offset + ((align - (offset mod align)) mod align)

Например, дополнение, добавляемое к смещению 0x59d для 4-байтовой выровненной структуры, равно 3. Тогда структура будет начинаться с 0x5a0, что кратно 4. Однако, когда выравнивание offset уже равно выравниванию align , второй модуль in (align - (offset mod align)) mod align вернет ноль, поэтому исходное значение остается неизменным.

Поскольку выравнивание по определению является степенью двойки, [а] операцию по модулю можно свести к поразрядной логической операции И.

Следующие формулы выдают правильные значения (где & — это побитовое И , а ~ — побитовое НЕ ) — при условии, что смещение беззнаковое или система использует с дополнением до двух арифметику : 

padding = (align - (offset & (align - 1))) & (align - 1)
        = -offset & (align - 1)
aligned = (offset + (align - 1)) & ~(align - 1)
        = (offset + (align - 1)) & -align

Типичное выравнивание структур C на x86 [ править ]

Члены структуры данных хранятся в памяти последовательно, так что в приведенной ниже структуре элемент Data1 всегда будет предшествовать Data2; и Data2 всегда будет предшествовать Data3: 

struct MyData
{
    short Data1;
    short Data2;
    short Data3;
};

Если тип «short» хранится в двух байтах памяти, то каждый член структуры данных, изображенной выше, будет выровнен по 2 байта. Данные1 будут находиться по смещению 0, Данные2 — по смещению 2, а Данные3 — по смещению 4. Размер этой структуры будет составлять 6 байт.

Тип каждого члена структуры обычно имеет выравнивание по умолчанию, что означает, что, если иное не запрошено программистом, он будет выровнен по заранее определенной границе. Следующие типичные выравнивания действительны для компиляторов Microsoft ( Visual C++ ), Borland / CodeGear ( C++Builder ), Digital Mars (DMC) и GNU ( GCC ) при компиляции для 32-разрядной версии x86:

  • Символ (один байт ) будет выровнен по 1 байту.
  • Короткий . (два байта) будет выровнен по 2 байта
  • число Целое (четыре байта) будет выровнено по 4 байтам.
  • Длинный . (четыре байта) будет выровнен по 4 байтам
  • Число с плавающей запятой (четыре байта) будет выровнено по 4 байтам.
  • Двойной опцией (восемь байтов) будет выровнен по 8 байтам в Windows и по 4 байтам в Linux (8 байтов с времени компиляции -malign-double ).
  • Длинный длинный (восемь байт) будет выровнен по 8 байтам в Windows и по 4 байта в Linux (8 байт с опцией времени компиляции -malign-double ).
  • ( Длинный двойной номер десять байтов для C++Builder и DMC, восемь байтов для Visual C++, двенадцать байтов для GCC) будет 8-байтовым, выровненным по C++Builder, 2-байтовым, выровненным по DMC, 8-байтовым, выровненным по Visual. C++ и 4-байтовый формат, согласованный с GCC.
  • Любой указатель (четыре байта) будет выровнен по 4 байтам. (например: char*, int*)

Единственные заметные различия в выравнивании 64-битной системы LP64 по сравнению с 32-битной системой:

  • Длинный . (восемь байтов) будет выровнен по 8 байтам
  • Двойной . (восемь байтов) будет выровнен по 8 байтам
  • Длинный длинный (восемь байтов) будет выровнен по 8 байтам.
  • Длинный двойной номер (восемь байтов для Visual C++, шестнадцать байтов для GCC) будет выровнен по 8 байтам с помощью Visual C++ и по 16 байтам с выравниванием по GCC.
  • Любой указатель (восемь байт) будет выровнен по 8 байтам.

Некоторые типы данных зависят от реализации.

Вот структура с членами разных типов общим размером 8 байт до компиляции: 

struct MixedData
{
    char Data1;
    short Data2;
    int Data3;
    char Data4;
};

После компиляции структура данных будет дополнена байтами заполнения, чтобы обеспечить правильное выравнивание каждого из ее членов: 

struct MixedData  /* After compilation in 32-bit x86 machine */
{
    char Data1; /* 1 byte */
    char Padding1[1]; /* 1 byte for the following 'short' to be aligned on a 2 byte boundary
assuming that the address where structure begins is an even number */
    short Data2; /* 2 bytes */
    int Data3;  /* 4 bytes - largest structure member */
    char Data4; /* 1 byte */
    char Padding2[3]; /* 3 bytes to make total size of the structure 12 bytes */
};

Скомпилированный размер структуры теперь составляет 12 байт. Важно отметить, что последний элемент дополняется необходимым количеством байтов, так что общий размер структуры должен быть кратен наибольшему выравниванию любого члена структуры ( в данном случае alignof(int) , что = 4 в linux-32bit/gcc) [ нужна ссылка ] .

В этом случае к последнему элементу добавляются 3 байта, чтобы дополнить структуру до размера 12 байт ( alignof(int) * 3 ). 

struct FinalPad {
  float x;
  char n[1];
};

В этом примере общий размер структуры sizeof (FinalPad) == 8 , а не 5 (чтобы размер был кратен 4 ( alignof(float) )). 

struct FinalPadShort {
  short s;
  char n[3];
};

В этом примере общий размер структуры sizeof (FinalPadShort) == 6 , а не 5 (и не 8) (чтобы размер был кратен 2 ( alignof(short) == 2 в linux-32bit/gcc)).

Можно изменить выравнивание структур, чтобы уменьшить требуемую им память (или чтобы они соответствовали существующему формату), переупорядочив члены структуры или изменив выравнивание (или «упаковку») членов структуры компилятором. 

struct MixedData  /* after reordering */
{
    char Data1;
    char Data4;   /* reordered */
    short Data2;
    int Data3;
};

Скомпилированный размер структуры теперь соответствует предварительно скомпилированному размеру в 8 байт . Обратите внимание, что Padding1[1] был заменен (и, следовательно, удален) на Данные4 и Padding2[3] больше не нужен, поскольку структура уже выровнена по размеру длинного слова.

Альтернативный метод принудительного исполнения Структура MixedData, выровненная по границе в один байт, приведет к тому, что препроцессор откажется от заранее определенного выравнивания членов структуры, и, таким образом, никакие байты заполнения не будут вставлены.

Хотя не существует стандартного способа определения выравнивания членов структуры (в то время как C и C++ позволяют использовать alignas для этой цели его можно использовать только для указания более строгого выравнивания), некоторые компиляторы используют Директивы #pragma для указания упаковки внутри исходных файлов. Вот пример: 

#pragma pack(push)  /* push current alignment to stack */
#pragma pack(1)     /* set alignment to 1 byte boundary */

struct MyPackedData
{
    char Data1;
    long Data2;
    char Data3;
};

#pragma pack(pop)   /* restore original alignment from stack */

эта структура будет иметь скомпилированный размер 6 байт В 32-битной системе . Вышеуказанные директивы доступны в компиляторах от Microsoft , [9] Борланд , ГНУ , [10] и многие другие.

Другой пример: 

struct MyPackedData
{
    char Data1;
    long Data2;
    char Data3;
} __attribute__((packed));

Упаковка по умолчанию и #pragma пакет [ править ]

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

Выделение памяти в соответствии со строками кэша [ править ]

Было бы полезно выделить память, выровненную по строкам кэша . Если массив разделен для работы более чем одного потока, несовпадение границ подмассива со строками кэша может привести к снижению производительности. Вот пример выделения памяти (двойной массив размером 10), выровненный по кешу размером 64 байта. 

#include <stdlib.h>
double *foo(void) { //create array of size 10
   double *array;
   if (0 == posix_memalign((void**)&array, 64, 10*sizeof(double)))
     return array;

   return 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 (п+1) - 1 всегда имеет один подблок размера 2 н выровнено по 2 н байты.

Вот как динамический распределитель, не знающий выравнивания, может использоваться для предоставления выровненных буферов ценой двукратной потери пространства. 

// Example: get 4096 bytes aligned on a 4096 byte buffer with malloc()

// unaligned pointer to large area
void *up = malloc((1 << 13) - 1);
// well-aligned pointer to 4 KiB
void *ap = aligntonext(up, 12);

где aligntonext( p , r ) работает путем добавления выровненного приращения, а затем очистки r младших битов p . Возможная реализация: 

// Assume `uint32_t p, bits;` for readability
#define alignto(p, bits)      (((p) >> bits) << bits)
#define aligntonext(p, bits)  alignto(((p) + (1 << bits) - 1), bits)

Примечания [ править ]

  1. ^ На современных компьютерах, где целевое выравнивание представляет собой степень двойки. Это может быть не так, например, в системе, использующей 9-битные байты или 60-битные слова.

Ссылки [ править ]

  1. ^ «Представления и прагмы Ады» . Справочное руководство GNAT 7.4.0w. Документация . Проверено 30 августа 2015 г.
  2. ^ «Оговорки о представительстве F.8». Руководство программиста SPARCompiler Ada (PDF) . Проверено 30 августа 2015 г.
  3. ^ Спецификации языка PL/I операционной системы IBM System/360 (PDF) . ИБМ . Июль 1966. стр. 55–56. C28-6571-3.
  4. ^ Никлаус Вирт (июль 1973 г.). «Язык программирования Паскаль (пересмотренный отчет)» (PDF) . п. 12.
  5. ^ «Атрибуты — язык программирования D: выравнивание атрибута» . Проверено 13 апреля 2012 г.
  6. ^ «Рустономикон – Альтернативные представления» . Проверено 19 июня 2016 г.
  7. ^ «Перечисление LayoutKind (System.Runtime.InteropServices)» . docs.microsoft.com . Проверено 1 апреля 2019 г.
  8. ^ Куруса, Левенте (27 декабря 2016 г.). «Любопытный случай несогласованного доступа на ARM» . Середина . Проверено 7 августа 2019 г.
  9. ^ упаковка
  10. ^ 6.58.8 Прагмы структурной упаковки
  11. ^ «Работа с упаковочными конструкциями» . Библиотека MSDN . Майкрософт. 9 июля 2007 г. Проверено 11 января 2011 г.

Дальнейшее чтение [ править ]

  • Брайант, Рэндал Э .; Дэвид, О'Халларон (2003). Компьютерные системы: взгляд программиста (изд. 2003 г.). Река Аппер-Сэддл, Нью-Джерси, США: Pearson Education . ISBN  0-13-034074-Х .
  • «1. Введение: выравнивание сегментов». Утилиты семейства 8086 — Руководство пользователя для систем разработки на базе 8080/8085 (PDF) . Версия E (A620/5821 6K DD изд.). Санта-Клара, Калифорния, США: Корпорация Intel . Май 1982 г. [1980, 1978]. стр. 1–6, 3–5. Номер заказа: 9800639-04. Архивировано (PDF) из оригинала 29 февраля 2020 г. Проверено 29 февраля 2020 г. […] Сегмент может иметь один (а в случае атрибута inpage — два) из пяти атрибутов выравнивания: […] Байт, что означает, что сегмент может находиться по любому адресу. […] Слово, что означает, что сегмент может быть расположен только по адресу, кратному двум, начиная с адреса 0H. […] Абзац, что означает, что сегмент может быть расположен только по адресу, кратному 16, начиная с адреса 0. […] Страница, что означает, что сегмент может быть расположен только по адресу, кратному 256. , начиная с адреса 0. […] Внутристраница, что означает, что сегмент может быть расположен в зависимости от того, какой из предыдущих атрибутов применяется, плюс должен быть расположен так, чтобы он не пересекал границу страницы […] Коды выравнивания: […] B — байт […] W — слово […] G — абзац […] xR — входная страница […] P — страница […] A — абсолютный […] x в коде выравнивания на странице может быть любым другим кодом выравнивания. […] сегмент может иметь атрибут inpage, что означает, что он должен находиться на странице размером 256 байт, и может иметь атрибут word, что означает, что он должен находиться в четном байте. […]

Внешние ссылки [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Data_structure_alignment&oldid=1209741102"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 4f3c2f13982122bafd6ed32bedaa8c7f__1708672620
URL1:https://arc.ask3.ru/arc/aa/4f/7f/4f3c2f13982122bafd6ed32bedaa8c7f.html
Заголовок, (Title) документа по адресу, URL1:
Data structure alignment - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)