Game++. run, thread, run…

Разрабатывая свою игру, движок или фреймворк, вы в любом случае столкнетесь с необходимостью реализации системы загрузки ресурсов, выполнения задач вне основного цикла игры, вынесения различных подсистем (звук, рендер, физика, эффекты) в отдельные потоки, чтобы снизить время подготовки кадра и улучшить общую производительность. Будучи классическим программистом, вы, наверное, знаете о проблемах реализации реализации многопоточности, использовании блокировок и алгоритмов, которые основаны на блокировках.

В обычном программировании с блокировками, когда возникает необходимость пошарить данные, приходится использовать механизмы сериализации доступа к таким данным, чтобы операции, выполняющие работу с такими данными, были ограничены от одновременного вмешательства со стороны других потоков и возможности их поломать. В прямом смысле поломать. Даже такая простая операция, как ++count, где count имеет тип integer, требует блокировки, поскольку операция инкремента в общем случае представляет собой трехшаговую операцию (чтение, модификация, запись), которая не является атомарной. Про что-то более сложное и длительное я уже и не говорю.

За кажущейся простотой скрывается множество граблей и ловушек: взаимные блокировки (deadlock), «голодание» потоков, асинхронные ошибки. Это похоже на попытку дирижировать оркестром, где музыканты игнорируют ритм. Проще говоря, любые действия над данными могут привести к проблемам, и чтобы этого не происходило, операции над данными должны быть атомарными, это решается вводом в код примитивов синхронизации, вроде мьютексов, семафоров, спинлоков.

Первая хорошая сторона программирования с блокировками состоит в том, что пока ресурс заблокирован, никакая другая логика не может вмешаться. Вторая хорошая сторона — люди прекрасно понимают, читают и работают с таким кодом, потому что он хорошо вписывается в "естественное" понимание устройства мира.

А вот дальше начинаются проблемы...

Game++. String interning

Game++. Cooking vectors

Game++. Dancing with allocators

Game++. Juggling STL algoritms

Game++. run, thread, run... <=== Вы тут

Аналогии многопоточных алгоритмов в реальной жизни часто напоминают ситуации, где несколько людей взаимодействуют с общим ресурсом.

• Ключ от комнаты:
  Человеку, который хочет войти в комнату, требуется ключ, который висит на крючке у двери. Кто взял ключ, тот может работать в комнате. Остальные ждут у двери окончания работ. Это точно отражает работу мьютекса в коде.

• Очередь в магазине:
  Кассир обслуживает одного покупателя за раз. Если клиенты начнут толкаться и лезть без очереди — возникнет хаос, будет гонка данных (race condition), и у кассира появятся ошибки. Очередь покупателей, в данном случае, выполняет роль синхронизации, позволяя обрабатывать их последовательно и избегать ошибок.

• Менеджер "над душой":
  Пятница, конец рабочего дня. Менеджер Василий ожидает от вас завершения некоей задачи и каждые пять минут спрашивает: "А не закончил ли ты таску?", чтобы отметить её в недельном отчёте как закрытую и пойти с менеджером Ваней пить холодный кофе в пабе. Классический спинлок, на букву М, с постоянным временем ожидания.

Однако именно это "естественное понимание" возможных действий внутри заблокированной секции кода создаёт проблемы. Можно заблокировать некий общий ресурс — в случае разработки игр время фрейма тоже является общим ресурсом, причём очень и очень ограниченным — и начать долгую операцию, например, распаковку текстуры. Можно запустить операции ввода-вывода, которые уже сами по себе несут накладные расходы и содержат внутренние блокировки ОС или фреймворка, тем самым задерживая все остальные потоки.

Хуже всего, когда в попытках улучшить производительность игры мы приходим к ситуации взаимной блокировки (deadlock). Они в любом случае будут, как бы правильно вы ни спроектировали свой код. Чем больше мьютексов в приложении, тем выше шансы возникновения deadlock-ситуаций. И всё — никто никуда не едет, даже если полосы свободны.

Кроме всем понятного deadlock, который, кстати, может быть вызван несколькими причинами:

• Mutual Exclusion (взаимное исключение): Ресурс может использоваться только одним потоком.

• Hold and Wait (удержание и ожидание): Поток удерживает ресурс и ждёт другой.

• No Preemption (отсутствие вытеснения): Ресурс нельзя отобрать у потока.

• Circular Wait (циклическое ожидание): Цепочка потоков, каждый из которых ждёт ресурс от следующего.

Есть еще проблема инверсии приоритетов (Priority Inversion), когда низкоприоритетный поток или задача удерживает ресурс, необходимый высокоприоритетному, из-за чего тот не может выполняться. Это может привести к значительным задержкам и падению производительности. Как это было например в CP2077 с падением fps в толпе на релизе: помню, я долго боролся с этим багом, пока на одном из форумов не нашел мод, который просто снижал приоритет для навигации AI пешеходов, а то FPS проседал до 8, хотя в среднем держался стабильно выше 40

Архитектура RED4 довольно классическая для игровых движков, где потоки распределены следующим образом:

• Главный поток: отвечает за логику игры, обработку физики, анимацию и обновление состояния мира.

• Поток рендеринга: выполняет подготовку и отправку данных для видеокарты. Работает параллельно с главным потоком.

• Рабочие потоки для тасок: используются для выполнения всех второстепенных, таких как ИИ NPC, трафик, загрузка ассетов, обновление навигационных данных и все остальное.

Потоки пешеходов и трафика активно использовали общие данные о позициях NPC и граф навигации. Как я понял из обсуждения на форуме, таски ИИ пешеходов несколько раз за фрейм обновляли позиции NPC, которые одновременно использовались потоком рендеринга для отрисовки. Эти данные защищались синхронизационными примитивами. Если таска навигации надолго захватывала ресурс при расчёте сложного маршрута, рендеринг был вынужден ждать, что приводило к статтерам, микрозависаниям и резкому снижению частоты кадров. Особенно это проявлялось в районах с высокой плотностью NPC и сложной застройкой (например, рынок в районе Кабуки) FPS мог падать с 40 до 10, а игра «подфриживала» при резком повороте камеры, когда потоку рендеринга приходилось ожидать освобождения заблокированных данных, в то время как движок пытался пересчитать маршруты сразу для многих NPC, если игрок создавал затор или провоцировал толпу.

