Искусство упаковки структур в C


Оглавление (нажмите, чтобы открыть):

Упаковать или не упаковать структуру, содержащую только массив

Эксперимент:
Давайте объявим контейнер дайджеста SHA-512 в c / c ++ как (используя GCC):

Давайте не будем спорить о выборе массива uint32_t вместо массива char. Будь как будет.

И тогда мы можем прочитать в дайджест из рабочего буфера, как показано ниже:

Точно так же мы можем записать дайджест в рабочий буфер:

Мои вопросы:

A. Является ли упакованный атрибут необходимым и достаточным условием, чтобы sizeof (Digest) всегда возвращал правильный размер (= 512 бит или 64 байта)?

B. Является ли digest-> bits [i] безопасной операцией на всех архитектурах, пока мы сохраняем упакованный атрибут?

C. Можем ли мы упростить представление, оставив контейнер непрозрачным?

D. Есть ли штраф за время выполнения, если мы сохраняем представительство?

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

Решение

A. Является ли упакованный атрибут необходимым и достаточным условием для
sizeof (дайджест), чтобы всегда возвращать правильный размер (= 512 бит или 64
байт)?

B. Является ли digest-> bits [i] безопасной операцией на всех архитектурах, пока мы
сохранить упакованный атрибут?

Я думаю, что вы не понимаете, __attribute__((packed)) , Ниже то, что на самом деле.

Когда упакованный используется в объявлении структуры, он сжимает его
такие поля, что sizeof (структура) == sizeof (first_member) +
… + SizeOf (last_member).

РЕДАКТИРОВАТЬ:

Конечно это безопасно. Упаковка определяет расположение в памяти, но не беспокойтесь, потому что доступ к определенному типу данных обрабатывается компилятором, даже если данные выровнены неправильно.

C. Можем ли мы упростить представление, сохраняя контейнер
непрозрачным?

Да, вы можете просто определить простой буфер uint32_t bits[LENGTH]; и это будет работать таким же образом для вас.

D. Есть ли штраф за время выполнения, если мы сохраняем представительство?

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

Пожалуйста, проверьте ниже эту очень простую программу, показывающую влияние упаковки на размер структуры.

Объяснение:

Компилятор делает это для того, чтобы генерировать код, который обращается к типам данных быстрее, чем код без оптимизации заполнения и выравнивания памяти.

Вы можете запустить мой код по этой ссылке демонстрационная программа

Другие решения

Структура имеет только один член, поэтому «упаковывать» это не имеет смысла. Между членами нет отступов, потому что нет другого члена.

Возможно, вы хотели упаковать массив, но это не нужно, так как uint32_t это тип точного размера. (Не обязательно существовать, но для архитектур, в которых отсутствует uint32_t , вопрос не имеет значения.)

Поэтому, если у вас была какая-то эксцентричная 48-битная архитектура, в которой каждое «слово» состоит из четырех адресуемых 12-битных «байтов», у вас может быть компилятор, в котором int длиной три байта с выравниванием в четыре байта, но у вас не будет uint32_t , поскольку int тип равен 36 битам, а не 32 битам, и (C99 §7.20.1.1, который включен посредством ссылки в C ++ 11):

Имя определения типа intN_t обозначает целочисленный тип со знаком шириной N, нет битов заполнения, и два дополнительных представления.

Сложные типы данных в Си

Структура — это объединение нескольких объектов, возможно, различного типа под одним именем, которое является типом структуры. В качестве объектов могут выступать переменные, массивы, указатели и другие структуры.

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

Общая форма объявления структуры:

После закрывающей фигурной скобки > в объявлении структуры обязательно ставится точка с запятой.

Пример объявления структуры

В указанном примере структура date занимает в памяти 12 байт. Кроме того, указатель *month при инициализации будет началом текстовой строки с названием месяца, размещенной в памяти.

При объявлении структур, их разрешается вкладывать одну в другую.

Инициализация полей структуры

Инициализация полей структуры может осуществляться двумя способами:

  • присвоение значений элементам структуры в процессе объявления переменной, относящейся к типу структуры;
  • присвоение начальных значений элементам структуры с использованием функций ввода-вывода (например, printf() и scanf() ).

В первом способе инициализация осуществляется по следующей форме:

Имя элемента структуры является составным. Для обращения к элементу структуры нужно указать имя структуры и имя самого элемента. Они разделяются точкой:

Второй способ инициализации объектов языка Си с использованием функций ввода-вывода.

Имя структурной переменной может быть указано при объявлении структуры. В этом случае оно размещается после закрывающей фигурной скобки > . Область видимости такой структурной переменной будет определяться местом описания структуры.

Поля приведенной структурной переменной: number.real, number.imag .

Объединения

Объединениями называют сложный тип данных, позволяющий размещать в одном и том же месте оперативной памяти данные различных типов.

Размер оперативной памяти, требуемый для хранения объединений, определяется размером памяти, необходимым для размещения данных того типа, который требует максимального количества байт.

Когда используется элемент меньшей длины, чем наиболее длинный элемент объединения, то этот элемент использует только часть отведенной памяти. Все элементы объединения хранятся в одной и той же области памяти, начиная с одного адреса.

Общая форма объявления объединения

Объединения применяются для следующих целей:


  • для инициализации объекта, если в каждый момент времени только один из многих объектов является активным;
  • для интерпретации представления одного типа данных в виде другого типа.

Например, удобно использовать объединения, когда необходимо вещественное число типа float представить в виде совокупности байтов

Пример Поменять местами два младших байта во введенном числе

Битовые поля

Используя структуры, можно упаковать целочисленные компоненты еще более плотно, чем это было сделано с использованием массива.

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


При работе с битовыми полями нужно внимательно следить за тем, чтобы значение переменной не потребовало памяти больше, чем под неё выделено.

Пример Разработать программу, осуществляющую упаковку даты в формат

Массивы структур

Работа с массивами структур аналогична работе со статическими массивами других типов данных.

Пример Библиотека из 3 книг

Указатели на структуры

Доступ к элементам структуры или объединения можно осуществить с помощью указателей. Для этого необходимо инициализировать указатель адресом структуры или объединения.

Для организации работы с массивом можно использовать указатель. При этом обращение к полям структуры через указатель будет выглядеть как:

Структуры в языке C#

Вы уже знаете, что классы относятся к ссылочным типам данных. Это означает, что объекты конкретного класса доступны по ссылке. Ссылка -это 32/64-х битный адрес, указывающий на расположение членов-данных в управляемой куче, в отличие от значений простых типов, доступных непосредственно.

Но иногда прямой доступ к объектам (например, как к значениям простых типов) полезно иметь ради повышения эффективности программы. Ведь каждый доступ к объектам по ссылке связан с дополнительными издержками на расход вычислительных ресурсов и оперативной памяти.

Для разрешения подобных затруднений в C# предусмотрена структура, которая подобна классу, но относится к типу значений, а не к ссылочному типу данных.

Структуры отличаются от классов тем, как они сохраняются в памяти и как к ним осуществляется доступ (для начала – краткая формула «классы — это ссылочные типы, размещаемые в куче, структуры — типы значений, размещаемые в стеке»). Эта формула не совсем точная, пояснения см. позже. Структуры отличаются от классов некоторыми свойствами (например, структуры не поддерживают наследование).

Из соображений производительности следует использовать структуры для небольших типов данных. Однако в отношении синтаксиса структуры очень похожи на классы.

Первое и очевидное отличие состоит в том, что при их объявлении используется ключевое слово struct вместо class. Ниже приведена общая форма объявления структуры:

