stringtranslate.com

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

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

Процессор в современном компьютерном оборудовании наиболее эффективно выполняет чтение и запись в память, когда данные естественным образом выровнены , что обычно означает, что адрес памяти данных кратен размеру данных. Например, в 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/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 — оператор по модулю ):

дополнение = (выравнивание - (смещение mod выравнивание)) mod alignвыровнено = смещение + заполнение = смещение + ((выравнивание - (смещение mod выравнивание)) mod align)

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

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

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

отступ = (выравнивание - (смещение & (выравнивание - 1))) & (выравнивание - 1) = -смещение & (выравнивание - 1)выровнено = (смещение + (выравнивание - 1)) & ~(выравнивание - 1) = (смещение + (выравнивание - 1)) & -выравнивание

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

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

структура MyData { короткие данные1 ; короткие Данные2 ; короткие Данные3 ; };

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

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

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

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

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

структура MixedData { char Data1 ; короткие Данные2 ; интервал данных3 ; символ Данные4 ; };

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

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 ; символ 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 ; символ Данные4 ; /* переупорядочение */ short Data2 ; интервал данных3 ; };

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

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

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

#pragma package(push) /* помещаем текущее выравнивание в стек */ #pragma package(1) /* устанавливаем выравнивание на границу 1 байта */структура MyPackedData { символ Data1 ; длинные Данные2 ; символ Данные3 ; };       #pragma package(pop) /* восстанавливаем исходное выравнивание из стека */

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

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

структура MyPackedData { символ Data1 ; длинные Данные2 ; символ Данные3 ; } __attribute__ (( упаковано ));

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

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

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

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

#include <stdlib.h> double * foo ( void ) { //создаем массив размером 10 double * array ; if ( 0 == posix_memalign (( void ** ) & array , 64 , 10 * sizeof ( double ))) return array ;               вернуть НУЛЬ ; }

Аппаратное значение требований к выравниванию

Проблемы с выравниванием могут затронуть области, намного большие, чем структура 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), биты)

Примечания

  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 г.

дальнейшее чтение

Внешние ссылки