Геймдев на Lisp. Часть 1: ECS и металингвистическая абстракция

В данной серии практических руководств мы подробно рассмотрим создание несложных 2D-игр на Common Lisp. Результатом первой части станет настроенная среда разработки и простая симуляция, отображающая двумерную сцену с большим количеством физических объектов. Предполагается, что читатель владеет некоторым языком программирования высокого уровня, в общих чертах представляет, как на экране компьютера отображается графика, и заинтересован в расширении своего кругозора.

Common Lisp — язык программирования с богатой историей, предоставляющий эффективные инструменты для разработки комплексных интерактивных приложений, каковыми являются видеоигры. Данная серия руководств ставит перед собой задачу наглядно продемонстрировать ряд возможностей CL, отлично вписывающихся в контекст разработки игровых приложений. Общий обзор таковых возможностей и особенностей Common Lisp приводится в статье Юкари Хафнер "Использование высокодинамичного языка для разработки".

Многие возможности, впервые появившиеся в Lisp, такие, как условный оператор if/then/else, функции как объекты первого класса, сборка мусора и другие давно перекочевали в мейнстримные языки программирования, однако есть одна уникальная возможность, которую мы рассмотрим сегодня, и это — металингвистическая абстракция.

Металингвистическая абстракция

Чтобы вникнуть в данную концепцию, обратимся к известному фундаментальному учебнику "Структура и интерпретация компьютерных программ":

...однако по мере того, как мы сталкиваемся со все более сложными задачами, мы обнаруживаем, что Лиспа, да и любого заранее заданного языка программирования, недостаточно для наших нужд. Чтобы эффективнее выражать свои мысли, постоянно приходится обращаться к новым языкам. Построение новых языков является мощной стратегией управления сложностью в инженерном проектировании; часто оказывается, что можно расширить свои возможности работы над сложной задачей, приняв новый язык, позволяющий нам описывать (а следовательно, и обдумывать) задачу новым способом, используя элементы, методы их сочетания и механизмы абстракции, специально подогнанные под стоящие перед нами проблемы.
Метаязыковая абстракция (metalinguistic abstraction), то есть построение новых языков, играет важную роль во всех отраслях инженерного проектирования.
...c этой мыслью приходит и новое представление о себе самих: мы начинаем видеть в себе разработчиков языков, а не просто пользователей языков, придуманных другими.

Итак, важный механизм, предоставляемый практически любым диалектом Лиспа, включая, конечно, один из самых мощных из них Common Lisp, — это возможность создания собственных языковых конструкций внутри уже данного нам языка. Данная концепция также известна под названием DSL (Domain Specific Languages), однако лишь в диалектах Лиспа она невероятно тесно интегрирована в их суть. В большинстве из них механизм металингвистической абстракции выстраивается вокруг т.н. макросов, специальных функций, определяемых программистом, которые вызываются на этапе компиляции и возвращают небольшие фрагменты кода программы для подстановки компилятором в место, где они встречаются; особенность Лиспов состоит в том, что код на них по сути является обычным вложенным списком, что позволяет легко и эффективно генерировать и обрабатывать фрагменты кода программы.

Есть масса различных способов креативно использовать и эксплуатировать эту возможность. Я хотел бы рассказать о созданной мной библиотеке макросов cl-fast-ecs, которая предоставляет мини-язык для описания игровых объектов и процессов их обработки с использованием паттерна Entity-Component-System, часто используемого в разработке игр.

Entity Component System

ECS — довольно нехитрый паттерн организации хранения и обработки данных в игровых приложениях, который позволяет достигнуть сразу две важные концептуальные цели:

1. гибкость в определении и изменении структуры игровых объектов,

2. производительность за счёт эффективной утилизации кэшей центрального процессора.

Гибкость, интерактивность и возможность переопределять поведение программы "на ходу" — краеугольные камни большинства Lisp-подобных языков. Мы вернёмся к этому вопросу позднее, а пока остановимся чуть подробнее на второй цели, которая часто преподносится как основное преимущество паттерна ECS. Начнём издалека.

