Почему важно оптимизировать формат данных

Если вам нужно повысить скорость вашей программы, то первым делом логично будет вспомнить курс по структурам данных и оптимизировать алгоритмическую сложность.
Алгоритмы — важнейшая часть программы: замена «горячего» алгоритма O(n) менее сложным, например, O(log n), обеспечивает практически произвольное увеличение производительности. Однако существенно влияет на производительность и структурированность данных: программы выполняются на физических машинах с физическими свойствами, например, разными задержками чтения/записи данных в кэши, на диски или в ОЗУ. После оптимизации алгоритмов стоит изучить эти свойства, чтобы достичь наибольшей производительности. Оптимизированный формат данных учитывает используемые алгоритмы и паттерны доступа при выборе того, как сохранять структуру данных на физическом носителе. Благодаря этому можно увеличить скорость алгоритмов в несколько раз. В этом посте мы покажем пример, в котором нам удалось достичь четырёхкратного повышения скорости чтения простым изменением формата данных в соответствии с паттерном доступа.

Сравнение хранилищ данных AoS и SoA

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

Простой и интуитивно понятный формат данных хранит полную запись по каждому сотруднику в смежной памяти, называемой массивом структур (Array of Structures, AoS). Это упрощает работу с отдельными сотрудниками, поскольку вся их информация упакована вместе и может быть получена при помощи одной операции доступа к [i] массива. Формат структуры массивов (Structure of Arrays, SoA) выделяет поля в отдельные массивы. Каждый массив содержит конкретный атрибут для всех сотрудников. В этом случае все идентификаторы сгруппированы в одном смежном пространстве памяти, после них идут все имена, а затем и все зарплаты.

Пример разбиения данных сотрудников на AoS и SoA

Чтобы понять, как разные форматы данных влияют на производительность, мы воспользуемся простой программой на C++ и проведём разные эксперименты. В процессе этих экспериментов мы проанализируем время исполнения программы с разными форматами данных, чтобы разобраться в преимуществах и недостатках каждого формата. Ниже показан код примера реализации AoS и SoA.

#include <array> #include <vector> #include <cstdint> // ---------------------------------------------------------------------------- using series = uint64_t; using decimal = uint64_t; // ---------------------------------------------------------------------------- // Сохраняем все элементы строки последовательно в памяти struct Employee {     series id;     decimal salary;     std::array<char, 16> firstname; }; // Вектор — это наращиваемый массив данных, каждый элемент которого — полная строка struct ArrayOfStruct {     std::vector<Employee> table; }; // ---------------------------------------------------------------------------- // Сохраняем один и тот же столбец последовательно в памяти struct StructOfArrays {     std::vector<series> id;     std::vector<decimal> salary;     std::vector<std::array<char, 16>> firstname; }; // ----------------------------------------------------------------------------

В формате AoS мы определяем struct для сотрудника, содержащую все необходимые поля: id, имя и зарплату. Затем мы создаём вектор (то есть массив с изменяемым размером) этой структуры, чтобы хранить данные множества сотрудников. В случае SoA мы разделяем каждое поле данных сотрудников на отдельные векторы. Это значит, что у нас будет один массив для id, второй для имён и третий для зарплат.

? Производительность обновления данных

Давайте исследуем свойства этих типов хранения. Сначала нам нужно понять типичный объектно-ориентированный способ доступа к данным. Приложения обычно вставляют, обновляют и удаляют объекты. В нашем примере мы создаём сотрудников при их найме, обновляем зарплату в процессе их работы в компании и удаляем их при увольнении.

Так как перемещение данных крайне важно для производительности, мы исследуем различные пути доступа разных форматов данных. Во всех последующих экспериментах будут использоваться 100 миллионов записей, а измерения будут выполняться на процессоре i7-13700H. Чтобы понять производительность объектно-ориентированного пути доступа, мы обновляем имена людей (согласно полученным им новым должностям) и адаптируем их зарплату, чтобы имитировать обновления объектов в процессе их жизненного цикла. Суммарно в течение эксперимента обновляются 10% сотрудников.

