Ответ 1

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

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

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

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

• int64_t всегда 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, что делает массивы возможными без нарушения гарантии выравнивания.

И вообще, становится сложнее, когда ваши члены структуры сами являются агрегатами (struct или union) с 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] ([-128.. +127]). Так что, если у вас есть большой массив любого вида, предпочтите поместить его позже в структуру после часто используемых членов. Даже если это стоит немного набивки.

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

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

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

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

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

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

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

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

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

Ответ 2

У 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 (но я бы не стал его -Wpadded вообще, поскольку иногда требуется заполнение).

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

Ответ 3

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

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

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

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

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

Ответ 4

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

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

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

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

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

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

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

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

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

Ответ 5

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

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

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

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

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

Ответ 6

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

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

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

Ответ 7

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

#include <type_traits>
#include <iostream>
#include <algorithm>

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


int main()
{
    const std::size_t TOTAL_SIZE = sizeof(int) + sizeof(double) + sizeof(int);
    // const std::size_t MAX_ALIGNMENT = std::max(alignof(double), alignof(int));
    const std::size_t MAX_ALIGNMENT = alignof(X); //probably a better approach than above

    std::aligned_storage<TOTAL_SIZE, MAX_ALIGNMENT>::type buffer;
    X* pX = new(static_cast<void*>(&buffer)) X;

    std::cout << "but sizeof(buffer) = "  << sizeof(buffer)  << std::endl;
    pX->a = 10;
    pX->b = 12334.5353;
    pX->c = 44;

    std::cout << pX->a << "\t" << pX->b << "\t" << pX->c << std::endl;

    return 0;
}

delete нет, потому что Placement-New обрабатывает распределение, так что это происходит в стеке (buffer является переменной стека). Кроме того, что-то более сложное должно быть передано в качестве параметров шаблона, некоторые вычисления во время компиляции желаемого размера буфера и выравнивания (если честно, то, где я не совсем уверен в себе).... и, возможно, вам придется использовать такие типы, как int16_t, и, возможно, вам лучше переупорядочить члены структуры с учетом всех соображений, которые уже были предложены по этому поводу.

Но основная идея такова.

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

Ответ 8

Я бы долго смотрел на "Потерянное искусство упаковки конструкций" (или сразу переходил к переупорядочению структуры).

Если кто-то хочет получить ответ SO на основе содержимого, добро пожаловать.

Ответ 9

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

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

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