VM Design: больше опкодов или меньше опкодов? Что лучше?

Question

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

Предпосылки

Поскольку на этот вопрос, вероятно, вообще невозможно ответить, если не установлены хотя бы некоторые предварительные условия, вот предварительные условия:

• Код виртуальной машины должен интерпретироваться. Не обязательно, чтобы был JIT-компилятор, но дизайн должен быть ориентирован на интерпретатор.
• ВМ должна быть основана на регистре, а не на стеке.
• Ответ не может предполагать, что существует фиксированный набор регистров или что их существует неограниченное количество, либо один из них может иметь место.

Далее нам нужно лучшее определение «лучше». Есть несколько свойств, которые необходимо учитывать:

1. Место для хранения кода виртуальной машины на диске. Конечно, вы всегда можете отказаться от всех оптимизаций и просто сжать код, но это отрицательно сказывается на (2).
2. Скорость декодирования. Лучший способ сохранить код бесполезен, если его преобразование в нечто, что может быть непосредственно выполнено, занимает слишком много времени.
3. Место для хранения в памяти. Этот код должен быть непосредственно исполняемым либо с дополнительным декодированием, либо без него, но если требуется дальнейшее декодирование, это кодирование выполняется во время выполнения и каждый раз, когда выполняется инструкция (декодирование выполняется только один раз при загрузке кода, подсчитанного для элемента 2).
4. Скорость выполнения кода (с учетом распространенных методов интерпретатора).
5. Сложность виртуальной машины и насколько сложно написать для нее интерпретатор.
6. Количество ресурсов, необходимых виртуальной машине для себя. (Это не очень хороший дизайн, если код, который запускает виртуальная машина, имеет размер 2 КБ и выполняется быстрее, чем мгновение ока, однако для этого требуется 150 МБ, а время его запуска намного превышает время выполнения кода это выполняется)

Теперь примеры того, что я на самом деле имею в виду под более или менее кодами операций. Может показаться, что количество кодов операций действительно установлено, так как вам нужен один код операции на операцию. Однако это не так просто.

Несколько опкодов для одной и той же операции

У вас может быть такая операция, как

ADD R1, R2, R3

добавление значений R1 и R2 и запись результата в R3. Теперь рассмотрим следующие особые случаи:

ADD R1, R2, R2
ADD R1, 1, R1

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

ADD2 R1, R2
INC R1

То же, что и раньше. Где преимущество? ADD2 нужно только два аргумента, вместо 3, INC даже нужен только один. Так что это может быть закодировано более компактно на диске и / или в памяти. Поскольку также легко преобразовать любую форму в другую, этап декодирования может преобразовать оба способа выражения этих утверждений. Я не уверен, насколько сильно любая форма повлияет на скорость выполнения.

Объединение двух опкодов в один

Теперь давайте предположим, что у вас есть ADD_RRR (R для регистра) и LOAD для загрузки данных в регистр.

LOAD value, R2
ADD_RRR R1, R2, R3

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

ADD_RMR R1, value, R3

Типы данных и коды операций

Предположим, что у вас есть 16-битное целое и 32-битное целое число как собственные типы. Регистры 32-битные, поэтому подходит любой тип данных. Теперь, когда вы добавляете два регистра, вы можете сделать тип данных параметром:

ADD int16, R1, R2, R3
ADD int32, R1, R2, R3

То же самое верно для целых чисел со знаком и без знака, например. Таким образом, ADD может быть коротким кодом операции, одним байтом, а затем у вас есть другой байт (или, может быть, всего 4 бита), сообщающий ВМ, как интерпретировать регистры (они содержат 16-битные или 32-битные значения). Или вы можете отказаться от кодировки типа и вместо этого иметь два кода операции:

ADD16 R1, R2, R3
ADD32 R1, R2, R3

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

case ADD16: add16(p1, p2, p3); break; // pX pointer to register
case ADD32: add32(p1, p2, p3); break;

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

case ADD: add(type, p1, p2, p3); break;

// ...
// and the function

void add (enum Type type, Register p1, Register p2, Register p3)
{
    switch (type) {
       case INT16: //...
       case INT32: // ...
    }
}

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

мета-коды

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

ADD R1, R2, R3
WIDE
ADD R1, R2, R3

например. во втором случае регистры 16-битные (так что вы можете добавить их больше), в первом - только 8. В качестве альтернативы вы не можете иметь такой мета-код операции и иметь ADD и код операции ADD_WIDE. Мета-коды, такие как WIDE, избегают использования SUB_WIDE, MUL_WIDE и т. Д., Так как вы всегда можете добавить любой другой обычный код операции с помощью WIDE (всегда только один код операции). Недостаток в том, что один только код операции становится бессмысленным, вы всегда должны проверять код операции перед ним, если это был мета-код операции или нет. Кроме того, виртуальная машина должна хранить дополнительное состояние для каждого потока (например, находимся ли мы в расширенном режиме или нет) и снова удалять это состояние после следующей инструкции. Даже процессоры имеют такие коды операций (например, код операции блокировки x86).

Как найти хороший компромисс ???

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

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

Я много читал о всевозможных виртуальных машинах в Интернете, но ни один из источников на самом деле не делал хорошего и справедливого компромисса в любом случае. Проектирование ВМ похоже на проектирование ЦП, есть ЦП с небольшими кодами операций, они быстрые, но вам также нужно много таких. И есть процессоры с множеством кодов операций, некоторые из них очень медленные, но вам понадобится гораздо меньше их, чтобы выразить один и тот же кусок кода. Похоже, что «чем больше опкодов, тем лучше» процессоры полностью завоевали потребительский рынок, а «меньше опкодов лучше» могут выжить только в некоторых частях рынка серверов или в суперкомпьютерном бизнесе. А виртуальные машины?

Answer 1

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

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

Конечно, я понимаю, что вы, вероятно, представляете абстрактную, очень универсальную виртуальную машину, которую можно использовать как внутреннюю / внутреннюю реализацию для других языков программирования?

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

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

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

Это поможет вам сформулировать требования и упростить процесс разработки инструкций на основе разумных допущений.

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

Если, с другой стороны, вы будете использовать сервер в качестве бэкэнда для ОО-языков, вы захотите изучить оптимизацию соответствующих инструкций низкого уровня (т. Е. Хэшей / словарей).

В целом, я бы рекомендовал вначале сохранять набор инструкций как можно более простым и интуитивно понятным, и добавлять специальные инструкции только тогда, когда вы доказали, что их наличие действительно полезно (т. Е. Дамп профиля и кода операции) и делает вызвать увеличение производительности. Таким образом, это будет во многом определяться самыми первыми «клиентами», которые будут иметь вашу ВМ.

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

Answer 2

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

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

Answer 3

Я предпочитаю минималистичные наборы инструкций, потому что они могут быть объединены в один код операции. Например, код операции, состоящий из двух 4-битных полей команд, может быть отправлен с таблицей переходов из 256 записей. Так как накладные расходы на отправку являются основным узким местом в производительности интерпретации, увеличенной в ~ два раза, потому что нужно отправлять только каждую вторую инструкцию. Один из способов реализовать минималистичный, но эффективный набор инструкций - это дизайн аккумулятора / магазина.