Почему компиляторы C не могут переставлять элементы структуры для устранения отступов выравнивания?

Question

Возможный дубликат:
Почему GCC не оптимизирует структуры?
Почему C++ не делает структуру более узкой?

Рассмотрим следующий пример на 32-битной машине x86:

Из-за ограничений выравнивания, следующая структура

struct s1 {
    char a;
    int b;
    char c;
    char d;
    char e;
}

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

struct s2 {
    int b;
    char a;
    char c;
    char d;
    char e;
}

Я знаю, что компиляторы C/C++ не могут делать это. Мой вопрос, почему язык был разработан таким образом. В конце концов, мы можем в конечном итоге тратить огромное количество памяти, и такие ссылки, как struct_ref->b не заботился бы о разнице.

РЕДАКТИРОВАТЬ: Спасибо всем за ваши чрезвычайно полезные ответы. Вы очень хорошо объясняете, почему перестановка не работает из-за того, как был разработан язык. Тем не менее, это заставляет меня задуматься: сохранятся ли эти аргументы, если бы перестановка была частью языка? Допустим, было определенное правило перестановки, из которого мы требовали, по крайней мере,

1. мы должны реорганизовать структуру только в случае необходимости (ничего не делать, если структура уже "плотная")
2. правило смотрит только на определение структуры, а не на внутренние структуры. Это гарантирует, что тип структуры имеет одинаковое расположение независимо от того, является ли он внутренним в другой структуре
3. компоновка скомпилированной памяти данной структуры является предсказуемой с учетом ее определения (то есть правило является фиксированным)

Обращаясь к вашим аргументам один за другим, я рассуждаю:

• Низкоуровневое отображение данных, "элемент наименьшего удивления": просто напишите свои структуры в строгом стиле (как в ответе @Perry), и ничего не изменилось (требование 1). Если по какой-то странной причине вы хотите, чтобы там было внутреннее заполнение, вы можете вставить его вручную, используя фиктивные переменные, и / или могут быть ключевые слова / директивы.

• Различия в компиляторах. Требование 3 устраняет эту проблему. На самом деле, из комментариев @David Heffernan, кажется, что у нас сегодня есть эта проблема, потому что разные компиляторы по-разному дополняют?

• Оптимизация: весь смысл переупорядочения - оптимизация (памяти). Я вижу большой потенциал здесь. Возможно, мы не сможем удалить все отступы вместе, но я не понимаю, как переупорядочение может каким-либо образом ограничить оптимизацию.

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

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

Обратите внимание, что я не говорю об изменении языка - только если он мог (/ должен) быть разработан по-другому.

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

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

Answer 1

Существует несколько причин, по которым компилятор C не может автоматически переупорядочивать поля:

• Компилятор C не знает, является ли struct представляет структуру памяти объектов за пределами текущего модуля компиляции (например: чужая библиотека, файл на диске, сетевые данные, таблицы страниц ЦП и т. д.). В таком случае двоичная структура данных также определяется в месте, недоступном для компилятора, поэтому порядок struct поля будут создавать тип данных, который не согласуется с другими определениями. Например, заголовок файла в ZIP-файле содержит несколько смещенных 32-разрядных полей. Изменение порядка полей сделало бы невозможным прямое чтение или запись заголовка кода C (при условии, что реализация ZIP хотела бы получить прямой доступ к данным):

  struct __attribute__((__packed__)) LocalFileHeader {
      uint32_t signature;
      uint16_t minVersion, flag, method, modTime, modDate;
      uint32_t crc32, compressedSize, uncompressedSize;
      uint16_t nameLength, extraLength;
  };
  

  packed Атрибут не позволяет компилятору выравнивать поля в соответствии с их естественным выравниванием и не имеет отношения к проблеме упорядочения полей. Можно было бы изменить порядок полей LocalFileHeader так что структура имеет минимальный размер и все поля выровнены по своему естественному выравниванию. Однако компилятор не может изменить порядок полей, потому что он не знает, что структура на самом деле определяется спецификацией ZIP-файла.

• С небезопасный язык. Компилятор C не знает, будет ли доступ к данным через тип, отличный от того, который видит компилятор, например:

  struct S {
      char a;
      int b;
      char c;
  };
  
  struct S_head {
      char a;
  };
  
  struct S_ext {
      char a;
      int b;
      char c;
      int d;
      char e;
  };
  
  struct S s;
  struct S_head *head = (struct S_head*)&s;
  fn1(head);
  
  struct S_ext ext;
  struct S *sp = (struct S*)&ext;
  fn2(sp);
  

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

• Если struct тип встроен в другой struct типа, невозможно встроить внутренний struct:

  struct S {
      char a;
      int b;
      char c, d, e;
  };
  
  struct T {
      char a;
      struct S s; // Cannot inline S into T, 's' has to be compact in memory
      char b;
  };
  

  Это также означает, что перемещение некоторых полей из S в отдельную структуру отключает некоторые оптимизации:

  // Cannot fully optimize S
  struct BC { int b; char c; };
  struct S {
      char a;
      struct BC bc;
      char d, e;
  };
  

