Заполнение в структурах в C - PullRequest
40 голосов
/ 06 августа 2011

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

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

struct A {  
  int* a;  
  char b;  
 }  

а,

struct B {  
  char a;  
  int* b;  
}  

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

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

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

Ответы [ 5 ]

34 голосов
/ 06 августа 2011

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

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

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

Vs.

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

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

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

Struct X:

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

структура Y:

|     |     |     |     |     |     |     |     |
 char  char  pad   pad   ---------int----------        = 8 bytes
11 голосов
/ 06 августа 2011

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

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

Таким образом, вы могли бы иметь

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

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

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

4 голосов
/ 07 августа 2011

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

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к -aligned просто нужно будет обращаться по-другому, возможно, путем загрузки константы в регистр, а не с непосредственным значением, потому что они выходят за пределы ограничения в 256 байт.

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

2 голосов
/ 06 августа 2011

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

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

1 голос
/ 06 августа 2011

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

...