Что такое AOS, SOA, SOS?

Эти термины описывают разные способы расположения данных в памяти, что является важным для SIMD (Single Instruction, Multiple Data) – вычислительного принципа параллелизма, в котором одна команда применяется к большому числу данных.

AOS – Array of Structs, массив структур. То есть, определяется структура с содержимым одного элемента, и на её основе создаётся массив даных:

struct point3D {
    float x;
    float y;
    float z;
};
struct point3D points[N];
// соответственно, для обращения к конкретному элементу
// обращаемся к соответствующей структуре из массива:
float get_point_x(int i) { return points[i].x; }

В памяти это выглядит как ряд XYZ:

x0, y0, z0, x1, y1, z1, ... xn-1, yn-1, zn-1

Этот способ очень прост для разработчика (т.к массив структур можно создать в любом месте в программе), но не очень эффективен в SIMD.

SOA – Struct of Arrays, структура с массивами. То есть, определяется структура, содержащая массивы данных:

struct pointlist3D {
    float x[N];
    float y[N];
    float z[N];
};
struct pointlist3D points;
// для обращения к конкретному элементу
// обращаемся к массиву значений в структуре:
float get_point_x(int i) { return points.x[i]; }

Таким образом, значения одного типа и смысла находятся вместе. В памяти это выглядит так:

x0, x1, ... xn-1, y0, y1, ... yn-1, z0, z1, ... zn-1

Для SIMD этот подход гораздо более эффективен, но для разработчиков не очень – ведь размер структуры нужно знать на этапе компиляции.

SOS – Struct of Structs, структура с структур. Этот способ создан для объединения удобства AOS и скорости SOA посредством группировки однотипных данных в блоки заданного размера (в общем-то, его можно назвать AOSOA – массив структур с массивами):

struct point3Dx4 {
    float x[N];
    float y[N];
    float z[N];
};
struct point3Dx4 points[(N+3)/4]; // для округления в большую сторону
// здесь обращение чуть более сложное:
float get_point_x(int i) { return points[i/4].x[i%4]; }

В памяти это выглядит так:

x0, x1, x2, x3, y0, y1, y2, y3, ... yn-4, yn-3, yn-2, yn-1, zn-4, zn-3, zn-2, zn-1

На основе этой статьи