struct имя
<
объявления членов
>
где имя обозначает конкретное имя структуры.

Как у класса, так и у каждой структуры имеются свои члены: методы, поля, индексаторы, свойства, операторные методы и события. Так в структуре Double (библиотека System) определено 6 констант, 6 операторов отношения, 19 методов, 5 интерфейсов (проверьте, используя интеллектуальную подсказку). Не многовато ли для вещественного числа, как вы думаете?

В структурах допускается также определять конструкторы. В то же время для структуры нельзя определить конструктор, используемый по умолчанию (без параметров), который определяется для всех структур автоматически и не подлежит изменению. Такой конструктор инициализирует поля структуры значениями, задаваемыми по умолчанию (false для типа bool, 0 – для чисел). А поскольку структуры в отличие от классов не поддерживают наследование, то их члены нельзя указывать как abstract, virtual или protected.

Экземпляр (можно говорить и «объект») структуры может быть создан с помощью оператора new таким же образом, как и объект класса, но в этом нет особой необходимости. Когда используется оператор new, то вызывается конструктор, используемый по умолчанию. А когда этот оператор не используется, объект по-прежнему создается, хотя и не инициализируется. В этом случае инициализацию любых членов структуры придется выполнить вручную. Рассмотрим пример.

Результат выполнения программы:

Исследуем программу. Закомментируем вторую строку в методе Main():
// stud1.name = «Петр»;
При запуске программы получим сообщение об ошибке:
Использование локальной переменной «stud1», которой не присвоено значение.
Хотя структура stud1 объявлена, но полю name никакого значения не присвоено, что приводит к ошибке. Такая же ошибка возникнет, если мы станем использовать переменную целого типа, которая объявлена, но не инициализирована.
Такой вот жесткий контроль компилятора за нашими действиями!

Проверим, как работает конструктор без параметров. Первую строку метода Main() заменим на
student stud1 = new student();
Вторую и третью строку – закомментируем. Тогда при выводе результата в 1 строке получим:
студент 1: Имя: , возраст: 0
Следовательно, полю name была присвоена пустая строка, а полю возраст – число 0.

Проверим, как работает защита данных. В второй строке описания структуры student удалим модификатор поля public, т.е. получим byte age;
При запуске программы получим два сообщения об ошибке:
«ConsoleApplication1.student.age» недоступен из-за его уровня защиты
в операторах stud1.age = 18; и stud2.age = 19;

Это означает, что так как по умолчанию поле age является полем private, то оно не может быть изменено в другом классе с помощью оператора присваивания, однако оно доступно методам класса student, объявленным как public. С учетом этих результатов, программа может быть записана так:

Здесь поля объектов stud1 и stud2 структуры student являются private-полями, а метод и конструктор объявлены как public.

А теперь ВНИМАНИЕ! Ключевая идея — Создание сложных конструкций данных, используя один тип данных, как элемент другой конструкции. В статье про типы данных мы выяснили, что все встроенные типы, относящиеся к типам значений (их еще называют простыми типами данных), являются структурами, хотя фактически каждая из них имеет одно поле, содержащее значение числа, символа или булевой переменной.

Структура позволяет объединять несколько различных по типу элементов под одним именем. Более того можно использовать неоднократное вложение одних типов данных в другие, используя структуры.

Для понимания этой идеи рассмотрим пример. Прототипом для него являются структуры из библиотеки System. Drawing: Point, Size и Rectangle.

Известно, что точка на экране задается парой целых чисел (X,Y) в пикселях. Объединим эти два числа в структуру точка. Установим максимальную защиту (private – по умолчанию) для этих полей. Добавим конструктор с параметрами точка(x,y) для инициализации объектов структуры точка, а также метод Get() для извлечения полей в строковом формате.

Размер прямоугольника на экране также задается парой чисел: шириной и высотой. Соответственно объявим структуру размер с полями (W,H). Добавим аналогичный конструктор с параметрами размер(w,h) для инициализации объектов структуры размер, а также метод Get() для извлечения полей в строковом формате.

Прямоугольник на экране определяется координатами верхнего левого угла (точка) и размером изображения (размер). Поэтому третью структуру построим на основе первых двух, назовем ее Rect (сокращенно от «прямоугольник»), полями которой будут объекты первых двух структур: точка P и размер S. Эти поля также будут защищенными (private – по умолчанию). Добавим в эту структуру конструктор с параметрами public Rect(int x, int y, int w, int h) и три метода: Get() для извлечения информации о прямоугольнике, Get_P() и Get_S для извлечения координат и размеров по отдельности.

В методе Main( ) последовательно инициализируем объект Rect r и покажем работу методов всех этих трех структур.

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

Искусство упаковки структур в C

This page is about a technique for reducing the memory footprint of programs in compiled languages with C-like structures — manually repacking these declarations for reduced size. To read it, you will require basic knowledge of the C programming language.

You need to know this technique if you intend to write code for memory-constrained embedded systems, or operating-system kernels. It is useful if you are working with application data sets so large that your programs routinely hit memory limits. It is good to know in any application where you really, really care about optimizing your use of memory bandwidth and minimizing cache-line misses.

Finally, knowing this technique is a gateway to other esoteric C topics. You are not an advanced C programmer until you have grasped these rules. You are not a master of C until you could have written this document yourself and can criticize it intelligently.

This document originated with «C» in the title, but many of the techniques discussed here also apply to the Go language — and should generalize to any compiled language with C-like structures. There is a note discussing Go and Rust towards the end.

2.В Why I wrote it

This webpage exists because in late 2013 I found myself heavily applying an optimization technique that I had learned more than two decades previously and not used much since.

I needed to reduce the memory footprint of a program that used thousands — sometimes hundreds of thousands — of C struct instances. The program was cvs-fast-export and the problem was that it was dying with out-of-memory errors on large repositories.

There are ways to reduce memory usage significantly in situations like this, by rearranging the order of structure members in careful ways. This can lead to dramatic gains — in my case I was able to cut the working-set size by around 40%, enabling the program to handle much larger repositories without dying.

But as I worked, and thought about what I was doing, it began to dawn on me that the technique I was using has been more than half forgotten in these latter days. A little web research confirmed that programmers don’t seem to talk about it much any more, at least not where a search engine can see them. A couple of Wikipedia entries touch the topic, but I found nobody who covered it comprehensively.

There are actually reasons for this that aren’t stupid. CS courses (rightly) steer people away from micro-optimization towards finding better algorithms. The plunging price of machine resources has made squeezing memory usage less necessary. And the way hackers used to learn how to do it back in the day was by bumping their noses on strange hardware architectures — a less common experience now.

But the technique still has value in important situations, and will as long as memory is finite. This document is intended to save programmers from having to rediscover the technique, so they can concentrate effort on more important things.

3.В Alignment requirements

The first thing to understand is that, on modern processors, the way your compiler lays out basic datatypes in memory is constrained in order to make memory accesses faster. Our examples are in C, but any compiled language generates code under the same constraints.


Storage for the basic C datatypes on an x86 or ARM processor doesn’t normally start at arbitrary byte addresses in memory. Rather, each type except char has an alignment requirement ; chars can start on any byte address, but 2-byte shorts must start on an even address, 4-byte ints or floats must start on an address divisible by 4, and 8-byte longs or doubles must start on an address divisible by 8. Signed or unsigned makes no difference.

Мастер Йода рекомендует:  Интересные GitHub-проекты DevDocs для чтения и поиска по документации

The jargon for this is that basic C types on x86 and ARM are self-aligned . Pointers, whether 32-bit (4-byte) or 64-bit (8-byte) are self-aligned too.

