ПК-01 ЛЬВОВ

форум о ПК-01,02 "Львов"
Текущее время: 16 дек 2018, 22:22

Forum Games WEB Tape Loader Twitter RSS

Часовой пояс: UTC + 2 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 10 ] 
Автор Сообщение
СообщениеДобавлено: 14 июн 2012, 09:12 
Не в сети

Зарегистрирован: 04 июн 2012, 22:08
Сообщений: 44
Откуда: Украина
Сколько видел исходников эмуляторов - практически везде дешифровка команд производится последовательно, например, начиная с кода 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[/code]

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

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

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

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


Последний раз редактировалось Tim0xA 14 июн 2012, 09:38, всего редактировалось 1 раз.

Вернуться наверх
 Профиль  
 
СообщениеДобавлено: 14 июн 2012, 09:18 
Не в сети

Зарегистрирован: 29 мар 2012, 21:35
Сообщений: 115
[quote="Tim0xA"]Сколько видел исходников эмуляторов - практически везде дешифровка команд производится последовательно

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

Вернуться наверх
 Профиль  
 
СообщениеДобавлено: 14 июн 2012, 09:21 
Не в сети

Зарегистрирован: 04 июн 2012, 22:08
Сообщений: 44
Откуда: Украина
[quote="b2m"]А там, где видел, обычно стоит switch(opcode), который обычно компилируется в jmp table (т.к. используются последовательные значения в case).


Ну я об этом тоже сказал:
[quote="Tim0xA"]компилятор вполне может сам преобразовать эту линейность в таблицу указателей, так что в этом случае как ни расставляй, на быстродействии это никак не скажется

Вернуться наверх
 Профиль  
 
СообщениеДобавлено: 14 июн 2012, 10:01 
Не в сети
Аватар пользователя

Зарегистрирован: 11 авг 2008, 17:05
Сообщений: 1403
Откуда: Украина
[quote="Tim0xA"]Может это ускорит онлайн-эмулятор на JavaScript, я просто не в курсе, как браузер выполняет JS, происходит ли компиляция-оптимизация и является ли там эмуляция процессора узким горлышком.

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

_________________
Carthago delenda est, Carthaginem delendam esse


Вернуться наверх
 Профиль  
 
СообщениеДобавлено: 14 июн 2012, 16:49 
Не в сети

Зарегистрирован: 07 дек 2010, 16:54
Сообщений: 202
[quote="b2m"][quote="Tim0xA"]Сколько видел исходников эмуляторов - практически везде дешифровка команд производится последовательно

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

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

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

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

Вернуться наверх
 Профиль  
 
СообщениеДобавлено: 14 июн 2012, 23:13 
Не в сети

Зарегистрирован: 20 апр 2012, 16:00
Сообщений: 372
Откуда: Конотоп
[quote="Tim0xA"]компилятор вполне может сам преобразовать эту линейность в таблицу указателей, так что в этом случае как ни расставляй, на быстродействии это никак не скажется

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

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

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

Вернуться наверх
 Профиль  
 
СообщениеДобавлено: 14 июн 2012, 23:43 
Не в сети

Зарегистрирован: 04 июн 2012, 22:08
Сообщений: 44
Откуда: Украина
[quote="sadfsdfsdaf"]то как не переставляй команды на быстродействие оно не повлияет?

http://www.delphimaster.ru/articles/optimization.html
[quote]Оптимизация case of

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

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

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

Вернуться наверх
 Профиль  
 
СообщениеДобавлено: 15 июн 2012, 11:30 
Не в сети

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


Вернуться наверх
 Профиль  
 
СообщениеДобавлено: 26 июн 2012, 23:54 
Не в сети
Аватар пользователя

Зарегистрирован: 11 авг 2008, 17:05
Сообщений: 1403
Откуда: Украина
Вчера случайно натолкнулся на Хабре на статью "Создаем эмулятор приставки" [[url=http://habrahabr.ru/post/100907/]1[/url], [url=http://habrahabr.ru/post/146496/]2[/url]], где в комментариях знающий, похоже, человек apangin [url=http://habrahabr.ru/post/100907/#comment_3126084]написал[/url]:

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

_________________
Carthago delenda est, Carthaginem delendam esse


Вернуться наверх
 Профиль  
 
СообщениеДобавлено: 27 июн 2012, 17:04 
Не в сети

Зарегистрирован: 07 дек 2010, 16:54
Сообщений: 202
[quote="liberation"]иногда имеет смысл разбить один case на два меньших: с частыми и редкими опкодами, как сделано в классической JVM.

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

Вернуться наверх
 Профиль  
 
Показать сообщения за:  Сортировать по:  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Forum Games WEB Tape Loader Twitter RSS

Часовой пояс: UTC + 2 часа [ Летнее время ]


Кто сейчас на форуме

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Free counters!
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB