Виртуальная машина Koei
Недавно я обнаружил забавный фактик на форумах nesdev (англ.): forums.nesdev.com/viewtopic.php?f=2&t=15931
Есть такая японская игростроительная фирма — Koei.
Основана она была в 1978 году и разумеется в начале истории выпускала кучу игр для 8-биток.
И в этом смысле фирма была всеядной — одни и те же игры выпускала и на NES и на MSX и на Amiga и на DOS и PC-98 и каких то уже мало мне известных FM-7, Sharp X1, Sharp X68000 и WonderSwan.
В общем плодовитость и по числу игр и по платформам где они выходили даже в ранние 8/16-битные годы была существенной.
Так вот — некто AWJ с форумов nesdev обнаружил, что все игры этой компании на NES кроме Mahjong Taikai используют один и тот же байткод некой виртуальной машины которая по своему внутреннему устройству как будто бы создана для того чтобы интерпретировать код на Си.
Немного позднее по теме выяснится, что в игре Aerobiz Supersonic от этой же фирмы на SNES в ROM картриджа сохранились небольшие фрагменты кода на Си: tcrf.net/Aerobiz_Supersonic_%28SNES%29 так что эта догадка блестяще подтвердилась — Koei явно использовала Си для кроссплатформы и на разных платформах видимо использовала разные виртуальные машины для интерпретации байткода, который суть уплотнял код так что его проще было запихать в ограниченные картриджи.
Более того — как минимум 1988 года и на 16-битных системах этот Koei Си мог генерировать и полноценный машинный код и более того — перемежать в одном и том же проекте машинную компиляцию с компиляцией в байткод.
Подробно работу этой виртуальной машины AWJ расписывает (англ.) там в теме, здесь же я вкратце обрисую её архитектуру.
Машина в начале памяти (в zero-page MOS 6502) располагает свои регистры, три из которых 16-битные, а два — 32-битные:
Левый и правый регистры названы так самим AWS в силу того, что в первый попадает результат операции, а в правом хранится операнд как во всяких a += b;
Каждая функция в байткоде начинается с машинной инструкции MOS 6502 вызова интерпретатора (JSR) и заголовка обозначающего сколько у функции локальных переменных и т.п. Интерпретатор реентерабельный и таким образом вплетается бесшовно в машинный код. Поэтому инструкция вызова машинного кода и инструкция вызова байт-кода в интерпретаторе есть одна и та же инструкция.
Кроме интерпретатора игры обычно содержат небольшое количество машинного кода — ну как сами интерпретатор так и обработчики прерываний и всякие вещи которые требовали тяжёлой оптимизации, но их вроде бы совсем немного обычно.
Вся арифметика совершенно по сишному или 16-битна или 32-битна. 8-битные значения сперва расширяются до 16 бит еще при загрузке в регистры.
Здесь стоит вспомнить, что машинный код 6502 весьма неплотен если речь идёт про 16-битные вычисления — сложение например надо делать в несколько операций постоянно перекладывая из аккумулятора в память. Даже просто загрузка константы (вшитой в код) в 16-битную ячейку памяти — это четыре инструкции в худшем случае занимающие 10 байт. Да, они выполнятся максимально быстро, но займут 10 байт.
А ведь даже на 8-битных машинах очень много 16-битного кода и виртуальная машина Koei это поддерживает — все основные короткие виды инструкций — 16-битные, а например вся 32-битная машинерия делается через префикс инструкции 0xB7.
Кстати тут выявляется забавность — инструкция 0xB728 по логике вещей должна была бы быть logical not (!LEFT) для 32-битного LEFT, но скорее всего по ошибке делает то же самое что 32-битное left != right (код 0xB71D). AWS прошерстил все игры Koei на NES и обнаружил что ни в одной из них не используется 32-битный logical not, так что видимо поэтому баг остался необнаруженным в своё время.
Помимо этого байткод Koei использует много трюков для оптимизации размера.
Так в нём очень много вариантов инструкций LOADL, LOADR и STORE. Это загрузки левого и правого регистров и сохранение левого регистра (результата) соответственно (названия выдумал AWS).
Много инструкций имеет в 16-ричном представлении вид 0xAB, где A — это код инструкции, а B — непосредственное данное от 0 до 15.
Так вот, во первых есть такие однобайтовые инструкции LOADL/LOADR где можно в LEFT или RIGHT за 1 байт загрузить число от 0 до 15 (с расширением до 16 бит).
Во вторых существуют однобайтовые варианты и LOADL/LOADR и STORE где число 0-15 обозначает 16-битное значение в стеке — от 0 до 11 это локальные переменные функции (отрицательные смещения от указателя фрейма) и 12-15 это четыре 16-битных аргумента (возможных конечно же). Таким образом 4 аргумента и 12 локальных переменных в байткоде Koei можно очень эффективно грузить в LEFT/RIGHT однобайтовыми инструкциями.
Если и этого не хватает, то есть уже двухбайтовые варианты этих инструкций где 1 байт выделен на смещение и, наконец, трёхбайтовые где можно адресовать всю память 16-битного адресного пространства.
Практически вся арифметика/логика делается так — сперва в LEFT/RIGHT загружаются через вышеприведённые инструкции два аргумента и потом идёт опкод выполняющий нечто вроде LEFT *= RIGHT, и далее через STORE результат сохраняется обратно в стек. Единственная инструкция у которой есть вариант работающий сразу с непосредственным данным (0-16) или данным в стеке по короткой адресации — это ADD. Как опять таки понятно — потому что часто нужно и существенно сэкономит размер.
Так, например, вещи типа if ( a >= b ) {… } делаются так: a и b грузятся в регистры, выполняется operator>= который поместит в LEFT 0 если условие ложно или 1 если условие истинно (т.е. то как булевы реально в спецификации Си должны приводится к int) и единственные инструкции условных переходов в самой виртуальной машине Koei выполняются если LEFT==0 и если LEFT!=0.
В общем плотность кода в такой среде конечно же вырастает и просто в разы.
Однако и скорость выполнения сильно падает — по моим оценкам где то на порядок.
На слабенькой 8-битной денди это было бы фатально, но тут видимо помогает то, что основная масса игр Koei в ту эпоху была всяческими стратегическими симуляторами, например менеджеры управления аэропортами, древними японскими империями и т.п. Т.е. игры медленные, вдумчивые, и не требующие от видеочипа невероятных эквилибристик на пределе возможного.
Видимо так и выкручивались.
Так что похоже такая плодовитость конторы была неслучайной и подпитывалась внедрением передовых технологий и виртуальных кросс-платформенных машин прямо в 8 бит! :)
Есть такая японская игростроительная фирма — Koei.
Основана она была в 1978 году и разумеется в начале истории выпускала кучу игр для 8-биток.
И в этом смысле фирма была всеядной — одни и те же игры выпускала и на NES и на MSX и на Amiga и на DOS и PC-98 и каких то уже мало мне известных FM-7, Sharp X1, Sharp X68000 и WonderSwan.
В общем плодовитость и по числу игр и по платформам где они выходили даже в ранние 8/16-битные годы была существенной.
Так вот — некто AWJ с форумов nesdev обнаружил, что все игры этой компании на NES кроме Mahjong Taikai используют один и тот же байткод некой виртуальной машины которая по своему внутреннему устройству как будто бы создана для того чтобы интерпретировать код на Си.
Немного позднее по теме выяснится, что в игре Aerobiz Supersonic от этой же фирмы на SNES в ROM картриджа сохранились небольшие фрагменты кода на Си: tcrf.net/Aerobiz_Supersonic_%28SNES%29 так что эта догадка блестяще подтвердилась — Koei явно использовала Си для кроссплатформы и на разных платформах видимо использовала разные виртуальные машины для интерпретации байткода, который суть уплотнял код так что его проще было запихать в ограниченные картриджи.
Более того — как минимум 1988 года и на 16-битных системах этот Koei Си мог генерировать и полноценный машинный код и более того — перемежать в одном и том же проекте машинную компиляцию с компиляцией в байткод.
Подробно работу этой виртуальной машины AWJ расписывает (англ.) там в теме, здесь же я вкратце обрисую её архитектуру.
Машина в начале памяти (в zero-page MOS 6502) располагает свои регистры, три из которых 16-битные, а два — 32-битные:
адрес| разм | регистр
-----+------+----------------
$02 | 2 | указатель стека (SP)
$04 | 2 | указатель фрейма (BP)
$06 | 2 | указатель инструкции (PC)
$08 | 4 | "левый" регистр
$0C | 4 | "правый" регистр
Левый и правый регистры названы так самим AWS в силу того, что в первый попадает результат операции, а в правом хранится операнд как во всяких a += b;
Каждая функция в байткоде начинается с машинной инструкции MOS 6502 вызова интерпретатора (JSR) и заголовка обозначающего сколько у функции локальных переменных и т.п. Интерпретатор реентерабельный и таким образом вплетается бесшовно в машинный код. Поэтому инструкция вызова машинного кода и инструкция вызова байт-кода в интерпретаторе есть одна и та же инструкция.
Кроме интерпретатора игры обычно содержат небольшое количество машинного кода — ну как сами интерпретатор так и обработчики прерываний и всякие вещи которые требовали тяжёлой оптимизации, но их вроде бы совсем немного обычно.
Вся арифметика совершенно по сишному или 16-битна или 32-битна. 8-битные значения сперва расширяются до 16 бит еще при загрузке в регистры.
Здесь стоит вспомнить, что машинный код 6502 весьма неплотен если речь идёт про 16-битные вычисления — сложение например надо делать в несколько операций постоянно перекладывая из аккумулятора в память. Даже просто загрузка константы (вшитой в код) в 16-битную ячейку памяти — это четыре инструкции в худшем случае занимающие 10 байт. Да, они выполнятся максимально быстро, но займут 10 байт.
А ведь даже на 8-битных машинах очень много 16-битного кода и виртуальная машина Koei это поддерживает — все основные короткие виды инструкций — 16-битные, а например вся 32-битная машинерия делается через префикс инструкции 0xB7.
Кстати тут выявляется забавность — инструкция 0xB728 по логике вещей должна была бы быть logical not (!LEFT) для 32-битного LEFT, но скорее всего по ошибке делает то же самое что 32-битное left != right (код 0xB71D). AWS прошерстил все игры Koei на NES и обнаружил что ни в одной из них не используется 32-битный logical not, так что видимо поэтому баг остался необнаруженным в своё время.
Помимо этого байткод Koei использует много трюков для оптимизации размера.
Так в нём очень много вариантов инструкций LOADL, LOADR и STORE. Это загрузки левого и правого регистров и сохранение левого регистра (результата) соответственно (названия выдумал AWS).
Много инструкций имеет в 16-ричном представлении вид 0xAB, где A — это код инструкции, а B — непосредственное данное от 0 до 15.
Так вот, во первых есть такие однобайтовые инструкции LOADL/LOADR где можно в LEFT или RIGHT за 1 байт загрузить число от 0 до 15 (с расширением до 16 бит).
Во вторых существуют однобайтовые варианты и LOADL/LOADR и STORE где число 0-15 обозначает 16-битное значение в стеке — от 0 до 11 это локальные переменные функции (отрицательные смещения от указателя фрейма) и 12-15 это четыре 16-битных аргумента (возможных конечно же). Таким образом 4 аргумента и 12 локальных переменных в байткоде Koei можно очень эффективно грузить в LEFT/RIGHT однобайтовыми инструкциями.
Если и этого не хватает, то есть уже двухбайтовые варианты этих инструкций где 1 байт выделен на смещение и, наконец, трёхбайтовые где можно адресовать всю память 16-битного адресного пространства.
Практически вся арифметика/логика делается так — сперва в LEFT/RIGHT загружаются через вышеприведённые инструкции два аргумента и потом идёт опкод выполняющий нечто вроде LEFT *= RIGHT, и далее через STORE результат сохраняется обратно в стек. Единственная инструкция у которой есть вариант работающий сразу с непосредственным данным (0-16) или данным в стеке по короткой адресации — это ADD. Как опять таки понятно — потому что часто нужно и существенно сэкономит размер.
Так, например, вещи типа if ( a >= b ) {… } делаются так: a и b грузятся в регистры, выполняется operator>= который поместит в LEFT 0 если условие ложно или 1 если условие истинно (т.е. то как булевы реально в спецификации Си должны приводится к int) и единственные инструкции условных переходов в самой виртуальной машине Koei выполняются если LEFT==0 и если LEFT!=0.
В общем плотность кода в такой среде конечно же вырастает и просто в разы.
Однако и скорость выполнения сильно падает — по моим оценкам где то на порядок.
На слабенькой 8-битной денди это было бы фатально, но тут видимо помогает то, что основная масса игр Koei в ту эпоху была всяческими стратегическими симуляторами, например менеджеры управления аэропортами, древними японскими империями и т.п. Т.е. игры медленные, вдумчивые, и не требующие от видеочипа невероятных эквилибристик на пределе возможного.
Видимо так и выкручивались.
Так что похоже такая плодовитость конторы была неслучайной и подпитывалась внедрением передовых технологий и виртуальных кросс-платформенных машин прямо в 8 бит! :)
1 комментарий
Таким образом переход к виртуальной машине дает возможность переноса на множество других платформ. А никогда не возникало ощущения, что аппаратные возможности платформы (ядра процессора) могли бы способствовать эффективному исполнению инструкций ВМ? Например у DEC в его последнем CISC-е VAX новые инструкции могли вносится как микрокод и нативно расширяли систему команд. В случае VM это конечно в большей степени касается вызова шитого кода.
Не могу точно сказать насчет первенства в JIT компиляции, DEC тоже делала шаги в эту сторону, кроме всего прочего снабжая ядро виртуальной машины профилировщиком, принимающим решение на определенной итерации начать «инлайнить код», то есть приложение становилось шустрее и шустрее, в зависимости от времени его работы.
У МК-85, приходилось читать Отрохова, разработчик Бейсика пошел на применение шитого кода для плавающей арифметики. Формально это тоже некая часть VM. Я хочу сказать что в определенный момент, когда сложность написания процедур, даже в такой удобной и интуитивно понятной
системе команд как PDP-11, начинает достигать пределов возможностей человеческого мозга. В таком случае уйти в форт-машину или еще какую либо VM, в конечном счете связано даже не с борьбой за плотность или переносимость кода, а за возможность продолжать вести разработку.