Кэш-дружественные структуры данных: AoS vs SoA на практике

Почему важна организация данных

Современные CPU быстрые; память — медленная. Промах кэша на современном CPU стоит 100–300 нс — сотни тактов, в течение которых CPU простаивает. Правильная организация данных может быть важнее любой алгоритмической оптимизации.

Кэш-линия — единица передачи между RAM и кэшем CPU. На x86 и ARM Cortex-A кэш-линия составляет 64 байта. Доступ к одному байту загружает 64 байта. Если следующий нужный байт находится в той же кэш-линии — бесплатно. Если в 65 байтах дальше — ещё один промах.

Правило: размещайте в памяти рядом данные, к которым обращаются вместе.

Массив структур (AoS)

Естественная разметка C++ — массив экземпляров структуры:

1struct Particle {
2    float x, y, z;    // позиция
3    float vx, vy, vz; // скорость
4    float mass;
5    uint32_t flags;
6};                     // 32 байта на частицу
7
8std::vector<Particle> particles(1000);

Разметка памяти:

[x0,y0,z0,vx0,vy0,vz0,m0,f0] [x1,y1,z1,vx1,vy1,vz1,m1,f1] ...

Когда AoS уместен

Когда обрабатываете одну частицу за раз — все поля одной частицы в одной операции — AoS хорош. Все поля находятся в одной (или соседней) кэш-линии:

1// Хорошо для AoS — используем все поля одной частицы
2void integrate(Particle& p, float dt) {
3    p.x += p.vx * dt;
4    p.y += p.vy * dt;
5    p.z += p.vz * dt;
6}

Структура массивов (SoA)

Отдельные массивы для каждого поля:

1struct Particles {
2    std::vector<float> x, y, z;
3    std::vector<float> vx, vy, vz;
4    std::vector<float> mass;
5    std::vector<uint32_t> flags;
6
7    Particles(size_t n)
8        : x(n), y(n), z(n), vx(n), vy(n), vz(n), mass(n), flags(n) {}
9};

Разметка памяти:

x: [x0, x1, x2, x3, ..., x999]
y: [y0, y1, y2, y3, ..., y999]
...

Когда SoA уместен

Когда обрабатываете одно поле по всем частицам — например, обновление всех позиций x — SoA плотно загружает кэш-линии:

1// Хорошо для SoA — доступны только x и vx, 16 float на кэш-линию
2void integrateX(Particles& p, float dt, size_t count) {
3    for (size_t i = 0; i < count; ++i) {
4        p.x[i] += p.vx[i] * dt;
5    }
6}

При AoS тот же цикл касается каждого 8-го float (шаг = 32 байта) — каждая кэш-линия содержит только 2 полезных значения, остальное — потраченная полоса пропускания.

При SoA x и vx непрерывны — каждая 64-байтная кэш-линия содержит 16 float, и все используются.

Практическое измерение

Простой бенчмарк: обновление 100 000 позиций.

1// Цикл AoS — шаг 8 float (32 байта) между значениями x
2for (size_t i = 0; i < N; ++i)
3    aos[i].x += aos[i].vx * dt;
4
5// Цикл SoA — шаг 1 float (4 байта), последовательный
6for (size_t i = 0; i < N; ++i)
7    soa.x[i] += soa.vx[i] * dt;

Типичные результаты на настольном CPU (N=100 000):

Разметка	Время	Промахи кэша
AoS (только обновление x)	~450 мкс	высокие
SoA (только обновление x)	~120 мкс	низкие
AoS (все поля)	~380 мкс	средние
SoA (все поля)	~490 мкс	средние

SoA выигрывает при доступе к одному полю по многим элементам
AoS выигрывает при доступе ко всем полям одного элемента за раз

SIMD и SoA

SoA — предпосылка для SIMD-векторизации. Компилятор может автовекторизировать SoA-цикл с SSE/NEON; как правило, не может векторизировать AoS-цикл с шагом.

1// Компилятор может векторизировать это — последовательный массив float
2for (size_t i = 0; i < N; i += 4) {
3    // Компилятор генерирует 4-широкий SIMD: vx[i..i+3] + vy[i..i+3]
4    soa.x[i+0] += soa.vx[i+0] * dt;
5    soa.x[i+1] += soa.vx[i+1] * dt;
6    soa.x[i+2] += soa.vx[i+2] * dt;
7    soa.x[i+3] += soa.vx[i+3] * dt;
8}

