live13 (live13) wrote,
live13
live13

Category:

Шаблоны игрового программирования. Байткод (2-я часть главы)

Байткод (Bytecode)



Первая часть главы
Оглавление


Архитектурные решения



Я старался сохранить эту главу настолько простой, насколько это возможно, но все что мы на самом деле сделали - это создали новый язык. Это прекрасное открытое пространство для творчества. Исследовать его - громадное удовольствие, но при этом нужно не забывать и о самой игре.

    Но раз уж эта глава получилась самой длинной в книге - значит с задачей я не справился.


Как инструкции будут получать доступ к стеку?



Виртуальные машины с байткодом делятся на два основных подвида: основанные на стеке(stack-based) и основанные на регистрах(register-based). В виртуальных машинах, основанных на стеках, инструкции всегда работают с верхом стека, как в наших примерах кода. Например, INST_ADD берет сверху два значения, складывает их и помещает на верх стека результат.

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


  • Виртуальные машины на основе стека:

    • Инструкции минимального размера. Так как каждая инструкция берет аргументы с верха стека, для этого не нужно декодировать никаких данных. Это значит что каждая инструкция довольно мала и обычно занимает один байт.

    • Генерация кода проще. Когда вы будете писать компилятор или инструмент для вывода байткода, вы увидите что генерировать байткод для стека проще. Так как каждая инструкция работает с вершиной стека, вам нужно просто вывести инструкции в правильном порядке чтобы между ними передавались параметры.

    • У вас будет больше инструкций. Каждая инструкция видит только верх стека. Это значит что для того чтобы сгенерировать код типа a = b + c, вам нужно будет использовать отдельные инструкции для помещения b и c наверх стека, выполнить операцию и потом поместить результат в a.



  • Виртуальные машины на основе регистров:

    • Инструкции больше. Так как инструкциям нужно указывать откуда из стека брать аргументы, сами инструкции будут требовать больше бит для описания. Например, в Lua - наверное самой известной виртуальной машине на основе регистров - на инструкцию отводится целых 32 бита. 6 из них используется для типа инструкции, а остальные - для аргументов.

      1. Lua не определяет собственную форму байткода и меняет ее от версии к версии. То, что я написал выше - справедливо для Lua 5.1. Прекрасное введение в Lua можно прочитать здесь.

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





Так что же вам выбрать? Я рекомендую остановиться на варианте виртуальной машины со стеком. Ее легче реализовывать и гораздо проще генерировать код для нее. Виртуальная машина на базе регистров получила репутацию более быстрой после того как на нее перешла Lua, но это все сильно зависит от ваших инструкций и многих других деталей реализации виртуальной машины.

Какие инструкции у нас бывают?



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


  • Внешние примитивы. Это те, которые выходят за пределы виртуальной машины, попадают в другие части игры и отвечают за видимые пользователем вещи. Они отвечают за типы реального поведения, которое можно выразить в байткоде. Без них ваша виртуальная машина не сможет делать ничего кроме пустого прожигания циклов процессора.

  • Внутренние примитивы. Это значения, которыми мы манипулируем внутри самой виртуальной машины типа литералов, арифметики, операторов сравнения и инструкций для жонглирования стеком.

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

    В нашей инструкции цикла будет присутствовать индекс чтобы следить за тем где в байткоде мы находится. Все переходы выполняются изменением этой переменной и присваиванием нового значения где мы теперь находимся. Другими словами это goto. С его помощью можно устроить любые условные переходы более высокого уровня.

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

    В простейшей форме они представляют собой всего лишь переход. Единственная разница заключается в том что виртуальная машина поддерживает второй возвращаемый стек. Когда она выполняет инструкцию "вызова(call)", она помещает индекс текущей инструкции в возвращаемый стек и затем делает переход к вызванному байткоду. Когда мы доходим до "возврата (return)", виртуальная машина берет из возвращаемого стека индекс и переходит по нему назад.



В каком виде могут быть представлены значения?



