1.5 AoS vs SoA
Введение
Для начала стоит вообще разобраться что это такое, зачем оно надо и как это всё использовать. Поехали.
Данный пост больше относится к архетипным ECS о которых я вскользь упоминал ранее и не заострял внимание т.к. тема довольно общирная, но не ограничивается ими и в общем случае относится к обработке линейных структур данных.
WARNING
Гибрид реализован через unsafe просто по причине, что C# это всё таки не С++ и нельзя просто так взять и лейаутить массивы пользовательских структур данных.
SoA
SoA, или дословно Struct of Arrays - подход, в котором каждый элемент структуры хранится в виде массива. К такому подходу относятся все спарс-сетные ECS, а так же те архетипные ECS, в которых в рамках архетипа компоненты хранятся в отдельных массивах.
Условно говоря выглядит это так:
struct Component1 {
public int Value;
public int Value1; // для толстости
public int Value2; // для толстости
public int Value3; // для толстости
}
struct Component2 {
public int Value;
public int Value1; // для толстости
public int Value2; // для толстости
public int Value3; // для толстости
}
struct Component3 {
public int Value;
public int Value1; // для толстости
public int Value2; // для толстости
public int Value3; // для толстости
}
public struct Data {
private Component1[] comp1;
private Component2[] comp2;
private Component3[] comp3;
// ...
// тут еще может быть какой-то код обрабатывающий это всё.
}Просто, нативно, понятно, удобно. Напомню, что рассматриваем мы это всё добро в контексте обработки данных, а не реализации ECS, так что будем считать, что все компоненты значимые, а другие туда и не попадут.
Из минусов стоит отметить:
- при добавлении\удалении элементов необходимо следить за размерами и ресайзить все массивы, т.е. чем больше массивов - тем больше ресайзов.
- при добавлении\удалении элемента необходимо переместить данные во всех массивах, т.е. тоже не атомарная операция
- при итерациях будет больше cache misses - т.к. менеджед массивы будут аллоцированы в разных участках памяти (разве что у вас кастомный аллокатор).
Код итерации по таким данным будет иметь следующий вид:
void ForEach() {
var n = Count;
for (var i = 0; i < n; i++) {
data[i].c1.Value++; // или любая другая полезная нагрузка
}
}Тоже просто и понятно, к скорости такого кода вернемся потом, в целом очень даже неплохо.
Стоит так же отметить, что при данном подходе хорошо работает комбинирование, что позволяет использовать только то, что нужно:
void ForEach2() {
var n = Count;
for (var i = 0; i < n; i++) {
data[i].c1.Value++; // или любая другая полезная нагрузка
data[i].c2.Value++; // или любая другая полезная нагрузка
}
}
void ForEach3() {
var n = Count;
for (var i = 0; i < n; i++) {
data[i].c1.Value++; // или любая другая полезная нагрузка
data[i].c2.Value++; // или любая другая полезная нагрузка
data[i].c3.Value++; // или любая другая полезная нагрузка
}
}Обратите внимание, что тут вообще нет обращений к каким либо полям с массивами, кроме тех, которые действительно нужны.
AoS
Всё то же самое, что и SoA, но наоборот. Даже ближе к классическому ООП - имеем 1 массив элементами которого являются структуры:
struct Component1 {
public int Value;
public int Value1; // для толстости
public int Value2; // для толстости
public int Value3; // для толстости
}
struct Component2 {
public int Value;
public int Value1; // для толстости
public int Value2; // для толстости
public int Value3; // для толстости
}
struct Component3 {
public int Value;
public int Value1; // для толстости
public int Value2; // для толстости
public int Value3; // для толстости
}
public struct Data {
struct Block {
public Component1 c1;
public Component2 c2;
public Component3 c3;
// ...
}
private Block[] data;
// тут еще может быть какой-то код обрабатывающий это всё.
}Из минусов стоит отметить:
- Писать руками удобно, но написать массив динамических кортежей или лейаутинг блока будет сложно - это будет либо дженерик ад, либо кодогенерация, либо unmanaged код с реинтерпретацией участков памяти. Основная проблема в том, что нужны поля.
- При итерации по такому массиву (особенно когда там много толстых компонентов) будет на порядок медленнее, чем в SoA версии просто потому, что при каждом обращении по индексу в кэш будет улетать вся пачка структур.
Итерация по такому массиву будет иметь следующий вид:
void ForEach1() {
var n = Count;
for (var i = 0; i < n; i++) {
data[i].c1.Value++; // или любая другая полезная нагрузка
}
}
void ForEach2() {
var n = Count;
for (var i = 0; i < n; i++) {
data[i].c1.Value++; // или любая другая полезная нагрузка
data[i].c2.Value++; // или любая другая полезная нагрузка
}
}
void ForEach3() {
var n = Count;
for (var i = 0; i < n; i++) {
data[i].c1.Value++; // или любая другая полезная нагрузка
data[i].c2.Value++; // или любая другая полезная нагрузка
data[i].c3.Value++; // или любая другая полезная нагрузка
}
}В целом тоже довольно удобно, не считая выше перечисленных минусов.
Данный подход хорошо себя покажет когда необходимо больше половины содержимого, т.к. минимизируется количество обращений к элементам массива.
Так же теперь только существует только одно место, гд, но за это мы платим тем, что приходится выдергивать в кэш весь блок - это будет видно в бенчмарках.
Hybrid
Гибрид - это подход, призванный взять лучшее из каждого вышеперечисленного подхода и при этом не затащить в себя его минусы.
Суть заключается в том, чтобы хранить данные линейно, как в SoA, но при этом побить массив на небольшие кусочки, чтобы prefetcher не затягивал в кэш как ненужные компоненты, так и не тянул гигантский хвост массива.
В С++ это будет шикарно работать с векторами, но в C# придется повозиться. Из-за особенностей языка у разработчика нет простых инструментов контроллировать лейаутинг элементов в памяти.
Я специально не провожу эксперименты на int'ах, с которыми можно пошаманить, именно для наглядности проблем.
По сути это SoA внутри AoS чанками по N элементов.
public struct Component1 {
public const int Size = sizeof(int) * 4; // уже появился доп код в виде констант, что увеличивает когнитивную сложность кода + возможность допустить ошибку
public int Value;
public int Value1; // для толстости
public int Value2; // для толстости
public int Value3; // для толстости
}
public struct Component2 {
public const int Size = sizeof(int) * 4;
public int Value;
public int Value1; // для толстости
public int Value2; // для толстости
public int Value3; // для толстости
}
public struct Component3 {
public const int Size = sizeof(int) * 4;
public int Value;
public int Value1; // для толстости
public int Value2; // для толстости
public int Value3; // для толстости
}
// ...
private const int BlockSize = 32; // аналогично с константами в компонентах. Эта, в частности, управляет размером блока
// вот эта вся разметка, это главный бич С# - очень хотелось бы юнионы и возможность объявлять поля-массивы не только примитивов
[StructLayout(LayoutKind.Explicit, Size = (Component1.Size + Component2.Size + Component3.Size /* ... */) * BlockSize)]
public struct Block {
[FieldOffset(0)]
public Component1 с1;
[FieldOffset(Component1.Size * BlockSize)] // каждое поле объявляется как нулевой элемент + подразумевается что за ним идет "хвост" из еще 32 таких же
public Component2 c2;
[FieldOffset((Component1.Size + Component2.Size) * BlockSize)]
public Component3 c3;
// ...
}
public struct Data {
private Block[] blocks;
// тут еще может быть какой-то код обрабатывающий это всё.
}Появилась вложенность типов, аллокации множества массивов, сам массив блоков надо инициализировать, ну, в общем, кода стало больше.
Минусы тоже у него есть:
- когнитивная сложность: читать такой код и дебажить становится на порядок сложнее
- менеджмент и структурные изменения требуют большего количества кода, а соответственно, операций
- усложняется код итерации
Итерация не отстает, и выглядеть будет примерно вот так:
Мини спойлер: попробовав разные варианты, и просто указатели и куча сейва и ансейва и тд остановился на этом, т.к. мне он кажется наиболее оптимальным и наглядным.
unsafe void ForEach1()
{
var n = Count / BlockSize;
var i = 0;
for (; i < n; i++)
{
ref var block = ref blocks[i];
Iterate(ref block, BlockSize);
}
var v = Count % BlockSize;
ref var lastBlock = ref blocks[i];
Iterate(ref lastBlock, v);
return;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
unsafe void Iterate(ref Block block, in int n) {
fixed (Component1* p1 = &block.c1) {
var rc1 = p1;
for (var j = 0; j < n; j++) {
rc1->Value++; // или любая другая полезная нагрузка
rc1++;
}
}
}
}
unsafe void ForEach2()
{
var n = Count / BlockSize;
var i = 0;
for (; i < n; i++)
{
ref var block = ref blocks[i];
Iterate(ref block, BlockSize);
}
var v = Count % BlockSize;
ref var lastBlock = ref blocks[i];
Iterate(ref lastBlock, v);
return;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
unsafe void Iterate(ref Block block, in int n)
{
fixed (Component1* p1 = &block.c1)
fixed (Component2* p2 = &block.c2)
{
var rc1 = p1;
var rc2 = p2;
for (var j = 0; j < n; j++) {
rc1->Value++; // или любая другая полезная нагрузка
rc2->Value++; // или любая другая полезная нагрузка
rc1++;
rc2++;
}
}
}
}
unsafe void ForEach3() {
var n = Count / BlockSize;
var i = 0;
for (; i < n; i++)
{
ref var block = ref blocks[i];
Iterate(ref block, BlockSize);
}
var v = Count % BlockSize;
ref var lastBlock = ref blocks[i];
Iterate(ref lastBlock, v);
return;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
unsafe void Iterate(ref Block block, in int n)
{
fixed (Component1* p1 = &block.c1)
fixed (Component2* p2 = &block.c2)
fixed (Component3* p3 = &block.c3)
{
var rc1 = p1;
var rc2 = p2;
for (var j = 0; j < n; j++) {
rc1->Value++; // или любая другая полезная нагрузка
rc2->Value++; // или любая другая полезная нагрузка
rc3->Value++; // или любая другая полезная нагрузка
rc1++;
rc2++;
rc3++;
}
}
}
}Страшный, страшный код, с вложенностью, указателями и прочими не очеть красивыми вещами. Ниже в цифрах увидим как это влияет на скорость обработки.
Его всегда можно реструктурировать и дженерализировать, или даже отдать на откуп кодогенерации. It's up to you.
Так что, всё таки, использовать?
Я был бы не я, если бы не померял, что из этого быстрее.
Замеры производились на M1Max, во всех компонентах по 4 интовых поля для создания нагрузки на prefetcher.
Step[N]по это итерация по 1, 2, 3 и т.д. компонентам соответственно, в рамках одного прохода.Количество элементов 1kk (один миллионов).
В табличке ниже победитель подсвечен зеленым, проигравший - красным, по середине - не подсвечен.
| Type | Method | Count | Mean | Error | StdDev |
|------- |------- |--------- |-------------:|----------:|----------:|
| AoS | Step1 | 10000000 | 35.162 ms | 0.2250 ms | 0.1488 ms |
| AoS | Step2 | 10000000 | 31.674 ms | 0.6115 ms | 0.4045 ms |
| AoS | Step3 | 10000000 | 33.846 ms | 0.5115 ms | 0.3044 ms |
| AoS | Step4 | 10000000 | 35.002 ms | 0.3747 ms | 0.2478 ms |
| AoS | Step5 | 10000000 | 37.280 ms | 0.4044 ms | 0.2675 ms |
| AoS | Step6 | 10000000 | 37.641 ms | 0.4709 ms | 0.3115 ms |
| AoS | Step7 | 10000000 | 39.376 ms | 0.2620 ms | 0.1733 ms |
| AoS | Step8 | 10000000 | 39.791 ms | 0.2997 ms | 0.1567 ms |
| AoS | Step9 | 10000000 | 40.939 ms | 0.6126 ms | 0.4052 ms |
| AoS | Step10 | 10000000 | 42.324 ms | 0.8813 ms | 0.5245 ms |
| AoS | Step11 | 10000000 | 42.589 ms | 0.4914 ms | 0.2924 ms |
| AoS | Step12 | 10000000 | 44.138 ms | 0.5851 ms | 0.3870 ms |
| AoS | Step13 | 10000000 | 45.769 ms | 0.6103 ms | 0.4037 ms |
| AoS | Step14 | 10000000 | 47.140 ms | 0.8175 ms | 0.5407 ms |
| AoS | Step15 | 10000000 | 46.995 ms | 0.2223 ms | 0.1470 ms |
| AoS | Step16 | 10000000 | 48.818 ms | 0.3407 ms | 0.2028 ms |
| AoS | Step17 | 10000000 | 49.678 ms | 0.3939 ms | 0.2606 ms |
| AoS | Step18 | 10000000 | 52.187 ms | 0.2884 ms | 0.1908 ms |
| AoS | Step19 | 10000000 | 53.463 ms | 0.1817 ms | 0.1202 ms |
| AoS | Step20 | 10000000 | 54.774 ms | 0.2482 ms | 0.1298 ms |
| Type | Method | Count | Mean | Error | StdDev |
|------- |------- |--------- |-------------:|----------:|----------:|
| SoA | Step1 | 10000000 | 6.267 ms | 0.0414 ms | 0.0274 ms |
| SoA | Step2 | 10000000 | 11.904 ms | 0.0133 ms | 0.0070 ms |
| SoA | Step3 | 10000000 | 19.064 ms | 0.1273 ms | 0.0842 ms |
| SoA | Step4 | 10000000 | 30.275 ms | 0.0571 ms | 0.0340 ms |
| SoA | Step5 | 10000000 | 238.250 ms | 0.2649 ms | 0.1752 ms |
| SoA | Step6 | 10000000 | 424.348 ms | 0.2432 ms | 0.1272 ms |
| SoA | Step7 | 10000000 | 622.912 ms | 1.0963 ms | 0.6524 ms |
| SoA | Step8 | 10000000 | 828.956 ms | 0.5696 ms | 0.3768 ms |
| SoA | Step9 | 10000000 | 877.664 ms | 2.9837 ms | 1.9735 ms |
| SoA | Step10 | 10000000 | 1,145.340 ms | 1.3835 ms | 0.9151 ms |
| SoA | Step11 | 10000000 | 1,202.752 ms | 3.9214 ms | 2.5938 ms |
| SoA | Step12 | 10000000 | 1,141.439 ms | 2.9407 ms | 1.9451 ms |
| SoA | Step13 | 10000000 | 1,520.562 ms | 1.6564 ms | 1.0956 ms |
| SoA | Step14 | 10000000 | 1,761.528 ms | 1.5312 ms | 1.0128 ms |
| SoA | Step15 | 10000000 | 1,855.929 ms | 1.7290 ms | 1.1436 ms |
| SoA | Step16 | 10000000 | 1,830.698 ms | 1.3030 ms | 0.8619 ms |
| SoA | Step17 | 10000000 | 1,679.585 ms | 1.3195 ms | 0.7852 ms |
| SoA | Step18 | 10000000 | 1,619.472 ms | 1.6495 ms | 1.0910 ms |
| SoA | Step19 | 10000000 | 1,973.583 ms | 8.6983 ms | 5.1762 ms |
| SoA | Step20 | 10000000 | 2,293.830 ms | 1.6763 ms | 0.9975 ms || Type | Method | Count | Mean | Error | StdDev |
|------- |------- |--------- |-------------:|----------:|----------:|
| Hybrid | Step1 | 10000000 | 30.764 ms | 0.3450 ms | 0.1805 ms |
| Hybrid | Step2 | 10000000 | 40.182 ms | 0.3125 ms | 0.2067 ms |
| Hybrid | Step3 | 10000000 | 50.265 ms | 0.1783 ms | 0.1061 ms |
| Hybrid | Step4 | 10000000 | 51.241 ms | 0.2616 ms | 0.1730 ms |
| Hybrid | Step5 | 10000000 | 76.930 ms | 0.9220 ms | 0.6099 ms |
| Hybrid | Step6 | 10000000 | 83.634 ms | 0.2978 ms | 0.1557 ms |
| Hybrid | Step7 | 10000000 | 89.111 ms | 0.7560 ms | 0.4499 ms |
| Hybrid | Step8 | 10000000 | 93.006 ms | 0.5081 ms | 0.3361 ms |
| Hybrid | Step9 | 10000000 | 101.911 ms | 1.5217 ms | 1.0065 ms |
| Hybrid | Step10 | 10000000 | 108.056 ms | 2.6164 ms | 1.7306 ms |
| Hybrid | Step11 | 10000000 | 119.447 ms | 1.8171 ms | 1.0813 ms |
| Hybrid | Step12 | 10000000 | 116.118 ms | 6.6427 ms | 4.3938 ms |
| Hybrid | Step13 | 10000000 | 109.516 ms | 1.0092 ms | 0.6005 ms |
| Hybrid | Step14 | 10000000 | 121.404 ms | 1.8718 ms | 1.2381 ms |
| Hybrid | Step15 | 10000000 | 117.430 ms | 6.6916 ms | 3.9821 ms |
| Hybrid | Step16 | 10000000 | 120.022 ms | 4.9221 ms | 3.2556 ms |
| Hybrid | Step17 | 10000000 | 91.136 ms | 0.6531 ms | 0.4320 ms |
| Hybrid | Step18 | 10000000 | 85.625 ms | 0.4673 ms | 0.3091 ms |
| Hybrid | Step19 | 10000000 | 96.137 ms | 3.2057 ms | 2.1204 ms |
| Hybrid | Step20 | 10000000 | 98.116 ms | 1.9292 ms | 1.2760 ms |Код можно посмотреть тут.
И так, выводы:
- При итерации по до 5 компонентов AoS проигрывает. Это обусловлено тем, что в случае SoA prefetcher затягивает в кэш больше валидных данных. Гибрид проигрывает еще больше из-за накладных расходов на итерации.
- При итерации по 5+ компонентам AoS и гибрид выигрывают. Это обусловлено тем, что в случае SoA prefetcher затягивает в кэш новые данные затирая предыдущие (которые були бы актуальны на следующей итерации). С гибридом - аналогично.
- Кривая деградация производительности в случае AoS плавнее, даже при том, что SoA обгоняет на относительно "простых" итерациях. В перспективе (или в "среднем" случае) AoS будет эффективнее при итерациях (!).
- Цифры гибрида довольно сильно скачут, причем имеют тенденцию к уменьшению при увеличении сложности операций - возможно я просто криворукий.
Если в двух словах: Если система оперирует одним-двумя компонентами, то эффективнее использовать SoA, если 5+ - то AoS. При этом выигрыш хоть и составляет почти 50%, в выражении времени выполнения им можно пожертвовать в целях поддержания единообразности подхода. Гибрид имеет смысл использовать, если у вас C++ и такие конструкции можно реализовать нативно (ну или если у вас руки прямее чем у меня).
Просто напоминаю, что сейчас рассматривается исплючительно набор значимых данных, т.е. интерпретировать все выше написанное можно сугубо в контексте одного единственного архетипа.
Выводы
Выводом является то, что теперь читающий понимает влияние лейаута данных на скорость их обработки. Однозначного фаворита выделить сложно, т.к. в контексте разных задач - разное количество данных и требования к их обработке.
Просто под каждый конкретный кейс нужно выбирать правильный интструмент и подход.
ECS дисклеймер
В контексте ECS ценой быстрой итерации будет высокая цена структурных изменений. При "толстых" сущностях (читай - наборах данных) добавление или удаление одного компонента даже в случае использования Remove and Swap Back, о котором я писал ранее, копирование будет довольно ресурсоёмким и будет по скорости уступать sparse-set'ным решениям.
Использовать SoA обработку имеет смысл, ИМХО, в ситуациях, когда составныые части архетипа не связаны друг с другом или связаны косвенно минимальным количеством пересечений в рамках логики обработки.