Приветствую всех, кто хочет делать свой код быстрым и оптимальным. В этой статье мы расссмотрим несколько простых способов, как можно оптимизировать программу при работе со структурами.
Размещение данных в памяти. L1, L2, L3 кэши и RAM
Мы все знаем, что данные (переменные, поля классов и т.д.) размещаются в "памяти". Но зачастую программист даже не задумывается, что именно представляет из себя эта абстрактная "память". Давайте рассмотрим этот вопрос чуть глубже, посколько понимание этого позволит ускорить код на двузначное число процентов.
Память компьютера не состоит полностью из RAM и файлов, она также имеет так называемые L1, L2 и L3 кеши. Не будем погружаться в их устройство и реализацию, для нас важен тот факт, что они гораздо быстрее оперативной памяти.
Но за высокую скорость работы с кэшами присутствует плата в виде их ограниченного размера. Он варьируется в зависимости от модели процессора, то примерный размер и скорость работы кешей такие:
L1: объем около 100Кб, скорость 2-3 такта (быстрее RAM в 16-100 раз);
L2: объем около 500Кб, скорость 3-5 тактов (быстрее RAM в 10-66 раз);
L3: объем около 10-15Мб, скорость 30-50 тактов (быстрее RAM в 1-6.6 раз).
Кэш-линия и кэш-промах
Однако, в эти кэши наши данные из RAM попадают не каким-то секретным магическим способом, а с помощью чтения процессором ОЗУ блоками, так называемыми, кэш-линиями. На современных архитектурах x86/x64 размер одной кэш-линии обычно составляет 64 байта.
То есть, если процессору необходимо прочитать переменную размером 1 байт из RAM, он не будет читать строго 1 байт, он прочитает кэш-линию размером 64 байта.
И вот тут начинается самое интересное для нас, программистов на C++. Если нужные нам данные лежат в памяти плотно (внутри этих 64 байт), процессор обработает их мгновенно. Если они разбросаны — мы получим Cache Miss (кэш-промах), и процессор остановится на сотню-другую тактов, ожидая следующую кэш-линию из RAM.
Тем не менее, это еще не всё. Процессору ещё надо доставить данные из кэшей в регистры для совершения вычислений.
Машинное слово
Не будем углубляться в устройство процессора. Нам достаточно знать, что данные из кэшей в регистры читаются уже не кэш-линией по 64 байта, а машинным словом, размер которого зависит от разрядности регистров процессора (либо 32 бита, либо 64 бита). Данная особенность строгого чтения "по сетке" создает два возможных сценария при чтении данных в регистры:
Хороший сценарий. Если размер машинного слова позволяет полностью вместить в себя данные, никаких плохих событий не происходит, задержки отсутствуют.
Плохой сценарий. Если размер машинного слова не позволяет полностью вместить в себя данные, процессор проделывает несколько очень трудозатратных операций: ему придется прочитать 2 машинных слова, а затем "склеить" их с помощью битовых сдвигов. Пример: int занимает 1 байт из одного машинного слова и 3 байта из следующего.
Чтобы не происходило плохого сценария, в языках программирования присутствуют встроенные инструменты, предотвращающие это. Мы же рассмотрим C++.
C++. Выравнивание, паддинг. "Мусор" на ровном месте
В C++ для исключения случая, описанного выше, созданы так называемые паддинг (padding) и выравнивание (alignment). Их формальные определения Вы можете прочитать на профессиональных ресурсах по C++, но я в данной статье хотел бы рассмотреть работу с ними на практике.
Напишем простую структуру, в которой поля расставлены в произвольном порядке (спойлер: в наихудшем возможном):
struct BadStruct { bool active; // 1 байт double position; // 8 байта int id; // 4 байта bool is_liquid; // 1 байт int energy; // 4 байта };
С первого взгляда кажется, что структура будет занимать 18 байт. Но если мы сделаем sizeof(BadStruct), результат будет, мягко скажем, не совсем таким:
std::cout << sizeof(BadStruct); 32
32 байта вместо 18, разница в целых 44%! Почему так, откуда такой большой размер? В этом замешано то самое машинное слово и вытекающее из него выравнивание.
Для предотвращения неполного расположения данных в машинном слове при чтении данных в регистры в C++ введено "правило выравнивания": адрес переменной в памяти должен быть кратен её размеру. Например, тип int (4 байта) может лежать только по адресам 0, 4, 8, 12 и так далее. Тип double (8 байт) — по адресам 0, 8, 16.
Если компилятор видит, что следующее поле не попадает на кратный адрес, он вставляет пустые байты — тот самый паддинг. Рассмотрим его влияние на размер нашей структуры, проследив за каждым байтом:
bool active(1 байт) — занимает байт с адресом0.double position(8 байт) — по правилу должен лежать на адресе, кратном 8. Ближайший такой адрес —8. Поэтому компилятор вставляет 7 байт мусора (адреса с 1 по 7).int id(4 байта) — ложится на адреса16..19. Адрес 16 кратен 4, тут всё идеально.bool is_liquid(1 байт) — занимает адрес20.int energy(4 байта) — требует адрес, кратный 4. Ближайший —24. Компилятор снова вставляет 3 байта мусора (адреса 21–23), чтобы сдвинутьint.
Наши данные и внутренний мусор закончились на 27-м байте (текущий размер — 28 байт). Но почему sizeof выдал 32?
Здесь вступает в игру неочевидное правило хвостового выравнивания. Размер всей структуры обязан быть кратен выравниванию самого большого её поля. У нас это double (8 байт). Ближайшее к 28 число, кратное 8 — это 32.
Поэтому компилятор добавляет еще 4 байта мусора в самый конец. Это делается для того, чтобы в массиве таких структур (BadStruct array[2]) второй элемент тоже начался с «правильного» адреса, кратного 8.
Как же это решить? Ответ простой — изменить порядок полей структуры по убыванию размера. Перепишем по этому принципу нашу структуру.
struct GoodStruct { double position; // 8 байт int id; // 4 байта int energy; // 4 байта bool active; // 1 байт bool is_liquid; // 1 байт };
Снова выясним ее размер:
std::cout << sizeof(GoodStruct); 24
Невероятно — простой перестановкой полей мы добились уменьшения размера структуры в памяти на целых 25%! Но, чтобы не быть голословными, подтвердим теоретические выводы практическими доказательствами.
C++. Цена паддинга. Бенчмарки
Напишем простой тест производительности наших "плохой" и "хорошей" структур с использованием Google Benchmark. Суть теста заключается в итерировании по массиву из 1000000 структур и простой математической операции прибавки единицы к полю position.
Тест для массива BadStruct:
static void BM_BadStructIteration(benchmark::State& state) { std::vector<BadStruct> data(state.range(0)); for (auto _ : state) { for (auto& item : data) { if (item.active) { benchmark::DoNotOptimize(item.position += 1.0); } } benchmark::ClobberMemory(); } }
Тест для массива GoodStruct:
static void BM_GoodStructIteration(benchmark::State& state) { std::vector<GoodStruct> data(state.range(0)); for (auto _ : state) { for (auto& item : data) { if (item.active) { benchmark::DoNotOptimize(item.position += 1.0); } } benchmark::ClobberMemory(); } }
Примечание: benchmark::DoNotOptimizeдобавлен, чтобы умный компилятор не вырезал наш цикл (Dead Code Elimination).
Запускаем тесты и инициализируем программу:
BENCHMARK(BM_BadStructIteration)->Range(10000, 1000000); BENCHMARK(BM_GoodStructIteration)->Range(10000, 1000000); BENCHMARK_MAIN();
Таким образом, результаты работы программы следующие:
------------------------------------------------------------------------- Benchmark Time CPU Iterations ------------------------------------------------------------------------- BM_BadStructIteration/10000 4011 ns 4011 ns 165946 BM_BadStructIteration/32768 13408 ns 13407 ns 50500 BM_BadStructIteration/262144 107153 ns 107146 ns 6240 BM_BadStructIteration/1000000 940122 ns 939709 ns 1013 BM_GoodStructIteration/10000 4230 ns 4226 ns 169877 BM_GoodStructIteration/32768 14302 ns 14302 ns 48910 BM_GoodStructIteration/262144 119729 ns 119669 ns 6144 BM_GoodStructIteration/1000000 579492 ns 579507 ns 1103
Столбец Iterations показывает, сколько раз библиотека Google Benchmark прогнала наш цикл для сбора статистически достоверных данных. Быстрые тесты (на 10 000 элементов) прогонялись более 160 тысяч раз, а тяжелые (на миллион) — около тысячи. Время в столбцах Time и CPU — это среднее время за одно выполнение функции.
Сложновато интерпретировать результаты в таком виде, не правда ли? Переведем их в графики для наглядности.
Что мы видим? Результаты нелинейны, неравномерны. До 262144 итераций разница во времени минимальна, но на 1000000 итераций она уже составляет 38%! В чем причина данного явления?
Всё просто — причина в объеме данных. Массив плохих структур из 10000 и 32768 элементов с размерами спокойно влезает в кэш, 312.5Кб и 1024Кб соответственно. Но, когда количество элементов становится больше 262144 (объем 8192Кб), место в кэше L3 постепенно начинает заканчиваться, что вынуждает размещать данные уже в медленной RAM. Тут в дело вступает кэш-линия.
Вспомним про кэш-линию в 64 байта:
Размер
BadStruct— 32 байта. В одну кэш-линию влезает ровно 2 структуры. Чтобы обработать миллион элементов, процессору нужно сделать 500 000 запросов к оперативной памяти.Размер
GoodStruct— 24 байта. В одну кэш-линию влезает 2.66 структуры. Чтобы обработать миллион элементов, процессору нужно сделать всего около 375 000 запросов.
Понимаете, что произошло? Мы на четверть сократили количество обращений к самой медленной памяти компьютера, просто отсортировав переменные в классе от больших к меньшим. Никаких изменений в логике, никаких сложных алгоритмов — чистый Data-Oriented Design.
Примечание: почему мы считаем чтение из RAM для всего миллиона элементов? Разве часть не осядет в кэше L3? Осядет, но ненадолго. Размер массива превышает размер кэша процессора. Пока процессор дойдет до конца миллионного массива, начало массива уже будет вытеснено (cache eviction) из кэша. При следующей итерации бенчмарка всё придется тянуть из RAM заново.
Заключение
В этой части "принципов DOD" мы рассмотрели простой способ оптимизации размера структур, протестировали реальное его влияние на производительность, а также изучили, почему же это так происходит.
TL;DR Располагаем поля структур/классов от большего к меньшему и всё будет хорошо.
В следующей части мы пойдем дальше и рассмотрим паттерны AoS (Array of Structures) и SoA (Structure of Arrays), которые позволят нам выжимать из процессора еще больше производительности, например, при разработке физических движков и сложных симуляций.
Спасибо за внимание, пишите быстрый код в свое удовольствие!