Хотя сгенерированный ассемблерный код практически идентичен (можете убедиться самостоятельно на godbolt), одно из решений примерно на 50% быстрее! Если виноват не процессор, то почему же возникла такая разница? Дело в подсистеме памяти, копирующей данные из основной памяти через кэши CPU в регистры CPU. Величина разбиения копируемых данных определяется размером линии кэша, обычно на машинах x86 она составляет 64 байта. Неважно, к какой части конкретной линии кэша нам нужно получить доступ, как только мы получаем к ней доступ, нам приходится расплачиваться временем на передачу данных из основной памяти. Операции доступа к линии кэша для доступа к одному объекту, хранимому как AoS или SoA

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

? Производительность чтения данных

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

// ---------------------------------------------------------------------------- decimal getTotalSalary(const ArrayOfStruct& store) // Вычисляем зарплату из массива структур {     decimal salary = 0;     // Итеративно обходим строки и выбираем зарплату     for (const auto& r : store.table)         salary += r.salary;     return salary; } // ---------------------------------------------------------------------------- decimal getTotalSalary(const StructOfArrays& store) // Вычисляем зарплату из структуры массивов {     decimal salary = 0;     // Iterate over the column     for (auto s : store.salary)         salary += s;     return salary; } // ----------------------------------------------------------------------------

Хотя код выглядит очень похожим, производительность сильно различается. На моей машине код с SoA приблизительно втрое быстрее, чем код с AoS.

Любопытно, что обе версии компилируются практически в одинаковый ассемблерный код. Единственное отличие ассемблерного кода заключается в смещении доступа к следующему элементу данных (32 байта или 8 байтов), что можно увидеть в godbolt. Как говорилось выше, за раз CPU загружает одну линию кэша на 64 байта. Поэтому очень важно структурировать данные с учётом этого. Код с SoA одновременно загружает 8 записей зарплат (8 * 8 байтов = 64 байта), а хранилище AoS может копировать только 2 записи (2 * 32 байта = 64 байта) на линию кэша (то есть только 2 записи зарплат). Получается, в этом случае впустую тратится 75% пропускной способности памяти, обеспечивая полезную нагрузку всего в 16 байтов на каждые загруженные 64 байта. Стоит отметить, что эксперименты выполняются исключительно в памяти, и если данные будут находиться на накопителях с меньшей пропускной способностью, то разница окажется ещё более серьёзной. Доступ к значениям на одну линию кэша

Кроме того, код с SoA может существенно выигрывать от автоматической векторизации в компиляторе. При уровне оптимизации O3 g++ генерирует для этого формата данных SIMD-код. В случае кода с AoS компилятор выполняет в цикле обход данных в массиве сотрудников, что можно увидеть в godbolt. Эта автоматическая векторизация даёт нам дополнительное повышение производительности в 1,5 раза, то есть суммарно SoA в четыре с лишним раза быстрее, чем AoS. Сравнив паттерны доступа обновления и чтения, мы можем увидеть, что выбор формата данных — это вопрос компромиссов и что хорошее знание приложения позволяет нам принять правильное решение. Если при обходе в цикле вы обычно задействуете большую часть данных в структуре, то лучше выбрать AoS. Эксперимент с агрегированием показывает, что SoA существенно повышает производительность, если требуются лишь некоторые поля записи.

? Сжатие

При оптимизации размера данных используется две распространённые методики: слабое и сильное сжатие. Сильное сжатие (например, LZ77 и код Хаффмана) минимизирует размер данных, не принимая дополнительных допущений о данных, но часто оказывается медленным и активно нагружает CPU, то есть мы получаем снижение размера ценой скорости. Методики слабого сжатия, например, кодирование длин серий (RLE), frame-of-reference или дельта-кодирование позволяет быстрым и эффективным образом снизить потребление памяти, не жертвуя при этом скоростью доступа. В отличие от сильного сжатия, многие методики слабого кодирования можно напрямую использовать для обработки сжатых данных без дополнительного извлечения, что ещё больше повышает скорость перемещения данных. Однако эффективность этих слабых методик сильно зависит от способа организации данных. Схемы слабого сжатия проявляют себя в полную силу, когда они могут обнаруживать паттерны или повторяющиеся значения. Примером такого паттерна может быть упорядоченная последовательность значений. При помощи формата SoA мы можем эффективно хранить данные с использованием дельта-кодирования или кодирования frame-of-reference. В целом, SoA лучше подходит для слабого сжатия, потому что схожие значения хранятся рядом друг с другом. Кроме того, SoA обеспечивает повышенную повторяемость в пределах каждого поля, что максимизирует коэффициент сжатия при таких схемах, как RLE. И наоборот: перемещающиеся поля в AoS ограничивают эффективность слабого сжатия. Вернёмся к нашему примеру и протестируем слабое сжатие с использованием frame-of-reference для десятичных последовательных значений. Кодирование frame-of-reference находит минимум значений и минимизирует количество байтов, требуемое для хранения разности с минимальным значением.
Представленный ниже упрощённый код реализует кодирование frame-of-reference, способное хранить значения разности до 2¹⁶. Полный код в Приложении реализует более обобщённую версию этой схемы кодирования. В нашем примере разность зарплат сотрудников умещается в 2 байта, поэтому мы можем вычислять зарплату при помощи минимального значения frame-of-reference и смещения.

