Как структура хранится в памяти c
От переводчика Объем памяти и скорость процессора стремительно растет. Старые техники оптимизации применяются все меньше, и, в конце концов, забываются. Однако иногда возникают ситуации, когда опыт прошлых лет становится бесценным.
Упаковка структур в C — старая, почти забытая, но все еще актуальная тема, если вы занимаетесь низкоуровневыми приложениями.
Кому предназначается данная статья
В этой статье я рассмотрю технику, с помощью которой можно уменьшить потребление памяти в программах на C путем реорганизации объявляемых структур. Вам потребуются базовые знания языка C.
Этот способ пригодится при написании программ для встроенных систем с ограниченным количеством памяти или компонентов ядра ОС. Также он полезен, если вы работаете с настолько большими структурами данных, что ваша программа постоянно упирается в лимит памяти. Кроме того, он пригодится в любом приложении, где действительно необходимо уменьшить промахи в кэше.
И, наконец, этот способ — первый шаг к некоторым магическим приемам в С. Вы не можете называть себя опытным C-программистом, если не овладели им. Вы не можете называться мастером C, пока не сможете написать подобную статью самостоятельно и грамотно ее критиковать.
Почему я написал эту статью
В 2013 мне пришлось использовать технику оптимизации, о которой я узнал более 20 лет назад и с тех пор практически не использовал. Мне понадобилось уменьшить потребление памяти программой, которая использовала тысячи, а иногда и десятки тысяч С-структур. Это был cvs-fast-export , и очень часто он рушился из-за недостатка памяти.
Существует способ значительно уменьшить потребление памяти в таких ситуациях путем грамотной реорганизации элементов структур. В моем случае программа стала потреблять на 40% меньше памяти и стала способна переработать бо́льшие репозитории без падений.
Однако в процессе работы я понял, что эта техника в наши дни почти забыта. Поиск в сети подтвердил мою догадку: сегодня в среде С-программистов мало кто пишет об этом, по крайней мере, в тех местах, которые индексируются поисковиком. Есть пара статей в Википедии, но нигде нет подробного разъяснения этой темы.
Этому есть вполне разумное объяснение. На всех курсах по информатике студентов приучают (и вполне обоснованно) избегать микрооптимизаций в пользу поиска лучшего алгоритма. Снижение цены на оборудование сделало охоту за байтами менее актуальной. И сегодня все реже встречается опыт глубокого погружения в различные архитектуры процессоров.
Однако описываемый трюк все еще имеет ценность в некоторых ситуациях и будет иметь ее до тех пор, пока количество памяти на машине конечно. Эта статья убережет С-программистов от изобретения велосипеда и поможет сконцентрироваться на более важных вещах.
Выравнивание
Первое, что необходимо учесть: на современных процессорах ваш компилятор располагает базовые типы в памяти так, чтобы обеспечить наиболее быстрый доступ к ним.
На процессорах x86 и ARM примитивные типы не могут находиться в произвольной ячейке памяти. Каждый тип, кроме char , требует выравнивания. char может начинаться с любого адреса, однако двухбайтовый short должен начинаться только с четного адреса, четырехбайтный int или float — с адреса, кратного 4, восьмибайтные long или double — с адреса, кратного 8. Наличие или отсутствие знака значения не имеет. Указатели — 32-битные (4 байта) или 64-битные (8 байт) — также выравниваются.
Выравнивание ускоряет доступ к памяти за счет генерации кода, в котором на чтение и запись ячейки памяти требуется по одной инструкции. Без выравнивания мы можем столкнуться с ситуацией, когда процессору придется использовать две и более инструкции для доступа к данным, расположенным между адресами, кратными размеру машинного слова. char — особый случай, они занимают ровно одно машинное слово и всегда требуют одинакового количества инструкций для доступа. Поэтому для них нет предпочтительного выравнивания.
Я специально упомянул, что это происходит на современных процессорах, потому что на некоторых старых процессорах небезопасный код (например, приведение некратного адреса в указатель на int и его использование) не просто замедлит работу процессора, он упадет с ошибкой о невалидной инструкции. Так вел себя, например, Sun SPARK. На самом деле такое поведение можно воспроизвести на x86 с правильным флагом ( e18 ) в детерминированной ситуации.
Заполнение
Давайте посмотрим на простой пример расположения переменных в памяти. Допустим, у нас есть следующие строки в C-коде:
Если вы не знакомы с выраниванием, вы можете предположить, что эти три значения располагаются в памяти последовательно. Таким образом, на 32-битной машине за четырьмя байтами указателя сразу расположится 1 байт char , а следом за ним четыре байта целого. На 64-битной машине отличие будет в размере указателя — 8 байт вместо 4.
А вот что происходит на самом деле (на x86, ARM или другом процессоре с выравниваением данных). Память для p начинается с адреса, кратного 4. Выравнивания указателя — самое строгое.
Следом за ним идет c . Но четырехбайтный x требует заполнения (padding) пустыми байтами. Происходит примерно то же самое, как если бы мы добавили еще одну переменную:
Массив символов pad[3] в данном случае указывает на то, что мы заполняем пространство тремя пустыми байтами. Раньше это называли «мусор» («slop»).
Если тип x будет short , который занимает 2 байта, данные будут располагаться так:
С другой стороны, на 64-битной машине эти данные расположатся в памяти следующим образом:
У вас наверняка уже возник вопрос: а что, если переменная с меньшим размером будет объявлена в начале:
Если мы представим расположение структуры в памяти как:
что мы можем сказать о M и N ?
Для начала, N в данном случае будет равно 0. Адрес x гарантированно будет выравниваться по адресу указателя p , выравнивание которого, в свою очередь, более строгое.
Значение M менее предсказуемо. Если компилятор расположит c в последнем байте машинного слова, следующий за ним байт (первый байт p ) будет находиться в начале следующего машинного слова. В этом случае M будет равен 0.
Более вероятно, что c расположится в первом байте машинного слова. В этом случае размер M будет таким, чтобы p был выровнен по началу следующего слова — 3 на 32-битной машине, 7 на 64-битной.
Возможны промежуточные ситуации. M может быть от 0 до 7 (от 0 до 3 на 32-битной машине), потому что char может начинаться на любом байте машинного слова.
Если вы хотите, чтобы эти переменные занимали меньше памяти, вы можете поменять местами x и c .
Обычно, путем реорганизации скалярных величин можно сэкономить несколько байт памяти. Но в случае использования нескалярных величин — особенно структур — мы можем получить более выдающиеся результаты.
Прежде чем мы коснемся структур, следует упомянуть массивы скалярных величин. На платформе с выравниванием данных массивы char / short / int / long или указателей располагаются в памяти последовательно, без заполнения.
В следующем разделе мы увидим, что это не всегда выполняется для массивов структур.
Выравнивание и заполнение структур
В общем случае, экземпляр структуры будет выровнен по самому длинному элементу. Для компилятора это самый простой способ убедиться, что все поля структуры будут также выровнены для быстрого доступа.
Также, в C адрес структуры совпадает с адресом ее первого элемента, без сдвига в начале. Осторожно: в C++ классы, которые выглядят как структуры, могут нарушать это правило. (Это зависит от того, как устроен базовый класс и реализованы виртуальные методы, и может отличаться в различных компиляторах.)
(В случае сомнений вы можете использовать макрос offsetof() из ANSI C, с помощью которого можно рассмотреть расположение элементов струтур в памяти.)
Давайте рассмотрим следующую структуру:
На 64-битной машине любой экземпляр foo1 будет выравниваться по 8 байтам. Расположение в памяти идентично тому, которое мы получили бы, если бы в памяти находились скалярные величины. Однако, если мы перенесем c в начало, все поменяется:
Если бы мы рассматривали отдельные переменные, c мог бы начинаться с произвольного байта и размер заполнения мог бы варьироваться. Но выравнивание структуры foo2 идет по указателю, c также должен быть выровнен по указателю. В итоге мы получаем фиксированное заполнение в 7 байт.
Рассмотрим теперь концевое заполнение структур. Общее правило такое: компилятор заполняет все место до адреса следующей структуры так, чтобы она была выровнена по самому длинному элементу структуры. sizeof() возвращает размер структуры с учетом заполнения.
Например, на 64-битном x86 процессоре или ARM:
Вы можете подумать, что sizeof(struct foo3) вернет 9, однако верным ответом будет 16. Адрес следующей структуры будет (&p)[2] . Таким образом, в массиве из 4 элементов у каждого будет заполнение в 7 пустых байт, поскольку первые элементы каждой структуры должны быть выровнены в данном случае по 8 байтам. Расположение в памяти такое, какое было бы, если бы структура была объявлена следующим образом:
Для сравнения, рассмотрим такой пример:
Поскольку s требует 2-байтового выравнивания, следующий адрес будет отстоять от c на один байт, вся структура foo4 будет заполнена одним пустым байтом в конце и sizeof(struct foo4) вернет 4.
Выравнивание битовых полей и вложенных структур
Битовые поля позволяют объявить переменные, занимающие меньшую, чем char память, вплоть до 1 бита. Например:
Важно помнить, что они реализованы с помощью маски поверх байта или машинного слова и не могут выходить за его пределы.
С точки зрения компилятора битовые поля структуры foo5 выглядят как двухбайтовые значения, из 16 бит которых используются только 12. Место после них заполняется так, чтобы размер структуры был кратен sizeof(short) — размеру наибольшего элемента.
Ограничения битового поля на выход за пределы машинного слова приведет к тому, что на 32-битной машине первые две структуры поместятся в одно или два слова, но третья ( foo8 ) займет три слова, причем у последнего будет занят только первый бит. С другой стороны, структура foo8 поместится в одно 64-битное слово.
Важная деталь: если элементом вашей структуры является структура, она также будет выравниваться по самому длинному скаляру. Например:
char *p во внутренней структуре требует выравнивания по указателю как во внутренней, так и во внешней структуре. Реальное расположение в памяти на 64-битной машине будет примерно такое:
Эта структура дает нам подсказку, где и как мы можем сэкономить память переупаковкой. Из 24 байт 13 заполняющие. Это больше 50% потерянного места!
Реорганизация структур
Теперь, когда мы знаем как и зачем компилятор выравнивает данные в памяти, посмотрим, как мы можем уменьшить количество «мусора». Это и будет называться «искусство упаковки структур».
Первое, что можно заметить — мусор появляется в двух местах: когда данные большего размера расположены после данных меньшего размера и в конце структуры, заполняя место в памяти вплоть до адреса следующей структуры.
Наиболее простой способ избавиться от мусора — расположить элементы структуры по уменьшению размера. Таким образом, указатели будут располагаться в начале, поскольку на 64-битной машине они займут по 8 байт. Потом 4-битовые int ; 2-байтовые short ; затем char .
Рассмотрим, например, односвязный список:
Или, если мы явно укажем заполняющие байты:
Всего 24 байта. Однако, если мы перепишем следующим образом:
то, посмотрев на расположение структуры в памяти, мы увидим, что теперь данные не требуют заполнения, поскольку начало адреса более короткого элемента следует сразу после конца адреса более длинного. Все, что нам теперь требуется — концевое заполнение для выравнивания следующей структуры:
Переупаовкой мы добились сокращения занимаемого места с 24 до 16 байт. Это может показаться незначительным, но что, если у вас односвязный список из 200 тысяч элементов? Эффект растет быстро, особенно на встроенных системах с ограниченым объемом памяти или в критических участках ядра ОС.
Замечу, что реорганизация не всегда позволяет сохранить память. Если мы применим этот прием к нашей структуре foo9 , мы получим следующее:
Явно укажем заполнение:
Размер foo12 — также 24 байта, потому что c выравнивается по внутренней структуре. Для уменьшения занимаемой памяти нам придется изменить дизайн самой структуры данных.
Когда я выложил первый вариант этой статьи, меня спросили почему, если реогранизация для уменьшения «мусора» настолько проста, компилятор не делает ее автоматически. Ответ: C изначально разрабатывался для написания ОС и низкоуровневого кода. Автоматическая реорганизация структур будет мешать программисту организовать структуру с учетом требований оборудования к расположению битов и байтов в памяти.
Выравнивания перечислений и целочисленных типов
Будьте осторожны: несмотря на то, что обычно в перечислениях используется int , в некоторых компиляторах по умолчанию может использоваться short , long или char . Также в компиляторе может быть предусмотрена директива или опция для явного указания размера.
Тип long double также может создавать некоторые проблемы. Некоторые платформы реализуют его с помощью 80 бит, некоторые — 128 бит, некоторые 80-битные реализации заполняют место после данных до 96 или 128 бит.
В обоих случаях лучше использовать sizeof() для проверки занимаемого места.
Читаемость кода и локальность кэша
Несмотря на то, что реорганизация структур — самый простой способ избавиться от мусора в памяти, он не всегда будет оптимальным. Необходимо также учесть читаемость кода и локальность кэша («cache locality»).
Следует помнить, что программы пишутся не только для компьютера, но и для людей. Читаемый код важен даже тогда, когда единственный, кто его будет читать — это вы в будущем.
Бездумная механическая реструктуризация может серьезно снизить читаемость. Лучше оставлять семантически связанные поля структур вместе. В идеале, дизайн программы должен быть взаимосвязан с дизайном структур данных.
При написании программы, которой требуется частый доступ к данным или их части, стоит помнить, что произволительность будет выше, если запрашиваемые данные помещяются в кэш — блок памяти, целиком читаемый процессором при доступе к адресу в нем. На 64-битной машине он обычно занимает 64 байта, на других платформах — обычно 32 байта.
Группировка связанных данных не только улучшает читаемость, но и способствует локализации данных в кэше. Это дополнительная причина реорганизовывать структуры с учетом особенностей доступа к данным в вашей программе.
Если в вашем коде есть конкурентный (concurrent) доступ к данным, появляется третья проблема: «cache line bouncing». Для минимизации трафика в шине следует располагать данные так, чтобы чтение из одного кэша и запись в другой производились с меньшим промежутком.
Да, это противоречит предыдущему замечанию, однако многопоточный код — это всегда сложно. Оптимизация многопоточного кода — тема, заслуживающая отдельной большой статьи. Все, что я могу здесь сказать, такая проблема существует.
Другие способы упаковки
Реорганизация структур лучше всего работает вместе с другими способами уменьшения их размера. Например, если у вас есть несколько булевых флагов, вы можете привести их к битовым полям и упаковать их в структуру, которая в противном случае располагалась бы в памяти с зазорами.
Это освободит вам столько памяти, что эффект от уменьшения количества промахов в кэше перевесит увеличенное время доступа к данным.
В общем случае старайтесь уменьшить размер полей с данными. В cvs-fast-export , например, я воспользовался знанием от том, что CVS и RCS репозитории не существовали до 1982 года. Я заменил 64-битное Unix-время time_t (начинающееся с 1970) на 32-битное время с начальной точкой 1982-01-01T00:00:00 ; это должно покрыть даты до 2118 года. (Если вы применяете подобный трюк, не забудьте проверять границы устанавливаемого значения, чтобы избежать трудноуловимых багов.)
Каждое такое сокращение размера поля не только уменьшает размер структуры, но и уменьшает количество мусора или может создать дополнительные возможности для уменьшения структуры путем реорганизации элементов. Последовательно применяя эти шаги, мы можем добиться значительной экономии памяти.
Самый рискованый метод упаковки — использование union . Если вы уверены, что в вашей структуре данных поля никогда не будут использоваться совместно, можете рассмотреть этот вариант. Но будьте предельно осторожны, тщательно тестируйте свой код, потому что даже маленькая неточность может привести не только к трудноуловимым багам, но и к порче данных.
Инструменты
Я слышал много хороших отзывов о программе pahole , хотя сам ее не использовал. Она работает вместе с компилятором и позволяет генерировать отчет, описывающий реальное расположение данных в памяти.
Доказательства и исключения
Исходный код небольшой программы, которая иллюстрирует вышеописанное можно скачать здесь: packtest.c .
Если вы используете экзотические сочетания компилятора, опций и оборудования, вы, возможно, найдете исключения из правил, который я привожу. Причем, чем старше процессор, тем чаще вы с ними будете сталкиваться.
Следующий уровень владения данной техникой — знать, где и когда ожидать, что правила будут нарушены. В то время, когда я изучал ее (ранние 80-е), людей, которые не освоили эту технику называли «жертвами VAX» («all-the-world’s-a-VAX syndrome»). Помните, что не все компьютеры в мире — PC.
Полезные ссылки
Здесь я привожу ссылки на статьи и эссе, которые я считаю хорошим дополнением к данному материалу.
Прочитал, что поля структуры хранятся в памяти последовательно(в порядке объявления) (+- платформ.зависимое выравнивание). Вопрос такой: как влияют методы в структурах на их расположение в памяти? Предположим, есть структура вида:
Как экземпляр этой структуры (а именно его поля) будут расположены в памяти? И ещё, применимы ли все знания по структурам(и их расположению в памяти) к классам? И есть ли какая-то разница (с точки зрения памяти) между обычными методами и перегрузками / конструкторами / деструкторами?
Во-первых, как правильно заметили в комментариях, в С++ структур нет. Ключевое слово struct создает классы, в которых поля и родители по умолчанию публичные. Какой-то другой разницы между struct и class , с точки зрения стандарта, насколько я знаю, нет.
Поля классов хранятся в порядке объявления только если спецификатор доступа ( public/private/protected ) у них одинаковый.
Если спецификатор доступа одинаковый, то из двух полей в памяти идет раньше то, которое в определении класса написано выше. Если спецификатор доступа у двух полей разный, то компилятор вправе расположить их относительно друг друга как угодно.
В частности, соответствующий стандарту компилятор может располагать все поля в памяти по порядку, игнорируя спецификаторы доступа. А может сложить в кучку отдельно private , protected и public . Могут быть какие-то другие варианты.
Non-static data members of a (non-union) class with the same access control are allocated so that later members have higher addresses within a class object. The order of allocation of non-static data members with different access control is unspecified. Implementation alignment requirements might cause two adjacent members not to be allocated immediately after each other; so might requirements for space for managing virtual functions and virtual base classes.
У каждого экземпляра одного класса, очевидно, свой набор из всех нужных полей.
Но вот методы у всех экземпляров одного класса общие - они не занимают место в экземплярах класса и не влияют на его размер в байтах.*
(Не считая указателя на vtable для виртуальных функций.)
Обычно методы реализуются так же, как и обычные функции, но с добавленным невидимым параметром this . Так что нет смысла в каждом экземпляре хранить какую-то информацию о методах, не считая vtable pointer.
*Хотя разницы между class и struct быть не должно, и хотя не виртуальные методы на размер класса влиять не должны, мне у нас на SO недавно попался пример, в котором GCC с определенными настройками убирал выравнивание из struct как только к нему добавляли один любой метод, либо когда struct меняли на class . Видимо для совместимости с каким-то С-шным компилятором. Если кто-то найдет больше информации по этой теме, буду благодарен.
Структура — это объединение нескольких объектов, возможно, различного типа под одним именем, которое является типом структуры. В качестве объектов могут выступать переменные, массивы, указатели и другие структуры.
Структуры позволяют трактовать группу связанных между собой объектов не как множество отдельных элементов, а как единое целое. Структура представляет собой сложный тип данных, составленный из простых типов.
Общая форма объявления структуры:
тип ИмяЭлемента1;
тип ИмяЭлемента2;
. . .
тип ИмяЭлементаn;
>;
После закрывающей фигурной скобки > в объявлении структуры обязательно ставится точка с запятой.
Пример объявления структуры
int day; // 4 байта
char *month; // 4 байта
int year; // 4 байта
>;
Поля структуры располагаются в памяти в том порядке, в котором они объявлены:
В указанном примере структура date занимает в памяти 12 байт. Кроме того, указатель *month при инициализации будет началом текстовой строки с названием месяца, размещенной в памяти.
При объявлении структур, их разрешается вкладывать одну в другую.
struct personechar lastname[20]; // фамилия
char firstname[20]; // имя
struct date bd; // дата рождения
>;
Инициализация полей структуры
Инициализация полей структуры может осуществляться двумя способами:
- присвоение значений элементам структуры в процессе объявления переменной, относящейся к типу структуры;
- присвоение начальных значений элементам структуры с использованием функций ввода-вывода (например, printf() и scanf() ).
В первом способе инициализация осуществляется по следующей форме:
Имя элемента структуры является составным. Для обращения к элементу структуры нужно указать имя структуры и имя самого элемента. Они разделяются точкой:
Второй способ инициализации объектов языка Си с использованием функций ввода-вывода.
12
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Имя структурной переменной может быть указано при объявлении структуры. В этом случае оно размещается после закрывающей фигурной скобки > . Область видимости такой структурной переменной будет определяться местом описания структуры.
double real;
double imag;
> number; // имя структурной переменной
Поля приведенной структурной переменной: number.real, number.imag .
Объединения
Объединениями называют сложный тип данных, позволяющий размещать в одном и том же месте оперативной памяти данные различных типов.
Размер оперативной памяти, требуемый для хранения объединений, определяется размером памяти, необходимым для размещения данных того типа, который требует максимального количества байт.
Когда используется элемент меньшей длины, чем наиболее длинный элемент объединения, то этот элемент использует только часть отведенной памяти. Все элементы объединения хранятся в одной и той же области памяти, начиная с одного адреса.
Общая форма объявления объединения
тип ИмяОбъекта1;
тип ИмяОбъекта2;
. . .
тип ИмяОбъектаn;
>;
Объединения применяются для следующих целей:
- для инициализации объекта, если в каждый момент времени только один из многих объектов является активным;
- для интерпретации представления одного типа данных в виде другого типа.
Например, удобно использовать объединения, когда необходимо вещественное число типа float представить в виде совокупности байтов
Пример Поменять местами два младших байта во введенном числе
Битовые поля
Используя структуры, можно упаковать целочисленные компоненты еще более плотно, чем это было сделано с использованием массива.
Набор разрядов целого числа можно разбить на битовые поля, каждое из которых выделяется для определенной переменной. При работе с битовыми полями количество битов, выделяемое для хранения каждого поля отделяется от имени двоеточием
При работе с битовыми полями нужно внимательно следить за тем, чтобы значение переменной не потребовало памяти больше, чем под неё выделено.
Пример Разработать программу, осуществляющую упаковку даты в формат
Массивы структур
Работа с массивами структур аналогична работе со статическими массивами других типов данных.
Пример Библиотека из 3 книг
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Указатели на структуры
Доступ к элементам структуры или объединения можно осуществить с помощью указателей. Для этого необходимо инициализировать указатель адресом структуры или объединения.
Для организации работы с массивом можно использовать указатель. При этом обращение к полям структуры через указатель будет выглядеть как:
указатель — указатель на структуру или объединение;
поле — поле структуры или объединения;
Динамическое выделение памяти для структур
Динамически выделять память под массив структур необходимо в том случае, если заранее неизвестен размер массива. Для определения размера структуры в байтах используется операция sizeof (ИмяСтруктуры) .
Пример Библиотека из 3 книг
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Результат выполнения аналогичен предыдущему решению. Здравствуйте! Спасибо Вам за статью. Мне непонятен доступ к элементам структуры когда одним из элементов является массив. Например есть структура struct book <
char massiv[20];
int b [5];
char c;
>;
struct book lolik;
Мы можем проинициализировать поля структуры только при ее объявлении. Дальше уже идут операции присваивания. Причем инициализация должна быть выполнена для всех полей одновременно. Нельзя проинициализировать часть полей (причем из середины). Можно сделать так: Здравствуйте. Подскажите, как при задании массива структур правильно инициализировать поля каждой структуры? Массив статический. Если можно, хотелось бы увидеть какие-нибудь примеры. Добрый вечер! Подскажите, пожалуйста, как вывести несколько департаментов, если количество сотрудников одинаковое и не вывести ничего, если не удовлетворяет заданию? Заранее спасибо! Задание: найти самый маленький отдел, созданный не позднее заданной даты Вроде все работает, но не понимаю, как написать условие (возможно, if, else), чтобы при одинаковом кол-ве сотрудников вывел оба департамента и чтобы не вывел ничего, если не удовлетворяет условию, связанным с годом? P.S. Структура задана в заголовочном файле ЗАГОЛОВОЧНЫЙ ФАЙЛ (department.h):
struct int amount; // количество сотрудников
char lastname[50]; // фамилия начальника
> inc;
struct int year;
int month;
> date;
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
void display( struct Office* a, int i) //вывод одного отдела с помощью цикла
printf( "Название: %s\nКоличество сотрудников: %d\nФамилия начальника: %s\nДата создания: %d.%d\n\n" ,
a[i].title, a[i].inc.amount, a[i].inc.lastname, a[i].date.year, a[i].date.month);
>
void create( struct Office* a, int * pn) //функция ввода с клавиутары данных и вывод их на консоль
printf( "Введите количество отделов (< 20): " );
scanf_s( "%d%*c" , pn); //%*c применяется для удаления enter и считывания fgets дальше (чтобы они работали и воспринимались программой)
printf( "\n" );
for ( int i = 0; i < *pn; i++)
printf( "Название: " );
fgets(a[i].title, 50, stdin);
a[i].title[strlen(a[i].title) - 1] = 0;
printf( "Количество сотрудников: " );
scanf_s( "%d%*c" , &a[i].inc.amount);
printf( "Фамилия начальника: " );
fgets(a[i].inc.lastname, 50, stdin);
a[i].inc.lastname[strlen(a[i].inc.lastname) - 1] = 0;
printf( "Дата создания: " );
scanf_s( "%d%d%*c" , &a[i].date.year, &a[i].date.month);
puts( "" );
>
>
int small( struct Office* a, int n, int year, int month)
<
int i = 0, index = 0, min = 0;
while ((a[i].date.year > year) || (a[i].date.month > month) && (a[i].date.year == year)) //сравниваем дату создания с датой, введенной нами
i++;
>
index = i;
min = a[i].inc.amount;
for (i; i < n; i++) //находим самый маленький отдел и сравниваем дату с другими датами создания отдела
if ((a[i].inc.amount < min) && (a[i].date.year <= year) || (a[i].inc.amount < min) && (a[i].date.month <= month) && (a[i].date.year == year))
min = a[i].inc.amount;
index = i;
>
>
return index;
>
int main()
setlocale(LC_ALL, "Rus" ); //включение локализации
setlocale(LC_NUMERIC, "Eng" ); //использование "." в дробных значениях
int n = 0, year = 0, month = 0;
n = sizeof (A) / sizeof (A[0]); //размер (в байтах) всего массива, то есть сумма всех элементов/ размер (в байтах) одной структуры (50)
for ( int i = 0; i < n; i++)
display(A, i);
printf( "Введите дату создания: " );
scanf_s( "%d%d%*c" , &year, &month);
printf( "\n" );
n = small(A, n, year, month);
display(A, n);
return 0;
>
В данной статье сначала будет объяснено понятие гранулярности доступа к памяти, чтобы мы могли выработать базовое понимание того, как процессор обращается к памяти. Затем мы более подробно рассмотрим концепцию выравнивания данных и исследуем распределение памяти для нескольких примеров структур.
В предыдущей статье о структурах в языке C для встраиваемых систем мы увидели, что перестановка членов в структуре может изменить объем памяти, необходимый для хранения структуры. Мы также видели, что компилятор обладает некоторыми ограничениями при выделении памяти для членов структуры. Эти ограничения, называемые требованиями к выравниванию данных, позволяют процессору более эффективно обращаться к переменным за счет некоторого потраченного впустую пространства памяти (известного как «заполнение»), которое может появиться в распределении памяти.
Стоит отметить, что система памяти компьютера может быть гораздо более сложной, чем представленная здесь. Цель данной статьи – обсудить некоторые основные концепции, которые могут быть полезны при программировании встраиваемых систем.
Гранулярность доступа к памяти
Обычно мы представляем память как совокупность однобайтовых ячеек, как показано на рисунке 1. Каждая из этих ячеек имеет уникальный адрес, который позволяет нам получить доступ к данным по этому адресу.
Рисунок 1 – Память как совокупность однобайтовых ячеек
Однако процессор обычно обращается к памяти кусками размером более одного байта. Например, процессор может получать доступ к памяти в виде четырехбайтовых блоков. В этом случае мы можем представить 12 последовательных байтов на рисунке 1, как показано ниже на рисунке 2.
Рисунок 2 – Распределение памяти на четырехбайтовые области
Вы можете задаться вопросом, в чем разница между этими двумя способами обработки памяти. На рисунке 1 процессор читает и записывает в память за раз по одному байту. Обратите внимание, что перед чтением ячейки памяти или записью в нее нам необходимо получить доступ к этой ячейке, и каждая процедура доступа к памяти занимает некоторое время. Предположим, что мы хотим прочитать первые восемь байтов на рисунке 1. Для каждого байта процессор должен получить доступ к памяти и прочитать ее. Следовательно, чтобы прочитать содержимое первых восьми байтов, процессору придется обращаться к памяти восемь раз.
На рисунке 2 процессор читает и записывает в память за раз четыре байта. Следовательно, чтобы прочитать первые четыре байта, процессор обращается к адресу 0 в памяти и считывает четыре последовательных ячейки хранения (адреса с 0 до 3). Точно так же, чтобы прочитать следующий четырехбайтовый фрагмент процессору необходимо получить доступ к памяти еще один раз. Он идет по адресу 4 и считывает ячейки хранения по адресам с 4 по 7 одновременно. Для блоков размером в байт требуется восемь обращений к памяти, чтобы прочитать восемь последовательных байтов в памяти. Однако для распределения на рисунке 2 требуется только две процедуры доступа к памяти. Как упоминалось выше, каждая процедура доступа к памяти занимает некоторое время. Поскольку конфигурация памяти, показанная на рисунке 2, уменьшает количество обращений, она может привести к большей эффективности обработки.
Размер данных, который процессор использует при доступе к памяти, называется гранулярностью доступа к памяти. На рисунке 2 показана система с четырехбайтовой гранулярностью доступа к памяти.
Границы доступа к памяти
Существует еще один важный метод, который разработчики аппаратного обеспечения часто используют, чтобы сделать систему обработки более эффективной: они ограничивают процессор так, чтобы он мог обращаться к памяти только на определенных границах. Например, процессор может иметь доступ к памяти, представленной на рисунке 2, только на четырехбайтовых границах, как показано красными стрелками на рисунке 3.
Рисунок 3 – Границы доступа к памяти
Будет ли это ограничение границами делать систему значительно более эффективной? Давайте рассмотрим подробнее. Предположим, что нам нужно прочитать содержимое областей памяти с адресами 3 и 4 (на рисунке 3 обозначены зеленым и синим прямоугольниками). Если процессор бы мог прочитать четырехбайтовый фрагмент, начиная с произвольного адреса, мы могли бы получить доступ к адресу 3 и прочитать две нужных ячейки памяти за один раз доступа к памяти. Однако, как упоминалось выше, процессор не может напрямую получить доступ к произвольному адресу; он обращается к памяти только на определенных границах. Итак, как процессор будет считывать содержимое ячеек по адресам 3 и 4, если он может получить доступ только к четырехбайтовым границам?
Из-за ограничений границ доступа к памяти процессор должен получить доступ к ячейке памяти с адресом 0 и прочитать четыре последовательных байта (адреса с 0 по 3). Затем он должен использовать операции сдвига для отделения содержимого адреса 3 от других трех байтов (адреса с 0 по 2). Аналогично процессор может получить доступ к адресу 4 и прочитать другой четырехбайтовый фрагмент по адресам с 4 по 7. Наконец, операции сдвига могут снова использоваться для отделения нужного байта (синего прямоугольника) от других трех байтов.
Если бы не было ограничения границ доступа к памяти, мы могли бы прочитать ячейки по адресам 3 и 4 за одну процедуру доступа к памяти. Однако ограничение границ заставляет процессор обращаться к памяти дважды. Так зачем нам ограничивать доступ к памяти определенными границами, если это усложняет манипулирование данными? Ограничение доступа к памяти границами существует потому, что определенные предположения об адресе могут упростить конструкцию оборудования. Например, предположим, что для адресации всех байтов в блоке памяти требуется 32 бита. Если мы ограничим адрес четырехбайтовыми границами, то два младших бит 32-битного адреса всегда будут равны нулю (поскольку адрес всегда будет делиться на четыре без остатка). Следовательно, мы сможем использовать 30 бит для адресации памяти с 2 32 байтами
Выравнивание данных
Теперь, когда мы знаем, как базовый процессор обращается к памяти, мы можем обсудить требования к выравниванию данных. Как правило, любой K -байтовый тип данных языка C должен иметь адрес, кратный K . Например, четырехбайтовый тип данных может храниться только по адресам 0, 4, 8, . ; его нельзя хранить по адресам 1, 2, 3, 5, . . Такие ограничения упрощают конструкцию аппаратного интерфейса между процессором и системой памяти.
В качестве примера рассмотрим процессор с четырехбайтовой гранулярностью доступа к памяти, который может обращаться к памяти только на четырехбайтовых границах. Предположим, что четырехбайтовая переменная хранится по адресу 1, как показано на рисунке 4 (четыре байта соответствуют четырем разным цветам). В этом случае нам понадобятся два обращения к памяти и некоторая дополнительная работа для чтения невыровненных четырехбайтовых данных (под «невыровненными» я подразумеваю, что они разбиты на два четырехбайтовых блока). Процедура показана на рисунке.
Рисунок 4 – Чтение невыровненных данных
Однако, если мы храним четырехбайтовую переменную по любому адресу, кратному 4, нам потребуется только одна процедура доступа к памяти, чтобы изменить данные или прочитать их.
Вот почему хранение K -байтовых типов данных по адресу, кратному K , может сделать систему более эффективной. Следовательно, переменные " char " языка C (которые требуют только одного байта) могут храниться по любому байтовому адресу, но двухбайтовая переменная должна храниться по четным адресам. Четырехбайтовые типы должны начинаться с адресов, которые делятся на 4 без остатка, а восьмибайтовые типы данных должны храниться по адресам, которые делятся без остатка на 8. Например, предположим, что на конкретной машине переменным " short " требуется два байта, типы " int " и " float " занимают четыре байта, а " long ", " double " и указатели занимают восемь байтов. Каждый из этих типов данных обычно должен иметь адрес, кратный K , где K задается в следующей таблице.
| Тип данных | K |
|---|---|
| char | 1 |
| short | 2 |
| int , float | 4 |
| long , double , char* | 8 |
Обратите внимание, что размер разных типов данных может варьироваться в зависимости от компилятора и архитектуры машины. Оператор sizeof() будет лучшим способом для определения фактического размера типа данных.
Распределение памяти для структуры
Теперь давайте рассмотрим распределение памяти для структуры. Рассмотрим компилирование следующей структуры для 32-разрядной машины:
Мы знаем, что для хранения членов структуры будут выделены четыре области памяти, и порядок расположения областей памяти будет соответствовать порядку объявления членов. Первый член является однобайтовой переменной и может храниться по любому адресу. Следовательно, этой переменной будет выделена первая доступная область хранения. Предположим, что, как показано на рисунке 5, компилятор выделит этой переменной адрес 0. Следующий член является четырехбайтовым типом данных и может храниться по адресам, кратным 4. Первым доступным местом хранения является адрес 4. Однако для этого необходимо оставить адреса 1, 2 и 3 неиспользованными. Как видите, требование выравнивания данных приводит к некоторому потерянному пространству (или заполнению) в распределении памяти.
Следующий член – это e , который является однобайтовой переменной. Этой переменной может быть назначено первое доступное место хранения (адрес 8 на рисунке 5). Далее мы доходим до f , который является двухбайтовой переменной. Он может храниться по адресу, который делится на 2. Первое доступное пространство – это адрес 10. Как вы можете видеть, для удовлетворения требований выравнивания данных появится дополнительное заполнение.
Рисунок 5 – Выделение памяти для заданной структуры
Мы ожидали, что структура будет занимать 8 байтов, но на самом деле она потребовала 12 байтов. Интересно, что если нам известно о требованиях к выравниванию данных, мы сможем изменить порядок членов в структуре и повысить эффективность использования памяти. Например, давайте перепишем приведенную выше структуру, как показано ниже, где члены упорядочены от самого большого до самого маленького.
На 32-разрядной машине распределение памяти для объявленной выше структуры, вероятно, будет выглядеть как схема, изображенная на рисунке 6.
Рисунок 6 – Выделение памяти для заданной модифицированной структуры
В то время как первая структура требовала 12 байтов, новая модифицированная структура требует только 8 байтов. Это значительное улучшение, особенно в контексте встроенных процессоров с ограниченным объемом памяти.
Также обратите внимание, что после последнего члена структуры могут быть несколько байтов заполнения. Общий размер структуры должен делиться на размер ее наибольшего члена. Рассмотрим следующую ситуацию:
В этом случае распределение памяти будет таким, как показано на рисунке 7. Как вы можете видеть, в конце выделенной памяти добавляются три байта заполнения, чтобы увеличить размер структуры до 8 байт. Это сделает размер структуры кратным размеру наибольшего члена структуры (член c , который является четырехбайтовой переменной).
Рисунок 7 – Выделение памяти для заданной структуры. Добавление заполнения в конце выделенной памяти
Читайте также: