Как организовать членов в структуре, чтобы тратить на выравнивание меньше всего места?

[Не дубликат заполнения структуры и упаковки. Этот вопрос о том, как и когда происходит заполнение. Этот рассказ о том, как с этим бороться.]

Я только что понял, сколько памяти теряется в результате выравнивания в C++. Рассмотрим следующий простой пример:

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

int main()
{
    cout << "sizeof(int) = "                      << sizeof(int)                      << '\n';
    cout << "sizeof(double) = "                   << sizeof(double)                   << '\n';
    cout << "2 * sizeof(int) + sizeof(double) = " << 2 * sizeof(int) + sizeof(double) << '\n';
    cout << "but sizeof(X) = "                    << sizeof(X)                        << '\n';
}

При использовании g++ программа выдает следующий вывод:

sizeof(int) = 4
sizeof(double) = 8
2 * sizeof(int) + sizeof(double) = 16
but sizeof(X) = 24

Это 50% памяти! В 3-гигабайтном массиве 134'217'728 Xs 1 гигабайт будет чистым дополнением.

К счастью, решение проблемы очень простое - мы просто должны поменяться местами double b а также int c около:

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

Теперь результат гораздо более удовлетворительный:

sizeof(int) = 4
sizeof(double) = 8
2 * sizeof(int) + sizeof(double) = 16
but sizeof(X) = 16

Однако есть проблема: это не является кросс-совместимым. Да, под g++ int 4 байта и double 8 байт, но это не всегда верно (их выравнивание не обязательно должно быть одинаковым), поэтому в другой среде это "исправление" может быть не только бесполезным, но и потенциально может ухудшить ситуацию, увеличив количество дополнения необходимо.

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

осветление

Из-за недопонимания и путаницы я хотел бы подчеркнуть, что я не хочу "упаковывать" своиstruct, То есть я не хочу, чтобы его члены были выровнены и, следовательно, доступ к ним был медленнее. Вместо этого я по-прежнему хочу, чтобы все члены были выровнены самостоятельно, но таким образом, чтобы при заполнении использовалось меньше всего памяти. Эту проблему можно решить, используя, например, ручную перестановку, как описано здесь и в книге "Потерянное искусство упаковки " Эрика Рэймонда. Я ищу автоматизированный и максимально кроссплатформенный способ сделать это, аналогично тому, что описано в предложении P1112 для будущего стандарта C++20.

Источник

7 ответов

Решение

(Не применяйте эти правила, не задумываясь. См. Замечание ESR о локальности кэша для членов, которые вы используете вместе. А в многопоточных программах остерегайтесь ложного совместного использования элементов, написанных разными потоками. Как правило, вам не нужны данные для каждого потока в По этой причине вообще не существует единой структуры, если только вы не делаете это для управления разделением с большим alignas(128), Это относится к atomic и неатомные переменные; важно то, что потоки записывают в строки кэша независимо от того, как они это делают.)

Правило большого пальца: от наибольшего к наименьшему alignof(), Нет ничего, что вы можете сделать идеально, везде, но на сегодняшний день наиболее распространенным случаем в наши дни является нормальная "нормальная" реализация C++ для обычного 32- или 64-разрядного процессора. Все примитивные типы имеют размеры степени 2.

Большинство типов имеют alignof(T) = sizeof(T), или же alignof(T) ограничен в ширине регистра реализации. Поэтому более крупные типы обычно более выровнены, чем более мелкие.

Правила упаковки структур в большинстве ABI дают членам структуры абсолютную alignof(T) выравнивание относительно начала структуры, а сама структура наследует наибольшее alignof() любого из его членов.

  • Сначала ставьте всегда 64-битные члены (например, double, long long, а также int64_t). Конечно, ISO C++ не фиксирует эти типы в 64 бит / 8 байт, но на практике на всех процессорах вы заботитесь о них. Люди, портирующие ваш код на экзотические процессоры, могут настроить макеты структур для оптимизации при необходимости.

  • затем указатели и целые числа ширины указателя: size_t, intptr_t, а также ptrdiff_t (который может быть 32 или 64-разрядным). Все они имеют одинаковую ширину в обычных современных реализациях C++ для процессоров с плоской моделью памяти.

    Если вы заботитесь о процессорах x86 и Intel, в первую очередь рассмотрите возможность размещения списка ссылок и дерева влево / вправо. Поиск указателей через узлы в дереве или связанном списке имеет штрафы, когда начальный адрес структуры находится на странице 4k, отличной от того, к которому вы обращаетесь. Поставить их на первое место гарантирует, что это не может быть так.

  • тогда long (который иногда 32-битный, даже когда указатели 64-битные, в LLP64 ABI, таких как Windows x64). Но это гарантировано, по крайней мере, так же широко, как int,

  • затем 32-разрядный int32_t , int , float , enum, (При желании отдельно int32_t а также float впереди int если вам небезразличны возможные 8 / 16-битные системы, которые все еще дополняют эти типы до 32-битных, или лучше с их естественным выравниванием. Большинство таких систем не имеют более широких нагрузок (FPU или SIMD), поэтому более широкие типы в любом случае должны обрабатываться как несколько отдельных блоков).

    ISO C++ позволяет int быть 16-битным или произвольно широким, но на практике это 32-битный тип даже на 64-битных процессорах. Дизайнеры ABI обнаружили, что программы предназначены для работы с 32-битными int просто тратить память (и объем кеша), если int был шире. Не делайте предположений, которые могли бы вызвать проблемы с корректностью, но для "портативной производительности" вы просто должны быть правы в обычном случае.

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

  • тогда short / int16_t
  • тогда char / int8_t / bool
  • (для нескольких bool флаги, особенно если они в основном для чтения или если они все модифицированы вместе, рассмотрите возможность упаковки их в 1-битные битовые поля.)

(Для целочисленных типов без знака найдите соответствующий тип со знаком в моем списке.)

Массив из более чем 8 байтов более узких типов может пойти раньше, если вы этого хотите. Но если вы не знаете точные размеры типов, вы не можете гарантировать, что int i + char buf[4] заполнит 8-байтовый выровненный слот между двумя double s. Но это не плохое предположение, так что я бы сделал это в любом случае, если бы была какая-то причина (например, пространственное расположение элементов, к которым осуществляется доступ) для их объединения, а не в конце.

Экзотические типы: x86-64 System V имеет alignof(long double) = 16, но i386 System V имеет только alignof(long double) = 4, sizeof(long double) = 12, Это 80-битный тип x87, который на самом деле составляет 10 байтов, но дополняется до 12 или 16, так что он кратен его alignof, что делает возможным создание массивов без нарушения гарантии выравнивания.

И вообще становится сложнее, когда ваши члены структуры сами являются агрегатами (структура или объединение) с sizeof(x) != alignof(x) ,

Еще один поворот заключается в том, что в некоторых ABI (например, в 32-битной Windows, если я правильно помню) члены структуры выравниваются по своему размеру (до 8 байт) относительно начала структуры, даже если alignof(T) все еще только 4 для double а также int64_t,
Это необходимо для оптимизации общего случая отдельного выделения 8-байтовой выровненной памяти для одной структуры без предоставления гарантии выравнивания. i386 System V также имеет то же самое alignof(T) = 4 для большинства примитивных типов (но malloc по-прежнему дает вам 8-байтовую выровненную память, потому что alignof(maxalign_t) = 8). Но в любом случае, i386 System V не имеет этого правила упаковки структуры, поэтому (если вы не упорядочите свою структуру от самой большой до самой маленькой), вы можете получить 8-байтовые члены, выровненные относительно начала структуры.,

Большинство процессоров имеют режимы адресации, которые, учитывая указатель в регистре, разрешают доступ к любому байтовому смещению. Максимальное смещение обычно очень велико, но на x86 он сохраняет размер кода, если смещение байта помещается в байт со знаком ([-128 .. +127]). Так что, если у вас есть большой массив любого вида, предпочтите поместить его позже в структуру после часто используемых членов. Даже если это стоит немного набивки.

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

Эрик С. Рэймонд написал статью "Потерянное искусство упаковки конструкций". В частности, раздел о переупорядочении структуры в основном является ответом на этот вопрос.

Он также делает еще один важный момент:

9. Читабельность и локальность кэша

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

В большой структуре, которую можно легко разбить по границе строки кэша, имеет смысл поместить 2 вещи рядом, если они всегда используются вместе. Или даже смежный, чтобы разрешить объединение загрузки / хранения, например, копирование 8 или 16 байтов с одним (не целочисленным) целым числом или SIMD загрузка / сохранение вместо отдельной загрузки меньших элементов.

Строки кэша обычно занимают 32 или 64 байта на современных процессорах. (На современном x86 всегда 64 байта. И у семейства Sandybridge есть пространственный предварительный выборщик смежных линий в кэше L2, который пытается завершить 128-байтовые пары строк, отдельно от основного детектора шаблонов предварительной выборки H2-стримера и предварительной выборки L1d).

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