Наша простенькая виртуальная машина работает только с одним типом данных - целыми. Это все сильно упрощает, потому что наш стек - это просто стек целых чисел. В более совершенной виртуальной машине поддерживаются разные типы данных: строки, объекты, списки и т.д. И конечно нам нужно определиться с тем как мы будем их хранить.


  • Единый тип данных:


    • Это просто. Вам не нужно беспокоиться о тегах, преобразованиях и проверках типа.

    • Вы не можете работать с разными типами данных. Очевидный недостаток. Попытка хранить разные типы данных в едином представлении - например чисел в виде строк - не лучшее решение.



  • Вариант с тегами (tagged ):

    Это обычное представление для языков с динамической типизацией. Каждое значение состоит из двух частей. Первая часть - это таг типа enum, означающий какой тип данных внутри хранится. Оставшиеся биты интерпретируются в соответствии с указанным типом:


    enum ValueType
    {
    TYPE_INT,
    TYPE_DOUBLE,
    TYPE_STRING
    };

    struct Value
    {
    ValueType type;
    union
    {
    int intValue;
    double doubleValue;
    char* stringValue;
    };
    };



    • Значения знают свой тип. Преимуществом этого решения является то что мы можем проверить тип значения во время выполнения. Это важно для динамической диспетчеризации и проверки того, что вы не пытаетесь выполнить операцию над типом, который ее не поддерживает.

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



  • Безтеговые объединения (untagged union):

    Здесь тоже используется union, как и в предыдущем случае, но вместе с ним не хранится тип данных. У вас может быть кучка бит, представляющих больше чем один тип и правильная их интерпретация - это уже ваша забота.

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

      Еще именно таким образом хранят данные нетипизированные языки программирования, такие как ассемблер или Forth. Эти языки возлагают ответственность за правильное использование типов на пользователя. Подход явно не для слабонервных!



    • Этот вариант компактен. У вас есть возможность забронировать больше битов для хранения самого значения.

    • Это быстро. Отсутствие тегов означает что вам не придется тратить такты процессора на их проверку во время выполнения. Именно поэтому языки со статическим типизированием настолько быстрее языков с динамическими типами.

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


      1. Если ваш байткод скомпилирован из языка со статической типизацией, вы можете подумать что теперь вы в безопасности потому что компилятор не сгенерирует некорректный байткод. Это может быть и правдой, но помните что пользователь злоумышленник может сгенерировать зловредный код и без компилятора.

        Вот поэтому например в Java Virtual Machine перед выполнением программы запускается верификация байткода.



  • Интерфейс:

    Объектно-ориентированное решение для значения, которое может быть в одном из нескольких состояний с помощью полиморфизма. Интерфейс предоставляет виртуальные методы для различных типов тестов и конвертирования в таком духе:


    class Value
    {
    public:
    virtual ~Value() {}

    virtual ValueType type() = 0;

    virtual int asInt() {
    // Можно вызывать только для целых.
    assert(false);
    return 0;
    }

    // Другие методы конвертации...
    };


    Далее мы сделаем конкретные классы для разных типов данных, наподобие:


    class IntValue : public Value
    {
    public:
    IntValue(int value)
    : value_(value)
    {}

    virtual ValueType type() { return TYPE_INT; }
    virtual int asInt() { return value_; }

    private:
    int value_;
    };



    • Неограниченные возможности. Вы всегда можете определить новый класс за пределами виртуальной машины. Главное чтобы он реализовывал базовый интерфейс.

    • Объектно-ориентированность. Если вы придерживаетесь принципов ООП, такой подход реализует диспетчеризацию типов "правильным" образом, т.е. определяет специфичное для типа поведение, а не занимается чем-то типа переключения поведения в зависимости от тега.

    • Многословность. Вам нужно определить отдельный класс с полным набором возможностей для каждого типа данных. Обратите внимание что в предыдущих примерах мы продемонстрировали полное определение всех типов значений. А здесь ограничились только одним!

    • Неэффективность. Чтобы воспользоваться свойствами полиморфизма нам нужно выполнить переход по указателю. А это значит, что даже такое простейшее значение как булевское значение или число обернуты в объект, выделенный в куче. Каждый раз при получении значения нужно будет выполнять вызов виртуального метода.

      В таком ответственном коде как ядро виртуальной машины, даже самое незначительное снижение производительности может быть критичным. На самом деле такое решение страдает от тех же проблем, из-за которых мы отказались от шаблона Интерпретатор с тем лишь отличием что проблема у нас теперь в значении, а не коде.