• Поскольку большинство компиляторов C оптимизируют компиляторы, для переупорядочения структурных полей потребуются новые оптимизации. Сомнительно, чтобы эти оптимизации могли работать лучше, чем программисты. Ручное проектирование структур данных занимает гораздо меньше времени, чем другие задачи компилятора, такие как распределение регистров, встраивание функций, постоянное свертывание, преобразование оператора switch в бинарный поиск и т. Д. Таким образом, преимущества, которые можно получить, позволяя компилятору оптимизировать структуры данных кажется менее ощутимым, чем традиционные оптимизации компилятора.

Answer 2

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

Обратите внимание на этот актуальный код из NetBSD ip.h:

/*
 * Structure of an internet header, naked of options.
 */
struct ip {
#if BYTE_ORDER == LITTLE_ENDIAN
    unsigned int ip_hl:4,       /* header length */
             ip_v:4;        /* version */
#endif
#if BYTE_ORDER == BIG_ENDIAN
    unsigned int ip_v:4,        /* version */
             ip_hl:4;       /* header length */
#endif
    u_int8_t  ip_tos;       /* type of service */
    u_int16_t ip_len;       /* total length */
    u_int16_t ip_id;        /* identification */
    u_int16_t ip_off;       /* fragment offset field */
    u_int8_t  ip_ttl;       /* time to live */
    u_int8_t  ip_p;         /* protocol */
    u_int16_t ip_sum;       /* checksum */
    struct    in_addr ip_src, ip_dst; /* source and dest address */
} __packed;

Эта структура по структуре идентична заголовку дейтаграммы IP. Он используется для прямой интерпретации капель памяти, выделенных контроллером Ethernet, в качестве заголовков IP-датаграмм. Представьте, что компилятор произвольно переставил содержимое из-под автора - это было бы катастрофой.

И да, он не является переносимым (и есть даже непереносимая директива gcc, передаваемая через __packed макро) но дело не в этом. C специально разработан, чтобы позволить писать непереносимый код высокого уровня для управления оборудованием. Это его функция в жизни.

Answer 3

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

Другой пример - структура, подобная приведенной ниже, которая хранит данные переменного размера.

struct {
  uint32_t data_size;
  uint8_t  data[1]; // this has to be the last member
} _vv_a;

Answer 4

Не будучи членом WG14, я не могу сказать ничего определенного, но у меня есть свои идеи:

1. Это нарушило бы принцип наименьшего удивления - может быть, чертовски веская причина, почему я хочу расположить свои элементы в определенном порядке, независимо от того, является ли он наиболее экономичным, и я бы не хотел, чтобы компилятор переставлял эти элементы;

2. У него есть потенциал сломать нетривиальный объем существующего кода - есть много устаревшего кода, который полагается на такие вещи, как адрес структуры, совпадающий с адресом первого члена (видел много классических MacOS код, который сделал это предположение);

Обоснование C99 напрямую обращается ко второму пункту ("Существующий код важен, существующие реализации - нет") и косвенно обращается к первому пункту ("Доверьтесь программисту").

Answer 5

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

Answer 6

Если вы читали / записывали двоичные данные в / из структур C, переупорядочение struct участники будут катастрофой. Например, не было бы никакого практического способа заполнить структуру из буфера.

Answer 7

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

Однако было бы неразумно иметь #pragma, которая позволяла бы компилятору перестраивать чисто основанные на памяти структуры, которые используются только внутри программы. Однако я не знаю такого зверя (но это не значит, что приседать - я не в курсе C/C++)

Answer 8

Имейте в виду, что объявление переменной, такое как структура, предназначено для "публичного" представления переменной. Он используется не только вашим компилятором, но также доступен другим компиляторам, представляющим этот тип данных. Это, вероятно, в конечном итоге в файле.h. Поэтому, если компилятор собирается взять на себя ответственность за способ организации членов в структуре, тогда ВСЕ компиляторы должны иметь возможность следовать тем же правилам. В противном случае, как уже упоминалось, арифметика указателей будет путаться между различными компиляторами.

Answer 9

Ваш случай очень специфичен, так как для этого потребуется первый элемент struct переставить. Это невозможно, так как элемент, который определен первым в struct всегда должен быть смещен 0, Много (поддельного) кода сломалось бы, если бы это было позволено.

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

Answer 10

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

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

В качестве примера, подумайте о stat системный вызов и struct stat,
Когда вы устанавливаете Linux (например), вы получаете libC, который включает stat, который был когда-то составлен кем-то.
Затем вы компилируете приложение с вашим компилятором, с вашими флагами оптимизации, и ожидаете, что оба согласятся с макетом структуры.

Answer 11

Предположим, у вас есть заголовок ах с

struct s1 {
    char a;
    int b;
    char c;
    char d;
    char e;
}

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

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

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

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