Если вам нужно повысить скорость вашей программы, то первым делом логично будет вспомнить курс по структурам данных и оптимизировать алгоритмическую сложность.
Алгоритмы — важнейшая часть программы: замена «горячего» алгоритма
O(n) менее сложным, например, O(log n), обеспечивает практически произвольное увеличение производительности. Однако существенно влияет на производительность и структурированность данных: программы выполняются на физических машинах с физическими свойствами, например, разными задержками чтения/записи данных в кэши, на диски или в ОЗУ. После оптимизации алгоритмов стоит изучить эти свойства, чтобы достичь наибольшей производительности. Оптимизированный формат данных учитывает используемые алгоритмы и паттерны доступа при выборе того, как сохранять структуру данных на физическом носителе. Благодаря этому можно увеличить скорость алгоритмов в несколько раз. В этом посте мы покажем пример, в котором нам удалось достичь четырёхкратного повышения скорости чтения простым изменением формата данных в соответствии с паттерном доступа.Сравнение хранилищ данных AoS и SoA
Современное оборудование, и, в частности CPU, спроектировано так, чтобы обрабатывать данные определённым образом. Расположение данных в памяти влияет на то, насколько эффективно программа сможет использовать кэш CPU, как часто она сталкивается с промахами кэша и насколько оптимально она сможет задействовать векторные команды (SIMD). Даже при использовании оптимальных алгоритмов выбор неподходящего формата данных может приводить к частым перезагрузкам кэша, простаивающим конвейерам и чрезвычайно большому объёму передач содержимого памяти; всё это снижает производительность.
Одно из самых важных решений в выборе формата данных программы сводится к тому, как вы будете хранить коллекции объектов или записей. В этом посте мы рассмотрим простой пример хранения коллекции данных сотрудников компании, состоящих из идентификаторов сотрудников, их имён и зарплаты.
Простой и интуитивно понятный формат данных хранит полную запись по каждому сотруднику в смежной памяти, называемой массивом структур (Array of Structures, AoS). Это упрощает работу с отдельными сотрудниками, поскольку вся их информация упакована вместе и может быть получена при помощи одной операции доступа к
[i] массива. Формат структуры массивов (Structure of Arrays, 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% сотрудников.
| Тип хранения | Время исполнения |
|---|---|
| Array of Structs | 126,58 мс |
| Struct of Arrays | 195,66 мс |
Если виноват не процессор, то почему же возникла такая разница? Дело в подсистеме памяти, копирующей данные из основной памяти через кэши CPU в регистры CPU. Величина разбиения копируемых данных определяется размером линии кэша, обычно на машинах x86 она составляет 64 байта. Неважно, к какой части конкретной линии кэша нам нужно получить доступ, как только мы получаем к ней доступ, нам приходится расплачиваться временем на передачу данных из основной памяти.
В этом примере мы затрагиваем большую часть записи каждого сотрудника, так как получаем доступ и к имени, и к зарплате. Благодаря тому, что оба поля находятся в одной линии кэша, для обновления данных каждого сотрудника нам достаточно выполнить доступ только к одной линии кэша.
▍ Производительность чтения данных
После изучения обоих форматов данных на типичном процессе вставки/обновления/удаления мы хотим исследовать чтение и анализ свойств всей коллекции. Чтобы понять влияние на производительность этого процесса при использовании разных форматов данных, мы выполним агрегирование суммарных затрат на персонал.
// ----------------------------------------------------------------------------
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.
| Тип хранения | Время исполнения |
|---|---|
| Array of Structs | 137,22 мс |
| Struct of Arrays | 45,67 мс |
Как говорилось выше, за раз 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.
| Тип хранения | Время исполнения |
|---|---|
| Array of Structs | 137,22 мс |
| Struct of Arrays | 45,67 мс |
| Struct of Arrays (с автоматической векторизацией) | 33,13 мс |
▍ Сжатие
При оптимизации размера данных используется две распространённые методики: слабое и сильное сжатие. Сильное сжатие (например, LZ77 и код Хаффмана) минимизирует размер данных, не принимая дополнительных допущений о данных, но часто оказывается медленным и активно нагружает CPU, то есть мы получаем снижение размера ценой скорости. Методики слабого сжатия, например, кодирование длин серий (RLE), frame-of-reference или дельта-кодирование позволяет быстрым и эффективным образом снизить потребление памяти, не жертвуя при этом скоростью доступа. В отличие от сильного сжатия, многие методики слабого кодирования можно напрямую использовать для обработки сжатых данных без дополнительного извлечения, что ещё больше повышает скорость перемещения данных. Однако эффективность этих слабых методик сильно зависит от способа организации данных.
Схемы слабого сжатия проявляют себя в полную силу, когда они могут обнаруживать паттерны или повторяющиеся значения. Примером такого паттерна может быть упорядоченная последовательность значений. При помощи формата SoA мы можем эффективно хранить данные с использованием дельта-кодирования или кодирования frame-of-reference. В целом, SoA лучше подходит для слабого сжатия, потому что схожие значения хранятся рядом друг с другом. Кроме того, SoA обеспечивает повышенную повторяемость в пределах каждого поля, что максимизирует коэффициент сжатия при таких схемах, как RLE. И наоборот: перемещающиеся поля в AoS ограничивают эффективность слабого сжатия.
Вернёмся к нашему примеру и протестируем слабое сжатие с использованием frame-of-reference для десятичных последовательных значений. Кодирование frame-of-reference находит минимум значений и минимизирует количество байтов, требуемое для хранения разности с минимальным значением.
Представленный ниже упрощённый код реализует кодирование frame-of-reference, способное хранить значения разности до 216. Полный код в Приложении реализует более обобщённую версию этой схемы кодирования. В нашем примере разность зарплат сотрудников умещается в 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%. Учтите, что мы измерили эти результаты при помощи общей реализации, показанной в Приложении.
|
Способ хранения |
Время исполнения |
Размер |
|---|---|---|
| Array of Structs | 137,22 мс | 3051 МБ |
| Struct of Arrays (с автоматической векторизацией) | 33,13 мс | 3051 МБ |
| Struct of Compressed Arrays (с автоматической векторизацией) | 19,52 мс | 2098 МБ |
▍ Оптимизация 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 и прочих).
Приложение
Код бенчмарка сравнения Array of Struct и Struct of Arrays
#include <algorithm>
#include <array>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
// ----------------------------------------------------------------------------
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;
};
// ----------------------------------------------------------------------------
static decimal getTotalSalary(const ArrayOfStruct& store)
// Вычисляем зарплату из массива структур
{
decimal salary = 0;
// Итеративно обходим строки и выбираем зарплату
for (const auto& r : store.table)
salary += r.salary;
return salary;
}
// ----------------------------------------------------------------------------
static decimal getTotalSalary(const StructOfArrays& store)
// Вычисляем зарплату из структуры массивов
{
decimal salary = 0;
// Итеративно обходим столбец
for (auto s : store.salary)
salary += s;
return salary;
}
// ----------------------------------------------------------------------------
static void updateEntry(ArrayOfStruct& store, std::vector<series> ids, std::array<char, 16>& newName)
// Обновляем элементы хранилища AoS
{
for (auto id : ids) {
auto& record = store.table[id];
record.firstname = newName;
record.salary *= 2;
}
}
// ----------------------------------------------------------------------------
static void updateEntry(StructOfArrays& store, std::vector<series> ids, std::array<char, 16>& newName)
// Обновляем элементы хранилища SoA
{
for (auto id : ids) {
store.firstname[id] = newName;
store.salary[id] = 2 * store.salary[id];
}
}
// ----------------------------------------------------------------------------
int main() {
// Создаём 100 миллионов пользователей
auto users = 100 * 1000 * 1000ull;
std::array<char, 16> name = {"Moritz - Felipe"};
// Для обеих версий
ArrayOfStruct aos;
StructOfArrays soa;
// Заполняем хранилища
for (auto i = 0ull; i < users; i++) {
aos.table.emplace_back(static_cast<series>(i), static_cast<decimal>(i * 100) , name);
soa.id.push_back(static_cast<series>(i));
soa.salary.push_back(static_cast<decimal>(i) * 100);
soa.firstname.emplace_back(name);
}
// Вычисляем зарплату
auto measureSalary = []<typename T>(const T& store) {
// Запускаем таймер
std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
auto salary = getTotalSalary(store);
// Останавливаем таймер
std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
// Определяем тип хранилища
auto storeName = "SoA";
if constexpr (std::is_same_v<ArrayOfStruct, T>)
storeName = "AoS";
// Выводим результаты
std::cout << "Workload: Analyze; Store: " << storeName << "; Time: " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << " [μs]" << std::endl;
return salary;
};
// Проверяем корректность
if (measureSalary(aos) != measureSalary(soa))
return -1;
// -------------
std::random_device rnd_device;
std::mt19937 mt{rnd_device()}; // Генерирует случайные целые числа
std::uniform_int_distribution<uint64_t> dist{0, users - 1};
auto gen = [&]() {
return dist(mt);
};
std::vector<series> ids(0.1 * users);
std::generate(ids.begin(), ids.end(), gen);
// Обновляем столбец
auto measureUpdate = []<typename T>(T& store, std::vector<series> ids) {
// Обновляем имя и зарплату
std::array<char, 16> name = {"Dr. Moritz - F."};
// Запускаем таймер
std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
updateEntry(store, ids, name);
// Останавливаем таймер
std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
// Определяем тип хранилища
auto storeName = "SoA";
if constexpr (std::is_same_v<ArrayOfStruct, T>)
storeName = "AoS";
// Выводим результаты
std::cout << "Workload: Update; Store: " << storeName << "; Time: " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << " [μs]" << std::endl;
};
measureUpdate(aos, ids);
measureUpdate(soa, ids);
return 0;
}
// ----------------------------------------------------------------------------
Полный код бенчмарка
#include <algorithm>
#include <array>
#include <chrono>
#include <iostream>
#include <random>
#include <thread>
#include <vector>
// ----------------------------------------------------------------------------
using series = uint64_t;
using decimal = uint64_t;
// ----------------------------------------------------------------------------
// Сохраняем все элементы строки последовательно в памяти
struct Employee {
series id;
decimal salary;
std::array<char, 16> firstname;
};
// Вектор — это наращиваемый массив данных, каждый элемент которого — полная строка
struct ArrayOfStruct {
// The rows
std::vector<Employee> table;
// Вычисляем размер
size_t getSize() const {
return table.size() * sizeof(decltype(table)::value_type) + sizeof(ArrayOfStruct);
}
};
// ----------------------------------------------------------------------------
// Сохраняем один столбец последовательно в памяти
// Для упрощения мы игнорируем, что векторы помещают данные в разные области памяти.
// Скорее всего, база данных будет использовать специальную структуру данных, упаковывающую все столбцы.
struct StructOfArrays {
// Столбцы
std::vector<series> id;
std::vector<decimal> salary;
std::vector<std::array<char, 16>> firstname;
// Вычисляем размер
size_t getSize() const {
size_t size = id.size() * sizeof(decltype(id)::value_type);
size += salary.size() * sizeof(decltype(salary)::value_type);
size += firstname.size() * sizeof(decltype(firstname)::value_type);
return size + sizeof(StructOfArrays);
}
};
// ----------------------------------------------------------------------------
// Разные алгоритмы сжатия
enum class CompressionType : uint8_t {
RAW,
FOR1,
FOR2,
FOR4
};
// ----------------------------------------------------------------------------
// Базовый класс для сырых и несжатых столбцов
template <typename T>
struct Column {
using value_type = T;
// Схема сжатия
CompressionType type;
// Деструктор
virtual ~Column() {}
// Конструктор
Column(CompressionType type) : type(type) {}
// Вычисляем размер (virtual)
virtual size_t getSize() const = 0;
};
// ---------------------------------------------------------------------------
// Столбец хранится в сыром формате, например, vector<type>
template <typename T>
struct RawColumn : public Column<T> {
// Сырые значения
std::vector<T> column;
// Конструктор
RawColumn(auto begin, auto end) : Column<T>(CompressionType::RAW) {
column.reserve(end - begin);
for (auto it = begin; it != end; ++it)
column.emplace_back(*it);
}
// Деструктор
~RawColumn() override = default;
// Вычисляем размер
size_t getSize() const override {
return column.size() * sizeof(typename decltype(column)::value_type) + sizeof(RawColumn<T>);
}
};
// ----------------------------------------------------------------------------
// Столбец сжимается кодированием frame-of-reference
template <typename T, typename C>
requires std::is_unsigned_v<T>
struct FORCompressedColumn : public Column<T> {
// Минимальное значение столбца
T minValue;
// Максимальное значение столбца (для frame-of-reference необязательно, но пригодится в дальнейшем)
T maxValue;
// Значения, сжатые frame-of-reference
std::vector<C> compressed;
// Конструктор
FORCompressedColumn(auto begin, auto end, T minValue, T maxValue, CompressionType type) : Column<T>(type), minValue(minValue), maxValue(maxValue) {
compressed.reserve(end - begin);
for (auto it = begin; it != end; ++it)
compressed.emplace_back(*it - minValue);
}
// Деструктор
~FORCompressedColumn() override = default;
// Вычисляем размер
size_t getSize() const override {
return compressed.size() * sizeof(typename decltype(compressed)::value_type) + sizeof(FORCompressedColumn<T, C>);
}
};
// ----------------------------------------------------------------------------
// Сохраняем тот же столбец со сжатием
struct CompressedStructOfArrays {
// Потенциально сжатые столбцы
std::unique_ptr<Column<series>> id;
std::unique_ptr<Column<decimal>> salary;
std::unique_ptr<Column<std::array<char, 16>>> firstname;
// Вычисляем размер
size_t getSize() const {
return id->getSize() + salary->getSize() + firstname->getSize() + sizeof(CompressedStructOfArrays);
}
};
// ---------------------------------------------------------------------------
static constexpr auto createColumn(auto begin, auto end) -> std::unique_ptr<Column<typename decltype(begin)::value_type>>
// Вычисляем идеальную схему сжатия на основании значений
{
using T = decltype(begin)::value_type;
if constexpr (!std::is_unsigned_v<T>) {
return std::make_unique<RawColumn<T>>(begin, end);
} else {
auto [minValue, maxValue] = std::ranges::minmax_element(begin, end);
if (*maxValue - *minValue > std::numeric_limits<uint32_t>::max())
return std::make_unique<RawColumn<T>>(begin, end);
if (*maxValue - *minValue <= std::numeric_limits<uint8_t>::max()) {
return std::make_unique<FORCompressedColumn<T, uint8_t>>(begin, end, *minValue, *maxValue, CompressionType::FOR1);
} else if (maxValue - minValue <= std::numeric_limits<uint16_t>::max()) {
return std::make_unique<FORCompressedColumn<T, uint16_t>>(begin, end, *minValue, *maxValue, CompressionType::FOR2);
} else {
return std::make_unique<FORCompressedColumn<T, uint32_t>>(begin, end, *minValue, *maxValue, CompressionType::FOR4);
}
}
}
// ----------------------------------------------------------------------------
// Сохраняем те же столбцы в формате PAX
struct PaxStore {
// Блоки сжатых столбцов
std::vector<CompressedStructOfArrays> pax;
// Вычисляем размер
size_t getSize() const {
size_t size = sizeof(PaxStore);
for (const auto& elem : pax)
size += elem.getSize();
return size;
}
};
// ---------------------------------------------------------------------------
static PaxStore createPaxColumn(StructOfArrays& store, size_t paxSize)
// Вычисляем идеальную схему сжатия на основании значений
{
PaxStore pax;
pax.pax.reserve(store.id.size() / paxSize + 1);
for (size_t i = 0; i < store.id.size(); i += paxSize) {
CompressedStructOfArrays c;
if (i + paxSize > store.id.size()) {
c.id = createColumn(store.id.begin() + i, store.id.end());
c.salary = createColumn(store.salary.begin() + i, store.salary.end());
c.firstname = createColumn(store.firstname.begin() + i, store.firstname.end());
} else {
c.id = createColumn(store.id.begin() + i, store.id.begin() + i + paxSize);
c.salary = createColumn(store.salary.begin() + i, store.salary.begin() + i + paxSize);
c.firstname = createColumn(store.firstname.begin() + i, store.firstname.begin() + i + paxSize);
}
pax.pax.emplace_back(std::move(c));
}
return pax;
}
// ----------------------------------------------------------------------------
static decimal getTotalSalary(const ArrayOfStruct& store)
// Вычисляем зарплату
{
decimal salary = 0;
// Итеративно обходим строки и выбираем зарплату
for (const auto& r : store.table)
salary += r.salary;
return salary;
}
// ----------------------------------------------------------------------------
static decimal getTotalSalary(const StructOfArrays& store)
// Вычисляем зарплату
{
decimal salary = 0;
// Итеративно обходим столбец
for (auto s : store.salary)
salary += s;
return salary;
}
// ----------------------------------------------------------------------------
static decimal getTotalSalary(const CompressedStructOfArrays& store)
// Вычисляем зарплату
{
auto forComputation = []<typename T>(const T& column) {
decimal salary = 0;
for (auto s : column.compressed) {
salary += s + column.minValue;
}
return salary;
};
using T = decltype(store.salary)::element_type::value_type;
decimal salary = 0;
// Итеративно обходим столбец
switch (store.salary->type) {
case CompressionType::RAW:
{
auto column = static_cast<RawColumn<T>*>(store.salary.get());
for (auto s : column->column) {
salary += s;
}
break;
}
case CompressionType::FOR1:
return forComputation(*static_cast<FORCompressedColumn<T, uint8_t>*>(store.salary.get()));
case CompressionType::FOR2:
return forComputation(*static_cast<FORCompressedColumn<T, uint16_t>*>(store.salary.get()));
case CompressionType::FOR4:
return forComputation(*static_cast<FORCompressedColumn<T, uint32_t>*>(store.salary.get()));
}
return salary;
}
// ----------------------------------------------------------------------------
static decimal getTotalSalary(const PaxStore& store)
// Вычисляем зарплату
{
decimal salary = 0;
// Итеративно обходим столбец
for (const auto& p : store.pax)
salary += getTotalSalary(p);
return salary;
}
// ----------------------------------------------------------------------------
static void updateEntry(ArrayOfStruct& store, std::vector<size_t> ids, std::array<char, 16>& newName)
// Обновляем элементы
{
for (auto id : ids) {
auto& record = store.table[id];
record.firstname = newName;
record.salary *= 2;
}
}
// ----------------------------------------------------------------------------
static void updateEntry(StructOfArrays& store, std::vector<size_t> ids, std::array<char, 16>& newName)
// Обновляем элементы
{
for (auto id : ids) {
store.firstname[id] = newName;
store.salary[id] = 2 * store.salary[id];
}
}
// ----------------------------------------------------------------------------
int main() {
// Создаём 100 миллионов пользователей
auto users = 100 * 1000 * 1000ull;
std::array<char, 16> name = {"Moritz - Felipe"};
// Для обеих версий
ArrayOfStruct aos;
StructOfArrays soa;
CompressedStructOfArrays compressed;
PaxStore pax;
// Заполняем хранилища
for (auto i = 0ull; i < users; i++) {
aos.table.emplace_back(static_cast<unsigned>(i), (1000 + (static_cast<decimal>(i) % 500)) * 100, name);
soa.id.push_back(static_cast<unsigned>(i));
soa.salary.push_back((1000 + (static_cast<decimal>(i) % 500)) * 100);
soa.firstname.emplace_back(name);
}
compressed.id = createColumn(soa.id.cbegin(), soa.id.cend());
compressed.salary = createColumn(soa.salary.cbegin(), soa.salary.cend());
compressed.firstname = createColumn(soa.firstname.cbegin(), soa.firstname.cend());
pax = createPaxColumn(soa, std::numeric_limits<uint16_t>::max());
// Вычисляем зарплату
auto measureSalary = []<typename T>(const T& store) {
// Запускаем таймер
std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
auto salary = getTotalSalary(store);
// Останавливаем таймер
std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
// Определяем тип хранилища
auto storeName = "compressed";
if constexpr (std::is_same_v<ArrayOfStruct, T>)
storeName = "aos";
if constexpr (std::is_same_v<StructOfArrays, T>)
storeName = "soa";
if constexpr (std::is_same_v<PaxStore, T>)
storeName = "pax";
// Выводим результаты
std::cout << "Workload: Analyze; Store: " << storeName << "; Time: " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << " [μs]; Size: " << store.getSize() / (1024 * 1024) << " [MB]" << std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(1000));
return salary;
};
// Проверяем корректность
decimal salary = 0;
if (salary = measureSalary(soa); salary != measureSalary(compressed))
return -1;
// Проверяем корректность
if (salary != measureSalary(pax))
return -1;
// Проверяем корректность
if (salary != measureSalary(aos))
return -1;
// -------------
std::random_device rnd_device;
std::mt19937 mt{rnd_device()}; // Генерирует случайные целые числа
std::uniform_int_distribution<uint64_t> dist{0, users - 1};
auto gen = [&]() {
return dist(mt);
};
std::vector<uint64_t> ids(0.1 * users);
std::generate(ids.begin(), ids.end(), gen);
// Обновляем столбец
auto measureUpdate = []<typename T>(T& store, std::vector<uint64_t> ids) {
// Обновляем имя и зарплату
std::array<char, 16> name = {"Dr. Moritz - F."};
// Запускаем таймер
std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
updateEntry(store, ids, name);
// Останавливаем таймер
std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
// Определяем тип хранилища
auto storeName = "soa";
if constexpr (std::is_same_v<ArrayOfStruct, T>)
storeName = "aos";
// Выводим результаты
std::cout << "Workload: Update; Store: " << storeName << "; Time: " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << " [μs]" << std::endl;
};
measureUpdate(aos, ids);
measureUpdate(soa, ids);
return 0;
}
// ----------------------------------------------------------------------------Telegram-канал со скидками, розыгрышами призов и новостями IT ?
iShrimp
В C++ могут применяться оба подхода, а как сейчас обстоят дела c AoS в Java? Там JVM до сих пор интерпретирует массив объектов как массив ссылок (даже если внутри класса используются только элементарные типы), а объекты хранит в куче?
denis_iii
В java стало можно читать С-структуры через кодогенерацию из .h фалов, но это будет off-heap. Что в принципе и делают многие (хранение набора в off heap) – Solr, Cassandra и пр. В куче, все ссылки (адреса) хранимые в массиве будут перемешаны после GC.