Заполнение в структурах в C

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

Предположим, вам предоставлены две структуры:

struct A {  
  int* a;  
  char b;  
 }

и,

struct B {  
  char a;  
  int* b;  
}

Итак, какой из них вы бы предпочли и почему? Мой ответ прошел так (хотя я несколько стрелял в темноте), что первая структура должна быть предпочтительной, поскольку компилятор выделяет пространство для структуры в нескольких кратных размеру слова (который представляет собой размер указателя - 4 байта на 32 бит и 8 байтов на 64-битных). Таким образом, для обеих структур компилятор выделил бы 8 байтов (предположив, что это 32-битная машина). Но в первом случае заполнение будет выполняться после всех моих переменных (т.е. После a и b). Поэтому, даже если случайно, b получает некоторое значение, которое переполняет и уничтожает мои следующие заполненные байты, но мой a по-прежнему безопасен.

Он не казался очень довольным и попросил одного недостатка первой структуры над второй. Мне нечего было сказать.: D

Пожалуйста, помогите мне с ответами.

Ответ 1

Я не думаю, что есть преимущество для любой из этих структур. В этом уравнении есть одна (!) Константа. Порядок членов структуры гарантированно будет объявлен.

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

struct {
    char a;
    int b;
    char c;
} X;

Vs.

struct {
    char a;
    char b;
    int c;
} Y;

Немного больше объяснений относительно комментариев ниже:

Все ниже - это не 100%, а общий способ построения структур в 32-битной системе, где int - 32 бита:

Структура X:

|     |     |     |     |     |     |     |     |     |     |     |     |
 char  pad    pad   pad   ---------int---------- char   pad   pad   pad   = 12 bytes

struct Y:

|     |     |     |     |     |     |     |     |
 char  char  pad   pad   ---------int----------        = 8 bytes

Ответ 2

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

На современных 32-битных машинах, таких как SPARC или Intel [34] 86, или любой Микросхема Motorola от 68020 вверх, каждая информация должна быть обычно `` self-aligned '', начиная с адреса, который кратен его тип размер. Таким образом, 32-разрядные типы должны начинаться с 32-разрядной границы, 16-разрядной типы на 16-битной границе, 8-битные типы могут начинаться где угодно, struct/array/union имеют выравнивание их наиболее ограничительных член.

Итак, у вас может быть

struct B {  
    char a;
    /* 3 bytes of padding ? More ? */
    int* b;
}

Простое правило, которое сводит к минимуму заполнение в случае "самовыравнивания" (и не вредит большинству других) заключается в том, чтобы упорядочить членов вашей структуры на уменьшающийся размер.

Лично я вижу недостаток первой структуры по сравнению со второй.

Ответ 3

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

struct A {  
    int* a;
    short b;
    A(short num) : b(2*num+1), a(new int[b]) {} 
    // OOPS, `b` is used uninitialized, and a good compiler will warn. 
    // The only way to get `b` initialized before `a` is to declare 
    // it first in the class, or of course we could repeat `2*num+1`.
}

Я также слышал о довольно сложном случае для больших структур, где у процессора есть режимы быстрой адресации для доступа к указателю + смещение для небольших значений смещения (например, до 8 бит или какого-либо другого предела немедленного значения). Лучше всего микро-оптимизировать большую структуру, поместив как можно больше наиболее часто используемых полей в диапазон самых быстрых инструкций.

ЦП может даже иметь быструю адресацию для смещения указателя + смещения и смещения указателя + 4 *. Тогда предположим, что у вас было 64 char поля и 64 int поля: если вы поместили сначала поля char, тогда все поля обоих типов могут быть адресованы с использованием лучших инструкций, тогда как если вы сначала поместите поля int, а char поля, которые не имеют 4-выравнивания, просто должны быть доступны по-разному, возможно, путем загрузки константы в регистр, а не с немедленным значением, поскольку они находятся за пределами 256-байтного предела.

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

Ответ 4

Вкратце, нет никакого преимущества при выборе либо в общем случае. Единственная ситуация, когда выбор имеет значение на практике, заключается в том, что если структура упаковки включена, в случае struct A будет лучшим выбором (поскольку оба поля будут выровнены в памяти, а в struct B поле b будет расположенный с нечетным смещением). Структурная упаковка означает, что в структуру не вставлены байты заполнения.

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

Ответ 5

Это тоже догадка, но большинство компиляторов имеют неправильную опцию, которая явно не добавляет байты заполнения. Для этого требуется (на некоторых платформах) исправление времени выполнения (аппаратная ловушка) для выравнивания доступа "на лету" (с соответствующим снижением производительности). Если я помню, что правая HPUX попала в эту категорию. Таким образом, первая структура полей по-прежнему выравнивается, даже если используются неправильные параметры компилятора (поскольку, как вы сказали, заполнение будет в конце).