Комментарии 77
Зачем вообще проверять инструкции на корректность в рантайме? Как минимум можно это сделать отдельно от выполнения — тогда в случае циклов не будем дублировать эти проверки над одними и теми же данными.
Еще возможно стоит попробовать организовать хранение нескольких верхних значений стека в регистрах, а не в памяти — скорость доступа к ним наиболее важна.
P. S. Примечательно, что суперинструкции дали такой прирост. Ждем поддержку SIMD))
Еще возможно стоит попробовать организовать хранение нескольких верхних значений стека в регистрах, а не в памяти — скорость доступа к ним наиболее важна.
P. S. Примечательно, что суперинструкции дали такой прирост. Ждем поддержку SIMD))
Я не уверен, что понял про корректность в рантайме. Инструкции нигде ничего лишнего не проверяют. Или вы про что?
Хранение вершины стека в регистрах надо делать на ассемблере, это отдельная статья потребуется. Я тут решил не маньячить так прям сильно. Кстати, именно так работает GForth, основанный на vmgen. Там хитро жонглируются инструкции и аргументы инструкций так, чтобы все время держать один-два элемента в регистрах. Говоря, дает 10-15% примерно.
Суперинструкции — первое, что стоит делать: легко, быстро, хорошо работает. Но, с другой стороны, их делают все, тут что-то особенное не получится.
SIMD не SIMD, но любопытно, как бы так заюзать возможность тащить и выполнять несколько инструкций разом при условии, что между ними нет зависимостей. Типа как процессор делает… Это так, мысли вслух.
Хранение вершины стека в регистрах надо делать на ассемблере, это отдельная статья потребуется. Я тут решил не маньячить так прям сильно. Кстати, именно так работает GForth, основанный на vmgen. Там хитро жонглируются инструкции и аргументы инструкций так, чтобы все время держать один-два элемента в регистрах. Говоря, дает 10-15% примерно.
Суперинструкции — первое, что стоит делать: легко, быстро, хорошо работает. Но, с другой стороны, их делают все, тут что-то особенное не получится.
SIMD не SIMD, но любопытно, как бы так заюзать возможность тащить и выполнять несколько инструкций разом при условии, что между ними нет зависимостей. Типа как процессор делает… Это так, мысли вслух.
Про корректность — имеется в виду упражнение второе. В конце концов, все равно делается побитовое «и». Мне кажется, лучше было бы вообще не проверять корректность инструкции на данном этапе:
В этом случае лишних действий вообще нет. А если есть риск, что код может оказаться некорректным, просто предварительно пройтись по буферу и сделать чисто проверки на корректность.
Про SIMD — имелось в виду введение непосредственно инструкций, аналогичных Intel SSE, например взять из стека два вектора значений, просуммировать, и результат засунуть в стек. Но вообще это шутка была.
uint8_t instruction = NEXT_OP();
/* Let the compiler know that opcodes are always between 0 and 31 */
switch (instruction) {
/* All the instructions here */
default: {
__builtin_unreachable();
}
}В этом случае лишних действий вообще нет. А если есть риск, что код может оказаться некорректным, просто предварительно пройтись по буферу и сделать чисто проверки на корректность.
Про SIMD — имелось в виду введение непосредственно инструкций, аналогичных Intel SSE, например взять из стека два вектора значений, просуммировать, и результат засунуть в стек. Но вообще это шутка была.
Про корректность. Разницы никакой не будет. Это, считай, просто еще одна инструкция в таблице переходов, которую сгенерит компилятор. Озвучить же проблемы байт-кода всегда бывает полезно. Например, когда указатель текущей инструкции сбился, или ассемблер какую-нибудь ерунду влепил в байт-код, мало ли.
Ходить лишний раз по байт-коду и валидировать… Зачем? Это должен делать компилятор в байт-код. Хотя в данном случае компилятором работал я сам :-)
Я шутку понял :-) Про внеочередное выполнение байт-кода — ответная шутка.
Ходить лишний раз по байт-коду и валидировать… Зачем? Это должен делать компилятор в байт-код. Хотя в данном случае компилятором работал я сам :-)
Я шутку понял :-) Про внеочередное выполнение байт-кода — ответная шутка.
Что-то я запутался — то кто-то влепил в байт-код ерунду, то его валидирует компилятор. Допускается ли ситуация, что байт-код на входе будет невалидным? Если да, то предлагается предварительно пройтись по всему буферу байт-кода, и для каждого байта проверить, что он является валидной инструкцией. Профит тут очевиден — когда в программе есть циклы (всегда), мы вместо N проверок на валидность тела цикла проверим его только один раз.
Тогда, использовав в switch'е пометку про недостижимость ветки default, информируем компилятор о том, что все инструкции валидны. Тогда если сравнивать с изначальным вариантом, то мы избавляемся от лишнего прыжка, если с оптимизированным — от лишнего логического «и».
Тогда, использовав в switch'е пометку про недостижимость ветки default, информируем компилятор о том, что все инструкции валидны. Тогда если сравнивать с изначальным вариантом, то мы избавляемся от лишнего прыжка, если с оптимизированным — от лишнего логического «и».
Пардон, я все не понял сначала.
При условии полной валидности байт-кода да, конечно, так и будет. Можно убрать этот хвост и маску, и посмотреть, что компилятор сделает с __builtin_unreachable. Разумно предположить, что компилятор догадается, о чем речь.
А вы проверяли?
В принципе, это то же самое, хотя на стандартном Си эту мысль изложить трудней. Я эта в статье указывал.
При условии полной валидности байт-кода да, конечно, так и будет. Можно убрать этот хвост и маску, и посмотреть, что компилятор сделает с __builtin_unreachable. Разумно предположить, что компилятор догадается, о чем речь.
А вы проверяли?
В принципе, это то же самое, хотя на стандартном Си эту мысль изложить трудней. Я эта в статье указывал.
Ну, статья про оптимизацию вроде, вот я и указал как еще больше улучшить.
Только что проверил тут, вроде все как надо.
Только что проверил тут, вроде все как надо.
По ассемблеру у меня выходит, что обе версии работают одинаково с точки зрения инструкций (__builtin_unreachable или явно покрывать весь возможный интервал).
Мне нравится, признаться unreachable за то, что название как бы явно говорит, что, мол, такого-то быть не может, и этого быть не должно. Единственный недостаток — нестандартность.
По производительности разницы не будет, если верить godbolt.org :-)
Мне нравится, признаться unreachable за то, что название как бы явно говорит, что, мол, такого-то быть не может, и этого быть не должно. Единственный недостаток — нестандартность.
По производительности разницы не будет, если верить godbolt.org :-)
> в библиотеках вроде GNU Lightning или LibJIT вся грязная работа уже сделана. Но время на разработку и общий объём кода даже с использованием библиотек здорово увеличиваются.
А всё же на сколько трудно и долго будет прикрутить jit для этого? В чём основная сложность? Делаю самопальную виртуальную машину для самообразования, и с темой интеграции jit'ом пока вообще не соприкасался.
P.S. Поделюсь своим скриптиком для генерации H-файла с опкодами на основе описания в Yaml файле github.com/tekord/cpp-opcode-generator, мелочь, конечно, но вдруг кому-нибудь пригодится.
А всё же на сколько трудно и долго будет прикрутить jit для этого? В чём основная сложность? Делаю самопальную виртуальную машину для самообразования, и с темой интеграции jit'ом пока вообще не соприкасался.
P.S. Поделюсь своим скриптиком для генерации H-файла с опкодами на основе описания в Yaml файле github.com/tekord/cpp-opcode-generator, мелочь, конечно, но вдруг кому-нибудь пригодится.
Ну, jit-компиляторы и техники компиляции бывают очень разные по сложности. В самой простой форме, с полной компиляцией байт-кода примитивной машинки уровня Поросенка и на libjit, можно за пару недель что-то быстрое сделать.
Я делал кое-что с libjit, но особого профита не получил. В финале разработки понял, наконец, что было неправильно, но время кончилось, и код пришлось выбросить. Мораль: надо знать, как и что делать, и выяснение этих вопросов — тоже календарное время.
Сюрпризы, встреченные по дороге:
1. Компиляция занимает ощутимое время.
2. Вызов кода через динамический линковщик не бесплатен. Скачки между динамическим кодом и кодом родительским тяжелее обычных вызовов функций. Работа по возможности производиться без перехода между ними.
3. Для коротких одноразовых последовательностей байт-кода простой интепретатор всегда будет быстрее.
Без libjit, на портативном ассемблере типа GNU Lightning, разработка займет еще больше времени.
Я делал кое-что с libjit, но особого профита не получил. В финале разработки понял, наконец, что было неправильно, но время кончилось, и код пришлось выбросить. Мораль: надо знать, как и что делать, и выяснение этих вопросов — тоже календарное время.
Сюрпризы, встреченные по дороге:
1. Компиляция занимает ощутимое время.
2. Вызов кода через динамический линковщик не бесплатен. Скачки между динамическим кодом и кодом родительским тяжелее обычных вызовов функций. Работа по возможности производиться без перехода между ними.
3. Для коротких одноразовых последовательностей байт-кода простой интепретатор всегда будет быстрее.
Без libjit, на портативном ассемблере типа GNU Lightning, разработка займет еще больше времени.
К сожалению не описана работа виртуальной машины с вещественными числами, строками, структурами. А все это очень интересно.
Еще нет бинарного формата файла байткода, чтобы понять как хранить скомпилированные опкоды, целые и вещественные константы, строки, ресуры и т.д.
Еще нет бинарного формата файла байткода, чтобы понять как хранить скомпилированные опкоды, целые и вещественные константы, строки, ресуры и т.д.
Согласен, все это очень интересно.
Но надо же на чем-то концентрироваться, а виртуальные машины бывают очень разные. Здесь я выбрал именно главный цикл виртуальной машины, так как это то, что встречается в любой реализации. То есть оптимизация именно этого цикла даст выигрыш в любом случае.
Если интересно, могу на пальцах вот прямо в комментариях изложить, как, например, константы, строки и структуры хранятся.
Но надо же на чем-то концентрироваться, а виртуальные машины бывают очень разные. Здесь я выбрал именно главный цикл виртуальной машины, так как это то, что встречается в любой реализации. То есть оптимизация именно этого цикла даст выигрыш в любом случае.
Если интересно, могу на пальцах вот прямо в комментариях изложить, как, например, константы, строки и структуры хранятся.
Да изложите. Интересно как происходят операции со строками, структурами и вещественными числами на стеке.
Давайте начну с вещественных чисел, для случая низкоурвневых машинок языков, а ля JVM, то есть с типами значений, известными на этапе компиляции.
1. Вещественные числа.
Вводится второй комплект инструкций для арифметических операции с вещественными чисел + конвертирующие между ними и целочисленными значениями инструкции.
Вещественные числа представляются приличным числом байт, в непосредственные аргументы пихаются хуже, поэтому обычно оказываются в таблице констант. Соответственно, для добавляются операции извлечения чисел из таблицы констант на стект.
Таблица констант со всем содержимым вкладывается в байт-код, т.е. тут не просто поток байт, как в «ПоросенокВМ», у набор структур данных (сам байт-код + таблица констант).
2. Строки (и структуры, для них оно похожим образом работает).
Тут возможны варианты, но обычно вводится специальный тип обобщенных объектов. Это, в сущности, маркер типа объекта («здесь строка» или «здесь структура») + сам объект Байт-код или стек не оперирует самими значениями объектов (было бы странно хранить длиннющие строки в стеке ограниченного размера), а указателями на них. Указатели на эти объекты-строки или объекты-структуры помещают в ту же таблицу констант, если значение известно заранее, либо уж в динамическую память (англ. heap).
Соответственно, появляются специальные инструкции для помещения указателей на объекты из таблицы констант на стек + инструкции для работы с этими указателями.
Раз уж мы заговорили про динамическую память, то, конечно, появляется необходимость в сборщике мусора и инструкциях аллокации/деаллокации объектов…
3. Вы про это не спрашивали. Функции и методы — тоже важная штука.
Байт-код и таблица констант тоже не в одной пачке хранится в файле. Они сгруппированы по функциями, если только это не таблица глобальных констант… Т.е. файл с байт-кодом это: таблица глобальных констант + методы. Каждый метод: таблица локальных констант + сам байт-код функции.
Не стесняйтесь спрашивать, если что-то еще интересно.
1. Вещественные числа.
Вводится второй комплект инструкций для арифметических операции с вещественными чисел + конвертирующие между ними и целочисленными значениями инструкции.
Вещественные числа представляются приличным числом байт, в непосредственные аргументы пихаются хуже, поэтому обычно оказываются в таблице констант. Соответственно, для добавляются операции извлечения чисел из таблицы констант на стект.
Таблица констант со всем содержимым вкладывается в байт-код, т.е. тут не просто поток байт, как в «ПоросенокВМ», у набор структур данных (сам байт-код + таблица констант).
2. Строки (и структуры, для них оно похожим образом работает).
Тут возможны варианты, но обычно вводится специальный тип обобщенных объектов. Это, в сущности, маркер типа объекта («здесь строка» или «здесь структура») + сам объект Байт-код или стек не оперирует самими значениями объектов (было бы странно хранить длиннющие строки в стеке ограниченного размера), а указателями на них. Указатели на эти объекты-строки или объекты-структуры помещают в ту же таблицу констант, если значение известно заранее, либо уж в динамическую память (англ. heap).
Соответственно, появляются специальные инструкции для помещения указателей на объекты из таблицы констант на стек + инструкции для работы с этими указателями.
Раз уж мы заговорили про динамическую память, то, конечно, появляется необходимость в сборщике мусора и инструкциях аллокации/деаллокации объектов…
3. Вы про это не спрашивали. Функции и методы — тоже важная штука.
Байт-код и таблица констант тоже не в одной пачке хранится в файле. Они сгруппированы по функциями, если только это не таблица глобальных констант… Т.е. файл с байт-кодом это: таблица глобальных констант + методы. Каждый метод: таблица локальных констант + сам байт-код функции.
Не стесняйтесь спрашивать, если что-то еще интересно.
Первый раз слышу, что на уровне байткода есть функции. В них действительно есть смысл? Или достаточно делать JMP на подпрограмму.
На уровне байт-кода виртуальных машин для языков программирования функции есть почти всегда, это я вам точно говорю. И целая машинерия для их обслуживания. И рядовой jit компилирует именно в терминах этих самых функций.
Делаются они по-разному, но есть всегда. Да чего уж!.. Бывают и классы даже.
В машинном коде и микрокоде эмуляторов железных процессоров их, конечно, нет.
Делаются они по-разному, но есть всегда. Да чего уж!.. Бывают и классы даже.
В машинном коде и микрокоде эмуляторов железных процессоров их, конечно, нет.
А почему рассматривался именно динамический JIT? Можно ведь при старте программы распаковывать ее транслируя в нативные инструкции, пусть и без хитрых оптимизаций.
Это вы точно заметили :-)
Можно было бы один раз на старте транслировать программу в машинный код — и не париться.
Но! Машинный код еще скомпилировать и прилинковать к программе надо. Для быстрого запуска маленьких программок это не подходит, что бы там не говорили поклонники JVM. Тот же Питон запускается и приступает к работе намного быстрей.
Опять же, программы здорово распухают в памяти с таким подходом, что, конечно, в наши дни уже не так страшно, но все же…
Да и… Для быстрой компиляции нужен какой-то ассемблер, типа GNU Lightning, это не так просто, как может показаться (но и не суперсложно, да).
Практические виртуалки обычно выбирают какой-то отдельный «горячий» участок программы для компиляции. Особенно с этим стараются не переборщить реализации Javascript: пользователи не любят ждать загрузку страниц.
Можно было бы один раз на старте транслировать программу в машинный код — и не париться.
Но! Машинный код еще скомпилировать и прилинковать к программе надо. Для быстрого запуска маленьких программок это не подходит, что бы там не говорили поклонники JVM. Тот же Питон запускается и приступает к работе намного быстрей.
Опять же, программы здорово распухают в памяти с таким подходом, что, конечно, в наши дни уже не так страшно, но все же…
Да и… Для быстрой компиляции нужен какой-то ассемблер, типа GNU Lightning, это не так просто, как может показаться (но и не суперсложно, да).
Практические виртуалки обычно выбирают какой-то отдельный «горячий» участок программы для компиляции. Особенно с этим стараются не переборщить реализации Javascript: пользователи не любят ждать загрузку страниц.
Я подразумевал не полную компиляцию всего и вся в единую бинарную программу. А компилировать только тела функций, набрасывая ассемблерные команды по шаблону на каждую из них. Пуская с nop выравниванием и оригинальными вызовами функций. В одном теле не так много переходов, чтобы оно «распухало» при переводе в ассемблерный вид. Хотя конечно не спорю, в больших программах потребуется время на подготовку.
Это, кажется, называется «шаблонной динамической компиляцией» (или англ. template jit), и она действительно довольно быстро работает. В GNU Guile недавно именно такой jit добавили на базе GNU Lightning.
Я ж не против :-) Думаю, в случае «ПоросенокВМ» такой подход отлично сработает, особенно если не кешировать скомпилированные функции между запусками программ. Тип тут один, инструкции простенькие… Да, должно быть несложно.
Вы что-нибудь такое пробовали делать?
Я ж не против :-) Думаю, в случае «ПоросенокВМ» такой подход отлично сработает, особенно если не кешировать скомпилированные функции между запусками программ. Тип тут один, инструкции простенькие… Да, должно быть несложно.
Вы что-нибудь такое пробовали делать?
Пробовал, частично, в виде тестов. Этот подход неплохой как компромисс, но проблема у меня в методе отладки при таком подходе. Если с обычным байткодом отладка реализуема и понятна, то при переводе в машинные коды пока не увидел адекватного решения.
Добро пожаловать в дивный мир деоптимизации :-) Это типа целая наука, особенно в случая продвинутых оптимизирующих jit-ов.
В случае шаблонного jit это еще несложно. Можно, например, прямо в ассемблере вкомпилировать необходимую для отладки инфу типа адреса текущей инструкции. А по адресу можно и всякое другое уже извлечь, типа номера строки в исходном коде или что-нибудь еще.
Вы что-нибудь сделали в итоге или сдались?
В случае шаблонного jit это еще несложно. Можно, например, прямо в ассемблере вкомпилировать необходимую для отладки инфу типа адреса текущей инструкции. А по адресу можно и всякое другое уже извлечь, типа номера строки в исходном коде или что-нибудь еще.
Вы что-нибудь сделали в итоге или сдались?
Это сейчас одно и моих направлений, нужно выбирать за основу какой-то вариант реализации. При этом скорость исполнения на первом месте, именно поэтому читаю и смотрю варианты с пред-компиляцией.
Разве, если делать такие вставки, то не придется ли слишком много прыгать?
Разве, если делать такие вставки, то не придется ли слишком много прыгать?
не знаю, обсуждаем ли мы одно и то же, но раз уж на то пошло…
В случае обычного шаблонного jit-а, думаю, можно сделать что-то вроде двух режимов: отладочный и обычный, и в отладочном добавлять какой-то дополнительный код или дополнительные данные. Либо вообще всегда включать в машинный хранить дополнительные отладочные символы, но трогать их только при необходимости.
В любом случае начать можно с байт-кода, а там при необходимости и наличии времени можно сбоку прикруть компилятор-ускорялку.
В случае обычного шаблонного jit-а, думаю, можно сделать что-то вроде двух режимов: отладочный и обычный, и в отладочном добавлять какой-то дополнительный код или дополнительные данные. Либо вообще всегда включать в машинный хранить дополнительные отладочные символы, но трогать их только при необходимости.
В любом случае начать можно с байт-кода, а там при необходимости и наличии времени можно сбоку прикруть компилятор-ускорялку.
Два режима понятно, но накладно. То есть переключаясь в режим отладки, мы получаем другой машинный код, что уже может повлечь за собой какие-то различия в исполнении. Вопрос у меня скорее в другом. Как будут работать эти отладочные символы, про которые Вы говорите? На стороне IDE есть только инструкции байткода, и их соответствие с языком верхнего уровня. В runtime уже появляется две сущности, одна это оригинальный байткод, другая это исполняемый код. Как Вы предполагаете осуществлять работу, для начала, точек останова?
А вот тут я вам не помогу, признаться. Все зависит от IDE и того, как она отладочные символы понимает.
Я бы для начала обошелся жирным комлпектом тестов, без привязки к конкретной IDE, который бы и гонял как на простом байт-коде, так и jit-компилированном коде.
IDE и отладочными символами заниматься имеет смысл, если только это какой-то более долгосрочный проект. Но это мой подход.
Я бы для начала обошелся жирным комлпектом тестов, без привязки к конкретной IDE, который бы и гонял как на простом байт-коде, так и jit-компилированном коде.
IDE и отладочными символами заниматься имеет смысл, если только это какой-то более долгосрочный проект. Но это мой подход.
Так я скорее про сам возможный принцип работы точек останова в таком виде. Речь не идет о какой-то конкретной IDE. В моем случае это долгосрочный проект, поэтому этот момент пытаюсь у Вас расспросить. Мне показалось, что у Вас есть представление о том, как это может быть реализовано.
Ну в каком-то ограниченном смысле я могу вам что-то подсказать, но, честно говоря, слишком много темой внешних дебаггеров не занимался.
Кроме того, весь мой опыт это Линукс, а на каждой платформе свой подход к этим вещам. Под Линуксом есть специальный syscall для этого — ptrace, и все дебаггеры его используют.
Вот неплохое введение по тому, как работает gdb:
sourceware.org/gdb/wiki/Internals/Breakpoint%20Handling
А вот хороший туториал от знающего специалиста:
eli.thegreenplace.net/2011/01/23/how-debuggers-work-part-1
Для остального потребуется знание уже конкретного проекта и конкретной платформы.
Кроме того, весь мой опыт это Линукс, а на каждой платформе свой подход к этим вещам. Под Линуксом есть специальный syscall для этого — ptrace, и все дебаггеры его используют.
Вот неплохое введение по тому, как работает gdb:
sourceware.org/gdb/wiki/Internals/Breakpoint%20Handling
А вот хороший туториал от знающего специалиста:
eli.thegreenplace.net/2011/01/23/how-debuggers-work-part-1
Для остального потребуется знание уже конкретного проекта и конкретной платформы.
Если программа будет осуществлять самомодифицируемый код: сместить блок кода или проставить значение jp, что бы без ифов, эти оптимизации будут применимы?
С самомодифицируемым кодом, как и в железных машинах, все сложней, но ничего непреодолимого.
1. Суперинструкции будут работать как работали.
2. Оптимизация проверки интервала значений байт-кода будет работать как работала.
3. Трассы придется на каждую модификацию инвалидировать и пересобирать.
НО! Опять же, как и в обычном машинном коде будут проблемы с адресами и метками. Если мы смещаем блок кода, то надо будет исправлять адреса всех меток во всех условных и безусловных переходах.
А почему вы спрашиваете? Есть какой-то живой пример?
1. Суперинструкции будут работать как работали.
2. Оптимизация проверки интервала значений байт-кода будет работать как работала.
3. Трассы придется на каждую модификацию инвалидировать и пересобирать.
НО! Опять же, как и в обычном машинном коде будут проблемы с адресами и метками. Если мы смещаем блок кода, то надо будет исправлять адреса всех меток во всех условных и безусловных переходах.
А почему вы спрашиваете? Есть какой-то живой пример?
Спрашиваю, потому что оптимизации компилятора не должны ломать уровень железа. Почему суперинструкции будут работать: если первая её часть модифицирует вторую?
Потому что статические суперинструкции это просто рядовые инструкции, куда вложена логика сразу двух инструкций. У них свой конкретный адрес есть, и их нельзя модифицировать по кускам. Использует их сразу компилятор, сама же виртуалка видит их как неделимое целое.
Динамические — другой вопрос, но я не слышал, чтобы кто-то вообще разрешал двигать куда-то байт-код в виртуалках для языков. Даже самые динамические из интерпретаторов байт-кода обычно просто подменяют байт-код функции целиком.
Динамические — другой вопрос, но я не слышал, чтобы кто-то вообще разрешал двигать куда-то байт-код в виртуалках для языков. Даже самые динамические из интерпретаторов байт-кода обычно просто подменяют байт-код функции целиком.
Например, в проекте есть много циклов где используется подряд две инструкции xor [addr], value; setbit7 reg1. Вы объединяете это в суперинструкцию, а в другом проекте xor [addr], value изменяет не данные в графическом буфере, а бит инструкции setbit7 reg1 (и так же они идут подряд), превращая её в setbit3 reg1, соответственно, при выполнении суперинструкции код изменится, но инструкция будет выполнена старая.
Вы говорите, вероятно, о динамических суперинструкция, когда при запуске кода создается новый временный байт-код. Но такие новые байт-коды будут создаваться каждый раз при запуске программы, поэтому другого проекта и других программ такие инструкции касаться не будут.
Тут я показывал статические суперинструкции, которые делаются один раз, при разработке виртуальной машины. С учетом, скажем, поиска популярных последовательности инструкций среди какого-нибудь стандартного набора программ. Рядовые пользователи виртуальной машины не могут их менять под себя. Байт-код и его смысл в случае статических суперинструкций будет все время один и тот же на всех программах.
Грубо говоря, если в новой версии JVM появится новая сложная (супер)инструкция «взять со стека, прибавить число, умножить на число», то она будет одинаковой для всех.
Тут я показывал статические суперинструкции, которые делаются один раз, при разработке виртуальной машины. С учетом, скажем, поиска популярных последовательности инструкций среди какого-нибудь стандартного набора программ. Рядовые пользователи виртуальной машины не могут их менять под себя. Байт-код и его смысл в случае статических суперинструкций будет все время один и тот же на всех программах.
Грубо говоря, если в новой версии JVM появится новая сложная (супер)инструкция «взять со стека, прибавить число, умножить на число», то она будет одинаковой для всех.
А ещё, меня интересует, можно ли на автомате перейти от стековой к регистровой модели, то есть, создать такие суперинструкции, которые не гоняют память через стек, а вообще используют какую-то внутреннюю переменную (регистр), это может быть сильно эффективней. Просто ISA современных процессоров, что RISC, что CISC создавалась людьми и по наитию или из каких-то идейных соображений, но теперь-то можно взять программы на ЯВУ и получить низкоуровневые суперинструкции из который создать оптимальную ISA статистическими методами.
Однажды сделал для специфических нужд (хотя больше поиграться) машину с весьма ограниченным объёмом памяти (восьмибитная шина на всё про всё). Машину написать было просто, а вот научиться что-то вменяемое в неё уместить не совсем. В частности код постоянно самомодифицировался таким образом, чтобы экономить на его объёме, например весь ввод-вывод шел через чтение/запись по 0x01 в цикле по одному байту. И сам код цикла и обслуживания буфера занимал столько места, что его пришлось переиспользовать. Так как условные переходы потребовали бы много инструкций, пришлось реализовать это динамической заменой безусловных переходов. В принципе можно было это обойти суперинструкциями, но это религия не позволила. Ибо байт-код должен был быть прост и минимален как пробка: два с половиной регистра, двадцать элементарных команд без всяких аргументов. Например что-то в роде a = 1; b = 2; c = a + b; выполняемое в рантайме занимало 19 байт из которых 13 инструкции. С некоторыми плясками можно уместить в 17.
В таких условиях приходилось иногда использовать команды в качестве констант и константы в качестве команд. И использовать константы в роли переменных с таким расчётом, чтобы к моменту, когда понадобится первоначальное значение там оказалось бы именно оно. Само-собой такие программы любили внезапно превращаться в ГПСЧ, а их отладка в ад адовый. Но это работало и кушать не просило. И в «конвееры» потоковой обработки чего-либо стакалось.
Собственно суперинструкции тут конечно много чего позволили бы. Замену свича на арифметику с указателями пробовал, толку очень мало дало почему-то. Трассы точно не сработают. Правда можно сделать как-бы кеш, длиной в машинное слово хоста, чтобы не по байту читать, но сохранить полную совместимость с «честными» восьмью битами.
А с адресами меток в таких случаях проблем нет т.к. это остаётся на совести программиста.
В таких условиях приходилось иногда использовать команды в качестве констант и константы в качестве команд. И использовать константы в роли переменных с таким расчётом, чтобы к моменту, когда понадобится первоначальное значение там оказалось бы именно оно. Само-собой такие программы любили внезапно превращаться в ГПСЧ, а их отладка в ад адовый. Но это работало и кушать не просило. И в «конвееры» потоковой обработки чего-либо стакалось.
Собственно суперинструкции тут конечно много чего позволили бы. Замену свича на арифметику с указателями пробовал, толку очень мало дало почему-то. Трассы точно не сработают. Правда можно сделать как-бы кеш, длиной в машинное слово хоста, чтобы не по байту читать, но сохранить полную совместимость с «честными» восьмью битами.
А с адресами меток в таких случаях проблем нет т.к. это остаётся на совести программиста.
Ну. трассы имеют смысл для больших программ, и чем больше длина участков кода без ветвлений — тем лучше для трасс. Но в принципе, можно просто инвалидировать трассы в местах изменившегося кода.
Собственно, физические процессоры, поддерживающие модификацию кода, так и делают: сбрасывают весь кеш декодированных инструкций.
Собственно, физические процессоры, поддерживающие модификацию кода, так и делают: сбрасывают весь кеш декодированных инструкций.
Хм, а что если распознавать модифицированный код как ещё один набор инструкций, а момент этой модификации как переход между ними? Правда это потребует как минимум дополнительной памяти. Зато в итоге имеем программу которая относительно эффективно работает и на очень ограниченном железе и на машине с кучей памяти, где эти оптимизации по памяти фактически будут развёрнуты обратно в оптимизации по времени. Тот факт что написание такого кода обойдётся дороже любого железа опустим
Большое спасибо за популяризацию техник создания интерпретаторов/языковых ВМ!
А вот эта фраза меня раззадорила. Дело в том, что у меня как раз, совершенно случайно, завалялся набор инструментов для быстрого создания компиляторов. В результате полдня ушло вот на такой миниатюрный компилятор PigletC, написанный с нуля: github.com/true-grue/PigletC
Пример.
Результат компиляции.
Запускаем.
Надеюсь, PigletVM и PigletC сумеют кого-то заинтересовать тематикой создания инструментального ПО.
«Писать программы для виртуальной машины прямо в C — моветон, но и создавать язык программирования — долго, поэтому мы с поросёнком решили ограничиться свинским языком ассемблера»
А вот эта фраза меня раззадорила. Дело в том, что у меня как раз, совершенно случайно, завалялся набор инструментов для быстрого создания компиляторов. В результате полдня ушло вот на такой миниатюрный компилятор PigletC, написанный с нуля: github.com/true-grue/PigletC
Пример.
int r;
int n;
void main() {
n = 5;
r = 1;
while (n > 1) {
r = r * n;
n = n - 1;
}
print(r);
}Результат компиляции.
PUSHI 1
PUSHI 5
STORE
PUSHI 0
PUSHI 1
STORE
L0:
PUSHI 1
LOAD
PUSHI 1
GREATER
JUMP_IF_FALSE L1
PUSHI 0
PUSHI 0
LOAD
PUSHI 1
LOAD
MUL
STORE
PUSHI 1
PUSHI 1
LOAD
PUSHI 1
SUB
STORE
JUMP L0
L1:
PUSHI 0
LOAD
PRINT
DONE
Запускаем.
pigletvm-exec asm fact.c.pvm fact.c.b
pigletvm-exec run fact.c.b
120
Result value: 0
PROFILE: switch code finished took 0ms
120
Result value: 0
PROFILE: switch code (no range check) finished took 1ms
120
Result value: 0
PROFILE: threaded code finished took 0ms
120
Result value: 0
PROFILE: trace code finished took 1ms
Надеюсь, PigletVM и PigletC сумеют кого-то заинтересовать тематикой создания инструментального ПО.
Читатель iliazeus предложил еще одну оптимизацию: кеширование вершины стека в отдельной переменной.
А если её ещё и в регистр прикрепить вместе с ip — совсем летать будет:
register uint8_t *ip asm("%r14");
register uint64_t *stack_top asm("%r15");Использовать осторожно (особенно в x86_32) — эти регистры всегда будут заняты, их аллокатор не трогает вообще.
Да, спасибо большое! Мы тут с пользователем iliazeus уже обсуждали это расширение GCC.
И оно определенно имеет смысл при определенных обстоятельствах. Из недостатков сразу:
1. Надо быть уверенным, что код бежит под x86, т.к. тут упоминается конкретный регистр по имени.
2. Желательно обходится без труднопортируемых расширений.
И если уж использовать, то, наверное, можно тогда вообще на ассемблере писать, чтобы избегать всяких странностей каждого компилятора. luajit2 так и делает, там (по крайней мере когда я смотрел) главный цикл на ассемблере написан во избежание неоднозначностей.
Мы так случайно выяснили, что шитый код GCC без кеширования стека очень странно компилировал в таблицу переходов с единственным местом ветвления, что убивало все преимущества шитого кода, т.е. наличие нескольких мест ветвления.
Я даже думаю сейчас, что надо бы попробовать ручками на ассемблере цикл написать.
И оно определенно имеет смысл при определенных обстоятельствах. Из недостатков сразу:
1. Надо быть уверенным, что код бежит под x86, т.к. тут упоминается конкретный регистр по имени.
2. Желательно обходится без труднопортируемых расширений.
И если уж использовать, то, наверное, можно тогда вообще на ассемблере писать, чтобы избегать всяких странностей каждого компилятора. luajit2 так и делает, там (по крайней мере когда я смотрел) главный цикл на ассемблере написан во избежание неоднозначностей.
Мы так случайно выяснили, что шитый код GCC без кеширования стека очень странно компилировал в таблицу переходов с единственным местом ветвления, что убивало все преимущества шитого кода, т.е. наличие нескольких мест ветвления.
Я даже думаю сейчас, что надо бы попробовать ручками на ассемблере цикл написать.
Я понимаю ваши опасения, но быстрый интерпретатор целиком на pure С вы не напишете. Так или иначе придётся применять«плохие» решения. И, поверьте, pinned registers — это довольно близко к золотой середине. Повторюсь, главный недостаток этого — уменьшение кол-ва доступных GPR для компилятора.
Вы попробуйте ради спортивного интереса.
Можно было бы также задействовать %rsp для стека VM, но во-первых, gcc не даст его закрепить, во-вторых, даже если его инициализировать принудительно через ассемблер, то gcc не обучен таким извращениям и не будет использовать стековые инструкции.
Вы попробуйте ради спортивного интереса.
Можно было бы также задействовать %rsp для стека VM, но во-первых, gcc не даст его закрепить, во-вторых, даже если его инициализировать принудительно через ассемблер, то gcc не обучен таким извращениям и не будет использовать стековые инструкции.
В следующей интерации работы в этом направлении я думаю вообще попробовать чисто на ассемблере (или типа-почти-ассемблере а ля GNU Lightning) главный цикл сделать. В конце концов, изрядная часть приемов — попытка загнать компилятор в суперузкие рамки, такие, чтоб ничего лишнего не делалось.
Ну и да, приделась специальные инструкции под вершину стека и указатель на инструкцию — дело полезное, я попробую. У меня еще в планах одна статья про интерпретаторы, можно будет побаловаться.
Ну и да, приделась специальные инструкции под вершину стека и указатель на инструкцию — дело полезное, я попробую. У меня еще в планах одна статья про интерпретаторы, можно будет побаловаться.
Вы мыслите в правильном направлении. :) Нужно что-то «повыше» ассемблера и «пониже» С. Для этих целей отлично подходит LLVM IR.
Я очень долго боролся с С за интерпретатор, пробовал всякие варианты — в том числе и аналог «трасс», замешанный с continuation passing style. Лучшее, что получилось — это threaded code с прибитыми регистрами.
И после некоторых упражнений с LLVM я понял — это то что надо. В итоге наш новый VA Smalltalk содержит интерпретатор, написанный на LLVM IR. :)
Собирался написать об этом статью тут, но решил, что мало кому будет интересно.
Я очень долго боролся с С за интерпретатор, пробовал всякие варианты — в том числе и аналог «трасс», замешанный с continuation passing style. Лучшее, что получилось — это threaded code с прибитыми регистрами.
И после некоторых упражнений с LLVM я понял — это то что надо. В итоге наш новый VA Smalltalk содержит интерпретатор, написанный на LLVM IR. :)
Собирался написать об этом статью тут, но решил, что мало кому будет интересно.
А почему LLVM IR? Почему не прямо на асме или портативном асме? LLVM столько всего потом с этим самым IR делает, что все равно как-то неудобно выходит, разве нет?
Хабр, кстати, не так уж и плох в смысл нишевых статей. Здесь очень широкий охват публики, весь бывший СССР. Лайков, может, и не наберете, но несколько интересных человек на статью обычно отзывается, это исходя из моего опыта.
Главное — не читать первые пять комментариев от случайных прохожих :-)
Хабр, кстати, не так уж и плох в смысл нишевых статей. Здесь очень широкий охват публики, весь бывший СССР. Лайков, может, и не наберете, но несколько интересных человек на статью обычно отзывается, это исходя из моего опыта.
Главное — не читать первые пять комментариев от случайных прохожих :-)
Это-то и хорошо, что он много чего делает с IR. К тому же, можно рулить тем, что делать, а что не делать. Потом, можно допилить, если он чего-то делает не так. Как сам LLVM, так и сделать свой LLVM pass.
На чистом асме было бы, конечно, здорово. Однако интерпретатор довольно большой и сложный. К тому же у нас три разных архитектуры, умножьте на два для 32-бит версий и вот уже слишком дофига кода.
В случае с LLVM IR — это и есть тот самый портативный асм, и весь код интерпретатора в одном месте.
Что не получилось, так это заставить LLVM использовать %rsp. Почему, потому что сама концепция LLVM не подразумевает использование понятия «стек» и в IR нет вещей для явной работы со стеком (за исключением пары интринсиков, добавленных по просьбам трудящихся). К тому же, в реализациях для платформ стековый регистр настолько прибит гвоздями, что оторвать его — очень трудоёмкая задача.
На чистом асме было бы, конечно, здорово. Однако интерпретатор довольно большой и сложный. К тому же у нас три разных архитектуры, умножьте на два для 32-бит версий и вот уже слишком дофига кода.
В случае с LLVM IR — это и есть тот самый портативный асм, и весь код интерпретатора в одном месте.
Что не получилось, так это заставить LLVM использовать %rsp. Почему, потому что сама концепция LLVM не подразумевает использование понятия «стек» и в IR нет вещей для явной работы со стеком (за исключением пары интринсиков, добавленных по просьбам трудящихся). К тому же, в реализациях для платформ стековый регистр настолько прибит гвоздями, что оторвать его — очень трудоёмкая задача.
Вы уже несколько раз упоминали, что не вышло использовать хардварный стек. Но, насколько мне известно, сейчас его использование уже вышло из моды, не так ли? Это вроде как архаизм на x86, оставшийся еще с 70-х.
Почему не регистровая, например, виртуальная машина..? Необходимость оптимизировать стек отпадает сама собой, а вопрос оптимизации становится вопросом аллокации регистров.
Я могу привести пару интересных публикаций на тему преимуществ регистровых машин, но вы и так, наверное, в курсе.
PS впрочем, видел и публикации про «отсталось» шитого кода, примеры из которых почему-то на практике не оказались быстрее.
Почему не регистровая, например, виртуальная машина..? Необходимость оптимизировать стек отпадает сама собой, а вопрос оптимизации становится вопросом аллокации регистров.
Я могу привести пару интересных публикаций на тему преимуществ регистровых машин, но вы и так, наверное, в курсе.
PS впрочем, видел и публикации про «отсталось» шитого кода, примеры из которых почему-то на практике не оказались быстрее.
Увы, в архитектуре особенно не разгуляешься. Например, обратная совместимость, так её разэтак — в общем, там всё сложно.
обратная совместимость — вечное проклятие :-)
Спасибо большое. Я никогда не думал про itermediate languages в роли портативных ассемблеров. Соберусь силами, видимо, этой зимой, и попробую еще немного побаловаться с Поросенком на предмет вещей, которые мне тут в комментах и личных сообщениях насоветовали.
Опять же, надо будет эксперименты и выводы как-нибудь внятно изложить в репозе на Гитхабе на английском, чтоб доступно всем желающим и интересующимся были, а не только на Хабре.
Любопытно, например, можно ли что-то подобное с libjit вытворить. Это, конечно, не LLVM, но, с другой стороны, либа намного проще и у меня с ней давние и довольно теплые отношения.
Спасибо большое. Я никогда не думал про itermediate languages в роли портативных ассемблеров. Соберусь силами, видимо, этой зимой, и попробую еще немного побаловаться с Поросенком на предмет вещей, которые мне тут в комментах и личных сообщениях насоветовали.
Опять же, надо будет эксперименты и выводы как-нибудь внятно изложить в репозе на Гитхабе на английском, чтоб доступно всем желающим и интересующимся были, а не только на Хабре.
Любопытно, например, можно ли что-то подобное с libjit вытворить. Это, конечно, не LLVM, но, с другой стороны, либа намного проще и у меня с ней давние и довольно теплые отношения.
Да не за что. Будут вопросы — обращайтесь. А я попробую выделить время на статью.
libjit я рассматривал, но у меня от него тогда остались какие-то противоречивые ощущения. Может, сейчас что-то там изменилось, давно не заглядывал.
самая большая проблема, пожалуй, это то, что сейчас мейнтейнер Алексей Демаков (https://demakov.com/projects/index.html#libjit) немного подзапустил либу, хотя еще буквально полгода назад он очень активно отвечал на вопросы, скажем, Eli Benderski (eli.thegreenplace.net/) или tom tromey (http://tromey.com).
Всякое бывает, но сейчас для этого очень неудачное время :-(
Сейчас на libjit, например, сделали новый аллокатор регистров и плюс еще патчи полезные прислали. Для емакса Том сделал jit, что автоматом к либе внимание привлекло…
Всякое бывает, но сейчас для этого очень неудачное время :-(
Сейчас на libjit, например, сделали новый аллокатор регистров и плюс еще патчи полезные прислали. Для емакса Том сделал jit, что автоматом к либе внимание привлекло…
я так понимаю, что вы на LLVM еще и jit делаете, верно?
И да и нет. Была попытка сделать jit-компиляцию при помощи LLVM, но компиляция получилась настолько медленной, что выигрыш в производительности нивелируется временем на разогрев. Поэтому пока этот проект отложен и скорее всего будет продолжен уже как AOT-компилятор либо как second tier для templated jit.
Плюс рассматривается возможность применения JitBuilder/OMR от J9 — это вообще родственная душа. :)
Плюс рассматривается возможность применения JitBuilder/OMR от J9 — это вообще родственная душа. :)
:-) Могу подтвердить, что это jit зачастую не оправдывается себя, особенно для программ с коротким жизненным циклом.
Я пробовал на libjit делать компиляцию «трасс» для ПоросенокВМ, лишнюю неделю-две времени убил, но результат был хуже даже обычного свитча. Материал решил не включать в статью — чтобы не позориться :-)
Может, однажды переосмыслю подход (в пользу шаблонного jit) и попробую еще раз, но пока грамотный jit у меня не вышел.
Я пробовал на libjit делать компиляцию «трасс» для ПоросенокВМ, лишнюю неделю-две времени убил, но результат был хуже даже обычного свитча. Материал решил не включать в статью — чтобы не позориться :-)
Может, однажды переосмыслю подход (в пользу шаблонного jit) и попробую еще раз, но пока грамотный jit у меня не вышел.
Вопрос: может я просмотрел в статье, вы Поросёнка для себя как академический проект делаете или это отражение вашей работы?
Есть еще первая часть статьи, где я немного писал об этом.
Интерес, скажем так, полупрофессиональный. Мне в одном проекте понадобился интепретатор байт-кода для очень специализированных регулярных выражений. От обычных регулярок это отличвается тем, что искать надо заданные последовательности в потоке событий, а не символов.
И тут случился отпуск довольно большой. На море бывает скучно ничего не делать, ну я и решил ознакомиться с разными аспектами интерпретатороделания. За месяц перечитал все, что нашел на Google Scholar на эту тему, понапробвал всякого в коде…
А серия статей позволяет немного структурировать все в голове на будущее и побеседовать с людьми, прями или косвенно с этими вещами связанными.
Интерес, скажем так, полупрофессиональный. Мне в одном проекте понадобился интепретатор байт-кода для очень специализированных регулярных выражений. От обычных регулярок это отличвается тем, что искать надо заданные последовательности в потоке событий, а не символов.
И тут случился отпуск довольно большой. На море бывает скучно ничего не делать, ну я и решил ознакомиться с разными аспектами интерпретатороделания. За месяц перечитал все, что нашел на Google Scholar на эту тему, понапробвал всякого в коде…
А серия статей позволяет немного структурировать все в голове на будущее и побеседовать с людьми, прями или косвенно с этими вещами связанными.
Смотрите, какую я книгу (на русском языке!) нашел случайно: iscalare.mipt.ru/materials/course_materials/simulation-lectures-2nd-edition
Обратите внимание на раздел «Модели процессора на основе интерпретации».
Обратите внимание на раздел «Модели процессора на основе интерпретации».
HTTP Status 404 -
The requested resource () is not available.
У меня ссылка работает. Попробуйте через страничку скачать: iscalare.mipt.ru/materials/course_materials
Даже просто поддомен не открывается. Вероятно, оно доступно только для сотрудников или обучающихся в МФТИ.
Нет, я успешно открыл.
Переложил на какой-то PDF-хостинг: www.scribd.com/document/393618832/Simulation-Lectures-2nd-Edition
Ага, спасибо. Уже скачал по ссылке, любезно размещённой MaxVetrov'ым в комментарии ниже. Кстати, проверил сейчас опять изначальную ссылку — уже открывается, видимо, был какой-то кратковременный сбой на сервере.
НЛО прилетело и опубликовало эту надпись здесь
Ух ты, очень, очень интересно. На эмуляторы вообще стоит поглядывать, в них встречаются очень любопытные техники. Трассы, например, для ПоросенокВМ я подсмотрел в эмуляторе Bochs.
Как вы на эти лекции наткнулись?
Как вы на эти лекции наткнулись?
Глянул по дороге на работе первые 50 стр. Разогрев долгий, т.е. автор очень разжевывает информацию. Не научна публикация, да :-)
Там дальше лучше..?
Там дальше лучше..?
На мой взгляд полезной информации там не так много, очень компактно. Для методического пособия в самый раз, хотя после него создается ощущение недосказанности.
Ну, мой интерес — техники интерпретации и, может быть, что-нибудь по двоичной трансляции. Если будут хотя бы интересные ссылки на публикации, то уже нормально.
Кстати, мы же с вами про дебаггер говорили? Я вас совсем неправильно понял тогда.
В общем, я редко gdb использую. Конкретно интерпретаторы я обычно обкладываю со всех сторон тестами, предельно подробно. Сначала обычный интерпретатор, потом рядом вставлю тесты для jit-кода. Результаты выполнения последнего должны точно соответствовать обычной интерпретации.
Выходит, что во время разработки я как бы с тестами работаю по большей части работаю, а т.к. тесты у меня на работу каждой инструкции есть, то и в случае ошибок обычно более-менее ясно, куда надо бы посмотреть.
В общем, я редко gdb использую. Конкретно интерпретаторы я обычно обкладываю со всех сторон тестами, предельно подробно. Сначала обычный интерпретатор, потом рядом вставлю тесты для jit-кода. Результаты выполнения последнего должны точно соответствовать обычной интерпретации.
Выходит, что во время разработки я как бы с тестами работаю по большей части работаю, а т.к. тесты у меня на работу каждой инструкции есть, то и в случае ошибок обычно более-менее ясно, куда надо бы посмотреть.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Полёт свиньи, или Оптимизация интерпретаторов байт-кода