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

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

Необходимые условия

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

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

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

  • Место для хранения кода VM на диске. Конечно, вы всегда можете отказаться от всех оптимизаций и просто сжать код, но это отрицательно влияет на (2).
  • Скорость декодирования. Лучший способ сохранить код бесполезен, если требуется слишком много времени, чтобы преобразовать его во что-то, что может быть выполнено непосредственно.
  • Объем памяти в памяти. Этот код должен быть непосредственно исполняемым с или без дальнейшего декодирования, но если есть дополнительное декодирование, это кодирование выполняется во время выполнения и каждый раз, когда выполняется команда (декодирование выполняется только один раз при загрузке кодовых значений в элемент 2).
  • Скорость выполнения кода (принимая во внимание общие методы интерпретатора).
  • Сложность VM и сложность написания интерпретатора для нее.
  • Объем ресурсов, необходимых VM для себя. (Это не хороший дизайн, если код, который запускает VM, имеет размер 2 КБ и выполняется быстрее, чем под глазами, однако для этого требуется 150 МБ, а время его запуска намного превышает время выполнения кода он выполняется)

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

Mulitple Opcodes для той же операции

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

ADD R1, R2, R3

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

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

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

ADD2 R1, R2
INC R1

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

Объединяя две Opcodes в один один

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

LOAD value, R2
ADD_RRR R1, R2, R3

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

ADD_RMR R1, value, R3

Типы данных и Opcodes

Предположим, что у вас есть 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 бит opcodes будут работать. Да, но очень наивный интерпретатор может выглядеть совсем по-другому. Например. если он имеет одну функцию для каждого кода операции и отправляет с помощью оператора switch (не лучший способ сделать это, служебные вызовы функции, оператор 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: // ...
    }
}

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

Метакоды

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

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

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

Как найти хорошую сделку???

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

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

Я много читал о всех видах виртуальных машин в Интернете, но ни один источник не делал хорошего и честного компромисса в любом случае. Проектирование виртуальной машины - это как проектирование процессора, есть процессоры с небольшим количеством операций, они быстры, но вам также нужно много. И есть процессоры со многими опкодами, некоторые из них очень медленные, но вам потребуется гораздо меньше, чтобы выразить один и тот же код. Похоже, что "больше опкодов лучше". ЦП полностью победили на потребительском рынке, а "меньше опкодов лучше" могут выживать только в некоторых частях серверного рынка или в суперкомпьютерном бизнесе. Как насчет виртуальных машин?

Ответы

Ответ 1

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

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

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

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

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

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

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

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

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

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

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

Меньше опкодов, атомных, в природе.

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

Например, многие из Higher PL имеют более простые инструкции "if" и "goto", но они также имеют составленные инструкции "while", "for", "do-while" или "repeat-till", основанные на по предыдущим инструкциям.