(@alexis опубликовал ответ только для ссылки со ссылкой на статью ESR, так что спасибо за эту отправную точку.)

Источник

GCC имеет -Wpadded предупреждение, которое предупреждает, когда дополнение добавлено к структуре:

https://godbolt.org/z/iwO5Q3:

<source>:4:12: warning: padding struct to align 'X::b' [-Wpadded]
    4 |     double b;
      |            ^

<source>:1:8: warning: padding struct size to alignment boundary [-Wpadded]
    1 | struct X
      |        ^

И вы можете вручную переставить элементы так, чтобы было меньше / нет заполнения. Но это не кроссплатформенное решение, так как разные типы могут иметь разные размеры / выравнивания в разных системах (в первую очередь указатели размером 4 или 8 байт на разных архитектурах). Общее правило при переходе от объявления членов к переходу от наименьшего к наименьшему, и, если вы все еще беспокоитесь, скомпилируйте свой код с помощью -Wpadded один раз (но я бы не стал его включать, потому что иногда необходимо заполнение).

Что касается причины, по которой компилятор не может сделать это автоматически, из-за стандарта ( [class.mem] / 19). Это гарантирует, что, поскольку это простая структура с только открытыми членами, &x.a < &x.c (для некоторых X x;), поэтому их нельзя переставить.

Источник

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

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

Вы можете использовать фиксированные типы ширины, такие как

struct foo
{
    int64_t a;
    int16_t b;
    int8_t c;
    int8_t d;
};

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

Источник

Mate, если у вас есть 3 ГБ данных, вам, вероятно, следует подойти к решению проблемы иным путем, чем менять элементы данных.

Вместо использования "массива структуры" можно использовать "структуру массивов". Так сказать

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

constexpr size_t ArraySize = 1'000'000;
X my_data[ArraySize];

собирается стать

constexpr size_t ArraySize = 1'000'000;
struct X
{
    int    a[ArraySize];
    double b[ArraySize];
    int    c[ArraySize];
};

X my_data;

Каждый элемент по-прежнему легко доступен mydata.a[i] = 5; mydata.b[i] = 1.5f;...,
Заполнений нет (за исключением нескольких байтов между массивами). Расположение памяти подходит для кеша. Prefetcher обрабатывает чтение последовательных блоков памяти из нескольких отдельных областей памяти.

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


Массив структур (AoS), структура массивов

Источник

Это проблема памяти учебника против скорости. Заполнение - обменять память на скорость. Вы не можете сказать:

Я не хочу "упаковывать" мою структуру.

потому что прагма-пачка - это инструмент, изобретенный именно для того, чтобы сделать эту сделку иначе: скорость памяти.

Есть ли надежный кроссплатформенный способ?

Нет, не может быть. Выравнивание строго зависит от платформы. Размер разных типов зависит от платформы. Избегание заполнения путем реорганизации зависит от платформы в квадрате.

Скорость, память и кроссплатформенность - их может быть только два.

Почему компилятор не выполняет такую ​​оптимизацию (меняйте местами члены структуры / класса, чтобы уменьшить заполнение)?

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

Вы предлагаете, чтобы компилятор перемешал их, потенциально нарушая весь код с 1970-х годов. И по какой причине? Можете ли вы гарантировать, что каждый программист когда-нибудь захочет сэкономить 8 байтов на структуру? Я, например, уверен, что если у меня есть массив 3 ГБ, у меня проблемы больше, чем ГБ более или менее.

Источник

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

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

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

Код C может быть непереносимым. Хотя он стремился дать программистам возможность писать действительно переносимые программы, Комитет C89 не хотел заставлять программистов писать переносимо, чтобы исключить использование C в качестве "высокоуровневого ассемблера": способность писать машинный код одна из сильных сторон C.

В качестве небольшого дополнения к этому принципу способность кода, который должен выполняться только на 90% машин, использовать функции, характерные для этих 90% машин, даже если такой код не был бы "машинно-специфичным", является одна из сильных сторон языка C. Идея о том, что программисты на Си не должны отклоняться назад, чтобы приспособиться к ограничениям архитектур, которые десятилетиями использовались только в музеях, должна быть самоочевидной, но, очевидно, нет.

Источник

Вы можете использовать #pragma pack(1), но сама причина этого в том, что компилятор оптимизирует. Доступ к переменной через полный регистр быстрее, чем к младшему биту.

Специальная упаковка полезна только для сериализации и совместимости между компиляторами и т. Д.

Как правильно добавил NathanOliver, на некоторых платформах это может даже не сработать.

Источник
Другие вопросы по тегам