Содержание
Команда ВМ. Структура.
Отредактировано Евгений (2023-03-20 21:35:53)
Генератор виртуальной машины. Боковая ветвь "Сказочной колесницы"
Страница: 1
Сообщений 1 страница 26 из 26
Поделиться22023-03-20 21:30:47
Почему так, а не иначе?
Мы начали разработку нашей виртуальной машины не совсем обычным способом. Уже появились первые наброски кода, а до сих пор нет ясной спецификации или технического задания, какой именно должна стать виртуальная машина. Сейчас я говорю не о мультипроекте "Сказочная колесница", в который могут войти несколько виртуальных машин, а об отдельной его части. Почему так? Все дело в том, что мы начали работу в условиях сильно ограниченных ресурсов. Лично у меня нет полного понимания в настоящий момент, какой должна быть виртуальная машина, чтобы на ее базе можно было строить интерпретаторы, компиляторы и разрабатывать языки программирования. Ресурс лично моих знаний в этом вопросе ограничен. Ресурс времени на доскональное изучение теории и наработанных практик тоже сильно ограничен. Очередное изобретение велосипеда? Разумеется! Может ли этот велосипед быть хоть чем-то полезным? Думаю, да. Все, что мы пишем, написано на русском языке и может быть полезным материалом для дальнейших разработок. Лично мне любопытно, что из этого получится...
Поделиться32023-03-20 21:34:23
Первый шаг. Основной цикл ВМ.
Что должна делать виртуальная машина? Она должна принять на вход программу, в виде некоторой последовательности команд, и выполнить ее. Процесс чтения команды, ее распознавания и выполнения циклический и может быть описан обычным циклом языка программирования. Что еще важно? Важна скорость выполнения. Сегодня можно позволить себе немного проиграть в памяти, но достичь максимального быстродействия. А иначе для чего использовать Си, чтобы при этом писать тормозной код?
А теперь небольшие кусочки кода.
В виде чего будет представлена наша ВМ в коде на языке Си? В виде одной единственной переменной структурного типа. В нашем коде имя этой переменной эта_ВМ. А если еще точнее, то это имя указателя на эту переменную.
Внутри этой структуры есть член с именем регистр_команд. Это указатель на текущую команду. Тогда как будет выглядеть цикл ВМ?
для( ; эта_ВМ -> регистр_команд -> структура_команды.операция != СТОП; эта_ВМ -> регистр_команд++ )
{
таблица_вызовов[ эта_ВМ -> регистр_команд -> структура_команды.операция ](эта_ВМ);
}
Всё. Это весь цикл ВМ. Если кто-то знает, как можно сделать быстрее, пишите.
Разберем, что происходит внутри цикла. Мы вызываем функцию, указатель на которую лежит в ячейке массива с именем таблица_вызовов. Еще раз, в массиве лежат адреса малюсеньких функций, каждая из которых делает единственное действие. (например: поместить в регистр А сумму регистра А и регистра Б). Тогда возникает вопрос, а как нам найти нужную функцию в этом огромном массиве? По индексу, который мы извлечем из прочитанной команды.
Отредактировано Евгений (2023-03-20 21:38:35)
Поделиться42023-03-20 21:38:13
- Участник
- Зарегистрирован: 2023-03-10
- Приглашений: 0
- Сообщений: 649
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
3 дня 16 часов - Последний визит:
2024-04-12 10:52:41
Евгений написал(а):
какой именно должна стать виртуальная машина
Можно у Кнута про MMIX прочитать, и это ничем не плохо, кроме времени, думаю пару дней займёт. Или неделю, если читать в дороге на работу/с работы.
Она должна стать спецификацией, глядя на которую школьники, студенты и преподаватели смогут писать свои компиляторы.
Снизу у неё на выбор: Эльбрус, Арм64, Интел64, РискВ5 (Risc-V)
Сверху у неё: Рефал, Haskell, Rust, Си, JavaScript и что там ещё бывает.
Поделиться52023-03-20 22:37:40
В отличии от MMIX я хочу "ужать" размер команды до 16-бит. Вернее не самой команды, а ее операционной части (оперкод + адреса регистров). Мне это нужно, чтобы таблица указателей не "раздулась" до невероятных размеров.
Отредактировано Евгений (2023-03-20 22:42:57)
Поделиться62023-03-21 00:22:33
- Участник
- Зарегистрирован: 2023-03-10
- Приглашений: 0
- Сообщений: 649
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
3 дня 16 часов - Последний визит:
2024-04-12 10:52:41
Отличная идея!
Тратя на индекс в таблице 2 байта вместо 8 байтов (64 бита в типе uint на современных машинах) можно ужать таблицу в 4 раза.
Что при количестве команд 65 тысяч сэкономит почти полмегабайта памяти (384 килобайта, если точно).
Если каждый день по такой же идее придумывать, суперизделие получится.
Почитал википедию, у Кнута 256 команд, и все они влезают в один байт.
А если нужны регистры, то их 256 штук, и номера регистров указываются байтами, следующими за кодом команды.
Одно из значений опкодов зарезервировано для расширений в будущем.
Отредактировано Лис (2023-03-21 00:30:50)
Поделиться72023-03-21 00:30:47
Евгений написал(а):
В отличии от MMIX я хочу "ужать" размер команды до 16-бит.
Поскольку полное число различных вариаций команд скорее всего будет четырехзначным, то писать это вручную будет мягко говоря утомительно. И вот тут я и хочу сделать и использовать некий программный генератор.
Осталось решить, как оптимальнее распорядиться 16-ю битами.
Пока в мыслях сделать такую структуру: ОП Р1 Р2 Р,
где ОП - оперкод, занимающий 7 бит,
Р1, Р2 - регистры операнды по 3 бита,
Р - регистр, куда помещаем результат тоже 3 бита.
В результате у нашей ВМ получается восемь 64-битных регистров общего назначения, их можно дополнить восьмью регистрами для операций с плавающей точкой. И на все это богатство 128 команд.
Поделиться82023-03-21 00:35:36
- Участник
- Зарегистрирован: 2023-03-10
- Приглашений: 0
- Сообщений: 649
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
3 дня 16 часов - Последний визит:
2024-04-12 10:52:41
Евгений написал(а):
восемь регистров общего назначения ... восемь регистров для операций с плавающей точкой
Мало, не соответствует реалиям, данным нам в железе.
Эльбрус-8C имеет 192 регистра общего назначения и 256 регистров векторных вычислений
Байкал-М имеет 32 регистра общего назначения по 64 бита и 32 регистра SIMD длиной по 128 битов
Значит, битов должно быть не 16, вот и всё.
Какая разница, какая у таблицы длина?
Отредактировано Лис (2023-03-21 00:53:24)
Поделиться92023-03-21 00:36:27
Лис не уловил идею. У меня только число ячеек в таблице 65 тысяч. Каждый дополнительный бит удваивает таблицу.
Поделиться102023-03-21 00:38:26
- Участник
- Зарегистрирован: 2023-03-10
- Приглашений: 0
- Сообщений: 649
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
3 дня 16 часов - Последний визит:
2024-04-12 10:52:41
Евгений написал(а):
Каждый дополнительный бит удваивает таблицу.
Имея 256 гигабайт памяти на десктопном компе мне это пофиг.
256 гигабайт = (2^32*64)/1024/1024/1024
т.е. только таблица 4-х байтных команд с полными адресами переходов меня заставит задуматься.
Но вообще есть что-то в этом неправильное. Кеши, промахи, вот это всё.
Отредактировано Лис (2023-03-21 01:00:12)
Поделиться112023-03-21 01:00:05
Даже спорить не буду... Если у Лиса есть место на 2**32 * 8 Байт в оперативной памяти. Но это не значит, что нельзя сделать больше. Просто нельзя это сделать предложенным способом.
И зачем нам 256 регистров, если у них такая же скорость, как у ячейки памяти? Все же эмулятор железного процессора и эмулятор упрощенного процессора это разные вещи.
Отредактировано Евгений (2023-03-21 01:00:50)
Поделиться122023-03-21 01:01:39
- Участник
- Зарегистрирован: 2023-03-10
- Приглашений: 0
- Сообщений: 649
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
3 дня 16 часов - Последний визит:
2024-04-12 10:52:41
Евгений написал(а):
эмулятор железного процессора и эмулятор упрощенного процессора это разные вещи.
QEMU вполне себе эмулирует реальные процессоры, тот же Эльбрус, в котором 256 регистров. И всё у неё хорошо, не жалуется...
Поделиться132023-03-21 01:10:14
Хорошо, сколько Лис хочет регистров при максимальном быстродействии? При определенном пороге быстродействие упадет в 6-8 раз.
Если очень грубо 8 регистров 0.5 МБ
16 регистров 4 МБ
32 регистра 32 МБ
64 регистра 256 МБ
128 регистров 2 ГБ
256 регистров 16 ГБ
Хотя нет. Нет смысла сейчас спорить. Нужно попробовать этот вариант для 8 регистров и сделать вывод. Там только один файл исходника будет сумасшедший.
Отредактировано Евгений (2023-03-21 01:26:25)
Поделиться142023-03-21 01:23:19
- Участник
- Зарегистрирован: 2023-03-10
- Приглашений: 0
- Сообщений: 649
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
3 дня 16 часов - Последний визит:
2024-04-12 10:52:41
Евгений написал(а):
256 регистров 16 ГБ
Это не проблема, но ведь ещё столько же или больше места потребуется на код подпрограмм.
И тогда эмулятор не запустится на моём телефоне (там всего 32 ГБ)
Но я уже выше писал, что по-моему это не самый быстрый способ.
Потому что кеши и промахи.
Возможно одна подпрограмма, обрабатывающая регистры творчески, поместится в кеш процессора, не будет из него вылезать
и в итоге будет работать быстрее, чем огромная таблица, но с промахами.
Кеш процессора второго уровня обычно имеет объём от сотен килобайт до мегабайт
например 24 мегабайта L3, 768 килобайт L2, 24 кб L1
Отредактировано Лис (2023-03-21 01:29:47)
Поделиться152023-03-21 01:33:13
256 регистров нужно однозначно делать другим способом. Но генератор я все равно хочу обкатать. Может придут новые мысли.
Поделиться162023-03-21 01:37:58
- Участник
- Зарегистрирован: 2023-03-10
- Приглашений: 0
- Сообщений: 649
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
3 дня 16 часов - Последний визит:
2024-04-12 10:52:41
Евгений написал(а):
генератор я все равно хочу обкатать
Чем, по-твоему, генератор кода на Си принципиально отличается от генератора HTML-кода?
Слышал ли ты про T4 text templating engine ? Видел ли ты сравнения этого движка с web-движком Razor (тоже от Microsoft, но для web)?
Это я к тому, что не отличаются они почти ничем.
И если хочется сделать шаблонизатор, то лучше, наверное, для Web.
А команды как-нибудь по-другому.
Отредактировано Лис (2023-03-21 01:43:01)
Поделиться172023-03-21 20:38:35
Лис написал(а):
Но я уже выше писал, что по-моему это не самый быстрый способ.
Потому что кеши и промахи.
Предположение Лиса оказалось верно. Прямая обработка команды (декодирование и выполнение) примерно равна по скорости вызову функции через таблицу. Эксперимент был полезным.
Тестовая ветка для проверки производительности разных вариантов. Комит
Отредактировано Евгений (2023-03-21 21:37:10)
Поделиться182023-03-22 01:14:14
- Участник
- Зарегистрирован: 2023-03-10
- Приглашений: 0
- Сообщений: 649
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
3 дня 16 часов - Последний визит:
2024-04-12 10:52:41
Евгений написал(а):
#макрос РЕГИСТР_Е регистры[5]
#макрос РЕГИСТР_Ж регистры[6]
... е, ё, ж ...
«игнорирование или отказ печатать букву «ё» будет означать нарушение Федерального закона «О государственном языке Российской Федерации».»
й - по аналогии
Отредактировано Лис (2023-03-22 01:18:34)
Поделиться192023-03-22 08:36:14
Лис весьма вольно трактует нормативную базу.
Если провести параллель с ГОСТ Р 2.105—2019, то в нем есть такой пункт:
6.3.5 Элемент «Приложение» обозначают прописными буквами русского алфавита, начиная с А,
за исключением букв Ё, З, Й, О, Ч, Ь, Ы, Ъ.
На мой взгляд очень разумный подход. Для нашего случая можно выбрать любой вариант, но только в начале спецификации придется об этом написать. Хотя для 256 регистров использование букв не актуально.
Поделиться202023-03-22 18:51:09
Лис не пробовал запустить тестовый вариант? Мне любопытно, не наблюдалось ли явное преимущество одного варианта над другим по быстродействию.
Поделиться212023-03-22 19:29:47
- Участник
- Зарегистрирован: 2023-03-10
- Приглашений: 0
- Сообщений: 649
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
3 дня 16 часов - Последний визит:
2024-04-12 10:52:41
Евгений написал(а):
Лис не пробовал запустить тестовый вариант? Мне любопытно, не наблюдалось ли явное преимущество одного варианта над другим по быстродействию.
Лис уже сообщал о том, что в России миллион ДРУГИХ айтишников ждёт настоящих лидеров.
Если тебе любопытно, напиши твой запрос людям на нескольких посещаемых форумах.
Этим ты как прорекламируешь проект, так и получишь экспертизу многих опытных специалистов.
Всё знать невозможно, опыт многих людей шире опыта одного маленького лиса.
Рекомендую rsdn, lor и programmers forum
Разберут по костям всё, приведут все возможные соображения.
Поделиться222023-03-24 10:39:38
- Автор "Солуни"
- Откуда: Екатеринбург
- Зарегистрирован: 2020-10-06
- Приглашений: 0
- Сообщений: 654
- Уважение: [+0/-0]
- Позитив: [+1/-0]
- Пол: Мужской
- Возраст: 43 [1980-08-03]
- Провел на форуме:
8 дней 21 час - Последний визит:
Сегодня 09:03:24
Евгений написал(а):
Тестовая ветка для проверки производительности разных вариантов. Комит
Для тестирования мне нужен бинарник для запуска в ОС Windows 10 x64 или в ОС Windows 7 x64.
Поделиться232023-03-24 11:50:01
Пока не актуально, так как переделываю алгоритм. Но чуть позже будут опять два варианта, и тест понадобится.
Поделиться242023-03-24 12:13:51
NuShaman написал(а):
Евгений написал(а):
Тестовая ветка для проверки производительности разных вариантов. Комит
Для тестирования мне нужен бинарник для запуска в ОС Windows 10 x64 или в ОС Windows 7 x64.
Нужен быстрый алгоритм тестирования на переполнение целого знакового 64-битного числа. Пример:
рез = а1 +а2;
если(((рез ^ а1) >> 63) & (~ ((а1 ^ а2)>> 63)) )
{
//значит произошло переполнение
// ^ - побитовая XOR
// & - побитовая AND
// ~ - побитовая NOT
// >>63 - сдвиг вправо на 63 позиции
}
Отредактировано Евгений (2023-03-24 12:17:08)
Поделиться252023-03-24 13:09:38
- Участник
- Зарегистрирован: 2023-03-10
- Приглашений: 0
- Сообщений: 649
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
3 дня 16 часов - Последний визит:
2024-04-12 10:52:41
Возможно вот это поможет, но надо подумать, как применить:
[html]
<a href="https://ru.wikipedia.org/wiki/%D0%A1%D1%85%D0%B5%D0%BC%D0%B0_%D1%83%D1%81%D0%BA%D0%BE%D1%80%D0%B5%D0%BD%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%B5%D1%80%D0%B5%D0%BD%D0%BE%D1%81%D0%B0">Схема ускоренного переноса</a>[/html]
в принципе есть два входных n-битных набора, надо построить функцию от 2-n переменных, которая выдаёт последний бит переноса.
Как её запрограммировать после - это отдельный вопрос.
https://stackoverflow.com/questions/394 … low-in-c-c
https://stackoverflow.com/questions/199 … r-overflow
Отредактировано Лис (2023-03-24 13:34:05)
Поделиться262023-03-25 11:25:53
Похоже разработчики qemu тоже не обошлись без генератора кода.
Страница: 1