Современные техники оптимизации производительности в C++. Кэш-локальность, аллокаторы и параллелизм
Меня зовут Ибрагим, и я уже много лет занимаюсь программированием на C++. За это время мне довелось поработать с высоконагруженными системами, игровыми движками и даже embedded-проектами! Сегодня я хочу рассказать об опыте оптимизации, применениях которого я сталкивался на практике. Мы порассуждаем о кэш-локальности, кастомных аллокаторах, многопоточности, и как они часто остаются не замеченными в литературе. Тем не менее, они принципиально важны при нашем стремлении писать быстрый код.
Однако прежде чем мы начнем, короткое предупреждение. Если вы думаете, что оптимизация, это просто «быстрый код», то предупреждаем, будете удивлены. Современные процессоры это не просто «быстрые калькуляторы». Они больше похожи на капризных художников, которым необходимо подать данные именно в таком порядке, иначе они откажутся работать быстро.
Когда я впервые слышал о кэш-локальности, я думал, что это что-то связанное с кэшем процессора. Оказывается это одно из самых сущностных понятий в оптимизации производительности. Современные процессоры имеют несколько уровней кэша (L1, L2, L3), и доступ к данным в кэше в десятки раз быстрее доступа к данным в оперативной памяти. Если ваши данные не умещаются в кэш, процессор вынужден ждать пока они подгрузятся из RAM. Такой промах называется cache miss, и он одна из главных причин замедления программ.
Представьте, что у вас есть структура данных, которая представляет собой массив структур:
struct Player {
int health;
int armor;
float position[3]; //... ещё куча полей
};
std::vector players;Теперь допустим, что вам нужно обновить здоровье всех игроков. Вы пишете простой цикл:
for (auto& player : players) {
player.health -= damage;
}Суть проблемы в том, что структура Player может быть очень большой (например 64 байта и более). Когда Вы обращаетесь к ее полю health, аппарат загружает в кэш не только это поле, но и всю структуру Player. И если структуры Player в памяти будут идти не плотным массивом, это означает, что при чтении всем полям health кэш будет промахиваться многократно.
Один из способов улучшить кэш-локальность — использование структуры данных, ориентированной на данные (Data-Oriented Design). Сохранение всех данных в отдельной структуре приводит к использованию нескольких массивов:
std::vector playerHealth;
std::vector playerArmor;
std::vector playerPositionsX;
std::vector playerPositionsY;
std::vector playerPositionsZ; Теперь, когда вы обновляете здоровье, процессор загружает в кэш только те данные, которые вам нужны:
for (auto& health : playerHealth) {
health -= damage;
}Я провёл быстрый тест на своём ноутбуке (Intel i7–8750H, 16 ГБ ОЗУ). На массиве из миллиона игроков:
То есть в 3 раза меньше!
И это только начало.
Пример с более маленькими данными
Работая над игровым движком, я столкнулся с серьезной проблемой аллокации памяти. Стандартные аллокаторы, такие как new/delete, хороши для простых случаев, но оказываются неэффективны для систем с высокой нагрузкой.
После множества выделений и освобождений памяти она может стать фрагментированной, что ускорит скорость поиска свободного блока. Постоянные вызовы new и delete могут вызвать contention при работе в многопоточных приложениях.
Но существуют способы решения проблемы — например, использовать кастомные аллокаторы. К примеру, аллокатор, который выделяет память блоками фиксированного размера (memory pool). И это особенно полезно, если вы часто создаёте и удаляете объекты одного типа.
Пример простого аллокатора на основе pmr из С++ 17:
#include
#include
#include
class CustomAllocator : public std::pmr::memory_resource {
public:
void* do_allocate(size_t bytes, size_t alignment) override {
void* ptr = std::aligned_alloc(alignment, bytes);
if (!ptr) throw std::bad_alloc();
return ptr;
}
void do_deallocate(void* ptr, size_t bytes, size_t alignment) override {
std::free(ptr);
}
bool do_is_equal(const memory_resource& other) const noexcept override {
return this == &other;
}
};
int main() {
CustomAllocator allocator;
std::pmr::vector vec{&allocator};
for (int i = 0; i < 100; ++i) {
vec.push_back(i);
}
for (int i : vec) {
std::cout << i << " ";
}
return 0;
} В начале моего знакомства с многопоточностью у меня сложилось впечатление, что для повышения производительности достаточно лишь запустить несколько потоков. Однако, как я позже осознал, ситуация оказалась сложнее.
В случае, когда несколько потоков работают с данными, которые находятся в одной кэш-линии, возникает contention.
Наличие блокировок — результат ситуации, когда несколько потоков пытаются одновременно получить доступ к одним и тем же данным.
Для избежания подобных ситуаций часто применяются атомарные операции и lock-free структуры данных. Например, здесь приведена реализация простейшей многопоточной очереди:
#include
#include
#include
#include
template
class LockFreeQueue {
public:
LockFreeQueue() : head(new Node(T())), tail(head.load()) {}
~LockFreeQueue() {
while (Node* oldHead = head.load()) {
head.store(oldHead->next);
delete oldHead;
}
}
void push(const T& value) {
Node* newNode = new Node(value);
Node* oldTail = tail.load();
while (!tail.compare_exchange_weak(oldTail, newNode)) {}
oldTail->next.store(newNode);
}
bool pop(T& value) {
Node* oldHead = head.load();
while (oldHead && !head.compare_exchange_weak(oldHead, oldHead->next.load())) {}
if (!oldHead) return false;
value = oldHead->data;
delete oldHead;
return true;
}
private:
struct Node {
T data;
std::atomic next;
Node(const T& value) : data(value), next(nullptr) {}
};
std::atomic head;
std::atomic tail;
};
void producer(LockFreeQueue& queue, int id) {
for (int i = 0; i < 10; ++i) {
queue.push(id * 10 + i);
std::this_thread::sleep_for(std::chrono::milliseconds(10)); // Имитация работы
}
}
void consumer(LockFreeQueue& queue, int id) {
int value;
while (queue.pop(value)) {
std::cout << "Consumer " << id << " popped: " << value << std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(20)); // Имитация работы
}
}
int main() {
LockFreeQueue queue;
// Создаём производителей
std::vector producers;
for (int i = 0; i < 2; ++i) {
producers.emplace_back(producer, std::ref(queue), i + 1);
}
// Создаём потребителей
std::vector consumers;
for (int i = 0; i < 2; ++i) {
consumers.emplace_back(consumer, std::ref(queue), i + 1);
}
// Ждём завершения производителей
for (auto& producerThread : producers) {
producerThread.join();
}
// Ждём завершения потребителей
for (auto& consumerThread : consumers) {
consumerThread.join();
}
return 0;
} Оптимизация на C++ — это далеко не только скорость. Это поиск понимания, как работает железо, где какие данные и как ими управлять. Эти заметки я попытался собирать примерно два года. Так что приступайте к осуществлению вашего БОЛЕЕ ЭФФЕКТИВНОГО КОДА. Не забывайте об измерениях производительности перед оптимизацией. Иногда самый примитивный код оказывается самым быстрым.
