Оптимизация процесса эмуляции процессора ))

[Tim0xA]

Сколько видел исходников эмуляторов - практически везде дешифровка команд производится последовательно, например, начиная с кода 0x00 и до 0xFF. И вот подумалось мне, что такой подход нерационален и отрицательно сказывается на быстродействии эмуляции в системах, где скорость критична, а компилятор не оптимален. Как правило, все начинается с команды 'NOP' - это вообще нонсенс. Как часто используется NOP в качестве команды? Ну разве что для формирования задержек при работе с железом. А ведь можно упорядочить дешифрацию, используя статистику использования команд, чтобы не тратить время на анализ редко используемых команд.

Ради интереса я сделал выборки для 10 программ. Массив из 256 байт-счетчиков - индекс соответствует коду команды. Алгоритм прост: младший бит устанавливается, если команда выполняется хотя бы раз, в следующий раз к значению счетчика прибавляется 2. Как только счетчик переполняется, его значение делится на 2. Младший бит сохраняется.

Вот например, статистика игры "Пьяный лифтер":

Code: Select all

00: 00 03 00 00 00 2F 03 00 │ 00 03 00 00 00 9B 31 21
10: 00 03 91 93 00 00 00 03 │ 00 35 00 00 00 00 00 03
20: 00 07 03 B3 00 00 00 00 │ 00 00 03 03 00 00 00 00
30: 00 00 00 00 07 03 03 00 │ 00 00 00 00 00 00 03 03
40: 00 00 00 00 00 00 00 09 │ 00 00 00 00 00 00 00 00
50: 00 00 00 00 00 00 03 00 │ 00 00 00 00 00 00 03 00
60: 00 00 00 00 00 00 00 00 │ 00 00 00 00 00 00 00 00
70: 00 00 03 03 00 00 00 03 │ 00 00 00 00 00 03 A9 00
80: 00 00 00 00 00 00 00 00 │ 00 00 00 00 00 00 00 00
90: 00 00 00 00 00 00 00 00 │ 00 00 00 00 00 00 00 00
A0: 00 00 00 00 00 00 00 00 │ 00 00 00 00 00 00 00 00
B0: 00 00 00 00 00 00 00 00 │ 09 00 00 00 00 00 09 00
C0: 00 03 CB 03 00 03 03 00 │ 00 00 11 00 00 00 00 00
D0: 00 03 03 03 00 00 00 00 │ 00 00 03 03 00 00 00 00
E0: 00 03 00 5F 00 05 15 00 │ 00 00 00 61 00 00 00 00
F0: 00 00 03 00 00 00 00 00 │ 00 00 03 00 00 00 03 00

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

Очередь можно формировать динамически в зависимости от выполняемого кода.

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

Но в некоторых случаях и такой подход может пригодиться. Может это ускорит онлайн-эмулятор на JavaScript, я просто не в курсе, как браузер выполняет JS, происходит ли компиляция-оптимизация и является ли там эмуляция процессора узким горлышком.

[b2m]

Сколько видел исходников эмуляторов - практически везде дешифровка команд производится последовательно

Нигде такого не видел. А там, где видел, обычно стоит switch(opcode), который обычно компилируется в jmp table (т.к. используются последовательные значения в case).
Некоторые сами делают таблицу переходов, указывая в ней адреса процедур, но в этом случае будет лишний call/ret.

[Tim0xA]

А там, где видел, обычно стоит switch(opcode), который обычно компилируется в jmp table (т.к. используются последовательные значения в case).

Ну я об этом тоже сказал:

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

[liberation]

Может это ускорит онлайн-эмулятор на JavaScript, я просто не в курсе, как браузер выполняет JS, происходит ли компиляция-оптимизация и является ли там эмуляция процессора узким горлышком.

Оригинальное исследование! Действительно странно, что никто на эту очевидную вещь не обращал внимания.
Что касается js, то пока в роли "горлышка" выступает отрисовка экрана. Но и эта проблема относительна: все зависит от железа и загруженности среды, где запущен браузер. Хотя подумать над тем, чтобы замерить быстродействие js-эмуля в различных браузерах выглядит здравой. Надо над этим подумать.

[sadfsdfsdaf]

Сколько видел исходников эмуляторов - практически везде дешифровка команд производится последовательно

Нигде такого не видел. А там, где видел, обычно стоит switch(opcode), который обычно компилируется в jmp table (т.к. используются последовательные значения в case).
Некоторые сами делают таблицу переходов, указывая в ней адреса процедур, но в этом случае будет лишний call/ret.

это для 8 битов, 16/32-битные процессоры так не получится декодировать. так что для них вопрос уместный и корректный.

я, когда делал декодер (немного-недо-эмулятор) NEC V850, то использовал дерево:
все команды изначально представлялись в виде битовой матрицы, далее вычислялся срез, позволяющий выделить максимальное количество команд и минимальный "по ширине" (срез делался как SWITCH(AND, SHIFT), для 1-2 позиций использовался IF/ELSE), далее процедура повторялась для каждой оставшейся ветви... максимальная глубина получалась что-то около 6 переходов.

преимущество у систем команд при разборе в том, что они оптимизированы для обработки микропроцессором, а, значит, будут обладать вменяемыми форматами представления (обычно битовые поля).

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

[sas9568635]

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

Я извеняюсь если я чего неправильно понял...
То есть ты хочешь сказать что если я напишу на том же Дельфи
вот такое:
case COMMAND of

00: NOP;
...
C3: JMP;
...
FF: (еще чего-то там)
end;

то как не переставляй команды на быстродействие оно не повлияет?
А разве оно не будет перебирать все сравнения до последнего? и первая команды всегда будет выполняться быстрее чем последняя?...
Если это так то это очень хорошо!
А то я уже хотел впутывать вот такое:
var Command:array[0..$FF] of Procedure;
Массив процедурного типа, где присваивать каждому элементу массива выполняемую процедуру - Command[00]:= NOP;, а после вызывать ее: Command[00];
Или может лучше все таки так и сделать?

[Tim0xA]

то как не переставляй команды на быстродействие оно не повлияет?

http://www.delphimaster.ru/articles/optimization.html

Оптимизация case of

Анализ скомпилированного кода показывает, что Delphi проводит утрамбовку дерева. Т.е. значения case сортируются и выбор нужного элемента производится при помощи двоичного поиска.

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

В case of при возможности используйте элементы, расположенные в арифметической прогрессии. Тем не менее, даже при невыполнении данного условия мы получим качественный код после утрамбовки дерева.

Т.е. в данном случае можно расположить элементы case по возрастанию (как обычно делается) и довериться компилятору.

[sas9568635]

Вот статья о мифах виртуальной памяти http://www.gunsmoker.ru/2011/04/windows-spin-off.html, я думаю она в этой теме будет по делу, так как однажды прочитавши ее, я понял, что не стоит заморачиваться на мелочах (оптимизации) каких-то там единичных кодов (команд)...
Из собственных наблюдений я понял, что если быстродействия явно не хватает, то никакая, подобная практика (как в статье http://www.delphimaster.ru/articles/optimization.html) не поможет. Надо явно и глобально менять структуру программы и ее ход. Или возможно делать асм-вставки там где действительно это необходимо. А на заморачиваясь на мелочах – далеко не уедешь…
Подобное в статье про опитимизацию, полезно при иделизации части кода, либо для "выработки" у будущего программиста изначально подобного стиля написания.

[liberation]

Вчера случайно натолкнулся на Хабре на статью "Создаем эмулятор приставки" [1, 2], где в комментариях знающий, похоже, человек apangin написал:

О, интерпретаторы! Моя любимая тема и безграничное поле для деятельности! На ней можно всю информатику выучить
Для начала скажу, что цикл с большим switch/case по опкодам, как правило, неэффективный способ для написания интерпретатора. Лучше использовать таблицы перехода. Кроме того, и сам цикл не нужен (лишний безусловный переход) — реализация каждого опкода может заканчиваться прыжком на следующий опкод (например, при помощи computed goto в GNU C). Разумеется, для данного конкретного эмулятора это необязательно, но в образовательных целях можно и с него начать. Если опкодов слишком много, иногда имеет смысл разбить один case на два меньших: с частыми и редкими опкодами, как сделано в классической JVM. Указатель (PC) лучше кэшировать в локальной переменной. Память устройства можно эффективно эмулировать средствами виртуальной памяти ОС (VirtualAlloc, mmap). Ну, а потом потихоньку переходить к JIT, сначала однопродному, потом с промежуточным представлением и т.д.
В общем, замечательная тема. Удачи!

[sadfsdfsdaf]

иногда имеет смысл разбить один case на два меньших: с частыми и редкими опкодами, как сделано в классической JVM.

имхо, здесь про "линии кэширования" речь идёт, меньше адресов переходов - больше шансов, что они все попадут в TLB.
а вот с "вычислимым goto" я не понял, фактически это будет switch() в конце каждой эмулируемой команды..... т.е. одну команду мы экономим, но не факт, что гарантированная "выборка из памяти" (а иначе это место не реализовать) дешевле по тактам получится, чем "связка" if/then в виде дерева.