Self-alignment makes access faster because it facilitates generating single-instruction fetches and puts of the typed data. Without alignment constraints, on the other hand, the code might end up having to do two or more accesses spanning machine-word boundaries. Characters are a special case; they’re equally expensive from anywhere they live inside a single machine word. That’s why they don’t have a preferred alignment.

I said «on modern processors» because on some older ones forcing your C program to violate alignment rules (say, by casting an odd address into an int pointer and trying to use it) didn’t just slow your code down, it caused an illegal instruction fault. This was the behavior, for example, on Sun SPARC chips. In fact, with sufficient determination and the right (e18) hardware flag set on the processor, you can still trigger this on x86.

Also, self-alignment is not the only possible rule. Historically, some processors (especially those lacking barrel shifters) have had more restrictive ones. If you do embedded systems, you might trip over one of these lurking in the underbrush. Be aware this is possible.

From when it was first written at the beginning of 2014 until late 2020, this section ended with the last paragraph. During that period I’ve learned something rather reassuring from working with the source code for the reference implementation of NTP. It does packet analysis by reading packets off the wire directly into memory that the rest of the code sees as a struct, relying on the assumption of minimal self-aligned padding.

The interesting news is that NTP has apparently being getting away with this for decades across a very wide span of hardware, operating systems, and compilers, including not just Unixes but under Windows variants as well. This suggests that platforms with padding rules other than self-alignment are either nonexistent or confined to such specialized niches that they’re never either NTP servers or clients.

4.В Padding

Now we’ll look at a simple example of variable layout in memory. Consider the following series of variable declarations in the top level of a C module:

If you didn’t know anything about data alignment, you might assume that these three variables would occupy a continuous span of bytes in memory. That is, on a 32-bit machine 4 bytes of pointer would be immediately followed by 1 byte of char and that immediately followed by 4 bytes of int. And a 64-bit machine would be different only in that the pointer would be 8 bytes.

In fact, the hidden assumption that the allocated order of static variables is their source order is not necessarily valid; the C standards don’t mandate it. I’m going to ignore this detail because (a) that hidden assumption is usually correct anyway, and (b) the actual purpose of talking about padding and packing outside structures is to prepare you for what happens inside them.

Here’s what actually happens (on an x86 or ARM or anything else with self-aligned types). The storage for p starts on a self-aligned 4- or 8-byte boundary depending on the machine word size. This is pointer alignment — the strictest possible.

The storage for c follows immediately. But the 4-byte alignment requirement of x forces a gap in the layout; it comes out as though there were a fourth intervening variable, like this:

The pad[3] character array represents the fact that there are three bytes of waste space in the structure. The old-school term for this was «slop». The value of the padding bits is undefined; in particular it is not guaranteed that they will be zeroed.

Compare what happens if x is a 2-byte short:

In that case, the actual layout will be this:

On the other hand, if x is a long on a 64-bit machine

we end up with this:

If you have been following carefully, you are probably now wondering about the case where the shorter variable declaration comes first:

If the actual memory layout were written like this

what can we say about M and N ?

First, in this case N will be zero. The address of x , coming right after p , is guaranteed to be pointer-aligned, which is never less strict than int-aligned.

The value of M is less predictable. If the compiler happened to map c to the last byte of a machine word, the next byte (the first of p ) would be the first byte of the next one and properly pointer-aligned. M would be zero.

It is more likely that c will be mapped to the first byte of a machine word. In that case M will be whatever padding is needed to ensure that p has pointer alignment — 3 on a 32-bit machine, 7 on a 64-bit machine.

Intermediate cases are possible. M can be anything from 0 to 7 (0 to 3 on 32-bit) because a char can start on any byte boundary in a machine word.

If you wanted to make those variables take up less space, you could get that effect by swapping x with c in the original sequence.

Usually, for the small number of scalar variables in your C programs, bumming out the few bytes you can get by changing the order of declaration won’t save you enough to be significant. The technique becomes more interesting when applied to nonscalar variables — especially structs.

Before we get to those, let’s dispose of arrays of scalars. On a platform with self-aligned types, arrays of char/short/int/long/pointer have no internal padding; each member is automatically self-aligned at the end of the next one.

All these rules and examples map over to Go with only syntactic changes.

In the next section we will see that the same is not necessarily true of structure arrays.

5.В Structure alignment and padding

In general, a struct instance will have the alignment of its widest scalar member. Compilers do this as the easiest way to ensure that all the members are self-aligned for fast access.

Also, in C (and Go, and Rust) the address of a struct is the same as the address of its first member — there is no leading padding. Beware: in C++, classes that look like structs may break this rule! (Whether they do or not depends on how base classes and virtual member functions are implemented, and varies by compiler.)

(When you’re in doubt about this sort of thing, ANSI C provides an offsetof() macro which can be used to read out structure member offsets.)

Consider this struct:

Assuming a 64-bit machine, any instance of struct foo1 will have 8-byte alignment. The memory layout of one of these looks unsurprising, like this:

It’s la >c first, that’s no longer true.

If the members were separate variables, c could start at any byte boundary and the size of pad might vary. Because struct foo2 has the pointer alignment of its w >c has to be pointer-aligned, and following padding of 7 bytes is locked in.

Now let’s talk about trailing padding on structures. To explain this, I need to introduce a basic concept which I’ll call the stride address of a structure. It is the first address following the structure data that has the same alignment as the structure .

The general rule of trailing structure padding is this: the compiler will behave as though the structure has trailing padding out to its str >sizeof() will return.

Consider this example on a 64-bit x86 or ARM machine:

You might think that sizeof(struct foo3) should be 9, but it’s actually 16. The str >(&p)[2] . Thus, in the quad array, each member has 7 bytes of trailing padding, because the first member of each following struct wants to be self-aligned on an 8-byte boundary. The memory layout is as though the structure had been declared like this:

For contrast, consider the following example:

Because s only needs to be 2-byte aligned, the str >c , and struct foo4 as a whole only needs one byte of trailing padding. It will be laid out like this:

and sizeof(struct foo4) will return 4.

Here’s a last important detail: If your structure has structure members, the inner structs want to have the alignment of longest scalar too. Suppose you write this:

The char *p member in the inner struct forces the outer struct to be pointer-aligned as well as the inner. Actual layout will be like this on a 64-bit machine:

This structure gives us a hint of the savings that might be possible from repacking structures. Of 24 bytes, 13 of them are padding. That’s more than 50% waste space!

6.В Bitfields

Now let’s consider C bitfields. What they give you the ability to do is declare structure fields of smaller than character width, down to 1 bit, like this:

