Меня зовут Ибрагим, и я уже несколько лет занимаюсь программированием на 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<int> playerHealth; std::vector<int> playerArmor; std::vector<float> playerPositionsX; std::vector<float> playerPositionsY; std::vector<float> playerPositionsZ;
Теперь, когда вы обновляете здоровье, процессор загружает в кэш только те данные, которые вам нужны:
for (auto& health : playerHealth) { health -= damage; }
Я провёл быстрый тест на своём ноутбуке (Intel i7-8750H, 16 ГБ ОЗУ). На массиве из миллиона игроков:
Было (один массив) -
120 мсСтало (отдельные списки) -
40 мс
То есть в 3 раза меньше!
И это только начало.
Работая над игровым движком, я столкнулся с серьезной проблемой аллокации памяти. Стандартные аллокаторы, такие как new/delete, хороши для простых случаев, но оказываются неэффективны для систем с высокой нагрузкой.
После множества выделений и освобождений памяти она может стать фрагментированной, что ускорит скорость поиска свободного блока. Постоянные вызовы new и delete могут вызвать contention при работе в многопоточных приложениях.
Но существуют способы решения проблемы — например, использовать кастомные аллокаторы. К примеру, аллокатор, который выделяет память блоками фиксированного размера (memory pool). И это особенно полезно, если вы часто создаёте и удаляете объекты одного типа.
Пример простого аллокатора на основе pmr из С++ 17:
#include <memory_resource> #include <vector> #include <iostream> 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<int> 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 <atomic> #include <iostream> #include <thread> #include <vector> template <typename T> 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<Node*> next; Node(const T& value) : data(value), next(nullptr) {} }; std::atomic<Node*> head; std::atomic<Node*> tail; }; void producer(LockFreeQueue<int>& 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<int>& 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<int> queue; // Создаём производителей std::vector<std::thread> producers; for (int i = 0; i < 2; ++i) { producers.emplace_back(producer, std::ref(queue), i + 1); } // Создаём потребителей std::vector<std::thread> 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++ — это далеко не только скорость. Это поиск понимания, как работает железо, где какие данные и как ими управлять. Эти заметки я попытался собирать примерно два года. Так что приступайте к осуществлению вашего БОЛЕЕ ЭФФЕКТИВНОГО КОДА. Не забывайте об измерениях производительности перед оптимизацией. Иногда самый примитивный код оказывается самым быстрым.
