PC-01 Lviv

It is currently 19 Mar 2024, 10:10

Forum Games WEB Tape Loader Twitter RSS

All times are UTC+03:00




Post new topic  Reply to topic  [ 10 posts ] 
Author Message
PostPosted: 14 Jun 2012, 09:12 
Offline

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

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

Вот например, статистика игры "Пьяный лифтер":
Code:
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, происходит ли компиляция-оптимизация и является ли там эмуляция процессора узким горлышком.


Last edited by Tim0xA on 14 Jun 2012, 09:38, edited 1 time in total.

Top
   
PostPosted: 14 Jun 2012, 09:18 
Offline

Joined: 29 Mar 2012, 21:35
Posts: 115
Quote:
Сколько видел исходников эмуляторов - практически везде дешифровка команд производится последовательно
Нигде такого не видел. А там, где видел, обычно стоит switch(opcode), который обычно компилируется в jmp table (т.к. используются последовательные значения в case).
Некоторые сами делают таблицу переходов, указывая в ней адреса процедур, но в этом случае будет лишний call/ret.


Top
   
PostPosted: 14 Jun 2012, 09:21 
Offline

Joined: 04 Jun 2012, 22:08
Posts: 44
Location: Украина
Quote:
А там, где видел, обычно стоит switch(opcode), который обычно компилируется в jmp table (т.к. используются последовательные значения в case).
Ну я об этом тоже сказал:
Quote:
компилятор вполне может сам преобразовать эту линейность в таблицу указателей, так что в этом случае как ни расставляй, на быстродействии это никак не скажется


Top
   
PostPosted: 14 Jun 2012, 10:01 
Offline
User avatar

Joined: 11 Aug 2008, 17:05
Posts: 1405
Location: Украина
Quote:
Может это ускорит онлайн-эмулятор на JavaScript, я просто не в курсе, как браузер выполняет JS, происходит ли компиляция-оптимизация и является ли там эмуляция процессора узким горлышком.
Оригинальное исследование! Действительно странно, что никто на эту очевидную вещь не обращал внимания. :shock:
Что касается js, то пока в роли "горлышка" выступает отрисовка экрана. Но и эта проблема относительна: все зависит от железа и загруженности среды, где запущен браузер. Хотя подумать над тем, чтобы замерить быстродействие js-эмуля в различных браузерах выглядит здравой. Надо над этим подумать. :)

_________________
Carthago delenda est, Carthaginem delendam esse


Top
   
PostPosted: 14 Jun 2012, 16:49 
Offline

Joined: 07 Dec 2010, 16:54
Posts: 227
Quote:
Quote:
Сколько видел исходников эмуляторов - практически везде дешифровка команд производится последовательно
Нигде такого не видел. А там, где видел, обычно стоит switch(opcode), который обычно компилируется в jmp table (т.к. используются последовательные значения в case).
Некоторые сами делают таблицу переходов, указывая в ней адреса процедур, но в этом случае будет лишний call/ret.
это для 8 битов, 16/32-битные процессоры так не получится декодировать. так что для них вопрос уместный и корректный.

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

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

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


Top
   
PostPosted: 14 Jun 2012, 23:13 
Offline

Joined: 20 Apr 2012, 16:00
Posts: 372
Location: Конотоп
Quote:
компилятор вполне может сам преобразовать эту линейность в таблицу указателей, так что в этом случае как ни расставляй, на быстродействии это никак не скажется
Я извеняюсь если я чего неправильно понял...
То есть ты хочешь сказать что если я напишу на том же Дельфи
вот такое:
case COMMAND of

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

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


Top
   
PostPosted: 14 Jun 2012, 23:43 
Offline

Joined: 04 Jun 2012, 22:08
Posts: 44
Location: Украина
Quote:
то как не переставляй команды на быстродействие оно не повлияет?
http://www.delphimaster.ru/articles/optimization.html
Quote:
Оптимизация case of

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

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


Top
   
PostPosted: 15 Jun 2012, 11:30 
Offline

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


Top
   
PostPosted: 26 Jun 2012, 23:54 
Offline
User avatar

Joined: 11 Aug 2008, 17:05
Posts: 1405
Location: Украина
Вчера случайно натолкнулся на Хабре на статью "Создаем эмулятор приставки" [1, 2], где в комментариях знающий, похоже, человек apangin написал:
Quote:
О, интерпретаторы! Моя любимая тема и безграничное поле для деятельности! На ней можно всю информатику выучить :)
Для начала скажу, что цикл с большим switch/case по опкодам, как правило, неэффективный способ для написания интерпретатора. Лучше использовать таблицы перехода. Кроме того, и сам цикл не нужен (лишний безусловный переход) — реализация каждого опкода может заканчиваться прыжком на следующий опкод (например, при помощи computed goto в GNU C). Разумеется, для данного конкретного эмулятора это необязательно, но в образовательных целях можно и с него начать. Если опкодов слишком много, иногда имеет смысл разбить один case на два меньших: с частыми и редкими опкодами, как сделано в классической JVM. Указатель (PC) лучше кэшировать в локальной переменной. Память устройства можно эффективно эмулировать средствами виртуальной памяти ОС (VirtualAlloc, mmap). Ну, а потом потихоньку переходить к JIT, сначала однопродному, потом с промежуточным представлением и т.д.
В общем, замечательная тема. Удачи!

_________________
Carthago delenda est, Carthaginem delendam esse


Top
   
PostPosted: 27 Jun 2012, 17:04 
Offline

Joined: 07 Dec 2010, 16:54
Posts: 227
Quote:
иногда имеет смысл разбить один case на два меньших: с частыми и редкими опкодами, как сделано в классической JVM.
имхо, здесь про "линии кэширования" речь идёт, меньше адресов переходов - больше шансов, что они все попадут в TLB.
а вот с "вычислимым goto" я не понял, фактически это будет switch() в конце каждой эмулируемой команды..... т.е. одну команду мы экономим, но не факт, что гарантированная "выборка из памяти" (а иначе это место не реализовать) дешевле по тактам получится, чем "связка" if/then в виде дерева.


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 10 posts ] 

Forum Games WEB Tape Loader Twitter RSS

All times are UTC+03:00


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
cron
Powered by phpBB® Forum Software © phpBB Limited