Всем привет! Это продолжение статей про мою ECS with Sectors в моём движке Stellar Forge!

В предыдущей статье я описал структуру памяти, что являлось подготовкой фундамента для быстрой итерации, а сейчас хочу рассказать как по этой памяти передвигаться.
Получилась общая обзорная статья о том, как заставить C++ код быть быстрее, так что устраивайтесь поудобнее :-)

Статья будет полезна всем, кто пишет performance-critical код на C++: геймдев, HFT, обработка данных, embedded.

0. Профилирование, бенчмарки, тесты

Прежде чем начать что-то оптимизировать, нужно убедиться, что вы ничего не сломаете и не сделаете хуже.

Порядок действий:

1. Тесты - покройте оптимизируемый код юнит-тестами (чтобы не сломать)

2. Бенчмарки - напишите бенчмарки до оптимизации (чтобы было с чем сравнивать)

3. Профилировщик - найдите hot path (чтобы не оптимизировать то, что занимает 0.1% времени)

4. Оптимизация - только теперь

5. Бенчмарки - проверьте, что стало лучше

6. Тесты - проверьте, что не сломали

Профилируйте Release билд с debug symbols (-O2 -g), не Debug! В Debug вы будете оптимизировать совсем другой код.

1. Меньше кода = быстрее

У меня за время работы выработалось простое правило: чем меньше кода - тем быстрее.
И это не суеверие. Каждая строчка в hot path - это:

• инструкции процессора

• потенциальный branch

• регистры под переменные

• возможный cache miss

• меньше шанс inline

Плохо: "чистый" код с абстракциями

class Iterator {
    bool isValid() const { return mIndex < mSize; }
    Entity getEntity() const { return mEntities[mIndex]; }
    bool isAlive() const { return mAliveFlags[mIndex] & mMask; }
    
    Value operator*() const {
        if (!isValid()) throw std::out_of_range("...");
        if (!isAlive()) return nullptr;
        return getValue();
    }
};

Выглядит красиво. Но что видит компилятор:

• 3 вызова функций (даже если заинлайнит - лишние проверки)

• 2 условных перехода

• Exception handling код (даже если не бросим)

Хорошо: минимум в hot path

struct SlotInfo {
    std::byte* data;
    uint32_t isAlive;
    EntityId id;
};

SlotInfo operator*() const noexcept {
    return { mData + mIndex * mStride, 
             mIsAlive[mIndex], 
             mIds[mIndex] };
}

Один оператор. Три чтения из памяти. Ноль ветвлений.

В ecss в любой непонятной ситуации я старался придерживаться этого принципа.

---

2. inline - чем меньше вызовов функций, тем лучше

inline - это рекомендация компилятору вставить вместо вызова функции её код, в простонародье - "заинлайнить" функцию. Но inline в C++ - это лишь разрешение компилятору инлайнить. Он может отказаться. В критичных местах, если вы уверены в том что вы делаете, можно более настойчиво порекомендовать заинлайнить функцию через forceinline (реализация разная на разных компиляторах):

#if defined(_MSC_VER)
    #define FORCE_INLINE __forceinline
#elif defined(__GNUC__) || defined(__clang__)
    #define FORCE_INLINE __attribute__((always_inline)) inline
#endif

Почему это критично

Без force inline компилятор может решить не встраивать функцию, force тоже не дает гарантий (например, компилятор не заинлайнит рекурсию, виртуальные функции, указатели на функции или слишком большую функцию), но шансы повышаются:

// Вызов в цикле миллион раз
for (size_t i = 0; i < N; ++i) {
    if (isAlive(flags[i], mask)) {  // CALL? Stack frame?
        process(data[i]);
    }
}

Не заинлайнилось

.loop:
    mov     edi, [rbx + rcx*4]      ; flags[i] в первый аргумент
    mov     esi, r12d               ; mask во второй аргумент
    call    isAlive                 ; CALL - 20+ циклов
    test    al, al                  ; проверка результата
    je      .skip
    add     eax, [r13 + rcx*4]      ; sum += data[i]
.skip:
    inc     rcx
    cmp     rcx, r14
    jne     .loop

Заинлайнилось

.loop:
    mov     eax, [rbx + rcx*4]      ; flags[i]
    test    eax, r12d               ; flags & mask (одна инструкция!)
    je      .skip
    add     r8d, [r13 + rcx*4]      ; sum += data[i]
.skip:
    inc     rcx
    cmp     rcx, r14
    jne     .loop

Если isAlive не заинлайнится:

• CALL инструкция

• Сохранение регистров на стек

• Создание stack frame

• Возврат и восстановление

На каждой итерации! При N = 1,000,000 это существенная цифра.

В ecss все критичные методы помечены FORCE_INLINE:

---

3. Branch misprediction

Современные CPU выполняют инструкции спекулятивно - предсказывают куда пойдёт ветвление и начинают выполнять код заранее.

• Предсказание верное: ~1 цикл на branch

• Предсказание неверное: 15-20 циклов на сброс pipeline (https://users.elis.ugent.be/~leeckhou/papers/ispass06-eyerman.pdf)

Один if в hot path может убить перф настолько, что иногда дешевле выполнить код, чем спрятать его выполнение за if

for (size_t i = 0; i < N; ++i) {
    // Непредсказуемое условие
    int result = (data[i] > threshold) ? a : b;
    if (result) {
        process(data[i]);
    }
}

Если данные случайные - предсказатель ошибается в ~50% случаев.

N × 0.5 × 20 = 10N лишних циклов!

Branchless альтернативы

// Lookup table
int results[2] = {b, a};
int result = results[x > threshold];

// Bit manipulation
int mask = -(x > threshold);  // 0 или 0xFFFFFFFF
int result = (a & mask) | (b & ~mask);

// Для min/max
int min = b ^ ((a ^ b) & -(a < b));

Когда НЕ использовать

Если условие предсказуемое (почти всегда true или false) - обычный if быстрее. Branchless код всегда выполняет обе ветки.

---

4. то что посчитано в compile time остается в compile time

C++ позволяет некоторые операции выполнить во время компиляции, и освободить runtime для более интересных задач, поэтому если можно что-то посчитать во время компиляции - считайте.

Плохой пример:

void iterate(size_t stride, size_t offset) {
    for (size_t i = 0; i < N; ++i) {
        // stride читается из памяти каждую итерацию?
        auto* ptr = base + i * stride + offset;
        process(ptr);
    }
}

Компилятор не знает, что stride и offset не меняются. Может перечитывать из памяти.

Решение: constexpr

template<typename... Components>
void iterate() {
    constexpr size_t stride = sizeof(Sector<Components...>);
    constexpr size_t offset = offsetof(Sector<Components...>, firstComponent);
    
    for (size_t i = 0; i < N; ++i) {
        // stride и offset - immediate values!
        auto* ptr = base + i * stride + offset;
        process(ptr);
    }
}

Компилятор генерирует:

lea rax, [rbx + rcx*24 + 8]  ; stride=24, offset=8 вшиты в инструкцию

Повышается вероятность генерации SIMD кода и векторизации цикла.

---

5. Memory Layout: SoA vs AoS

Это, пожалуй, самое важное правило для работы с большими объёмами данных.

AoS - Array of Structures

struct Entity {
    float x, y, z;     // Position
    float vx, vy, vz;  // Velocity
    int health;
    bool alive;
};

Entity entities[10000];

// Итерируем только по позициям
for (auto& e : entities) {
    e.x += e.vx * dt;  // Тащим в кэш vx, vy, vz, health, alive
    e.y += e.vy * dt;  // Которые нам не нужны!
    e.z += e.vz * dt;
}

При итерации по x, y, z мы загружаем в кэш health и alive, которые не используем. Эффективность кэша ~30%.

SoA - Structure of Arrays

struct Entities {
    float x[10000];   // Только позиции - подряд в памяти
    float y[10000];
    float z[10000];
    float vx[10000];
    float vy[10000];
    float vz[10000];
    int health[10000];
    bool alive[10000];
};

// Итерируем по позициям
for (size_t i = 0; i < N; ++i) {
    entities.x[i] += entities.vx[i] * dt;  // Только нужные данные
    entities.y[i] += entities.vy[i] * dt;  // Кэш используется на 100%
    entities.z[i] += entities.vz[i] * dt;
}

В ecss используется гибридный подход - секторы:

// Можно сгруппировать компоненты, которые используются вместе
registry.registerArray<Position, Velocity>();  // В одном секторе
registry.registerArray<Health>();              // Отдельно

Position и Velocity лежат рядом (отличная locality при итерации по обоим), но Health - отдельно (не тащится в кэш, когда не нужен).

---

6. Alignment и Padding

Это не только про неэффективное использование памяти, но еще и про количество данных, которые поместятся в одну кэш линию процессора. А чем больше данных помещается в кэш - тем быстрее вы сможете по ним итерироваться.

struct Bad {
    bool a;     // 1 байт
    // 7 байт padding!
    double b;   // 8 байт
    bool c;     // 1 байт
    // 7 байт padding!
};  // Итого: 24 байта вместо 10

Просто сортируйте данные в структурах по уменьшению размера :)

struct Good {
    double b;   // 8 байт
    bool a;     // 1 байт
    bool c;     // 1 байт
    // 6 байт padding
};  // Итого: 16 байт

Hot и Cold данные

Лучше группировать данные не только по размеру, но еще и по частоте использования

struct Entity {
    // === HOT - одна cache line (64 байта) ===
    float x, y, z;        // 12 байт
    float vx, vy, vz;     // 12 байт  
    float health;         // 4 байта
    // padding до 32 или 64
    
    // === COLD ===
    std::string name;
    std::string description;
    int creationTime;
};

А лучше cold вынести в отдельную структуру

struct EntityHot {
    float x, y, z;
    float vx, vy, vz;
    float health;
};

struct EntityCold {
    std::string name;
    std::string description;
    int creationTime;
};

std::vector<EntityHot> hot;   // Итерируем каждый кадр
std::vector<EntityCold> cold; // Трогаем редко

Что бы ответить на вопрос "почему?", достаточно вспомнить как работает кэш:
Когда ты читаешь entity.x, процессор загружает целую cache line - 64 байта, начиная с адреса, выровненного на 64.

struct Entity {           // sizeof ≈ 80+ байт (больше cache line)
    float x, y, z;        // 12 байт - hot
    std::string name;     // 32 байт - cold (редко нужен)
    float vx, vy, vz;     // 12 байт - hot
};

При чтении y в кэш попадает и name (24-32 байта на большинстве реализаций).
При итерации for (auto& e : entities):

• Читаем e.x → загружается cache line с x, y, z, и часть name

• Читаем e.vx → другая cache line! (потому что name большой) 2 cache miss'а вместо 1.

struct Entity {           // sizeof = 28 байт - меньше cache line
    // HOT - всё в одной cache line
    float x, y, z;        // 12 байт
    float vx, vy, vz;     // 12 байт
    float health;         // 4 байта
    
    // COLD - в следующей cache line, не загружается, если не нужен
    std::string name;     
};

При итерации:

• Читаем e.x, e.y, e.z, e.vx, e.vy, e.vz, e.health → 1 cache line

• name не трогаем → не загружается 1 cache miss вместо 2. На миллионе сущностей - миллион сэкономленных cache miss'ов.

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

7. __restrict устраняет aliasing

Aliasing - это ситуация, когда два указателя ссылаются на одну и ту же область памяти. Компилятор должен учитывать эту возможность, даже если вы знаете, что указатели не пересекаются.

Проблема в том, что компилятор не знает, что указатели не пересекаются:

void add(float* a, float* b, float* result, int n) {
    for (int i = 0; i < n; ++i) {
        result[i] = a[i] + b[i];
        // Компилятор думает: а вдруг result == a?
        // Тогда a[i+1] мог измениться!
        // Нельзя векторизовать :(
    }
}

Решение: __restrict

void add(float* __restrict a, 
         float* __restrict b, 
         float* __restrict result, int n) {
    for (int i = 0; i < n; ++i) {
        result[i] = a[i] + b[i];  // Теперь векторизуется!
    }
}