// ---------------------------------------------------------------------------- // Столбец, сжимаемый кодированием frame-of-reference template <typename T> struct FORColumn : Column<T> {     // Минимальное значение столбца     T minValue;     // Значения, сжатые frame-of-reference     std::vector<uint16_t> compressed;     // Конструктор     FORColumn(const std::vector<T>& values, T minValue) : minValue(minValue) {         compressed.reserve(values.size());         for (const auto& elem : values)             compressed.emplace_back(elem - minValue);     } }; // ---------------------------------------------------------------------------- template <typename T> std::unqiue_ptr<Column<T>> createColumn(const std::vector<T>& values) // Вычисляем, можно ли применить схему сжатия, и создаём представление struct of array {     auto [minValue, maxValue] = std::ranges::minmax_element(values);     if (*maxValue - *minValue <= std::numeric_limits<uint16_t>::max()) {         return std::make_unique<FORColumn<T>>(values, *minValue);     } else {         return std::make_unique<Column<T>>(values);     } } // ---------------------------------------------------------------------------- template <typename T> decimal getTotalSalary(const FORColumn<T>& column) // Вычисляем зарплату {     decimal salary = 0;     for (auto s : column.compressed) {         salary += s + column.minValue;     }     return salary; } // ----------------------------------------------------------------------------

Как видно в приведённой ниже таблице, сжатие существенно уменьшает размер данных и повышает производительность. Наш способ сжатия позволяет обрабатывать данные напрямую, при этом требуя меньше перемещений данных. В целом, оптимизация формата хранения повышает скорость в семь раз и снижает потребление памяти и накопителя на 33%. Учтите, что мы измерили эти результаты при помощи общей реализации, показанной в Приложении.

? Оптимизация Out-Of-Memory

Поняв, что использование SoA может существенно повысить производительность благодаря применению методик слабого сжатия, рассмотрим вопрос масштабирования этих концепций при работе с большими датасетами. Когда датасет становится слишком большим, чтобы уместиться в памяти или когда требуется эффективный доступ только к части данных, в дело вступают разбитые на блоки структуры массивов (chunked structure of arrays): мы разделяем данные на блоки одного размера и сохраняем их на диск. Для ускорения обработки мы вначале сохраняем минимальное и максимальное значение каждого блока. Перед обработкой блока мы можем проверить минимальное и максимальное значения и пропускать блоки, которые нам не нужны; например, если нас интересуют блоки с именами, начинающимися на A-M, то не нужно обрабатывать блоки с именами на Z. Так как каждый блок сжимается по отдельности, мы можем масштабировать систему до более крупных датасетов, не беспокоясь о деградации производительности сжатия, особенно при использовании слабых форматов наподобие кодирования frame-of-reference.

Влияние на системы управления базами данных

Очевидно, что все эти наблюдения крайне важны для создания быстрой и масштабируемой системы управления базами данных. Специалисты по базам данных называют AoS способом хранения row-major, а SoA — способом хранения column-major. Для большинства традиционных систем управления базами данных наиболее важна обработка транзакций (то есть множества обновлений, вставок и удалений), поэтому в них реализуется AoS, а в современных аналитических системах управления базами данных (то есть со множеством операций чтения данных и обработки чисел) обычно предпочитают SoA. Первоисточником разбитых на блоки SoA стал формат Partition Attributes Across (PAX). Сегодня дополнительное сжатие данных внутри формата PAX используется для чтения с медленных накопителей, например, с облачных хранилищ объектов (AWS S3 и прочих).