Приветствую всех, кто хочет делать свой код быстрым и оптимальным. Традиционно, если нам нужно большое количество объектов какого-то класса, мы создаем массив этих объектов. Однако, каким бы простым и очевидным не казался данный подход, он не всегда эффективен. Рассмотрим плюсы и минусы каждого из подходов к размещению большого числа объектов в памяти, их область применения и, конечно же, рассмотрим их на примерах.
Цикл "Принципы DOD в C++"
О чем речь?
В прошлой части мы научились упаковывать структуру, исходя из явления выравнивания. Однако, в большинстве случаев этого оказывается недостаточно. Причина — даже идеально упакованная структура тащит в кэш-линию все свои поля, даже если нам прямо сейчас нужно только одно.
Последствия оценить весьма просто — кэш-линия забита лишними данными, и на чтение данных структур, которые нужно обработать, уходит гораздо больше времени. И всё было бы хорошо, если нам нужна только пара-тройка объектов структуры. А если нам нужен миллион/миллиард таких структур, причем каждую долю секунды с ними что-то происходит? Возникает проблема с быстродействием программы из-за большого объема данных.
Как же это решить? Какие подходы к этому существуют? ��ассмотрим далее.
AoS — Array of Structures
Дадим краткое определение. Array of Structures — массив, где каждый элемент это структура со всеми полями. Стандартный подход, который все программисты на C++ пишут по умолчанию.
Сразу приведем пример, как это выглядит, в виде структуры, описывающей частицу в физическом движке:
struct Particle { float x, y, z; // Координаты по трем осям float vx, vy, vz; // Скорости по трем осям float ax, ay, az; // Ускорения по трем осям }; std::vector<Particle> particles(N);
В общем, традиционный подход к хранению большого количества структур. В этом случае, физически данные в памяти лежат следующим образом:[x0 y0 z0 vx0 vy0 vz0 ax0 ay0 az0] [x1 y1 z1 vx1 vy1 vz1 ax1 ay1 az1] [x2 y2 z2 ...]
Каждый цикл обновления физического движка мы что-то делаем с этими структурами-частицами: обновляем координаты/скорости. И всё было бы хорошо, если бы мы всегда взаимодействовали со всеми полями структуры. Однако, в 99% случаев это не так: порой, нам нужно изменить скорости, никак не затрагивая позиции, и наоборот. Или вообще поменять значение только одного/двух полей из шестерых.
В таком случае AoS-подход ведет к весьма ощутимому снижению производительности: вместо того, чтобы в кэш грузились только поля, с которыми идет взаимодействие в текущий момент, в кэш грузятся целые структуры!
Приведем пример такого явления:
void ApplyGravity() { for (auto& particle : particles) { particle.ay = 9.81; } }
Функция взаимодействует только с одними данными, ускорением частицы по вертикальной оси. Однако, в кэш вместо лишь 4 байт, которые составляет это поле, грузится целых 36 байт (размер структуры)! Разница в объеме данных — в 9 раз.
Как же решить данную проблему? Воспользуемся подходом разделения данных под названием hot/cold splitting.
Hot/cold splitting
Вкратце, hot/cold splitting — это идея разделения данных на основе частоты обращения, а не размера.
В качестве примера из реального мира сравним с тем, чем каждый из нас пользуется каждый день — с магазином.
То, как продукты любезно расставлены сотрудниками магазина, имеет под собой совершенно четкое обоснование — не стоит мешать в кучу нужное и не совсем нужное. Вместо этого самые необходимые и пользующиеся спросом товары помещают ближе к путям обхода магазина покупателями, чтобы покупателям было легче и быстрее их взять. А остальное уже куда-нибудь вдаль, вдруг возьмут.
Ровно то же самое мы применяем и к структурам/классам. Магазин это RAM, товары это данные, а покупатель — часть программы, нуждающаяся в определенных данных. Напишем код, иллюстрирующий данный подход:
// "Горячие" данные — нужны каждый кадр struct ParticleHot { float x, y, z; float vx, vy, vz; }; // "Холодные" данные — нужны редко struct ParticleCold { float ax, ay, az; }; // Два параллельных ��ассива с общим индексом std::vector<ParticleHot> particles_hot(N); std::vector<ParticleCold> particles_cold(N); // Горячий цикл — итерируем только hot-массив for (size_t i = 0; i < N; ++i) { particles_hot[i].x += particles_hot[i].vx; particles_hot[i].y += particles_hot[i].vy; particles_hot[i].z += particles_hot[i].vz; } // Когда нужны холодные данные — обращаемся по тому же индексу particles_cold[some_index].ay = -9.81f;
Поясню. ParticleHot — 24 байта. В одну кэш-линию влезает 2.66 структуры. Для сравнения, исходная Particle (36 байт) — 1.77 структуры на кэш-линию. Утилизация кэша в горячем цикле выросла, потому что мы больше не тащим ускорения, которые в данный момент не нужны.
Hot/cold splitting уже даёт ощутимый эффект. Но обратим внимание: мы разделили структуру на две группы — "горячую" и "холодную". А что, если пойти дальше? Что, если внутри "горячей" части нам всё равно не нужны все поля одно��ременно — например, мы обновляем только координаты, не трогая скорости? Тогда даже ParticleHot тащит в кэш лишние данные.
Если довести эту идею до предела и вынести каждое поле в свой отдельный массив, мы получим подход под названием Structure of Arrays (SoA).
SoA — Structure of Arrays
Обозначим определение. Structure of Arrays — это когда каждое поле хранится в своём отдельном массиве. Сразу приведем пример, чтобы было понятнее:
struct Particles { std::vector<float> x, y, z; // Координаты по трем осям std::vector<float> vx, vy, vz; // Скорости по трем осям std::vector<float> ax, ay, az; // Ускорения по трем осям };
Хорошо, сделали. Теперь визуализируем расположение данных в памяти:
x: [x0 x1 x2 x3 x4 x5 x6 x7 ...] y: [y0 y1 y2 y3 y4 y5 y6 y7 ...] z: [z0 z1 z2 z3 z4 z5 z6 z7 ...] vx: [vx0 vx1 vx2 vx3 vx4 vx5 vx6 vx7 ...]и так далее
Заметили разницу? Теперь в функции ApplyGravity() для ay = 9.81 процессор читает только массив ay, не захватывая не нужные в данном контексте данные x, y, z, vx...
Однако, пока это голословные заявления. В качестве доказательства создадим бенчмарк в виде трех сценариев в конфигурации Release:
Сценарий 1: линейный обход, обновление одного поля;
Сценарий 2: линейный обход, обновление всех полей;
Сценарий 3: random access. Доступ к случайному элементу.
Benchmark, сценарий 1. Линейный обход, обновление одного поля
Создадим две структуры-частицы для сравнения AoS и SoA между собой, а также вспомогательную функцию Resize для выделения и заполнения векторов n элементами:
// AoS struct ParticleAoS { float x, y, z; float vx, vy, vz; float ax, ay, az; }; // SoA struct ParticlesSoA { std::vector<float> x, y, z; std::vector<float> vx, vy, vz; std::vector<float> ax, ay, az; void Resize(int n) { x.resize(n, 0.0f); y.resize(n, 0.0f); z.resize(n, 0.0f); vx.resize(n, 1.0f); vy.resize(n, 1.0f); vz.resize(n, 1.0f); ax.resize(n, 0.0f); ay.resize(n, 0.0f); az.resize(n, 0.0f); } };
Далее, напишем функции для бенчмарка первого сценария и запустим бенчмарк:
// Сценарий 1: линейный обход, обновление одного поля (x += vx) static void BM_AoS_SingleField(benchmark::State& state) { const int n = state.range(0); std::vector<ParticleAoS> particles(n); for (auto& p : particles) { p.x = 0.0f; p.vx = 1.0f; } for (auto _ : state) { for (auto& p : particles) { p.x += p.vx; } benchmark::ClobberMemory(); } } static void BM_SoA_SingleField(benchmark::State& state) { const int n = state.range(0); ParticlesSoA particles; particles.Resize(n); for (auto _ : state) { for (int i = 0; i < n; ++i) { particles.x[i] += particles.vx[i]; } benchmark::ClobberMemory(); } } BENCHMARK(BM_AoS_SingleField)->Range(10000, 1000000); BENCHMARK(BM_SoA_SingleField)->Range(10000, 1000000); BENCHMARK_MAIN();
В целях наглядности не буду приводить таблицу результатов бенчмарка, а сделаю график на основании их. Он выглядит так:
Подведем итоги первого сценария:
На всех тестируемых количествах частиц SoA быстрее, чем AoS;
На количествах частиц до миллиона SoA быстрее AoS в среднем в 4 раза, в то время как на миллионе частиц SoA быстрее AoS уже в 12 раз.
Рассмотрим причины этих результатов:
Утилизация кэша.
ParticleAoS— 9 float'ов = 36 байт. При обновлении одного поля (x += vx) мы используем только 8 байт из 36. Остальные 28 байт —y, z, vy, vz, ax, ay, az— загрузились в кэш-линию, но не пригодились. Утилизация кэша: 8/36 ≈ 22%.
В SoA массивыxиvxлежат отдельно и плотно. Каждый загруженный байт используется. Утилизация — 100%. В одну кэш-линию (64 байта) влезает 16 float'ов из массиваx. В AoS — 1.77 структуры, из которых полезны только 2 float'а на структуру. Но разница в утилизации ~4.5 раза, а реальный разрыв ~12 раз. Откуда остальная прибавка к производительности? Причина кроется в так называемом SIMD.Автовекторизация (SIMD). Более подробно SIMD мы будем рассматривать в следующих статьях, сейчас же достаточно просто знать, что компилятор в Release-режиме умеет автоматически превращать простые циклы по плотным массивам в SIMD-инструкции, что оптимизирует и ускоряет операции с векторами. Цикл
x[i] += vx[i]по непрерывному массиву float'ов — идеальный кандидат для SIMD, поскольку данные векторов лежат непрерывно. В AoS-вариантеxиvxлежат с шагом 36 байт — компилятор не может векторизовать такой цикл, потому что данные не непрерывны.
Хорошо, первый сценарий завершен. Перейдем ко второму.
Benchmark, сценарий 2. Линейный обход, обновление всех полей
Оставим AoS и SoA структуры из первого сценария и используем во втором, а затем напишем сам код для симуляции сценария и запустим:
// Сценарий 2: линейный обход, обновление всех полей static void BM_AoS_AllFields(benchmark::State& state) { const int n = state.range(0); std::vector<ParticleAoS> particles(n); for (auto& p : particles) { p.x = 0.0f; p.y = 0.0f; p.z = 0.0f; p.vx = 1.0f; p.vy = 1.0f; p.vz = 1.0f; p.ax = 0.1f; p.ay = -9.81f; p.az = 0.0f; } for (auto _ : state) { for (auto& p : particles) { p.vx += p.ax; p.vy += p.ay; p.vz += p.az; p.x += p.vx; p.y += p.vy; p.z += p.vz; } benchmark::ClobberMemory(); } } static void BM_SoA_AllFields(benchmark::State& state) { const int n = state.range(0); ParticlesSoA particles; particles.Resize(n); for (auto _ : state) { for (int i = 0; i < n; ++i) { particles.vx[i] += particles.ax[i]; particles.vy[i] += particles.ay[i]; particles.vz[i] += particles.az[i]; particles.x[i] += particles.vx[i]; particles.y[i] += particles.vy[i]; particles.z[i] += particles.vz[i]; } benchmark::ClobberMemory(); } } BENCHMARK(BM_AoS_AllFields)->Range(10000, 1000000); BENCHMARK(BM_SoA_AllFields)->Range(10000, 1000000); BENCHMARK_MAIN();
Построим график ровно как и в первом сценарии:
Результаты уже не такие очевидные. Снова сделаем выводы по получившимся значениям и по графикам:
SoA все еще имеет преимущество (кроме момента кол-ва частиц 262144), но уже не такое выраженное.
В среднем разница в производительности составляет ~6% против ~76% в первом сценарии, а на количестве частиц в 262144 вообще составляет 1%, что говорит о снижении эффективности преимуществ SoA по сравнению с AoS.
Проанализируем полученные результаты. Откуда взялось такое ухудшение производительности SoA подхода? Или всё же это, наоборот, увеличение быстродействия AoS?
Утилизация кэша. Теперь AoS не проигрывает. В первом сценарии AoS тратил ~76% пропускной способности впустую. Теперь мы обращаемся ко всем 9 полям — используем все 36 байт каждой структуры. Утилизация кэша в AoS стала 100%. Преимущество SoA по кэшу исчезло. Более того, в AoS все 9 полей одной частицы лежат в пределах 36 байт — одна-две кэш-линии, один линейный поток данных. Prefetcher, который параллельно с вычислениями загружает из RAM данные, которые, по его предсказанию, понадобятся в ближайшем будущем, справляется идеально.
В SoA теперь считывается и пишется 9 отдельных массивов в одном цикле. Это 9 независимых потоков данных. Prefetcher может отслеживать порядка 8-16 потоков — он на пределе. Это уже не идеальные условия для SoA.Автовекторизация (SIMD). SoA всё ещё имеет потенциал, но он ограничен. Компилятор всё ещё может векторизовать операции над плотными SoA-массивами. Но теперь в цикле 6 операций сложения с 9 массивами. Регистров процессора ограниченное количество, и компилятору сложнее построить эффективный SIMD-код, когда нужно одновременно работать с таким количеством потоков данных одновременно.
По итогу, получаем небольшое, в ~6%, преимущество SoA, иногда переходящее в паритет. Перейдем, наконец, к третьему сценарию, чтобы сделать окончательный вывод по эффективности SoA.
Benchmark, сценарий 3. Random access. Доступ к случайному элементу.
Теперь напишем код для доступа к случайным элементам. Создадим отдельный вектор для индексов и перемешаем его с помощью генератора псевдослучайных чисел. Затем пройдемся по всем частицам, используя этот вектор индексов в качестве идентификаторов, и просуммируем все элементы частиц, чтобы компилятор не оптимизировал чтения полей:
// Сценарий 3: random access, чтение всех полей static void BM_AoS_RandomAccess(benchmark::State& state) { const int n = state.range(0); std::vector<ParticleAoS> particles(n); for (auto& p : particles) { p.x = 1.0f; p.y = 2.0f; p.z = 3.0f; p.vx = 1.0f; p.vy = 1.0f; p.vz = 1.0f; p.ax = 0.1f; p.ay = -9.81f; p.az = 0.0f; } std::vector<int> indices(n); // Создаем вектор индексов std::iota(indices.begin(), indices.end(), 0); // Заполняем вектор индексов std::mt19937 rng(42); // Создаем генератор псевдослучайных чисел std::shuffle(indices.begin(), indices.end(), rng); // Перемешиваем вектор индексов for (auto _ : state) { float sum = 0.0f; for (int idx : indices) { auto& p = particles[idx]; sum += p.x + p.y + p.z + p.vx + p.vy + p.vz + p.ax + p.ay + p.az; } benchmark::DoNotOptimize(sum); } } static void BM_SoA_RandomAccess(benchmark::State& state) { const int n = state.range(0); ParticlesSoA particles; particles.Resize(n); std::vector<int> indices(n); // Создаем вектор индексов std::iota(indices.begin(), indices.end(), 0); // Заполняем вектор индексов std::mt19937 rng(42); // Создаем генератор псевдослучайных чисел std::shuffle(indices.begin(), indices.end(), rng); // Перемешиваем вектор индексов for (auto _ : state) { float sum = 0.0f; for (int idx : indices) { sum += particles.x[idx] + particles.y[idx] + particles.z[idx] + particles.vx[idx] + particles.vy[idx] + particles.vz[idx] + particles.ax[idx] + particles.ay[idx] + particles.az[idx]; } benchmark::DoNotOptimize(sum); } } BENCHMARK(BM_AoS_RandomAccess)->Range(10000, 1000000); BENCHMARK(BM_SoA_RandomAccess)->Range(10000, 1000000); BENCHMARK_MAIN();
Визуализируем полученные результаты.
Ого, уже что-то интересное! Ситуация повернулась на 180 градусов: теперь AoS быстрее SoA в среднем в 1,6 раза, то есть на ~35%. Откуда это взялось?
Random access убивает prefetcher. Обращения идут по случайным индексам, никакого паттерна нет, префетчеру предсказывать нечего. Каждое обращение к новому индексу — это гарантированный кэш-промах. И вот тут разница между AoS и SoA становится критичной.
В AoS все 9 полей частицы лежат в одном блоке 36 байт. Когда мы обращаемся к particles[idx], процессор загружает одну кэш-линию (64 байта) — и все 9 полей уже в кэше. Один промах — и все данные доступны.
В SoA обращение к particles.x[idx] загружает кэш-линию из массива x. Потом particles.y[idx] — промах, потому что массив y лежит в совершенно другом месте памяти. Потом particles.z[idx] — снова промах. И так для каждого из 9 массивов. Итого: 9 кэш-промахов на одну частицу вместо одного.
При этом из каждой загруженной кэш-линии используется только один float (4 байта из 64). Утилизация — 6%. Остальные 15 float'ов в кэш-линии — это значения x соседних частиц, но следующий индекс случайный, и эти соседние значения не пригодятся.
Итоги исследования. Что же лучше?
Скажу сразу — победителя нет и не будет. SoA не панацея для оптимального хранения данных, а лишь ситуативный метод их хранения, ровно как и AoS. Каждый из методов эффективен в разных случаях. Давайте же попробуем расписать эту "карту" для выбора, что использовать в каждом случае — AoS или SoA. Основной критерий: быстродействие.
Если доступ производится только к части полей структуры одновременно, используем SoA;
Если доступ производится ко всем или почти ко всем полям структуры одновременно, предпочтительнее AoS, если нету других причин для SoA;
Если доступ производится по случайным индексам, не имеющим какого-либо паттерна адресов, который может определить prefetcher, используем AoS.
Также стоит упомянуть, что кром�� фактора производительности существуют множество других факторов: удобство разработки, удобство поддержки, удобство изменения, удобство расширения, читабельность и так далее. Они также могут влиять на выбор метода в данной конкретной ситуации.
Моё субъективное мнение — AoS легче в плане удобства, поскольку код для взаимодействия менее объемен и более структурирован. Приведу пример кода для добавления объекта в AoS и в SoA:
// Попробуем добавить частицу в AoS particles.push_back(new_particle); // Попробуем добавить частицу в SoA particles.x.push_back(0.0f); particles.y.push_back(0.0f); particles.z.push_back(0.0f); particles.vx.push_back(1.0f); particles.vy.push_back(1.0f); particles.vz.push_back(1.0f); particles.ax.push_back(0.0f); particles.ay.push_back(0.0f); particles.az.push_back(0.0f);
Код более многословен для SoA. Понятно, что можно вынести такие вещи в отдельный метод, например, но факт есть факт. Однако, тут, думаю, уже каждый решит для себя сам.
Что дальше?
В следующей статье рассмотрим AoSoA и SIMD, которые в совокупности могут нивелировать некоторые негативные особенности изученных нами сценариев и еще сильнее увеличить производительность программы.
Спасибо за внимание! Если Вам нравится мое творчество, ставьте лайк и подписывайтесь на мой блог, чтобы не пропустить новых исследований :-)
Если у Вас есть какие-либо комментарии, замечания или просто идеи, пишите в комментарии или в ЛС. Буду рад обсудить.
