Why can't C compilers rearrange struct members to eliminate alignment padding?

c struct compiler-optimization memory-alignment

16244 просмотра

11 ответа

Possible Duplicate:
Why doesn't GCC optimize structs?
Why doesn't C++ make the structure tighter?

Consider the following example on a 32 bit x86 machine:

Due to alignment constraints, the following struct

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

could be represented more memory-efficiently (12 vs. 8 bytes) if the members were reordered as in

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

I know that C/C++ compilers are not allowed to do this. My question is why the language was designed this way. After all, we may end up wasting vast amounts of memory, and references such as struct_ref->b would not care about the difference.

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

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

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

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

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

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

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

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

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

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

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

Автор: Halle Knast Источник Размещён: 12.11.2019 09:24

Ответы (11)


71 плюса

Решение

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

  • Компилятор C не знает, structпредставляет ли структура памяти объектов за пределами текущего модуля компиляции (например: чужая библиотека, файл на диске, сетевые данные, таблицы страниц CPU, ...). В таком случае двоичная структура данных также определяется в месте, недоступном для компилятора, поэтому изменение порядка 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 небезопасный язык. Компилятор 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 в бинарный поиск и т. Д. Таким образом, преимущества, которые можно получить, позволяя компилятору оптимизировать структуры данных кажутся менее ощутимыми, чем традиционные оптимизации компилятора.

Автор: user811773 Размещён: 28.02.2012 06:31

30 плюса

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

Автор: Perry Размещён: 28.02.2012 11:27

11 плюса

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

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

struct {
  uint32_t data_size;
  uint8_t  data[1]; // this has to be the last member
} _vv_a;
Автор: perreal Размещён: 28.02.2012 05:21

10 плюса

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

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

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

C99 Обоснование непосредственно касается второй точки ( «Существующий код имеет важное значение, существующие реализации не являются») , так и косвенно обращаются к первому ( «Trust программист»).

Автор: John Bode Размещён: 28.02.2012 10:49

9 плюса

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

Автор: vicatcu Размещён: 28.02.2012 05:04

6 плюса

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

Автор: larsks Размещён: 28.02.2012 05:17

5 плюса

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

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

Автор: Peter M Размещён: 28.02.2012 05:39

4 плюса

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

Автор: Kluge Размещён: 28.02.2012 05:27

2 плюса

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

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

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

Автор: ugoren Размещён: 28.02.2012 05:48

2 плюса

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

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

Автор: Jens Gustedt Размещён: 28.02.2012 06:00

1 плюс

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

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

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

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

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

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

Автор: ratchet freak Размещён: 29.02.2012 01:41
Вопросы из категории :
32x32