Выравнивание данных в структурах влияет на их размер и скорость доступа к полям. Компилятор вставляет пустые байты (то есть делает выравнивание, padding) между полями или в конце, чтобы адреса полей были кратны их размеру. Это ускоряет чтение, но может увеличить общий размер структуры
Оптимизация - перестановка полей так, чтобы уменьшить количество выравнивающих пропусков. Самые большие типы стоит размещать первыми, затем средние, в конце самые маленькие
Пример плохо выровненной структуры и оптимизированной:
struct Bad {
char a; // 1 байт + 3 байта для выравнивания
int b; // 4 байта
char c; // 1 байт + 1 байт для выравнивания
short d; // 2 байта
};
// sizeof(Bad) = 12
// Оптимизированная перестановка
struct Good {
int b; // 4 байта
short d; // 2 байта
char a; // 1 байт
char c; // 1 байт
};
// sizeof(Good) = 8
Разница возникла из-за того, что int (4 байта) выровнен на границу 4, short (2 байта) на границу 2, char может быть по любому адресу. Правильный порядок убирает лишние пропуски
Ещё одна важная оптимизация - использование порядка обхода данных, дружественного к кэшу процессора. Процессор загружает данные из оперативной памяти блоками (кэш-линиями, обычно 64 байта). Если программа обращается к памяти не последовательно, а с большими шагами, происходят кэш-промахи - данные не находятся в быстрой кэш-памяти, и приходится ждать загрузки из медленной оперативной памяти. Это сильно снижает производительность
Классический пример промахов в кэш - умножение матриц при неправильном порядке циклов. Допустим, матрицы хранятся в памяти построчно, рассмотрим два варианта перемножения C = A * B:
Первый вариант - традиционный i-j-k:
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
for (int k = 0; k < N; ++k)
C[i][j] += A[i][k] * B[k][j];
Здесь обращение к B происходит по столбцам: B[k][j] меняет k быстрее всего, а значит перебор идёт с шагом N элементов между соседними k. При большом N каждая итерация k скорее всего вызывает кэш-промах при доступе к B, потому что следующая строка k+1 находится далеко в памяти. Это очень медленно
Оптимизированный порядок - i-k-j:
for (int i = 0; i < N; ++i)
for (int k = 0; k < N; ++k)
for (int j = 0; j < N; ++j)
C[i][j] += A[i][k] * B[k][j];
Здесь внутренний цикл идёт по j, что даёт последовательное чтение строки B[k] и обновление строки C[i]. Промахи кэша на B практически исчезают, а обращения к A[i][k] - константа на всю внутреннюю петлю, которая остаётся в регистре. Производительность может отличаться в несколько раз
На небольших размерах разница не так заметна, но при N=1000 время выполнения может уменьшиться с секунд до десятых долей секунды
Можно использовать директиву #pragma pack(1) для плотной упаковки, но это может замедлить доступ, потому что поля перестают быть выровненными на естественные границы. Обычно лучше оставить естественное выравнивание и переставить поля
Вот пример, показывающий влияние перестановки полей на размер:
struct A {
char x; // 1 байт + 7 байт выравнивание
double y; // 8 байт
char z; // 1 байт
// + 7 байт в конце для выравнивания
};
// sizeof(A) = 24
struct B {
double y; // 8 байт
char x; // 1 байт
char z; // 1 байт
// + 6 байт в конце для выравнивание
};
// sizeof(B) = 16
Использование ключевого слова alignas или __attribute__((aligned)) может принудительно менять выравнивание, но это нужно для особых случаев, например, для SSE/AVX инструкций, где данные должны быть выровнены на 16 или 32 байта
Разберём два способа организации коллекции объектов в памяти: массив структур (AoS, Array of Structures) и структура массивов (SoA, Structure of Arrays). Оба подхода влияют на производительность из-за особенностей работы кэша и векторных инструкций
Массив структур заключается в объявлении структуры, содержащей все поля объекта, и массива таких структур. Все данные одного объекта лежат рядом в памяти
struct Particle {
float x, y, z;
float vx, vy, vz;
int health;
};
Particle particles[1000];
Когда процессор загружает в кэш одну частицу, в кэш-линию попадают сразу все её поля: координаты, скорости, здоровье. Это отлично подходит, если программа обрабатывает частицу целиком. Но если нужно часто обновлять только координату x всех частиц, то вместе с x в кэш загружаются и y, z, vx, vy, vz, health, которые сейчас не нужны. Кэш забивается бесполезными данными, полезных данных помещается меньше, чаще происходят промахи
Структура массивов меняет представление: каждое поле объекта хранится в отдельном массиве. Все частицы по-прежнему существуют как единое целое, но физически разнесены
struct Particles {
float x[1000];
float y[1000];
float z[1000];
float vx[1000];
float vy[1000];
float vz[1000];
int health[1000];
};
Теперь при обходе x для всех частиц процессор загружает только массив x, и каждая кэш-линия целиком заполнена нужными координатами. Промахов становится значительно меньше, данные используются максимально эффективно
Важные различия и когда что применять:
particles[i].x = 5.0f выглядит естественно. Подходит для ситуаций, когда объекты обрабатываются целиком (сериализация, создание и удаление)x одновременно в SSE-регистр, потому что они лежат подрядx += vx * dt, y += vy * dt одновременно, и массив структур даст локальностьstruct Vec3 { float x,y,z; }; Vec3 pos[N]; Vec3 vel[N];), частично совмещая преимущества