The thing to know about bitfields is that they are implemented with word- and byte-level mask and rotate instructions operating on machine words, and cannot cross word boundaries. C99 guarentees that bit-fields will be packed as tightly as possible, provided they don’t cross storage unit boundaries (6.7.2.1 #10).

This restriction is relaxed in C11 (6.7.2.1p11) and C++14 ([ >struct foo9 to be 64 bits instead of 32; a bit-field can span multiple allocation units instead of starting a new one. It’s up to the implementation to decide; GCC leaves it up to the ABI, which for x64 does prevent them from sharing an allocation unit.

Assuming we’re on a 32-bit machine, the C99 rules imply that the layout may look like this:


But this isn’t the only possibility, because the C standard does not specify that bits are allocated low-to-high. So the layout could look like this:

That is, the padding could precede rather than following the payload bits.

Note also that, as with normal structure padding, the padding bits are not guaranteed to be zero; C99 mentions this.

Note that the base type of a bit field is interpreted for signedness but not necessarily for size. It is up to implementors whether «short flip:1» or «long flip:1» are supported, and whether those base types change the size of the storage unit the field is packed into.

Proceed with caution and check with -Wpadded if you have it available (e.g. under clang). Compilers on exotic hardware might interpret the C99 rules in surprising ways; older compilers might not quite follow them.

The restriction that bitfields cannot cross machine word boundaries means that, while the first two of the following structures pack into one and two 32-bit words as you’d expect, the third ( struct foo9 ) takes up three 32-bit words in C99, in the last of which only one bit is used.

Again, C11 and C++14 may pack foo9 tighter, but it would perhaps be unwise to count on this.

On the other hand, struct foo8 would fit into a single 64-bit word if the machine has those.

7.В Structure reordering

Now that you know how and why compilers insert padding in and after your structures we’ll examine what you can do to squeeze out the slop. This is the art of structure packing.

The first thing to notice is that slop only happens in two places. One is where storage bound to a larger data type (with stricter alignment requirements) follows storage bound to a smaller one. The other is where a struct naturally ends before its stride address, requiring padding so the next one will be properly aligned.

The simplest way to eliminate slop is to reorder the structure members by decreasing alignment. That is: make all the pointer-aligned subfields come first, because on a 64-bit machine they will be 8 bytes. Then the 4-byte ints; then the 2-byte shorts; then the character fields.

So, for example, consider this simple linked-list structure:

With the implied slop made explicit, here it is:

That’s 24 bytes. If we reorder by size, we get this:

Considering self-alignment, we see that none of the data fields need padding. This is because the stride address for a (longer) field with stricter alignment is always a validly-aligned start address for a (shorter) field with less strict requirements. All the repacked struct actually requires is trailing padding:

Our repack transformation drops the size from 24 to 16 bytes. This might not seem like a lot, but suppose you have a linked list of 200K of these? The savings add up fast — especially on memory-constrained embedded systems or in the core part of an OS kernel that has to stay resident.

Note that reordering is not guaranteed to produce savings. Applying this technique to an earlier example, struct foo5 , we get this:

With padding written out, this is

It’s still 24 bytes because c cannot back into the inner struct’s trailing padding. To collect that gain you would need to redesign your data structures.

Curiously, strictly ordering your structure fields by increasing size also works to mimimize padding. You can minimize padding with any order in which (a) all fields of any one size are in a continuous span (completely eliminating padding between them), and (b) the gaps between those spans are such that the sizes on either side have as few doubling steps of difference from each other as possible. Usually this means no padding at all on one side.

Even more general minimal-padding orders are possible. Example:

This struct has zero padding under self-alignment rules. Working out why is a useful exercise to develop your understanding.

Since shipping the first version of this guide I have been asked why, if reordering for minimal slop is so simple, C compilers don’t do it automatically. The answer: C is a language originally designed for writing operating systems and other code close to the hardware. Automatic reordering would interfere with a systems programmer’s ability to lay out structures that exactly match the byte and bit-level layout of memory-mapped device control blocks.

Go hews to the C philosophy and does not reorder fields. Rust makes the opposite choice; by default, its compiler may reorder structure fields.

8.В Awkward scalar cases

Using enumerated types instead of #defines is a good >which underlying integral type is to be used for them.

Be aware when repacking your structs that while enumerated-type variables are usually ints, this is compiler-dependent; they could be shorts, longs, or even chars by default. Your compiler may have a pragma or command-line option to force the size.

The long double type is a similar trouble spot. Some C platforms implement this in 80 bits, some in 128, and some of the 80-bit platforms pad it to 96 or 128 bits.

In both cases it’s best to use sizeof() to check the storage size.

Finally, under x86 Linux doubles are sometimes an exception to the self-alignment rule; an 8-byte double may require only 4-byte alignment within a struct even though standalone doubles variables have 8-byte self-alignment. This depends on compiler and options.

9.В Readability and cache locality

While reordering by size is the simplest way to eliminate slop, it’s not necessarily the right thing. There are two more issues: readability and cache locality.

Programs are not just communications to a computer, they are communications to other human beings. Code readability is important even (or especially!) when the audience of the communication is only your future self.

A clumsy, mechanical reordering of your structure can harm readability. When possible, it is better to reorder fields so they remain in coherent groups with semantically related pieces of data kept close together. Ideally, the design of your structure should communicate the design of your program.

When your program frequently accesses a structure, or parts of a structure, it is helpful for performance if the accesses tend to fit within a cache line — the memory block fetched by your processor when it is told to get any single address within the block. On 64-bit x86 a cache line is 64 bytes beginning on a self-aligned address; on other platforms it is often 32 bytes.

The things you should do to preserve readability — grouping related and co-accessed data in adjacent fields — also improve cache-line locality. These are both reasons to reorder intelligently, with awareness of your code’s data-access patterns.

If your code does concurrent access to a structure from multiple threads, there’s a third issue: cache line bouncing. To minimize expensive bus traffic, you should arrange your data so that reads come from one cache line and writes go to another in your tighter loops.

Мастер Йода рекомендует:  Класс-сервис для кэширования данных на PHP

And yes, this sometimes contradicts the previous guidance about grouping related data in the same cache-line-sized block. Multithreading is hard. Cache-line bouncing and other multithread optimization issues are very advanced topics which deserve an entire tutorial of their own. The best I can do here is make you aware that these issues exist.

10.В Other packing techniques

Reordering works best when combined with other techniques for slimming your structures. If you have several boolean flags in a struct, for example, consider reducing them to 1-bit bitfields and packing them into a place in the structure that would otherwise be slop.

You’ll take a small access-time penalty for this — but if it squeezes the working set enough smaller, that penalty will be swamped by your gains from avoided cache misses.

More generally, look for ways to shorten data field sizes. In cvs-fast-export, for example, one squeeze I applied was to use the knowledge that RCS and CVS repositories d >time_t (zero date at the beginning of 1970) for a 32-bit time offset from 1982-01-01T00:00:00; this will cover dates to 2118. (Note: if you pull a trick like this, do a bounds check whenever you set the field to prevent nasty bugs!)

Each such field shortening not only decreases the explicit size of your structure, it may remove slop and/or create additional opportunities for gains from field reordering. Virtuous cascades of such effects are not very hard to trigger.

The riskiest form of packing is to use unions. If you know that certain fields in your structure are never used in combination with certain other fields, consider using a union to make them share storage. But be extra careful and verify your work with regression testing, because if your lifetime analysis is even slightly wrong you will get bugs ranging from crashes to (much worse) subtle data corruption.

11.В Overriding alignment rules

Sometimes you can coerce your compiler into not using the processor’s normal alignment rules by using a pragma, usually #pragma pack . GCC and clang have an attribute packed you can attach to individual structure declarations; GCC has an -fpack-struct option for entire compilations.

Do not do this casually, as it forces the generation of more expensive and slower code. Usually you can save as much memory, or almost as much, with the techniques I describe here.

The only good reason for #pragma pack is if you have to exactly match your C data layout to some kind of bit-level hardware or protocol requirement, like a memory-mapped hardware port, and violating normal alignment is required for that to work. If you’re in that situation, and you don’t already know everything else I’m writing about here, you’re in deep trouble and I wish you luck.

12.В Tools

The clang compiler has a -Wpadded option that causes it to generate messages about alignment holes and padding. Some versions also have an undocumented -fdump-record-layouts option that yields more information.

If you’re using C11, you can deploy static_assert to check your assumptions about type and structure sizes. Example:

I have not used it myself, but several respondents speak well of a program called pahole . This tool cooperates with a compiler to produce reports on your structures that describe padding, alignment, and cache line boundaries. This was at one time a standalone C program, but that is now unmaintained; s script with the name pahole now ships with gdb and that is what you should use.

I’ve received a report that a proprietary code auditing tool called «PVS Studio» can detect structure-packing opportunities.


13.В Proof and exceptional cases

You can download sourcecode for a little program that demonstrates the assertions about scalar and structure sizes made above. It is packtest.c.

If you look through enough strange combinations of compilers, options, and unusual hardware, you will find exceptions to some of the rules I have described. They get more common as you go back in time to older processor designs.

The next level beyond knowing these rules is knowing how and when to expect that they will be broken. In the years when I learned them (the early 1980s) we spoke of people who didn’t get this as victims of «all-the-world’s-a-VAX syndrome». Remember that not all the world is a PC.

14.В Go and Rust

The Go language is in many respects similar to C. It has structures and arrays, though not bitfields or unions. Go compilers have the same optimization and alignment issues as C compilers. One important difference is that the Go specification requires structure fields to be self-aligned. As in C, array elements are padded up to the following stride address.

Therefore, if you know the implications of self-aligment in C, you can apply them directly to calculating sizes and offsets in Go and to space-optimizing Go structures. The obvious correspondence mostly works.

I say «mostly» because Go has one odd quirk. Since Go 1.5, a zero-length field at the end of a struct (that is, a zero-length array or empty struct) is sized and aligned as though it is one byte. The reasons for this are discussed in an essay Padding is Hard by one of the Go developers.

Rust follows C-like field alignment rules if a structure is annotated with «repr(C)». Otherwise (by default) all bets are off: padding rules are (deliberately) unspecified and the compiler may even reorder structure members. It is probably best to let the Rust compiler do space optimization rather than forcing it.

15.В Supporting this work

If you were educated or entertained by this document, please sign up for my Patreon feed. The time needed to write and maintain documents like this one is not free, and while I enjoying giving them to the world my bills won’t pay themselves. Even a few dollars a month — from enough of you — helps a lot.

16.В Related Reading

This section exists to collect pointers to essays which I judge to be good companions to this one.

Искусство упаковки структур в C

211740 просмотра

7 ответа

1855 Репутация автора

Размеры конструкций 12 и 8 соответственно.

Эти структуры дополнены или упакованы?

Когда происходит заполнение или упаковка?

Ответы (7)

5 плюса

59758 Репутация автора

Обивка и упаковка — это только два аспекта одного и того же:

  • упаковка или выравнивание — это размер, до которого округляется каждый элемент
  • отступ — это дополнительное пространство, добавляемое для выравнивания

В mystruct_A предположении, что выравнивание по умолчанию равно 4, каждый элемент выравнивается по кратности 4 байтов. Поскольку размер char равен 1, заполнение для a и c составляет 4 — 1 = 3 байта, в то время как заполнение не требуется, для int b которого уже 4 байта. Это работает так же, как для mystruct_B .

1 плюс

36705 Репутация автора

Упаковка структуры выполняется только тогда, когда вы явно указываете компилятору упаковать структуру. Обивка — это то, что вы видите. Ваша 32-битная система дополняет каждое поле выравниванием слов. Если бы вы сказали своему компилятору упаковать структуры, они бы составляли 6 и 5 байтов соответственно. Не делай этого, хотя. Он не переносим и заставляет компиляторы генерировать гораздо более медленный (а иногда даже ошибочный) код.

225 плюса

70892 Репутация автора

Заполнение выравнивает элементы структуры по «естественным» границам адресов — скажем, int члены будут иметь смещения, которые mod(4) == 0 на 32-битной платформе. Заполнение включено по умолчанию. Он вставляет следующие «пробелы» в вашу первую структуру:

Упаковка , с другой стороны, не позволяет компилятору выполнять заполнение (это должно быть явно запрошено) в GCC __attribute__((__packed__)) , поэтому следующее:

будет производить структуру размера 6 на 32-битной архитектуре.

Однако обратите внимание — доступ к невыровненной памяти медленнее на архитектурах, которые позволяют это (например, x86 и amd64), и явно запрещен на архитектурах со строгим выравниванием, таких как SPARC.

20 плюса

371 Репутация автора

Упаковка конструкции подавляет заполнение конструкции, прокладку, используемую, когда выравнивание имеет наибольшее значение, упаковку, используемую, когда пространство имеет наибольшее значение.

Некоторые компиляторы #pragma позволяют подавлять заполнение или упаковывать его в n байтов. Некоторые предоставляют ключевые слова для этого. Обычно прагма, которая используется для изменения заполнения структуры, будет иметь следующий формат (зависит от компилятора):

Например, ARM предоставляет __packed ключевое слово для подавления заполнения структуры. Просмотрите руководство по компилятору, чтобы узнать больше об этом.

Таким образом, упакованная структура — это структура без заполнения.

Обычно будут использоваться упакованные конструкции

отформатировать структуру данных для передачи по сети, используя некоторый протокол (конечно, это не очень хорошая практика, потому что вам нужно
иметь дело с порядком байтов)

-1 плюса

41 Репутация автора

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

  1. Чтобы выровнять данные в памяти, один или несколько пустых байтов (адресов) вставляются (или остаются пустыми) между адресами памяти, которые выделяются для других элементов структуры во время выделения памяти. Эта концепция называется заполнением структуры.
  2. Архитектура компьютерного процессора такова, что он может считывать из памяти 1 слово (4 байта в 32-разрядном процессоре) за раз.
  3. Чтобы использовать это преимущество процессора, данные всегда выровнены как 4-байтовый пакет, что приводит к вставке пустых адресов между адресами других членов.
  4. Из-за этой концепции дополнения структуры в C размер структуры всегда не совпадает с тем, что мы думаем.

Автор: manoj yadav Размещён: 15.08.2015 03:25

26 плюса

8389 Репутация автора

( Приведенные выше ответы объяснили причину довольно ясно, но, кажется, не совсем ясно о размере заполнения, поэтому я добавлю ответ в соответствии с тем, что я узнал из «Потерянного искусства структуры C» )

Выравнивание памяти (для структуры)


Правила:

  • Перед каждым отдельным членом будет заполнение, чтобы оно начиналось с адреса, кратного его размеру.
    например, в 64-битной системе int должен начинаться с адреса, кратного 4, а long 8 — short на 2.
  • char и char[] являются специальными, может быть любым адресом памяти, поэтому им не требуется заполнение перед ними.
  • Поскольку struct , кроме необходимости выравнивания для каждого отдельного элемента, размер всей структуры будет выровнен по размеру, кратному размеру наибольшего отдельного элемента, путем заполнения в конце.
    например, если самый большой член структуры long тогда делится на 8, int то на 4, short затем на 2.

Порядок участника:

  • Порядок членов может повлиять на фактический размер структуры, так что имейте это в виду. например, stu_c и stu_d из приведенного ниже примера имеют одинаковые элементы, но в другом порядке, и приводят к разному размеру для двух структур.

Адрес в памяти (для структуры)

Правила:

  • 64-битный
    адрес системной структуры начинается с (n * 16) байтов. ( Вы можете видеть в примере ниже, все напечатанные шестнадцатеричные адреса структур заканчиваются 0 . )
    Причина : возможный самый большой отдельный элемент структуры составляет 16 байт ( long double ).

Пустое место :

  • Пустое пространство между 2 структурами может использоваться неструктурными переменными, которые могут вписываться.
    Например, test_struct_address() ниже, переменная x находится между смежной структурой g и h .
    Независимо от того x , объявлен ли h адрес, адрес не изменится, x просто используется пустое пространство, которое было g потрачено впустую.
    Подобный случай для y .

пример

( для 64-битной системы )

memory_align.c :

Результат исполнения — test_struct_padding() :

Результат исполнения — test_struct_address() :

Таким образом, адресом начала для каждой переменной является g: d0 x: dc h: e0 y: e8

31 плюса

823 Репутация автора

Я знаю, что этот вопрос старый, и большинство ответов здесь очень хорошо объясняет заполнение, но, пытаясь понять его сам, я решил, что помогло «визуальное» представление о происходящем.

Процессор считывает память «кусками» определенного размера (слова). Скажем, процессорное слово имеет длину 8 байтов. Он будет смотреть на память как большой ряд 8-байтовых строительных блоков. Каждый раз, когда ему нужно получить некоторую информацию из памяти, он достигнет одного из этих блоков и получит его.

Как показано на рисунке выше, не имеет значения, где находится символ (длиной 1 байт), поскольку он будет находиться внутри одного из этих блоков, что потребует от процессора обработки только 1 слова.

Когда мы имеем дело с данными размером более одного байта, такими как 4-байтовое int или 8-байтовое двойное число, то, как они выровнены в памяти, влияет на то, сколько слов придется обрабатывать центральным процессором. Если 4-байтовые блоки выровнены таким образом, что они всегда соответствуют внутренней части блока (адрес памяти кратен 4), то нужно обработать только одно слово. В противном случае часть из 4 байтов может иметь часть себя в одном блоке и часть в другом, требуя, чтобы процессор обработал 2 слова для чтения этих данных.

То же самое относится к 8-байтовому двойному символу, за исключением того, что теперь он должен быть в адресе памяти, кратном 8, чтобы гарантировать, что он всегда будет внутри блока.

Это касается 8-байтового текстового процессора, но концепция применима к другим размерам слов.

Заполнение работает, заполняя промежутки между этими данными, чтобы удостовериться, что они выровнены с этими блоками, таким образом улучшая производительность, читая память.

Однако, как указано в ответах других, иногда пространство имеет большее значение, чем сама производительность. Возможно, вы обрабатываете много данных на компьютере, на котором недостаточно ОЗУ (можно использовать пространство подкачки, но оно НАМНОГО медленнее). Вы можете расположить переменные в программе до тех пор, пока не будет выполнено наименьшее заполнение (как это было продемонстрировано в некоторых других ответах), но если этого недостаточно, вы можете явно отключить заполнение, что и является упаковкой .

Выравнивание (объявления C++) Alignment (C++ Declarations)

Одной из низкоуровневых особенностей C++ является возможность указать точное выравнивание объектов в памяти, чтобы максимально использовать конкретную аппаратную архитектуру. One of the low-level features of C++ is the ability to specify the precise alignment of objects in memory to take maximum advantage of a specific hardware architecture. По умолчанию компилятор выстраивает элементы класса и структуры по значению размера: и bool char по 1 байтам, short в 2-байтовых int long границах,, и float в 4-байтовых границах. long long , идля long double 8-байтовых границ. double By default, the compiler aligns class and struct members on their size value: bool and char on 1-byte boundaries, short on 2-byte boundaries, int , long , and float on 4-byte boundaries, and long long , double , and long double on 8-byte boundaries. В большинстве случаев не нужно беспокоиться о выравнивании, так как выравнивание по умолчанию уже оптимально. In most scenarios, you never have to be concerned with alignment because the default alignment is already optimal. Однако в некоторых случаях можно добиться значительного улучшения производительности или экономии памяти, указав пользовательское выравнивание для структур данных. In some cases, however, you can achieve significant performance improvements, or memory savings, by specifying a custom alignment for your data structures. До Visual Studio 2015 можно использовать ключевые слова __alignof Майкрософт и declspec(alignas) задать выравнивание, превышающее значение по умолчанию. Before Visual Studio 2015 you could use the Microsoft-specific keywords __alignof and declspec(alignas) to specify an alignment greater than the default. Начиная с Visual Studio 2015 следует использовать стандартные ключевые слова C++ 11 alignof и alignas для максимального переноса кода. Starting in Visual Studio 2015 you should use the C++11 standard keywords alignof and alignas for maximum code portability. Новые ключевые слова ведут себя так же, как и расширения, специфичные для Майкрософт. The new keywords behave in the same way under the hood as the Microsoft-specific extensions. Документация для этих расширений также применима к новым ключевым словам. The documentation for those extensions also applies to the new keywords. Дополнительные сведения см. в разделе оператор __alignof и выровняйте. For more information, see __alignof Operator and align. В C++ стандарте не задано поведение упаковки для выравнивания по границам, меньшим, чем значение по умолчанию компилятора для целевой платформы, поэтому в этом случае необходимо использовать пакет Microsoft #pragma Pack . The C++ standard doesn’t specify packing behavior for alignment on boundaries smaller than the compiler default for the target platform, so you still need to use the Microsoft #pragma pack in that case.

Используйте класс aligned_storage для выделения памяти структур данных с пользовательскими выравниваниями. Use the aligned_storage class for memory allocation of data structures with custom alignments. Класс aligned_union предназначен для указания выравнивания для объединений с нетривиальными конструкторами или деструкторами. The aligned_union class is for specifying alignment for unions with non-trivial constructors or destructors.

О выравнивании About Alignment

Выравнивание представляет собой свойство адреса памяти, выражаемое как числовой адрес по модулю степени 2. Alignment is a property of a memory address, expressed as the numeric address modulo a power of 2. Например, адрес 0x0001103F остаток от деления 4 равен 3. For example, the address 0x0001103F modulo 4 is 3. Этот адрес считается согласованным с 4n + 3, где 4 обозначает выбранную степень 2. That address is said to be aligned to 4n+3, where 4 indicates the chosen power of 2. Выравнивание адреса зависит от выбранной степени 2. The alignment of an address depends on the chosen power of 2. Тот же адрес по модулю 8 равен 7. The same address modulo 8 is 7. Говорят, что адрес выровнен по X, если его выравнивание — Xn+0. An address is said to be aligned to X if its alignment is Xn+0.

Мастер Йода рекомендует:  IDE Eclipse за и против от ведущих программистов

Процессоры выполняют инструкции, которые работают с данными, хранящимися в памяти. CPUs execute instructions that operate on data stored in memory. Данные идентифицируются по их адресам в памяти. The data are identified by their addresses in memory. У одной из них также есть размер. A single datum also has a size. Мы вызываем объект «база» естественным образом, если его адрес выровнен по размеру. We call a datum naturally aligned if its address is aligned to its size. В противном случае он называется неправильно . It’s called misaligned otherwise. Например, 8-байтная база с плавающей запятой имеет естественное выравнивание, если адрес, используемый для его распознавания, имеет 8-байтовое выравнивание. For example, an 8-byte floating-point datum is naturally aligned if the address used to identify it has an 8-byte alignment.

Обработка выравнивания данных компилятором Compiler handling of data alignment

Компиляторы пытаются сделать выделение данных способом, который предотвращает неправильное выравнивание данных. Compilers attempt to make data allocations in a way that prevents data misalignment.

Для простых типов данных компилятор назначает адреса, которые кратны размеру в байтах для типа данных. For simple data types, the compiler assigns addresses that are multiples of the size in bytes of the data type. Например, компилятор назначает адреса переменным типа long , кратным 4, устанавливая младшие 2 бита адреса равными нулю. For example, the compiler assigns addresses to variables of type long that are multiples of 4, setting the bottom 2 bits of the address to zero.

Компилятор также дополняет структуры тем способом, который естественным образом соответствует каждому элементу структуры. The compiler also pads structures in a way that naturally aligns each element of the structure. Рассмотрим структуру struct x_ в следующем примере кода: Consider the structure struct x_ in the following code example:

Компилятор дополняет эту структуру для принудительного выравнивания естественным образом. The compiler pads this structure to enforce alignment naturally.

В следующем примере кода показано, как компилятор помещает заполненную структуру в память: The following code example shows how the compiler places the padded structure in memory:

Оба объявления возвращают sizeof(struct x_) 12 байт. Both declarations return sizeof(struct x_) as 12 bytes.

Второе объявление включает два дополняющих элемента: The second declaration includes two padding elements:

char _pad0[3] для выровняйте int b элемент на 4-байтовой границе. char _pad0[3] to align the int b member on a 4-byte boundary.

char _pad1[1] для выровняйте элементы массива структуры struct _x bar[3]; по 4-байтовой границе. char _pad1[1] to align the array elements of the structure struct _x bar[3]; on a four-byte boundary.

Заполнение выровнено между элементами bar[3] таким образом, что обеспечивает естественный доступ. The padding aligns the elements of bar[3] in a way that allows natural access.

В следующем примере кода показан bar[3] макет массива: The following code example shows the bar[3] array layout:

Выравнивание и размер структуры

Есть у нас, допустим структура.

Но если на разных платформах ( например avr и arm ) выполнить следующий код

printf(«размер структуры %u\r\n», sizeof( struct my_struct ) );

то мы получим разные результаты. Для arm размер структуры равен 12, а для avr равен 5. Почему?

На первый взгляд, потому, что переменные типа int на различных платформах имеют разную разрядность. Для arm это 4 байта, для avr 2 байта.


Перепишем нашу структуру.

Тип short имеет размер 2 байта на всех платформах.

Но мы опять получаем разный размер структуры, для arm 6 байт, для avr 5 байт.

Дело в том что компилятор gcc (да и большинство других) по умолчанию выравнивает поля структуры (дополняет неиспользуемыми байтами) в соответствии с следующим правилом: каждое поле выравнивается по адресу, кратному размеру данного поля. Поле типа int на 32-битной системе будет выровнено по границе 4 байт, short по границе 2 байта. Поля типа char не выравниваются. Размер структуры выравнивается до размера, кратному размеру его максимального элемента.

Но как нам быть, если мы хотим передать структуру с одной платформы на другую.

Устранить поведение по умолчанию и убрать выравнивание можно если указать
атрибут packed при описании структуры, директива компилятора #pragma pack(1) также может использоваться для этой цели

В этом случае «пустоты», связанные с выравниванием, исчезают и размер структуры на разных платформах становиться одинаковым.

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

С++ и упакованная структура

У меня есть проект базы данных, который я хочу переместить с C на С++. В этом проекте C у меня много маленьких упакованных структур, которые я пишу прямо в файл или читаю из mmaped файла — например. непосредственно из адреса памяти.

Мне нужно представление класса в памяти, чтобы быть точно таким же, как если бы я использовал обычную старую структуру C. Я считаю, что это называется стандартным расположением POD или С++.

Я могу выполнить несколько способов:

Я могу сделать класс, бу, я беспокоюсь, что если я добавлю методы в эту структуру, возможно, внутренняя структура будет изменена.

Если я завершу структуру в класс, мне нужно будет создавать/уничтожать классы все время вместе с структурами.

Если я использую стиль C — OO, мне нужно будет указать указатель на каждую функцию, например.

Я также могу сделать структуру полем и сделать что-то подобное

но чем больше я это вижу, тем меньше мне это нравится, потому что нет реального преимущества.

Что-нибудь мне не хватает?

Если я добавлю методы в эту структуру, возможно, внутренняя структура будет изменена.

Это неправильно; чтобы удовлетворить ваши потребности, вы хотите сохранить свою структуру POD, для которой по существу вы не хотите:

  • нетривиальные конструкторы/деструкторы/операторы присваивания;
  • виртуальные функции или виртуальные базовые классы;
  • разные спецификаторы доступа для членов данных.

(есть некоторые дополнительные ограничения (см. С++ 11 §9 ¶ 6-10), но они не особенно актуальны в вашем случае)

«POD» подразумевает две вещи:

что ваш класс является «стандартным макетом», что примерно означает «изложенным в четко определенном ключе, так же, как и C» (который оценивает вашу основную проблему);

методы добавления не должны разрушать материал, поскольку, поскольку они не являются виртуальными, они переводятся как свободные функции, которые принимают указатель на объект как скрытый параметр и не требуют модификации исходного макета C. static методы — это просто свободные функции с разным охватом, поэтому в целом они не являются проблемой.

что ваш класс может быть свободно скопирован с помощью memcpy без разрыва материала, что, вероятно, вам нужно, если вы читаете его прямо из файла (либо с помощью mmap , либо с помощью fread );

это объясняется «тривиальностью» конструкторов (т.е. если они пропущены, с вашими объектами ничего плохого не происходит) и отсутствием виртуальных членов, а это означает, что вы не рискуете перезаписать vptr устаревшим один из них читается из файла.

Искусство упаковки структур в C

211740 просмотра

7 ответа

1855 Репутация автора

Размеры конструкций 12 и 8 соответственно.

Эти структуры дополнены или упакованы?

Когда происходит заполнение или упаковка?

Ответы (7)

5 плюса

59758 Репутация автора

Обивка и упаковка — это только два аспекта одного и того же:

  • упаковка или выравнивание — это размер, до которого округляется каждый элемент
  • отступ — это дополнительное пространство, добавляемое для выравнивания

В mystruct_A предположении, что выравнивание по умолчанию равно 4, каждый элемент выравнивается по кратности 4 байтов. Поскольку размер char равен 1, заполнение для a и c составляет 4 — 1 = 3 байта, в то время как заполнение не требуется, для int b которого уже 4 байта. Это работает так же, как для mystruct_B .

1 плюс

36705 Репутация автора

Упаковка структуры выполняется только тогда, когда вы явно указываете компилятору упаковать структуру. Обивка — это то, что вы видите. Ваша 32-битная система дополняет каждое поле выравниванием слов. Если бы вы сказали своему компилятору упаковать структуры, они бы составляли 6 и 5 байтов соответственно. Не делай этого, хотя. Он не переносим и заставляет компиляторы генерировать гораздо более медленный (а иногда даже ошибочный) код.

225 плюса

70892 Репутация автора

Заполнение выравнивает элементы структуры по «естественным» границам адресов — скажем, int члены будут иметь смещения, которые mod(4) == 0 на 32-битной платформе. Заполнение включено по умолчанию. Он вставляет следующие «пробелы» в вашу первую структуру:

Упаковка , с другой стороны, не позволяет компилятору выполнять заполнение (это должно быть явно запрошено) в GCC __attribute__((__packed__)) , поэтому следующее:

будет производить структуру размера 6 на 32-битной архитектуре.

Однако обратите внимание — доступ к невыровненной памяти медленнее на архитектурах, которые позволяют это (например, x86 и amd64), и явно запрещен на архитектурах со строгим выравниванием, таких как SPARC.

20 плюса

371 Репутация автора


Упаковка конструкции подавляет заполнение конструкции, прокладку, используемую, когда выравнивание имеет наибольшее значение, упаковку, используемую, когда пространство имеет наибольшее значение.

Некоторые компиляторы #pragma позволяют подавлять заполнение или упаковывать его в n байтов. Некоторые предоставляют ключевые слова для этого. Обычно прагма, которая используется для изменения заполнения структуры, будет иметь следующий формат (зависит от компилятора):

Например, ARM предоставляет __packed ключевое слово для подавления заполнения структуры. Просмотрите руководство по компилятору, чтобы узнать больше об этом.

Таким образом, упакованная структура — это структура без заполнения.

Обычно будут использоваться упакованные конструкции

отформатировать структуру данных для передачи по сети, используя некоторый протокол (конечно, это не очень хорошая практика, потому что вам нужно
иметь дело с порядком байтов)

-1 плюса

41 Репутация автора

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

  1. Чтобы выровнять данные в памяти, один или несколько пустых байтов (адресов) вставляются (или остаются пустыми) между адресами памяти, которые выделяются для других элементов структуры во время выделения памяти. Эта концепция называется заполнением структуры.
  2. Архитектура компьютерного процессора такова, что он может считывать из памяти 1 слово (4 байта в 32-разрядном процессоре) за раз.
  3. Чтобы использовать это преимущество процессора, данные всегда выровнены как 4-байтовый пакет, что приводит к вставке пустых адресов между адресами других членов.
  4. Из-за этой концепции дополнения структуры в C размер структуры всегда не совпадает с тем, что мы думаем.

Автор: manoj yadav Размещён: 15.08.2015 03:25

26 плюса

8389 Репутация автора

( Приведенные выше ответы объяснили причину довольно ясно, но, кажется, не совсем ясно о размере заполнения, поэтому я добавлю ответ в соответствии с тем, что я узнал из «Потерянного искусства структуры C» )

Выравнивание памяти (для структуры)

Правила:

  • Перед каждым отдельным членом будет заполнение, чтобы оно начиналось с адреса, кратного его размеру.
    например, в 64-битной системе int должен начинаться с адреса, кратного 4, а long 8 — short на 2.
  • char и char[] являются специальными, может быть любым адресом памяти, поэтому им не требуется заполнение перед ними.
  • Поскольку struct , кроме необходимости выравнивания для каждого отдельного элемента, размер всей структуры будет выровнен по размеру, кратному размеру наибольшего отдельного элемента, путем заполнения в конце.
    например, если самый большой член структуры long тогда делится на 8, int то на 4, short затем на 2.

Порядок участника:

  • Порядок членов может повлиять на фактический размер структуры, так что имейте это в виду. например, stu_c и stu_d из приведенного ниже примера имеют одинаковые элементы, но в другом порядке, и приводят к разному размеру для двух структур.

Адрес в памяти (для структуры)

Правила:

  • 64-битный
    адрес системной структуры начинается с (n * 16) байтов. ( Вы можете видеть в примере ниже, все напечатанные шестнадцатеричные адреса структур заканчиваются 0 . )
    Причина : возможный самый большой отдельный элемент структуры составляет 16 байт ( long double ).

Пустое место :

  • Пустое пространство между 2 структурами может использоваться неструктурными переменными, которые могут вписываться.
    Например, test_struct_address() ниже, переменная x находится между смежной структурой g и h .
    Независимо от того x , объявлен ли h адрес, адрес не изменится, x просто используется пустое пространство, которое было g потрачено впустую.
    Подобный случай для y .

пример

( для 64-битной системы )

memory_align.c :

Результат исполнения — test_struct_padding() :

Результат исполнения — test_struct_address() :

Таким образом, адресом начала для каждой переменной является g: d0 x: dc h: e0 y: e8

31 плюса

823 Репутация автора

Я знаю, что этот вопрос старый, и большинство ответов здесь очень хорошо объясняет заполнение, но, пытаясь понять его сам, я решил, что помогло «визуальное» представление о происходящем.

Процессор считывает память «кусками» определенного размера (слова). Скажем, процессорное слово имеет длину 8 байтов. Он будет смотреть на память как большой ряд 8-байтовых строительных блоков. Каждый раз, когда ему нужно получить некоторую информацию из памяти, он достигнет одного из этих блоков и получит его.

Как показано на рисунке выше, не имеет значения, где находится символ (длиной 1 байт), поскольку он будет находиться внутри одного из этих блоков, что потребует от процессора обработки только 1 слова.

Когда мы имеем дело с данными размером более одного байта, такими как 4-байтовое int или 8-байтовое двойное число, то, как они выровнены в памяти, влияет на то, сколько слов придется обрабатывать центральным процессором. Если 4-байтовые блоки выровнены таким образом, что они всегда соответствуют внутренней части блока (адрес памяти кратен 4), то нужно обработать только одно слово. В противном случае часть из 4 байтов может иметь часть себя в одном блоке и часть в другом, требуя, чтобы процессор обработал 2 слова для чтения этих данных.

То же самое относится к 8-байтовому двойному символу, за исключением того, что теперь он должен быть в адресе памяти, кратном 8, чтобы гарантировать, что он всегда будет внутри блока.

Это касается 8-байтового текстового процессора, но концепция применима к другим размерам слов.

Заполнение работает, заполняя промежутки между этими данными, чтобы удостовериться, что они выровнены с этими блоками, таким образом улучшая производительность, читая память.

Однако, как указано в ответах других, иногда пространство имеет большее значение, чем сама производительность. Возможно, вы обрабатываете много данных на компьютере, на котором недостаточно ОЗУ (можно использовать пространство подкачки, но оно НАМНОГО медленнее). Вы можете расположить переменные в программе до тех пор, пока не будет выполнено наименьшее заполнение (как это было продемонстрировано в некоторых других ответах), но если этого недостаточно, вы можете явно отключить заполнение, что и является упаковкой .

Искусство упаковки структур в C

Потерянное искусство . кроме случаев, когда вы разработчик встраиваемых систем. Отмечено автором: «Единственная веская причина для #pragma pack состоит в том, что вам нужно точно сопоставить макет данных C с какими-либо требованиями к оборудованию на уровне битов или протоколом, такими как аппаратный порт с отображением в памяти, и нарушить нормальное выравнивание: требуется, чтобы это сработало. Если вы находитесь в такой ситуации, и вы еще не знаете всего, о чем я здесь пишу, у вас большие проблемы, и я желаю вам удачи ».

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

Правильно? Даже если вы хотите написать некоторый кросс-языковой + кросс-компилятор + кроссплатформенный код и вам необходимо отправить структуры уровня байтов, #pragma pack — это способ гарантировать, что совместно используемые заголовки действительно дают одинаковые результаты. Встраиваемому разработчику нужны все упомянутые вещи в его наборе инструментов, включая #pragma pack

Полностью согласен с тем, что в статье. Код, с которым я работаю, содержит несколько тысяч таких неорганизованных структур, и ни у кого нет времени на его очистку.

В статье говорится о том, что у Clang есть -Wpadded . Похоже, у gcc такая же опция.

Мне нравится, что автор говорит о других оптимизациях, связанных с кешем. Будет ли полезен такой инструмент, как cachegrind (один из инструментов valgrind), чтобы определить области, которые нужно оптимизировать для этого?

Почти все структуры в рабочем коде имеют фиксированный размер и дополняются. Мало кто из моих коллег, кажется, понимает последствия этого или как гарантировать, что структуры действительно упакованы. Я отослал рецензии кода, потому что они явно не упаковывали структуры, которые, очевидно, должны были быть упакованы только для того, чтобы им сказали, что они соответствуют тому, что описал rfc.

Потерял? Я всегда оптимизирую (или вручную дополняю) свои структуры.

Потерянное искусство . если вы не торчали здесь несколько месяцев или больше. #repost

Добавить комментарий