В фон-неймановской архитектуре, используемой на данный момент в большинстве вычислительных устройств, существует фундаментальная проблема, называемая "бутылочным горлышком фон Неймана". Суть её состоит в том, что насколько быстро данные ни обрабатывались бы центральным процессором, скорость их обработки ограничена производительностью памяти. Более того, производительность системы "CPU-память" ограничена сверху пропускной способностью шины, по которой данные узлы обмениваются информацией, и эта величина не может расти бесконечно или хотя бы с той же скоростью, с которой растёт производительность CPU. Проблему ярко иллюстрирует следующий график:

Кривая, помеченная "Processor", отображает количество запросов к памяти, которое CPU может сделать за единицу времени; кривая "Memory" отображает количество запросов, которое RAM способна обработать за единицу времени (оба значения отнормированы к средним значениям за 1980 г.). Даже поверхностно проанализировав график, можно прийти к неутешительному выводу — большую часть времени процессор простаивает в ожидании данных от памяти, и со временем разрыв между производительностью процессора и памяти становится всё больше.

Уже в начале девяностых, с выходом Intel 486, распространённым решением данной проблемы в железе широкого потребления стал кэш, находящийся на одном кристалле с процессором — небольшая, но крайне быстрая память, в которой хранятся данные, запрошенные процессором раннее, что позволяет сократить длительность последующих запросов к этим же данным, получая их из кэша вместо более медленной главной памяти. Ближе к концу девяностых кэш стал ещё и разделяться на несколько уровней (L1, L2 и т.д.), каждый последующий уровень имеет бо́льший объём, но также и бо́льшую латентность, впрочем, сильно уступающую латентности доступа к основной RAM. Типичные тайминги взаимодействия десктопного железа с памятью на момент 2020 г. выглядят следующим образом:

• регистр процессора: <1 нс

• L1 кэш: 1 нс

• L2 кэш: 3 нс

• L3 кэш: 13 нс

• RAM: 100 нс

(источник: dzone.com)

Кэш CPU здорово помогает в оптимизации последовательного доступа к ячейкам памяти: даже когда процессор обращается к RAM за одним-единственным байтом, ему в ответ приходит и "оседает" в кэше целая кэш-линия, на современных x86 имеющая длину 64 байта (512 бит). Таким образом, если мы в коде последовательно обрабатываем элементы некоторого массива, хранящего, скажем, числа с плавающей запятой одинарной точности длиной в 32 бита (более известные как float), при обращении к первому элементу мы получим от RAM не только запрошенный, но также последующих элементов, и на следующих 15 итерациях цикла получение элемента будет занимать 1 нс вместо 100 нс. Получается, благодаря кэшу наш цикл, вне зависимости от длины массива, работает в раз быстрее! На этом примере видно, как важно с точки зрения производительности обрабатывать данные так, чтобы они оставались "горячими" в кэше.

Чтобы понять, как архитектурный паттерн ECS способствует утилизации кэша, давайте рассмотрим его основные составляющие:

• entity (сущность) — составной игровой объект;

• component (компонент) — данные, описывающие некоторую логическую грань объекта;

• system (система) — код, обрабатывающий объекты определённой структуры.

Давайте сначала разберёмся с сущностями и компонентами на конкретном примере:

По горизонтали у нас отображены разноцветными прямоугольниками компоненты: Position, Movement, Render и так далее. Обратите внимание, что каждый из этих компонентов может содержать несколько полей с данными, например, Position и Movement почти наверняка будут содержать поля x и y. Далее, по вертикали в скобках подписаны сущности — Alien, Player и т.д. Каждая сущность имеет определённый набор компонентов. Что более важно, к любой сущности мы можем "на ходу", в рантайме, добавить или удалить некоторые компоненты, чем мы поменяем её структуру и, как следствие, поведение и статус в игровом мире, и всё это без перекомпиляции кода игры! Этим достигается первая концептуальная цель ECS, указанная выше — гибкость структуры игровых объектов.

Вышеприведённая иллюстрация, если взглянуть на неё слегка прищурившись, сильно напоминает обычную экселевскую таблицу. И по своей сути, ECS таковой и является