Проблема усугублялась тем, что в REDEngine основная логика игры, включая физику, анимацию и обработку событий, выполнялась в главном потоке, тогда как рендеринг и рабочие потоки работали параллельно. Из-за этого приоритет выполнения второстепенных задач начинал влиять на всё вокруг приводя к каскадным задержкам (подробнее тут https://www.gdcvault.com/play/1020197/Landscape-Creation-and-Rendering-in и тут https://gdcvault.com/play/1034318/A-Ticket-to-Redemption-How). Это очень странно, потому что теже люди сделали прекрассный Witcher 3: Blood and Wine, где все это бегало, прыгало и не тормозило на заведомо более слабом железе (https://youtu.be/9vEfH9SJ9mY).

Эффект перегруженной очереди (Convoying) — замедление работы из-за того, что множество задач выстраиваются в очередь за общим ресурсом, даже если они не конфликтуют при выполнении. Реальный пример в Crysis — бочки.

Для обработки физики и эффектов взрывов в этом движке используется пул рабочих потоков. Но бочки используют один и тот же эффект, а сами инстансы эффектов хранятся в списках по типу эффекта, доступ к списку защищён мьютексом. Физика отрабатывает свои таски вполне сносно, даже на 500 бочках движок выдает приличный фпс, пока бочки не начинают взрываться и добавлять свои эффекты одновременно в этот список.

Хотя движок без заметной просадки обрабатывает сотни разных объёмных эффектов на сцене в обычной ситуации (дым, следы пуль и повреждения), он плохо справляется конкретно с такими сценариями. Т.е. воркеров много, но все они упираются в доступ к одному ресурсу, из-за чего возникает общая просадка производительности.

Но всё же, блокировки позволяют писать код намного проще — так, будто потоки работают последовательно. Это соответствует нашему естественному линейному мышлению, где каждое действие идёт одно за другим.

Мозг вообще плохо справляется с истинной параллельностью (как и код без синхронизации), и блокировки упрощают моделирование: «Сначала делай ты, потом я» — как в реальной жизни. Это снижает нагрузку при проектировании систем и делает логику более предсказуемым. Несмотря на общую понятность, современные игры требуют всё больше ресурсов и всё меньших задержек, особенно рендер и звук, для которых даже минимальные задержки чреваты десинком кадра, дёргами, глитчами, шипением звука, щелчками и другими прелестями десинка.

Например, если поток аудио-рендеринга блокируется на доступе к буферу звука или не успевает наполнять его, вы услышите характерное «щёлканье» или хрип, а если блокируется рендер, это приводит к визуальным артефактам (глитчам), микрофризам(статтерам).

Non-blocking logic

Тут на сцене появляется безлоковое (lock-free) программирование, которое обещает потенциально быстрые и безопасные примитивы и алгоритмы для многопоточных приложений. Работа таких алгоритмов возможна благодаря существованию некоторого набора атомарных примитивов, которые дают строгие гарантии о прогрессе потоков и их взаимодействии.

Этот набор примитивов весьма ограничен. В 2003 году Морис Херлихи защитил свою работу "Wait-Free Synchronization", опубликованную ещё в 1991 году, где показал, какие примитивы подходят для построения безлоковых структур данных, а какие нет. Это исследование стало фундаментом для последующих разработок Intel и AMD в области параллельных вычислений, что не только изменило подход к проектированию многопоточных систем, но и предопределило дальнейшее развитие аппаратных архитектур.

Также в своей работе он показал невозможность реализации некоторых операций для корректной синхронизации более чем двух потоков, например test-and-set, swap, fetch-and-add. Саму работу, думаю, вы сможете найти самостоятельно. Статья сложная — предупреждаю сразу, я не осилил все нюансы даже с помощью более опытных коллег.

Самым большим достижением, кмк, было доказательство универсальности некоторых простых примитивов, с помощью которых можно реализовать любой безлоковый алгоритм для любого количества потоков, которые потом в том или ином виде появились в большинстве языков. Самым простым и популярным примитивом, является операция Compare-and-Swap (CAS):

template <class T>
bool compare_and_swap(T* addr, T exp, T val) {
    if (*addr == exp) {
        *addr = val;
        return true;
    }
    return false;
}

Примитив сравнивает содержимое памяти по адресу addr с ожидаемым значением exp. Если значения совпадают, addr обновляется новым значением val. Вся операция (примитив) должна выполняться атомарно.

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

Не используйтe lock-free без надобности

Вы мне, конечно, не поверите. Но, пройдя через опыт создания и портирования нескольких игр и движков с большим количеством параллельных задач, я могу дать один главный совет. Lock-free алгоритмы — это не столько серебряная пуля, сколько рискованная область с огромным количеством подводных камней. Они требуют глубокого понимания программирования в целом, многопоточного программирования в частности, а также хорошего знания аппаратных особенностей и устройства памяти.

Иногда лучше потерять миллисекунду на фрейме и поискать, где её можно нарыть в другом месте, чем иметь кучу невоспроизводимых багов. А ещё хуже — ловить редкие краши или графические глитчи, которые проявляются только на определённых конфигурациях железа, да ещё и через часы работы.

Но я всего лишь пишу статьи на Хабре и немного знаю плюсы. Может, кто-то из этих людей окажется более убедительным?