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

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

53 голосов
/ 25 июня 2019

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

Я только что понял, сколько памяти тратится впустую в результате выравнивания в 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 X с 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.То есть я не хочу, чтобы его члены были выровнены и, следовательно, доступ к ним был медленнее.Вместо этого я по-прежнему хочу, чтобы все члены были выровнены самостоятельно, но таким образом, чтобы при заполнении использовалось меньше всего памяти.Эту проблему можно решить, используя, например, ручную перестановку, как описано здесь и в The Lost Art of Packing Эрика Реймонда.Я ищу автоматизированный и максимально кроссплатформенный способ сделать это, аналогично тому, что описано в предложении P1112 для грядущего стандарта C ++ 20.

Ответы [ 7 ]

34 голосов
/ 26 июня 2019

(Не применяйте эти правила, не задумываясь. См. Замечание 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 с. Но это не плохое предположение, так что я бы сделал это в любом случае, если бы была какая-то причина (например, пространственное расположение элементов, к которым осуществляется доступ) для их объединения, а не в конце.

Экзотические типы : 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, так что спасибо за эту отправную точку.)

32 голосов
/ 25 июня 2019

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;), поэтому их нельзя переставить.

15 голосов
/ 25 июня 2019

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

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

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

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

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

5 голосов
/ 28 июня 2019

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), Структура массивов

4 голосов
/ 26 июня 2019

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

Я не хочу «упаковать» свою структуру.

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

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

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

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

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

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

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

3 голосов
/ 26 июня 2019

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

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

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

Код

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

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

0 голосов
/ 25 июня 2019

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

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

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

...