---

8. Избегайте аллокаций в куче в hot path

Тут всё просто: аллокация памяти в куче - дорого, аллокация памяти в цикле в hot path - перфоубийство.
Аллокация выглядит примерно так:

// 1. Системный вызов (иногда)
new int[1000];
// → malloc() 
// → если нет свободного блока → brk()/mmap() 
// → переключение в kernel mode → ~1000+ циклов
// 2. Поиск свободного блока
// Аллокатор должен найти подходящий кусок памяти
// Проход по free list, проверка размеров, возможная фрагментация
// Best-fit, first-fit, buddy system - всё это не бесплатно
// 3. Синхронизация (в многопоточке)
// malloc() обычно защищён mutex'ом
// Даже если используется thread-local cache (tcmalloc, jemalloc)
// - периодически нужна синхронизация с глобальным пулом
// 4. Cache pollution
// Новая память = холодная память
// При первом обращении - cache miss → ~100-300 циклов

❌ Аллокация в цикле

for (int i = 0; i < N; ++i) {
    std::vector<int> temp;  // malloc каждую итерацию!
    temp.reserve(100);
    process(temp);
}

✅ Переиспользуем

std::vector<int> temp;
temp.reserve(100);
for (int i = 0; i < N; ++i) {
    temp.clear();  // Без аллокации - capacity сохраняется
    process(temp);
}

✅✅ Stack allocation

Аллокация на стеке практически бесплатна, так как память уже выделена

for (int i = 0; i < N; ++i) {
    std::array<int, 100> temp;  // На стеке - бесплатно
    process(temp);
}

---

9. Битовые операции

Если есть возможность работать с числами равными степени двойки, то вы можете заменить дорогие операции, такие как: деление, умножение, деление с остатком на битовые операции.
Очень советую поиграть в какую-нибудь игру, где вас просят сделать свой процессор из базовых логических элементов. Когда вы своими руками сделаете ALU с умножением и делением, вы ужаснетесь насколько это может быть дорого.

Компилятор достаточно умен, и, если он видит, что число - степень двойки, он автоматически заменит дорогие операции на битовые.

Деление - дорого

int idx = value % tableSize;  // 20-80 циклов!

Битовая маска - 1 цикл

// Только если tableSize = 2^N
int idx = value & (tableSize - 1);  // 1 цикл

Умножение vs сдвиг

int bytes = count * 8;   // MUL - 3-4 цикла
int bytes = count << 3;  // SHL - 1 цикл

Как это сделано в ecss

Chunk capacity - степень двойки:

// ecss/memory/ChunksAllocator.h
static constexpr size_t mChunkCapacity = ChunkSize / SectorSize;
// ChunkSize = 8192 - степень двойки

// Вычисление индекса в чанке
size_t chunkIdx = linearIdx / mChunkCapacity;  // Компилятор заменит на сдвиг
size_t localIdx = linearIdx & (mChunkCapacity - 1);  // Битовая маска

---

10. ILP - Instruction Level Parallelism - убирайте зависимости между итерациями

Зависимость - нельзя параллелить

float sum = 0;
for (int i = 0; i < N; ++i) {
    sum += data[i];  // Каждая итерация ждёт предыдущую
}

Несколько аккумуляторов

float sum0 = 0, sum1 = 0, sum2 = 0, sum3 = 0;
for (int i = 0; i < N; i += 4) {
    sum0 += data[i];      // ──┐
    sum1 += data[i + 1];  // ──┼── 4 ALU работают параллельно
    sum2 += data[i + 2];  // ──┤
    sum3 += data[i + 3];  // ──┘
}
float sum = sum0 + sum1 + sum2 + sum3;

CPU может выполнять 4 сложения одновременно (ILP - Instruction Level Parallelism).
Современные CPU - это не "один такт = одна инструкция". Внутри одного ядра есть несколько исполнительных блоков:

Intel Skylake (одно ядро):
├── ALU #1 (сложение, логика)
├── ALU #2 (сложение, логика)  
├── ALU #3 (сложение, логика)
├── ALU #4 (сложение, логика)
├── FPU #1 (float операции)
├── FPU #2 (float операции)
├── Load Unit #1
├── Load Unit #2
├── Store Unit
└── Branch Unit

Почему компилятор не делает это сам?
Иногда делает (loop unrolling + vectorization). Но:

• Floating point - (a + b) + c ≠ a + (b + c) из-за округления. Компилятор не может менять порядок без -ffast-math

• Сложные циклы - компилятор не всегда видит, что можно распараллелить

• Зависимости через память - если пишем и читаем из массива, компилятор осторожничает

---

11. Избегайте виртуальных функций

Вот это я бы назвал самым жирным оверхедом "на ровном месте". Думаю, ни для кого не секрет, как работает виртуализация в C++ - это оверхед как по рантайму, так и по памяти.

Каждый виртуальный вызов:

• Чтение vtable pointer

• Чтение адреса функции из vtable

• Indirect jump (CPU не может предсказать)

Есть решения через темплейты, например, CRTP. В целом совет простой: если можете этого избежать - избегайте. В некоторых компаниях, в которых очень важна производительность, это явно прописано в code convention.

12. std::function - враг производительности

void forEach(std::function<void(Entity&)> func) {
    for (auto& e : entities) {
        func(e);  // Type erasure, virtual call, возможная аллокация
    }
}

std::function:

• Type erasure - скрытый virtual call

• Small buffer optimization может не сработать - heap allocation

• Нельзя инлайнить

Решение: templates

template<typename F>
void forEach(F&& func) {
    for (auto& e : entities) {
        func(e);  // Инлайнится!
    }
}

---

13. Compiler hints

В продолжение branch misprediction, если вы знаете что if часто false или true, вы можете подсказать компилятору:

[[likely]] / [[unlikely]]

if (error) [[unlikely]] {
    handleError();  // Этот код не будет мешать основному пути
}

[[assume]]

[[assume]] - это не проверка, а утверждение: "Я гарантирую что это правда. Если нет - UB, сам виноват."

Компилятор использует это для оптимизации:

// Хорошо - мы точно знаем, что это правда
void updateEntities(Entity* entities, size_t count) {
    [[assume(count > 0)]];           // Пустой мир не бывает
    [[assume(count % 64 == 0)]];     // Мы сами паддим до 64
    [[assume(entities != nullptr)]]; // Проверили выше
}

// Плохо - мы не уверены
void processUserInput(int* data, size_t n) {
    [[assume(n > 0)]];  // А вдруг пользователь передаст 0? → UB
}

---

14. Смотрите в ассемблер

Все эти правила бесполезны, если вы не проверяете результат.
Есть очень крутой инструмент, через который можно быстро посмотреть, какой код будет сгенерирован компилятором: godbolt.org. Но можно это делать любым удобным способом.
По ассемблеру, даже если почти ничего непонятно, отлично работает правило из начала статьи: чем меньше кода - тем лучше :)

Но я опишу некоторые маркеры, на которые можно обращать внимание:

На что смотреть

; Хорошо - простой цикл
.loop:
    add eax, [rdi + rcx*4]
    inc rcx
    cmp rcx, rsi
    jne .loop

; Плохо - вызовы функций в цикле
.loop:
    call some_function
    ; ...

Красные флаги

• call инструкции в hot loop

• Много cmp / jne (ветвления)

• push / pop (работа со стеком)

• Отсутствие SIMD инструкций (vmovups, vaddps) там где они ожидаются

Зеленые флаги

; SIMD - обрабатываем 4-8 элементов за раз
vmovups ymm0, [rdi + rax]     ; загрузка 8 float
vaddps  ymm0, ymm0, ymm1      ; 8 сложений параллельно
vmovups [rsi + rax], ymm0     ; запись 8 float

; Loop unrolling - меньше проверок условия
.loop:
    add eax, [rdi]
    add eax, [rdi + 4]        ; развёрнуто
    add eax, [rdi + 8]        ; развёрнуто  
    add eax, [rdi + 12]       ; развёрнуто
    add rdi, 16
    cmp rdi, rsi
    jne .loop

; LEA вместо MUL - компилятор оптимизирует умножение
lea rax, [rcx + rcx*2]        ; rcx * 3
lea rax, [rcx*8]              ; rcx * 8

---

15. exceptions

В двух словах: exceptions в С++ - это медленно, очень медленно.

for (size_t i = 0; i < N; ++i) {
    try {
        process(data[i]);
    } catch (const std::exception& e) {
        log(e.what());
    }
}

1. Даже если исключение НЕ бросается:

• Компилятор генерирует exception tables (.gcc_except_table)

• Stack unwinding информация - для каждого frame

• Код становится больше → хуже влезает в I-cache

• Компилятор ограничен в оптимизациях (не может перемещать код через try границы)

2. Если исключение бросается:

• throw → → _Unwind_RaiseException() → поиск catch по exception tables → раскрутка стека - (вызов деструкторов) → ~10,000-100,000 циклов Да, десятки тысяч циклов на одно исключение :)

---

Оптимизации в ecss: что ещё под капотом

Все правила выше - это база. Но в ecss есть ещё несколько специфичных оптимизаций, которые дали серьёзный прирост:

1. SlotInfo: O(1) sparse lookup

Классическая проблема sparse sets: чтобы получить данные компонента, нужно 3 обращения к памяти. Мы уже знаем, что чем больше обращений (и кода), тем хуже:

// Было: 3 memory access
uint32_t linearIdx = sparseMap[entityId];     // 1. Lookup в sparse
std::byte* data = chunks[linearIdx / capacity] // 2. Вычислить chunk
                 + (linearIdx % capacity) * stride;  // 3. Вычислить offset

Решение - хранить готовый указатель прямо в sparse map:

// Стало: 1 memory access
struct SlotInfo {
    std::byte* data;      // Готовый указатель!
    uint32_t linearIdx;   // Для isAlive lookup
};

SlotInfo slot = sparseMap[entityId];  // 1 lookup - и данные готовы

Результат: has_component ускорился в 7.6 раза.

2. findSlot вместо find + at

При удалении/модификации компонента часто нужно и найти индекс, и получить данные:

// Было: 2 операции
auto idx = array->findLinearIdx(entityId);  // Поиск
auto* data = array->at(idx);                 // Ещё один lookup

// Стало: 1 операция
auto slot = array->findSlot(entityId);       // Сразу и data, и idx

3. isPacked() fast path

Если в массиве нет "дыр" (удалённых элементов), можно итерировать без проверки isAlive:

if (array->isPacked()) { // Вынесли if из цикла - branchless код
    // Чистый линейный проход - компилятор векторизует
    for (size_t i = 0; i < size; ++i) {
        func(data[i]);
    }
} else {
    // С проверками
    for (size_t i = 0; i < size; ++i) {
        if (isAlive[i] & mask) func(data[i]);
    }
}

Флаг isPacked обновляется при добавлении/удалении - проверка бесплатна, в цикле больше нет ветвления.

4. Разделение eachSingle / eachGrouped

Итерация по одному компоненту и по нескольким - это разные задачи с разным оптимальным кодом:

• eachSingle - максимально простой цикл, идеален для автовекторизации

• eachGrouped - развёрнутый доступ к нескольким компонентам в секторе

Компилятор генерирует разный код для каждого случая, а не универсальный компромисс.

---

Про память

Все эти оптимизации работают поверх правильной организации памяти: chunk allocator, секторы с группировкой компонентов, SoA layout. Всё это - фундамент скорости, без которого остальные трюки бессмысленны.

Подробнее про архитектуру памяти ecss - в предыдущей статье.

---

Результаты

Применение всех этих правил в ecss:

Сравнение с EnTT (250,000 entities):

---

Заключение

Быстрый код - это магия не магия, а дисциплина.
Быстрый код - это код написанный для компилятора, а не для человека.
Но так как ваш код читают люди, не стесняйтесь "обмазывать" его комментариями.

И - измеряйте. Профилировщик и ассемблер - ваши лучшие друзья.

---

Исходный код ecss: ECSS. Бенчмарки