Вот что я рекомендую: Если вы способны ограничиться единственным типом данных - так и сделайте. В противном случае используйте объединение с тегом. Именно так и работает большинство интерпретаторов в мире.

Как генерируется байткод?



Самый главный вопрос я оставил напоследок. Я показал вам как применять и как интерпретировать байткод, но создавать что-то, с помощью чего можно производить байткод придется вам. Обычно для этого пишется компилятор, но это не единственное решение.


  • Если вы определяете язык на текстовой основе:


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

      Дизайн синтаксиса - это дизайн пользовательского интерфейса и этот процесс не становится легче от того что интерфейс сводится к строкам или символам.

    • Вам придется реализовать парсер. Несмотря на репутацию эта часть довольно простая. Вы можете использовать генератор наподобие ANTLR или Bison или по моему примеру самостоятельно написать рекурсивный спуск.

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

    • Этот способ практически недоступен для технически неподкованных пользователей. Мы программисты любим текстовые файлы. Вместе с мощными инструментами командной строки мы можем думать о них как о компьютерных LEGO блоках: простые, но легко сочетаемые миллионом способов.
      Большинство непрограммистов так текстовые файлы не воспринимают. Для них это подобно заполнению налоговой декларации для роботизированного аудитора, который ругается на них даже если они забыли поставить единственную точку с запятой.



  • Если вы разрабатываете графический инструмент:


    • Вам придется заниматься пользовательским интерфейсом. Кнопки, нажатия, перетаскивания и все такое. Некоторых от этого коробит, а мне лично даже нравится. Если вы пойдете по этому пути, крайне важно воспринимать пользовательский интерфейс как залог плодотворной работы дизайнера, а не как неприятную обязанность.

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

    • У вас будет меньше ошибок. Так как пользователь выстраивает поведение интерактивно шаг за шагом, ваше приложение может оберегать его от ошибок прямо во время работы.

      В текстовом языке инструмент не видит ничего из пользовательского контента пока не получит весь файл целиком. Поэтому там предотвращать ошибки гораздо сложнее.

    • Сложность портирования. Преимущество текстового файла заключается в том, что текстовый файл универсален. Простой компилятор просто считывает один файл и записывает другой. Портировать его на другую ОС - задача тривиальная.

        Если конечно забыть про символы перевода строки. Эх...


      Когда вы разрабатываете пользовательский интерфейс, вам нужно выбрать для этого определенный фреймворк и многие из них специфичны для конкретной ОС. Есть конечно и кроссплатформенные тулкиты для пользовательского интерфейса, но они обычно платят за кроссплатформенность привычностью: на любой платформе они смотрятся одинаково странными.





Смотрите также



Этот шаблон очень близок шаблону Интерпретатор ( Interpreter) GoF. Они оба позволяют вам выражать сложное поведение с помощью данных.

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

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


  • Язык программирования Lua - это самый известный скриптовый язык из используемых в играх. Внутри он реализован как крайне компактная виртуальная байткод машина на основе регистров.

  • Kismet - это графический скриптовый инстурмент, встроенный в UnrealEd - редактор движка Unreal engine.

  • Мой собственный скриптовый язык Wren - это простой интерпретатор байткода на основе стека.


Tags: c++, design patterns, game programming, programming, игры, книги, перевод, программирование, шаблоны, шаблоны проектирования
Subscribe

  • Fargo не так прост!

    Я уже писал что 4-й сезон вызвал у меня несколько смешанные чувства. С одной стороны это все так же стройная история, крайне достойно…

  • Про Некромунду

    Тут на подходе книга про Орлоков ожидается. А еще занимательный аванпост в пластике выпускают. Стоит даже несколько штук взять. Жаль пока не…

  • О том что случается когда фабрики стоят

    Примерно лет 12 назад (ну или оклол) качественные цифровые фотокамеры стали доступны даже фотолюбителям. И тогда очень был популярен мем про…

promo live13 may 11, 2014 17:58 46
Buy for 50 tokens
Примерно неделю назад я писал, что заинтересовался этой online-книжкой http://gameprogrammingpatterns.com/ и решил сделать ее перевод. Сам я мог бы ограничиться и английским вариантом, но думаю многим перевод пригодится. В прошлом я уже занимался переводом книг. Не как основной работой. Так,…
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments