Интерпретатор VM — взвешивание преимуществ производительности и недостатков большего набора команд / цикла диспетчеризации
Я разрабатываю простую виртуальную машину, и я нахожусь в середине перекрестка.
Моя первоначальная цель состояла в том, чтобы использовать длинную байтовую инструкцию, и, следовательно, маленький цикл и быструю вычисленную отправку goto.
Однако оказывается, что реальность не может быть дальше от нее — 256 далеко не достаточно, чтобы покрыть 8-, 16-, 32- и 64-разрядные целые числа со знаком, без знака, числа с плавающей запятой и двойные числа, операции с указателями, различные комбинации адресации. Один из вариантов заключался в том, чтобы не реализовывать байты и шорты, но цель состоит в том, чтобы создать виртуальную машину, которая поддерживает полное подмножество C, а также векторные операции, поскольку в любом случае они практически везде, хотя и в разных реализациях.
Поэтому я переключился на 16-битную инструкцию, поэтому теперь я также могу добавить переносимые встроенные SIMD-функции и более скомпилированные общие подпрограммы, которые действительно экономят на производительности, поскольку их не интерпретируют. Существует также кеширование глобальных адресов, первоначально скомпилированных как базовые смещения указателя, при первом компиляции адреса он просто перезаписывает смещение и инструкцию, так что в следующий раз это будет прямой переход за счет дополнительной инструкции в наборе для каждое использование глобального инструкцией.
Поскольку я не нахожусь на этапе профилирования, передо мной стоит дилемма, стоят ли дополнительные инструкции большей гибкости, будет ли наличие большего количества инструкций и, следовательно, отсутствие копирования копий туда и обратно инструкций компенсировать увеличение размера цикла отправки? Помните, что инструкции — это всего лишь несколько инструкций по сборке, например:
.globl __Z20assign_i8u_reg8_imm8v
.def __Z20assign_i8u_reg8_imm8v; .scl 2; .type 32; .endef
__Z20assign_i8u_reg8_imm8v:
LFB13:
.cfi_startproc
movl _ip, %eax
movb 3(%eax), %cl
movzbl 2(%eax), %eax
movl _sp, %edx
movb %cl, (%edx,%eax)
addl $4, _ip
ret
.cfi_endproc
LFE13:
.p2align 2,,3
.globl __Z18assign_i8u_reg_regv
.def __Z18assign_i8u_reg_regv; .scl 2; .type 32; .endef
__Z18assign_i8u_reg_regv:
LFB14:
.cfi_startproc
movl _ip, %edx
movl _sp, %eax
movzbl 3(%edx), %ecx
movb (%ecx,%eax), %cl
movzbl 2(%edx), %edx
movb %cl, (%eax,%edx)
addl $4, _ip
ret
.cfi_endproc
LFE14:
.p2align 2,,3
.globl __Z24assign_i8u_reg_globCachev
.def __Z24assign_i8u_reg_globCachev; .scl 2; .type 32; .endef
__Z24assign_i8u_reg_globCachev:
LFB15:
.cfi_startproc
movl _ip, %eax
movl _sp, %edx
movl 4(%eax), %ecx
addl %edx, %ecx
movl %ecx, 4(%eax)
movb (%ecx), %cl
movzwl 2(%eax), %eax
movb %cl, (%eax,%edx)
addl $8, _ip
ret
.cfi_endproc
LFE15:
.p2align 2,,3
.globl __Z19assign_i8u_reg_globv
.def __Z19assign_i8u_reg_globv; .scl 2; .type 32; .endef
__Z19assign_i8u_reg_globv:
LFB16:
.cfi_startproc
movl _ip, %eax
movl 4(%eax), %edx
movb (%edx), %cl
movzwl 2(%eax), %eax
movl _sp, %edx
movb %cl, (%edx,%eax)
addl $8, _ip
ret
.cfi_endproc
Этот пример содержит инструкции для:
- назначить неподписанный байт из непосредственного значения для регистрации
- назначить неподписанный байт из регистра для регистрации
- назначить неподписанный байт из глобального смещения для регистрации и, кэширования и изменения в прямую инструкцию
- назначить регистру неподписанный байт из глобального смещения (текущая кешированная предыдущая версия)
- … и так далее…
Естественно, когда я создам для него компилятор, я смогу протестировать поток команд в производственном коде и оптимизировать расположение инструкций в памяти, чтобы собрать вместе часто используемые и получить больше попаданий в кэш.
Мне просто трудно понять, является ли такая стратегия хорошей идеей, раздувание компенсирует гибкость, но как насчет производительности? Будут ли более скомпилированные подпрограммы компенсировать больший цикл диспетчеризации? Стоит ли кешировать глобальные адреса?
Я также хотел бы, чтобы кто-то, достойный в сборке, высказал мнение о качестве кода, сгенерированного GCC — есть ли очевидные недостатки и возможности для оптимизации? Чтобы прояснить ситуацию, есть sp указатель, который указывает на стек, который реализует регистры (другого стека нет), ip логически указатель текущей инструкции, и gp является глобальным указателем (на который нет ссылки, доступ осуществляется как смещение).
РЕДАКТИРОВАТЬ: Кроме того, это основной формат, в котором я реализую инструкции в:
INSTRUCTION assign_i8u_reg16_glob() { // assign unsigned byte to reg from global offset
FETCH(globallAddressCache);
REG(quint8, i.d16_1) = GLOB(quint8);
INC(globallAddressCache);
}
FETCH возвращает ссылку на структуру, которую использует инструкция, на основе кода операции
REG возвращает ссылку на значение регистра T из смещения
GLOB возвращает ссылку на глобальное значение из кэшированного глобального смещения (фактически абсолютного адреса)
INC просто увеличивает указатель инструкции на размер инструкции.
Некоторые люди, вероятно, предложат против использования макросов, но с шаблонами это гораздо менее читабельно. Таким образом, код довольно очевиден.
РЕДАКТИРОВАТЬ: Я хотел бы добавить несколько вопросов к вопросу:
-
Я мог бы пойти на решение «только операции с регистрами», которое может перемещать данные только между регистрами и «памятью» — будь то глобальный или куча. В этом случае каждый «глобальный» и доступ к куче должен будет скопировать значение, изменить или использовать его и переместить обратно для обновления. Таким образом, у меня есть более короткий цикл отправки, но несколько дополнительных инструкций для каждой инструкции, которая обращается к незарегистрированным данным. Таким образом, дилемма в несколько раз больше нативного кода с более длинными прямыми переходами или в несколько раз больше интерпретируемых инструкций с более коротким циклом отправки. Даст ли мне цикл короткой отправки достаточную производительность, чтобы компенсировать дополнительные и дорогостоящие операции с памятью? Может быть, дельта между более коротким и длинным циклом отправки недостаточна, чтобы реально изменить ситуацию? С точки зрения попаданий в кеш, с точки зрения стоимости сборки скачки.
-
Я мог бы пойти на дополнительное декодирование и только инструкции шириной 8 бит, однако это может добавить еще один переход — переход туда, где обрабатывается эта инструкция, а затем тратить время либо на переход к случаю, когда обрабатывается конкретная схема адресации, либо на операции декодирования и более сложные операции. метод исполнения. И в первом случае цикл диспетчеризации все еще увеличивается, добавляя еще один скачок. Второй вариант — операции с регистром могут использоваться для декодирования адресации, но для решения чего-либо потребуется более сложная инструкция с более неизвестным временем компиляции. Я не совсем уверен, как это будет складываться с более коротким циклом диспетчеризации, еще раз, я не уверен, как мой «более короткий и длинный цикл диспетчеризации» связан с тем, что считается коротким или длинным с точки зрения инструкций по сборке, требуемой памяти и скорости их исполнения.
-
Я мог бы пойти на решение «много инструкций» — цикл отправки в несколько раз больше, но он все еще использует предварительно вычисленный прямой переход. Сложная адресация специфична и оптимизирована для каждой инструкции и скомпилирована для собственной, поэтому дополнительные операции с памятью, которые потребуются при подходе «только регистр», будут компилироваться и в основном выполняться в регистрах, что хорошо для производительности. Как правило, идея состоит в том, чтобы добавить больше к набору инструкций, но также добавить к объему работы, который может быть скомпилирован заранее и выполнен в одной «инструкции». Одиночный набор команд также означает более длительный цикл диспетчеризации, более длинные переходы (хотя это можно оптимизировать для минимизации), меньшее количество обращений к кэшу, но вопрос в том, КАК НАМНОГО? Учитывая, что каждая «инструкция» — это всего лишь несколько инструкций по сборке, считается ли фрагмент сборки из 7-8 тыс. Инструкций нормальным или слишком большим? Учитывая, что средний размер инструкций варьируется в пределах 2-3b, это не должно превышать 20 КБ памяти, что достаточно для полного размещения в большинстве кэшей L1. Но это не конкретная математика, а просто то, что я нашел в поиске, так что, может быть, мои «расчеты» выключены? Или, может быть, это не так? Я не настолько опытен в механизмах кеширования.
Для меня, поскольку я в настоящее время взвешиваю аргументы, подход «много инструкций», по-видимому, имеет наибольшие шансы на лучшую производительность, при условии, конечно, моя теория о приспособлении «расширенного цикла диспетчеризации» в кеше L1 верна. Так вот, где ваши знания и опыт вступают в игру. Теперь, когда контекст сужен и представлены несколько идей поддержки, возможно, будет проще дать более конкретный ответ, преобладают ли преимущества большего набора команд над увеличением размера собственного кода за счет уменьшения количества более медленного интерпретируемого кода. ,
Мои данные о размере обучения основаны на тех статистика.
Решение
Возможно, вы захотите рассмотреть разделение виртуальной машины ISA и ее реализацию.
Например, в виртуальной машине, которую я написал, у меня была инструкция «прямое значение загрузки». Следующее значение в потоке команд не было декодировано как инструкция, но загружено как значение в регистр. Вы можете рассмотреть эту одну макроинструкцию или два отдельных значения.
Другой инструкцией, которую я реализовал, было «загрузить значение константы», которое загружало константу из памяти (используя базовый адрес для таблицы констант и смещения). Таким образом, общий шаблон в потоке команд был load value direct (index); load constant value, Ваша реализация виртуальной машины может распознать этот шаблон и обработать пару с одной оптимизированной реализацией.
Очевидно, что если у вас достаточно битов, вы можете использовать некоторые из них для идентификации регистра. С 8 битами может быть необходимо иметь один регистр для всех операций. Но опять же, вы можете добавить еще одну инструкцию with register X который изменяет следующую операцию. В вашем коде C ++ эта инструкция просто установит currentRegister указатель, который используют другие инструкции.
Другие решения
Будут ли более скомпилированные подпрограммы компенсировать больший цикл диспетчеризации?
Я так понимаю, вам не нравились однобайтовые инструкции со вторым байтом дополнительного кода операции для определенных инструкций? Я думаю, что декодирование для 16-битных опкодов может быть менее эффективным, чем 8-битные + дополнительные байты, если допустить, что дополнительные байты не слишком распространены или слишком сложны для декодирования сами по себе.
Если бы это был я, я бы работал над тем, чтобы компилятор (не обязательно полноценный компилятор со «всем», но базовая модель) работал с довольно ограниченным набором «инструкций». Сохраняйте часть генерации кода достаточно гибкой, чтобы потом было легко изменить фактическую кодировку. После того, как у вас это получится, вы можете экспериментировать с различными кодировками и посмотреть, каков результат в производительности и других аспектах.
На многие ваши второстепенные вопросы очень сложно ответить тем, кто не сделал оба варианта. В этом смысле я никогда не писал ВМ, но работал над несколькими дизассемблерами, симуляторами наборов команд и тому подобным. Я также реализовал несколько языков разных типов, с точки зрения интерпретируемых языков.
Возможно, вы также захотите рассмотреть подход JIT, где вместо загрузки байт-кода вы интерпретируете байт-код и создаете прямой машинный код для рассматриваемой архитектуры.
Код GCC не выглядит ужасно, но есть несколько мест, где код зависит от значения непосредственно предшествующей инструкции, что не очень хорошо для современных процессоров. К сожалению, я не вижу никакого решения этой проблемы — это проблема «слишком короткого кода, чтобы перемешать» — добавление дополнительных инструкций, очевидно, не сработает.
Я вижу одну маленькую проблему: загрузка 32-битной константы потребует ее выравнивания 32-бит для лучшей производительности. Я понятия не имею, как (или если) Java VM справляется с этим.
Я думаю, что вы задаете неправильный вопрос, и не потому, что это плохой вопрос, а наоборот, это интересная тема, и я подозреваю, что многие люди заинтересованы в результатах так же, как и я.
Тем не менее, до сих пор никто не делится подобным опытом, поэтому я думаю, что вам, возможно, придется сделать кое-что новаторское. Вместо того, чтобы интересоваться, какой подход использовать и тратить время на реализацию стандартного кода, сфокусируйтесь на создании «отражающего» компонента, который описывает структуру и свойства языка, создайте красивую полиморфную структуру с виртуальными методами, не беспокоясь о производительности, создайте модульные компоненты, которые вы можете собирать во время выполнения, есть даже возможность использовать декларативный язык после того, как вы установили иерархию объектов. Поскольку вы, похоже, используете Qt, у вас есть половина работы. Затем вы можете использовать древовидную структуру для анализа и генерации различных кодов — код C для компиляции или байт-код для конкретной реализации виртуальной машины, из которых вы можете создать несколько, вы даже можете использовать это для программного генерирования кода C для вашей виртуальной машины. вместо того, чтобы печатать все вручную.
Я думаю, что этот набор советов будет более полезен в случае, если вы прибегаете к пионерству по этому вопросу без конкретного ответа заранее, он позволит вам легко протестировать все сценарии и сосредоточиться на реальных результатах, а не на личных предположениях и те из других. Тогда, может быть, вы можете поделиться результатами и ответить на свой вопрос с данными о производительности.
Длина инструкции в байтах обрабатывается одинаково уже довольно давно. Очевидно, что ограничение до 256 инструкций не очень хорошая вещь, когда вы хотите выполнить так много типов операций.
Вот почему есть префиксное значение. Вернувшись в архитектуру gameboy, не было достаточно места для включения необходимых 256-битных инструкций управления, поэтому в качестве префиксной инструкции использовался один код операции. Это сохранило исходные 256 кодов операций, а также еще 256, если начинать с этого байта префикса.
Например:
Одна операция может выглядеть так: D6 FF знак равно SUB A, 0xFF
Но инструкция с префиксом будет представлена как: CB D6 FF знак равно SET 2, (HL)
Если процессор прочитал CB он сразу начал бы искать в другом наборе команд 256 кодов операций.
То же самое касается архитектуры x86 сегодня. Где любые инструкции с префиксом 0F будет частью другого набора инструкций, по сути.
С тем типом исполнения, который вы используете для своего эмулятора, это лучший способ расширить ваш набор команд. 16-битные коды операции заняли бы намного больше места, чем необходимо, и префикс не обеспечивает такой долгий поиск.
Вам нужно решить, какой баланс вы хотите достичь между эффективностью размера файла кода, эффективностью кэширования и эффективностью скорости необработанного выполнения. В зависимости от шаблонов кодирования кода, который вы интерпретируете, может быть полезно, чтобы каждая инструкция, независимо от ее длины в файле кода, была переведена в структуру, содержащую указатель и целое число. Первый указатель будет указывать на функцию, которая принимает указатель на структуру информация-инструкция, а также на контекст выполнения. Таким образом, основной цикл выполнения будет выглядеть примерно так:
do
{
pc = pc->func(pc, &context);
} while(pc);
функция, связанная с «добавлением короткой немедленной инструкции», будет выглядеть примерно так:
INSTRUCTION *add_instruction(INSTRUCTION *pc, EXECUTION_CONTEXT *context)
{
context->op_stack[0] += pc->operand;
return pc+1;
}
в то время как «добавьте долго немедленно» будет:
INSTRUCTION * add_instruction (INSTRUCTION * pc, EXECUTION_CONTEXT * context)
{
context-> op_stack [0] + = (uint32_t) pc-> operand + ((int64_t) (pc [1] .operand) << 32);
вернуть pc + 2;
}
и функция, связанная с инструкцией add local:
INSTRUCTION *add_instruction(INSTRUCTION *pc, EXECUTION_CONTEXT *context)
{
CONTEXT_ITEM *op_stack = context->op_stack;
op_stack[0].asInt64 += op_stack[pc->operand].asInt64;
return pc+1;
}
Ваши «исполняемые файлы» будут состоять из сжатого формата байт-кода, но затем они будут переведены в таблицу инструкций, устраняя уровень косвенности при декодировании инструкций во время выполнения.