Разнесение выполнения (concurrent) систем играют ключевую роль в играх — от обновления поведения ИИ и физики до рендеринга и загрузки ресурсов. Разные модели параллелизма позволяют по-разному организовать работу потоков, распределяя задачи и определяя, как потоки взаимодействуют между собой для достижения общей цели. Правильно выбранная модель влияет не только на производительность, но и зачастую на стабильность игры.
Модели выполнения используются разные — от простой многопоточности с ручной синхронизацией до более продвинутых систем акторов, job-based подходов или task graph. Например, системы поведения ИИ могут обновляться параллельно с физикой, пока основной поток отвечает за рендеринг. Некоторые движки, такие как Unreal Engine, используют task graph (граф задач), где зависимости между задачами выражаются явно, и задачи автоматически распределяются по доступным ядрам. Другие подходы, как в CryEngine Perth (аналог ECS, матрица задач), позволяют организовать данные так, чтобы минимизировать ложные зависимости и повысить кэш-эффективность. Конечный выбор всегда зависит от архитектуры движка, платформы и требований конкретной задачи или группы задач.
Game++. Work hard <=== Вы тут
Game++. Matching patterns
Game++. Game Over
Модели параллелизма, используемые в играх, во многом напоминают архитектуры распределённых систем — физика, ИИ, аудио, анимация, рендеринг — зачастую выполняются в отдельных потоках, которые должны эффективно взаимодействовать между собой. Это очень похоже на то, как в распределённых системах разные процессы обмениваются данными, только в случае с играми всё происходит в пределах одного устройства и ограничено рамками нескольких фреймов.
Потоки в играх и задачи в распределенных системах имеют схожую природу, поэтому и модели параллельного исполнения в играх часто перекликаются со старшими братьями. И хотя игры часто не зависят от сетевого соединения, в роли таких сбоев выступают например тротлинг CPU или GPU, ошибки в памяти, проблемы с доступом к диску. И когда одна система (например, поток загрузки текстур) зависает или выделяет слишком много ресурсов, это влияет на всю игру. Именно поэтому в большинстве условно "больших" игр используются task-системы и dependency-графы, которые напоминают модели балансировки нагрузки и отказоустойчивости из распределённых систем.
А с появлением такого понятия, как балансировка, приходят идеи вроде идемпотентности (возможности безопасно повторно выполнить задачу), fail-over (переключения на резервную логику), логирование задач, приоритизации и равномерного распределения нагрузки — всё это перекочевало в игровые фреймворки, особенно в крупных проектах и на консолях, где предсказуемость и стабильность важны уже не меньше, чем производительность. А на совещания вполне можно услышать спор о том, можно ли поступиться 5 фпс, но нагрузить в сцену больше контента, или добавить NPC и логики.
Shared state (Общее состояние)
Thread ==================| |==================| |===
| State | | State |
Thread ==================| |==================| |===Один из ключевых вопросов — будут ли потоки делить общее состояние (shared state) или каждый поток будет иметь свою копию (separate state).
В случае общего состояния, например, если несколько систем (физика, AI, анимация) одновременно обращаются к одним и тем же объектам игрового мира мы сталкиваемс с типичными проблемами многопоточности: гонки данных, дедлоки и ложные зависимости.
AI-логика обновляет позицию юнита одновременно с физическим движком, кому из них можно верить? Для предотвращения подобных ситуаций приходится использовать мьютексы, атомики или другие механизмы синхронизации, которые будут замедлять исполнение.
Separate state(Изолированное состояние)
Thread ==================[State]==================[State]===
Thread ==================[State]==================[State]===В отличие от этого, изолированное состояние (separate state) используется в системах, таких как задания (job systems) или ECS (Entity-Component-System), где каждый поток работает над своим куском данных: один поток обновляет только позиции, другой — только повороты, и они не пересекаются по данным. Такой подход повышает сложность кода и system complexity (понимаемость системы), но позволяет масштабироваться на современные CPU с большим количеством ядер, уменьшить накладные расходы на синхронизацию и повышая общую производительность игры.
Изолированное состояние (separate state) в означает, что разные потоки не разделяют между собой данные — каждый работает только со своим набором объектов, свойст или параметров. Если потокам нужно обменяться информацией, то делается это либо через неизменяемые объекты, либо через копии данных, что исключает одновременную запись в одну и ту же область памяти и снижает риск типичных проблем многопоточности, вроде гонок.
Например, в job-based-системах каждый поток получает своё задание и свой кусок игрового состояния, юнит, компонент или данные, не требующий синхронизации. Все эти решения в конечном итоге привели разработчиков движков к multithreaded rendering — когда потоки могут собирать команды рендеринга независимо друг от друга, после чего главный поток отправляет всё в GPU. Что позволило сделать супер эффективные системы вроде id.Tech5 и на полную использовать ресурсы современных CPU/GPU, но также сделало архитектуру таких игр хрупкой, мало предсказуемой и малопригодной для дебага обычными средствами. Хрупкой в плане того, что рендер от id.Tech ни для чего, кроме Doom под который он был написан больше не подходит.
Shadow state (теневая копия)
Thread ==================[State->State1]===========[State1]===
Thread ==================[State]===================[State1]===Подход к организации многопоточности, при котором каждый поток работает с собственной локальной копией общего состояния до первого изменения. Вместо того чтобы напрямую взаимодействовать с «живыми» данными, поток получает snapshot (снимок) — т. н. «теневую копию», с которой может безопасно работать, не беспокоясь о синхронизации. После завершения всех операций изменения агрегируются и, как правило, сливаются обратно в основное состояние на следующем этапе, часто в строго контролируемой фазе, например, в конце кадра.
Применяется в системах AI, симуляции и подготовки анимаций, где каждый поток обрабатывает поведение агентов или расчёты на основе состояния, актуального на начало кадра - все воркеры получают консистентный взгляд на мир.
Другой пример, копия имеет некий шареный флаг, на основе быстрого атомика, который говорит о том, что данные были изменены в другом потоке и их надо обновить. Если поток уже начал выполнять работу над данными, то он её продолжает, но если есть возможность их обновить, то берется актуальное состояние.
Workers
+--------------------------------------+
| Data |
+--------------------------------------+
/\ /\ /\
|| || ||
\/ \/ \/
+----------+ +----------+ +----------+
| | | | | |
| Worker | | Worker | | Worker |
| | | | | |
+----------+ +----------+ +----------+
^ ^ ^
| | |
+------------+ | | |
| | | | |
| Pool |----------+---------------+-------------+---->
| |
+------------+
Первая модель параллелизма, которую реализовывают в движке, это обычно параллельные задачи. Задания распределяются между различными рабочими потоками (workers). Каждый воркер выполняет задачу полностью, выполняются в разных потоках и, возможно, на разных процессорах, задачи не знают существовании других задач.
Если посмотреть на эту модель в реальном мире, будет похоже на сборку шкафа в квартире, сборщик получает книжку с инструкциями и собирает шкаф от основания до ручек дверей. Модель простая и потому наиболее часто используется в играх.
Преимущества воркеров заключаются в том, что во‑первых они понятны, а во‑вторых — легко масштабируются, достаточно добавить больше потоков обработки. Позволяет регулировать интенсивность вычислений, симуляцию физики или рендеринг. Чтобы определить сколько воркеров хватате игре можно легко протестировать итерации с разным числом потоков и посмотреть, какое количество даёт наивысшую производительность.
Недостатков однако тоже хватает, и они достаточно существенные, чтобы перейти к использованию других моделей. Если воркеры нуждаются в доступе к общим данным, будь то память или видеокарта, то расходы на синхронизацию могут забрать весь выигрыш по времени от разнесения в задачи, а то и вовсе стать существенной обузой и причиной непредвиденного поведения.
Как только в модель воркеров проникают общие данные, а они 99% там будут, как-то состояние объектов, информация об уровне и т.д. все становится сложнее. Это означает, что изменения в этих данных должны быть записаны обратно в основную память, а не оставаться только в кэше процессора, который выполняет этот поток, что, как вы понимаете существенно снижает общую производительность. Поскольку игровые объекты, физика, анимации и AI часто требуют синхронизации между несколькими системами то в итоге приводит это к:
Гонке данных (Race conditions): два потока одновременно пытаются изменить одну и ту же переменную (например, здоровье персонажа или позицию объекта) и возникает неопределённое состояние.
Взаимным блокировкам (Deadlocks): потоки пытаются заблокировать несколько ресурсов в разном порядке и застрять в ожидании друг друга. Один поток блокирует данные о физике, а другой — данные о состоянии игры, и оба будут ожидать освобождения блокировок, что приводит к зависанию.
Oversync: несколько потоков слишком часто синхронизируются между собой, что приводит к лишним накладным расходам на синхронизацию и замедляет игру.
Базовым простым решением для всех типов подобных систем будет реализация на связке queue + thread в виде пула потоков.
class thread_pool_t
{
public:
thread_pool_t(std::size_t n_threads)
{
for (std::size_t i = 0; i < n_threads; ++i)
{
_threads.push_back(make_thread_handler(_queue));
}
}
~thread_pool_t()
{
// Task = {Execute/Stop, function, args}
Task const stop_task{TaskType::Stop, {}, {}};
for (std::size_t i = 0; i < _threads.size(); ++i)
{
push(stop_task);
}
}
bool push(Task const& task)
{
_queue.push(task);
return true;
}
private:
std::queue<Task> _queue;
std::vector<std::jthread> _threads;
}Готовую к применению реализацию такой системы можно найти тут, тут или тут. Для игры применение системы воркеров будет не сложнее вызова функции. Так
int the_answer()
{
return 42;
}
int main()
{
thread_pool workers;
std::future<int> my_future = workers.submit_task(the_answer);
std::cout << my_future.get() << '\n';
}или так
int main()
{
const std::future<void> my_future = pool.submit_task([]
{
std::this_thread::sleep_for(std::chrono::milliseconds(500));
});
std::cout << "Waiting for the task to complete... ";
my_future.wait();
std::cout << "Done." << '\n';
}Stateless workers
+--------------------------------------+
| Data |
+--------------------------------------+
|| || ||
\/ \/ \/
+----------+ +----------+ +----------+
| | | | | |
| Worker | | Worker | | Worker |
| | | | | |
+----------+ +----------+ +----------+
^ ^ ^
| | |
+------------+ | | |
| | | | |
| Pool |---------+---------------+-------------+---->
| |
+------------+ Модель воркеров обладает интересным вариантом, когда воркер перечитывает состояние по необходимости, чтобы убедиться, что работает с актуальной копией, вместо того, чтобы сохранять состояние внутри себя.
Такая модель становится эффективной, когда большинство систем, которые обрабатывают общие данные, работают на чтение или с задержкой в один фрейм. Только физический движок обновляет положение объектов в мире, а AI использует эти данные для принятия решений и посылает новые состояния в конце фрейма. Такой подход используется в серии игр Assassin's Creed c самого появления серии, что позволяет обрабатывать огромную толпу акторов на очень скромном железе.
Подход «stateless» обработчиков, которые всегда перечитывают актуальное состояние предпочтительнее, так как он снижает риск работы с устаревшими данными и помогает избежать сложных проблем синхронизации. Чтение данных условно «ничего не стоит», по сравнению с использованием мьютексов, но такая модель не всегда и не везде подходит.
Другая, не менее известная игра, которая использует подход stateless workers — это Factorio. Автор у себя в блоге подробно описывал реализацию этой системы, чтобы иметь возможность обрабатывать движение на карте толп по 3–4к юинтов, ну и собственно не только юнитов.
Workers chain
Вторая модель, которую широко используют в играх — это то, что я называю цепочками. Название выбрано, чтобы сохранить аналогию с «рабочим, который собирает шкаф». Здесь у нас шкаф разделен на две части — низ и верх, и рабочие собирают их друг за другом, нельзя собрать верх без собранного низа, нельзя распаковать текстуру без загрузки с диска, но загрузка и распаковка вместе занимают долгое время и отбирают ресурсы у фрейма.
+----------+ +----------+ +----------+
| | | | | |
+--->| Worker |->| Base | | Top |
| | | | | | |
| +----------+ +----------+ +----------+
| |
| +-------------+
+------------+ | +----------+ +----------+ +---\|/----+
| | | | | | | | |
| Pool |--+--->| Worker |->| Base | | Top |
| | | | | | | |
+------------+ +----------+ +----------+ +----------+Использование такой модели позволяет сделать неблокирующий ввод-вывод (non-blocking IO), т.е. когда начинается такая операция (например, чтение файла текстуры, декомпрессия, загрузка в видеокарту), поток может не ожидать её завершения. Операции ввода-вывода, как правило, медленные, и ожидание их завершения просто пустая трата времени процессора. Когда такая операция завершается, её результат передаётся свободному рабочему из пула. И чем больше таких подзадач можно выделить у долгой задачи, тем более эффективно получится использовать ресурсы процессора, тем меньше будет задержек на прогрузке текстур. Вместо того, чтобы грузить все текстуры сразу и вешать фрейм на несколько секунд (фриз) мы растягием это время, разбивая загрузку на мелкие части. Да, возможно игрок в какой-то момент увидит пару замыленных текстур, которые ещё в процессе загрузки, но зато стабильный и высокий FPS, а не фризы и лаги, которые все привыкли относить на счет кривизны рук.
Это возможно похоже на предыдущую, но такая модель плохо ложится на беспорядочную выборку задач, нет гарантии что задачу заберут сразу, нет гарантии что бюджета хватит на выполнение.
Чаще всего такая модель используется(но не ограничивается только ей) для асинхронной загрузки ресурсов — уровней, текстур, моделей, анимаций и выделяются воркеры по число возможных этапов задачи. Один поток может распаковывать заголовок файла, передавать данные потоку, который загружает их из диска, затем — потоку, который обрабатывает и размещает ресурсы в памяти видеокарты. К томуже, благодаря тому, что мы знаем этапы на которые пришлось разбить эту задачу, её можно двигать по времени фрейма и не мешать основному игровому потоку, который отвечает за основную логику и рендер.
Обычно в конце фрейма, перед тем как данные уходят в видео карту у нас остаются свободные потоки, которые можно временно сделать такими «цепочками» и грузить ресурсы когда точно знаем, что не мешаем игре.
[ Main Game Thread ]
|
[ End of Frame ]
|
+---------------+----------------+
| |
[Worker Thread 1] [Worker Thread 2]
Stage 1: Schedule Stage 1: Schedule
resource load another resource
| |
[Worker Thread 3] [Worker Thread 4]
Stage 2: Disk read Stage 2: Disk read
(non-blocking IO) (non-blocking IO)
| |
[Worker Thread 5] [Worker Thread 6]
Stage 3: Decode / Stage 3: Decode /
Decompress asset Decompress asset
| |
[Worker Thread 7] [Worker Thread 8]
Stage 4: GPU upload Stage 4: GPU upload
(enqueue commands) (enqueue commands)
| |
[Back to Main Thread / Rendering Queue]Положительных свойств у цепочек предостаточно — тот факт, что рабочие потоки не разделяют общее состояние с другими потоками, означает, что их можно реализовывать, не задумываясь о типичных проблемах параллельного программирования, связанных с одновременным доступом к общим данным. Это значительно упрощает их реализацию, каждый поток можно реализовать будто он единственный, кто выполняет свою часть работы. Это снижает сложность кода, избавляет от необходимости использовать мьютексы, блокировки и прочие средства синхронизации, и соответственно делает логику более предсказуемой.
Поскольку воркеры не разделяют данные, они могут иметь «состояние» (stateful). То есть, каждый поток может хранить необходимые данные у себя в памяти и не обращаться к внешним источникам каждый раз при необходимости их обновить. Изменения перемещаются в оперативную память или обновляются только по завершении задачи.
Локальное хранение стейта позволяет такому потоку работать быстрее, чем stateless (минус синхронизаци, минус чтение данных). Это особенно выгодно когда мы имеем много задач за кадром — обработка поведения AI, симуляция анимаций, планирование пути и т.д. В итоге цепочки объединяют простоту однопоточной логики и производительность локального состояния, не жертвуя безопасностью или масштабируемостью.
Ну и как же без локальности данных? Однопоточный код имеет очень важное преимущество: он лучше соответствует архитектуре самого железа, проц конечно многоядерный, но внутри связка кеш-ядро, как была расчтитана на один поток двадцать лет назад, так и работает сейчас. Если можно быть уверенным, что код выполняется в однопоточном режиме, становится возможным разрабатывать оптимальные структуры данных и алгоритмы. Нет необходимости защищать доступ к памяти, учитывать гонки, блокировки и другие накладные расходы многопоточности — всё это упрощает и ускоряет код.
А еще, как было сказано выше однопоточные воркеры с локальным состоянием могут эффективно использовать кеш для своих данных, что как вы понимаете на порядки быстрее, чем обращение к общей или даже локальной оперативной памяти. Это называется (hardware conformity) — знание матчасти, когда код написан таким образом, что естественным образом использует архитектурные преимущества процессора.
Пика использования такой подход достиг в движках и играх Naughty Dog, которые упоролись и сделали воркеры аж на fibers, т.е. внутри потока он мог еще перебирать несколько нитей отдельных задач (т.е. получились задачи с подзадачами), чтобы полностью забить цпу вычислениями и убрать простои на ожидании данных. В отдельный момент PS3 реализация могла иметь 196 активных fiber-task, каждая из которых находилась в состоянии выполнения. За счет такой плотной упаковки, получилось утилизировать 92% cpu, что совершенно фантастические цифры при средней температуре по больнице меньше 50% на плоечных играх, т.е. движок наути догов почти выжал все, что можно, из проца третьей плойки.
Недостатки тоже есть - выполнение одной задачи зачастую разбивается между несколькими рабочими потоками, а значит — между разными классами и модулями. Из-за этого классы становятся похожи на набор колбеков, никак между собой не связанных, а понимание какой именно код выполняется в рамках обработки конкретной задачи выносится на уровень графов данных. Вся логика рабочих потоков перемещается callback handlers, они становятся вложенными друг в друга, появляется то, что разработчики игр называют (callback hell), на винде был dll hell, а тут в погоне за утилизацией проца сделали себе уютный филиал ада сами. И уже для такой системы, приходится писать отдельную тулзу для оркестрации и отладки. Подробнее можно посмотреть на видео ниже.
Где это посмотреть в коде? В 2019 Николас Капенс (Nicolas Capens) и Бен Клайтон (Ben Clayton) адаптировали решение наутидогов и заопенсорсили его на гитхабе. По коду всё тоже самое, общие вызовы почти ничем не отличаются от реализации воркеров на тредпуле.
int main() {
// Create a marl scheduler using all the logical processors available to the process.
// Bind this scheduler to the main thread so we can call marl::schedule()
marl::Scheduler scheduler(marl::Scheduler::Config::allCores());
scheduler.bind();
defer(scheduler.unbind()); // Automatically unbind before returning.
constexpr int numTasks = 10;
// Create an event that is manually reset.
marl::Event sayHello(marl::Event::Mode::Manual);
// Create a WaitGroup with an initial count of numTasks.
marl::WaitGroup saidHello(numTasks);
// Schedule some tasks to run asynchronously.
for (int i = 0; i < numTasks; i++) {
// Each task will run on one of the 4 worker threads.
marl::schedule([=] { // All marl primitives are capture-by-value.
// Decrement the WaitGroup counter when the task has finished.
defer(saidHello.done());
printf("Task %d waiting to say hello...\n", i);
// Blocking in a task?
// The scheduler will find something else for this thread to do.
sayHello.wait();
printf("Hello from task %d!\n", i);
});
}
sayHello.signal(); // Unblock all the tasks.
saidHello.wait(); // Wait for all tasks to complete.
printf("All tasks said hello.\n");
// All tasks are guaranteed to complete before the scheduler is destructed.
}В студии мы проводили замеры скорости выполнения разных задач, ниже приведен график зависимости числа выполненных задач (для пейлода взяли перемножение больших матриц) с периодическими столлами (имитация задержки IO), т.е. открыли задачу, прочитали данные, рандом фриз + ивент что таска заблочена, продолжили. Так себя ведет к примеру SSD на консолях без разной магии вроде Oodle/Kraken/DirectStorage. За счет того, что fibers позволяет переключаться даже на заблокированных тасках, получаем ощутимый прирост. На цепочках все зависит насколько успешно мы разбили наши цепочки, т.е. насколько близко фриз попадает на то время, пока таска находится в очереди на выполнение. У любого алгоритма будет точка насыщения, после которой затраты на управление и перебор текущих задач начнут влиять на время выполнения, т.е. будут расти накладные расходы и снижаться реальная утилизация.
Ну и наверное более понятный график - загрузка моделей на уровень. Условно модели грузятся за сценой, но от этого зависит насколько долго нам придется держать экран загрузки, четырем воркерам нужно загрузить сотню моделей, а это стулья, столы, стены и другая геометрия, НПС, оружие, какие-то физические объекты и вообще всё что есть на сцене. Да, модельки тяжелые, даже в релизе, 0.5с на загрузку всей модели это еще немного. Четыре воркера потратят на загрузку такой сцены (100 / 4 * 0.4) = 10 секунд, реального времени. Так вот marl и его аналоги позволяют почти вдвое снизить это время, за счет более полной утилизации cpu ну и соответственно минимизации периодов простоя и ожидания данных, ну повысить скорость загрузки уровня, окружения вокруг игрока, текстур, мира и т.д.
Что лучше
Как обычно, ответ зависит от того, что именно должна делать ваша игра и как быстро должна это делать. Если ваши задачи могут выполняться параллельно, независимы и не требуют общего состояния, то модель workers подходящее решение.
Если задачи в играх не являются полностью независимыми и требуют взаимодействия с общими ресурсами, такими как игровые объекты, состояния мира или сложные действия. Цепочки воркеров имеют больше преимуществ. Обработка загрузки контента в фоне, асинхронная обработка анимаций или физики — это всё может эффективно выполняться в виде цепочек, где каждый этап отвечает за свою часть работы, и состояние передается между воркерами.
К счастью у нас есть гитхаб, и не нужно реализовывать всю эту инфраструктуру с нуля, а можно подсмотреть как это сделали большие движки вроде Unreal. Где уже уже есть инструменты для асинхронной обработки задач, параллельной загрузки ресурсов и работы с многозадачностью. Для себя я лично планирую использовать цепочки, как более подходящие моей реставрации Фараона, и пусть там пока что в тред вынесена только загрузка звуков, но как минимум она перестала фризить игру.
Не телеграм ^_^
Приходите на гитхаб, я потихоньку допиливаю игру, ну и стараюсь реализовывать те вещи о которых тут пишу. Недавно вот воркеры и стены запилил.
https://github.com/dalerank/Akhenaten