Явно с ARM NEON intrinsics:

 1#include <arm_neon.h>
 2
 3void integrateX_neon(float* __restrict x, const float* __restrict vx,
 4                     float dt, size_t n) {
 5    float32x4_t vdt = vdupq_n_f32(dt);
 6    for (size_t i = 0; i < n; i += 4) {
 7        float32x4_t xi  = vld1q_f32(x  + i);
 8        float32x4_t vxi = vld1q_f32(vx + i);
 9        xi = vmlaq_f32(xi, vxi, vdt);  // xi += vxi * dt
10        vst1q_f32(x + i, xi);
11    }
12}

Четыре float обрабатываются за одну инструкцию. В этом выигрыш разметки SoA.

Гибрид: AoSoA

Горячие поля вынесены в SoA, холодные оставлены в отдельном AoS:

 1struct ParticleHot {       // доступ каждый кадр
 2    float x, y, z;
 3    float vx, vy, vz;
 4};
 5
 6struct ParticleCold {      // периодический доступ
 7    float mass;
 8    uint32_t flags;
 9    uint32_t id;
10    char name[16];
11};
12
13std::vector<ParticleHot>  hot(N);   // дружественно для SoA: упаковать в отдельные массивы x/y/z
14std::vector<ParticleCold> cold(N);  // холодные данные отдельно — не загрязняют кэш

Или AoSoA — блоки SoA, хранящиеся как блоки AoS:

1struct ParticleBlock {
2    float x[8], y[8], z[8];    // 8-широкий SIMD-блок
3    float vx[8], vy[8], vz[8];
4};                               // одна кэш-линия на массив компонент
5
6std::vector<ParticleBlock> blocks(N / 8);

Каждый блок помещается в несколько кэш-линий. Внутри блока SIMD обрабатывает все 8 частиц одновременно. Это типично для физических движков и трассировщиков лучей.

Применение во встраиваемых системах

На Cortex-M кэш меньше (16–64 кБ) и штраф за промах меньше (~10 тактов на M4 vs ~300 на настольном). Но принцип по-прежнему применим.

Буферы DMA и многоканальный АЦП: чередующиеся данные АЦП — это AoS (ch1,ch2,ch3, ch1,ch2,ch3, …). Разчередование в SoA перед обработкой улучшает производительность фильтров:

1// Перемежённый АЦП: [ch0_0, ch1_0, ch2_0, ch0_1, ch1_1, ch2_1, ...]
2// Разчередование в SoA
3for (size_t i = 0; i < N; ++i) {
4    ch0[i] = raw[i * 3 + 0];
5    ch1[i] = raw[i * 3 + 1];
6    ch2[i] = raw[i * 3 + 2];
7}
8// Теперь фильтруем ch0[] последовательно — всё в кэше

Массивы отсчётов сенсора: если ваш DSP всегда обрабатывает один канал, храните отсчёты в плоском массиве (SoA), а не в структурах с полем канала.

Чеклист

Сначала профилируйте. Используйте perf stat -e cache-misses (Linux) или счётчик PMU. Не оптимизируйте организацию данных вслепую.
Определите горячий цикл. К каким полям структуры он обращается? Если только к 1–2 из N — рассмотрите SoA.
Разделяйте горячие и холодные данные. Поля, к которым редко обращаются в главном цикле, не должны делить кэш-линию с полями, к которым обращаются на каждой итерации.
Выравнивайте по границам кэш-линий для независимых массивов:
```
1alignas(64) float x[N];
2alignas(64) float vx[N];
```
Используйте __restrict на указателях в горячих циклах, чтобы разрешить компилятору предположить отсутствие алиасинга и генерировать лучший SIMD-код.

Итоги

Кэш-линия = 64 байта = 16 float — всё между двумя обращениями в этом диапазоне «бесплатно»
AoS: хорош, когда все поля одного элемента обрабатываются вместе
SoA: хорош, когда одно поле обрабатывается по многим элементам (фильтры, DSP, физика)
SoA позволяет автовекторизацию и SIMD — AoS, как правило, нет
AoSoA: гибрид на основе блоков — SIMD-дружественные блоки, кэш-дружественная итерация
Разчередуйте данные DMA/АЦП в SoA перед DSP — одна кэш-линия на канал на итерацию

Что дальше

Lock-free очереди — передача SoA-буферов между потоками
Распределители памяти — выравнивание аллокаций пула по кэш-линиям
Семантика перемещения — перемещение SoA-контейнеров без копирования