Comments 107
Спасибо за статью! Можете рассказать почему решили делать свой байткод а не интерпритатор без компиляции?
Мы сейчас делаем что-то вроде специализированного движка регулярных выражений. В байт-коде это в разы легче будет сделать — смотрите последний пример, это сильно упрощенная версия.
В байт-коде легче отвязать всякий синтаксический мусор от того, что реального происходит за кадром.
Ну и… Работает значительно быстрее.
В байт-коде легче отвязать всякий синтаксический мусор от того, что реального происходит за кадром.
Ну и… Работает значительно быстрее.
Виртуальную машину будете свою реализовывать? Если да, то смотрели ли в сторону готовых GraalVM либо LLVM ?
Подождите-подождите…
При чем здесь GraalVM или LLVM? У нас относительно небольшой движок регулярных выражений, а не новый язык программирования, упаси боже. Использоваться он будет использоваться в контексте, о котором я расскажу, вероятно, в другой статье.
Регулярные выражения будут компилироваться в байт-код, который будет интерпретироваться маленькой виртуальной машинкой. Последняя — часть специализированной поисковой системы, пока еще только находящейся на этапе работающего прототипа.
При чем здесь GraalVM или LLVM? У нас относительно небольшой движок регулярных выражений, а не новый язык программирования, упаси боже. Использоваться он будет использоваться в контексте, о котором я расскажу, вероятно, в другой статье.
Регулярные выражения будут компилироваться в байт-код, который будет интерпретироваться маленькой виртуальной машинкой. Последняя — часть специализированной поисковой системы, пока еще только находящейся на этапе работающего прототипа.
У LLVM низкий порог вхождения, есть оптимизатор, интерпретатор и JIT. Это лучше велосипедов даже для не очень больших проектов, мне кажется.
От статьи больше вреда, чем пользы.
Вы предлагаете включать LLVM в проект ради десятка-двух операций над строкой интов..?
Я понимаю интерес, например, PostgreSQL, которые ведут борьбу за любые проценты при вычислении выражений в запросах, но в данном проекте это смысла не имеет точно.
А когда смысл начнет иметь, то, признаться, я все равно бы взял что-то чуть более легковесное, вроде замечательной libjit.
Обратите внимание, статья о том, как виртуальные машины устроены, а не о том, какой just-in-time компилятор стоит использовать.
Я понимаю интерес, например, PostgreSQL, которые ведут борьбу за любые проценты при вычислении выражений в запросах, но в данном проекте это смысла не имеет точно.
А когда смысл начнет иметь, то, признаться, я все равно бы взял что-то чуть более легковесное, вроде замечательной libjit.
Обратите внимание, статья о том, как виртуальные машины устроены, а не о том, какой just-in-time компилятор стоит использовать.
Я могу переформулировать свой вопрос.
Было интересно почему вы решили писать свою виртуальную машину а не взять готовую, поэтому и вспомнил LLVM и GraalVM которые должны, в моем представлении, помогать в таких случаях.
В nginx тоже своя легкая вм для реврайтов. Насколько я понял, здесь требуется высокая скорость создания контекста и низкое потребление памяти вкупе с приемлемой производительностью. Разве LLVM/GraalVM здесь подойдет?
Мне нужно просто выполнять легкие и простенькие запросы. Маленькая виртуальная машинка в таких случаях — практически стандартное решение. Такие машинки есть в ядре Линукса, SQLite и т.д.
LLVM это вообще не виртуальная машина в традиционном смысле слова, а фреймворк — и очень хороший фреймворк! — для компиляции промежуточного представления кода в нативный код. В сравнении с бэкэндом GCC сам фреймворк действительно проще. Но объективно это огромный проект в сотни тысяч строк, использовать который не так уж и дешево в смысле времени и нервов.
GraalVM это дальнейшая эволюция JVM. Мне даже страшно думать о том, чтобы мои 500-1000 строк кода заменять на JVM-подобную махину.
Приведенные же в статье примеры — маленькие машинки.
LLVM это вообще не виртуальная машина в традиционном смысле слова, а фреймворк — и очень хороший фреймворк! — для компиляции промежуточного представления кода в нативный код. В сравнении с бэкэндом GCC сам фреймворк действительно проще. Но объективно это огромный проект в сотни тысяч строк, использовать который не так уж и дешево в смысле времени и нервов.
GraalVM это дальнейшая эволюция JVM. Мне даже страшно думать о том, чтобы мои 500-1000 строк кода заменять на JVM-подобную махину.
Приведенные же в статье примеры — маленькие машинки.
Такие машинки есть в ядре Линукса,
Можете поделиться ссылкой? очень интересно почитать.
Например, вот эта. И еще одна с недавних пор появилась, не помню, как называется.
Спасибо, ради этого ответа я вас и мучал вопросами, не знал просто как лучше спросить.
А не знаете случаем легковесного компилятора си в байткод с интерпретатором. Именно легковесного, чтобы интерпретатор влез на микроконтроллер (компилятор не обязательно).
Кое-что в голову приходит.
Прежде чем я почешу голову и залезу в старые заметки, можно вопрос? А почему именно интерпретатор, а не просто какой-нибудь маленький компилятор в бинарный код для микроконтроллера?
Прежде чем я почешу голову и залезу в старые заметки, можно вопрос? А почему именно интерпретатор, а не просто какой-нибудь маленький компилятор в бинарный код для микроконтроллера?
Уже использую picoc как просто интерпретатор. Проблема в том, что если встроить его, скажем, в плеер некого формата, то развитие и фиксы багов приведут к несовместимости версий плееров. Отладить 1 раз байткод-интерпретатор, встраивать в формат именно байт-код, а потом спокойно доводить компилятор видится проще.
github.com/jnz/q3vm
У них был вроде еще один, проще. Компилятор основан на LCC.
Собственно, LCC можно переделать под любую виртуальную машину. Бэкэнды там делаются легко, виртуальную машину тоже возможно наклепать.
Но я бы взял готовую, ту, что выше.
У них был вроде еще один, проще. Компилятор основан на LCC.
Собственно, LCC можно переделать под любую виртуальную машину. Бэкэнды там делаются легко, виртуальную машину тоже возможно наклепать.
Но я бы взял готовую, ту, что выше.
Кстати, ваш picoc тоже, думаю, должно быть очень легко портировать на вашу же гипотетическую виртуальную машинку. Кода там мало, и он хороший.
Да, код хороший. С ним больше проблема что он далеко не полный стандарт си понимает, потому и хотел посмотреть что еще есть. Да и не нужен строковый парсер в самом плеере, вм достаточно.
Надо будет мне глянуть этот picoc, интересно, как они так лаконично все сделали.
tcc смотрели?
Да, изначально именно его и использовал, привлекает то что у него есть JIT. Но у него нашлись баги, mob бранч сломан, там фактически нет того, кто принимает и проверяет патчи. Я даже находил коммит который сломал, но починить самостоятельно за обозримое время не смог, код уже довольно запутанный. Есть еще про проблемы — он не виртуализирует #include, мне пришлось переделывать/вырезать всю работу с FILE и код разошелся с апстримом. Кроме того опять же нет возможности сделать JIT готового откомпилированного байт-кода (или просто его исполнить, для платформ где JIT не поддерживается).
Присмотритесь к pawn. Си подобный. Есть отладка через последовательный порт. Сам использую на микроконтроллерах и очень доволен.
Байт-код, это виртуальная машина. Виртуальная машина, это виртуальная архитектура. Архитектура должна по меньшей мере отвечать каким-то потребностям. Просто «перегонять» программу в байт-код, занятие… так себе. С таким же успехом можно просто взять за байткод команды процессора, ну например, х86, и исполнять их собственным двиглом, добавив блекджек и… Собственно как-то так работают эмуляторы. При этом хотя бы архитектура будет внятной и документированной. Не говоря уже о компиляторах. Можно будет использовать даже C/С++.
Интерпретационные языки, чем замечательны, так это тем, что не сводят сложные функции и синтаксис к байт-коду. Интерпретатор интерпритирует код, используя оптимизированный код для конкретной платформы. Да, бывает так, что парсер сначала переводит файл со скриптом в оптимизированную форму (p-код) для последующей ускоренной интерпритации. Но это совсем иное, чем компиляция в байт-код. Как минимум, такое упрощение чаще всего обратимо, а концепция интерпретатора не нарушается.
В общем, все здорово, но не ясно зачем это, если не ответить на ключевой вопрос — какие задачи будет решать виртуальная машина и какую архитектуру при этом будет иметь.
Интерпретационные языки, чем замечательны, так это тем, что не сводят сложные функции и синтаксис к байт-коду. Интерпретатор интерпритирует код, используя оптимизированный код для конкретной платформы. Да, бывает так, что парсер сначала переводит файл со скриптом в оптимизированную форму (p-код) для последующей ускоренной интерпритации. Но это совсем иное, чем компиляция в байт-код. Как минимум, такое упрощение чаще всего обратимо, а концепция интерпретатора не нарушается.
В общем, все здорово, но не ясно зачем это, если не ответить на ключевой вопрос — какие задачи будет решать виртуальная машина и какую архитектуру при этом будет иметь.
Сводят. Все современные интерпретируемым языки типа Python, Java — сводят, и ещё как! Есть лексер-парсер-транслятор в байт-код, и есть собственно какой-нибудь CPython, который этот байт-код выполняет.
У функций в питоне можно в runtime посмотреть (а на самом деле даже и создать функцию из байт-кода) байт-код функции через объект func.code
Вы все правильно сказали: просто так делать байт-код не надо.
Интерпретаторы байт-кодов — техника, которая может быть к месту, а может быть не к месту. Вероятные причины применения байт-кодов я указал, их много.
Насчет «совсем иное, чем компиляция в байт-код» и компиляции я вас не понял, возможно, либо мне, либо вам надо определения глянуть.
«Обратимость». Характерный байт-код языков программирования сильно теряет по сравнению с самим языком, и именно поэтому его легче выполнять интерпретатору, т.к. в нем меньше всяких деталей. Машинный код по сравнению с языком Си, например, очень сильно теряет в выразительности и подробностях. Что вы имеете в виду, когда говорите, что «оно чаще всего обратимо»?
Интерпретаторы байт-кодов — техника, которая может быть к месту, а может быть не к месту. Вероятные причины применения байт-кодов я указал, их много.
Насчет «совсем иное, чем компиляция в байт-код» и компиляции я вас не понял, возможно, либо мне, либо вам надо определения глянуть.
«Обратимость». Характерный байт-код языков программирования сильно теряет по сравнению с самим языком, и именно поэтому его легче выполнять интерпретатору, т.к. в нем меньше всяких деталей. Машинный код по сравнению с языком Си, например, очень сильно теряет в выразительности и подробностях. Что вы имеете в виду, когда говорите, что «оно чаще всего обратимо»?
p-код, кстати, как раз таки и является байт-кодом. Непонятно, чем так не угодили вм товарищу rpiontik )
ok. С терминологией, да, мегостранно. Моя школа разделяла понятие бат-кода и P-кода, теперь, это оказывается синонимы. Последую совету, но все же, думаю неспроста они по разному пишутся. Суть же такова:
— при трансляции в байт-код, происходит фактически компиляция, что с одной стороны позволяет использовать механизмы оптимизации, но с другой, устраняет саму суть языка из которого сгенерирован этот самый байт-код;
— при трансляции в P-код (в моем понимании), происходит кодирование синтаксиса языка. Ну к примеру, функция заменяется ее уникальным кодом, параметры кодируются в бинарное представление, а строковые константы оформляются ссылками в оптимизированную область памяти. При этом, обратная трансляция может восстановить исходный код. В этом случае синтаксис языка сохраняется даже на уровне интерпретации.
И если вариант 2 мне в целом понятен как «быстрое решение для простых задач». То вариант 1 мне кажется чрезмерным, т.к. требует больше телодвижений и должен быть оправдан уникальными свойствами виртуальной машины.
Надеюсь так яснее.
— при трансляции в байт-код, происходит фактически компиляция, что с одной стороны позволяет использовать механизмы оптимизации, но с другой, устраняет саму суть языка из которого сгенерирован этот самый байт-код;
— при трансляции в P-код (в моем понимании), происходит кодирование синтаксиса языка. Ну к примеру, функция заменяется ее уникальным кодом, параметры кодируются в бинарное представление, а строковые константы оформляются ссылками в оптимизированную область памяти. При этом, обратная трансляция может восстановить исходный код. В этом случае синтаксис языка сохраняется даже на уровне интерпретации.
И если вариант 2 мне в целом понятен как «быстрое решение для простых задач». То вариант 1 мне кажется чрезмерным, т.к. требует больше телодвижений и должен быть оправдан уникальными свойствами виртуальной машины.
Надеюсь так яснее.
В золотые времена Паскаля, когда использовался p-code (или portable code), терминология еще не устоялась, если судить по публикациям того времени. В понимании авторов термина p-код это код для абстрактной машины, который легко и выполнять, и компилировать в машинный код.
Я сомневаюсь, что тот p-код был вот прям очень высокоуровневым, и из него можно было полность исходный код восстановить.
Байт-код в современном понимании потому и используется, что его легко и генерировать, и интерпретировать. Вариант 1 на практике делается очень несложно. В примерах статьи я за часа три-четыре сделал 5(!) виртуальных машинок. Уверяю вас, компиляторы в коды для этих машин из несложных языков я сделаю каждый за те же полдня.
Более того, избавление от синтаксических деталей языка все только упрощает. Сложно добавить jit-компиляцию, это да, хотя и тут все сильно зависит от языка.
Конкретный пример из личного опыта.
Работал я как-то в одной игровой конторе, делающей популярную онлайн-игру. Игра состоит из матчей, в процессе и финале каждого из которых надо обсчитывать сотни мелких условий, типа кому медальку дать, кого оштрафовать и т.д.
Условия эти формируются гейм-дизайнерами в виде XML-описаний, или, если условия хитрые, пишутся программистами. Сначала мы компилировали XML в язык программирования (Питон), и вкладывали в проект. Но потом выяснилось, что дизы хотят другой формат, и хотят легко код подменять чуть ли не лету.
Так вот. За месяц работы одного программиста система была переделана на виртуальную машинку, понимающую байт-код. Логику условий можно было писать на чем угодно — специальном языке, XML или генерить прямиком при помощи GUI — и больше не трогать программистов. Опять же, байт-код легко подменить без перезапуска кластера…
Профит со всех сторон.
Я сомневаюсь, что тот p-код был вот прям очень высокоуровневым, и из него можно было полность исходный код восстановить.
Байт-код в современном понимании потому и используется, что его легко и генерировать, и интерпретировать. Вариант 1 на практике делается очень несложно. В примерах статьи я за часа три-четыре сделал 5(!) виртуальных машинок. Уверяю вас, компиляторы в коды для этих машин из несложных языков я сделаю каждый за те же полдня.
Более того, избавление от синтаксических деталей языка все только упрощает. Сложно добавить jit-компиляцию, это да, хотя и тут все сильно зависит от языка.
Конкретный пример из личного опыта.
Работал я как-то в одной игровой конторе, делающей популярную онлайн-игру. Игра состоит из матчей, в процессе и финале каждого из которых надо обсчитывать сотни мелких условий, типа кому медальку дать, кого оштрафовать и т.д.
Условия эти формируются гейм-дизайнерами в виде XML-описаний, или, если условия хитрые, пишутся программистами. Сначала мы компилировали XML в язык программирования (Питон), и вкладывали в проект. Но потом выяснилось, что дизы хотят другой формат, и хотят легко код подменять чуть ли не лету.
Так вот. За месяц работы одного программиста система была переделана на виртуальную машинку, понимающую байт-код. Логику условий можно было писать на чем угодно — специальном языке, XML или генерить прямиком при помощи GUI — и больше не трогать программистов. Опять же, байт-код легко подменить без перезапуска кластера…
Профит со всех сторон.
Ну я все же пока радикально не утвердился в верности "новой" терминологии. Потрачу время на поиск "истины".
Со слов "это сделать просто", на моей памяти, начиналось оч много великов.
В остальном, посмотрим, по следующим статьям, чем же плохи остальные реализации и почему нужно ваять что-то свое.
Так вот. За месяц работы одного программиста система была переделана на виртуальную машинку, понимающую байт-код. Логику условий можно было писать на чем угодно — специальном языке, XML или генерить прямиком при помощи GUI — и больше не трогать программистов. Опять же, байт-код легко подменить без перезапуска кластера…
А в чем плюс по сравнению с иcпользованием, например, lua? А то месяц работы программиста — не очень много, но ощутимо.
Там ж большая система, а не сайтик для дяденьки :-) Месяц — нормальная единица планирования.
В общем-то, никто против Луа, или любого другого такого же языка программирования, ничего не имел. Дело было не том, что нужен был еще один язык, а в том, что была плюс минус-понятная абстрактная машина, в термины которогой надо было разные языки переводить.
В общем-то, никто против Луа, или любого другого такого же языка программирования, ничего не имел. Дело было не том, что нужен был еще один язык, а в том, что была плюс минус-понятная абстрактная машина, в термины которогой надо было разные языки переводить.
Ну, я к тому, что луа легковесный и легко встраивается. Я не агитирую, а просто интересно, в чем выигрыш использования своего байт-кода по сравнению с использованием распространенного языка.
Будь это большой проект на плюсах или простом Си, где надо было бы местами быстренько логику менять, то да, имело бы смысл встроить что-нибудь легковесное.
Но там и так логика на Питоне была, т.е. уже был простой язык. Задача была несколько другая: найти формат, куда можно компилировать разные мини-языки.
Но там и так логика на Питоне была, т.е. уже был простой язык. Задача была несколько другая: найти формат, куда можно компилировать разные мини-языки.
Но там и так логика на Питоне была, т.е. уже был простой язык. Задача была несколько другая: найти формат, куда можно компилировать разные мини-языки.
Знаете все равно не понятно, зачем следовало создавать виртуальную машину, когда можно было бы все в тот же питон перегонять.
Возможно какой-нибудь наглядный кейс из той задачи, дал бы некое прояснение)
1. С питоном надо было перезагружать кластер, со своим же байт-кодом можно делать что угодно.
2. В питон трудно компилировать.
3. Питон — и его программы — слишком много чего умеет, а в собственной виртуалке можно строго ограничить возможности програамы.
По схожим причинам опен-сорсная игра Battle for Wesnoth в свое время убрала возможность скриптовать расширения на питоне в пользу собственного декларативного языка.
2. В питон трудно компилировать.
3. Питон — и его программы — слишком много чего умеет, а в собственной виртуалке можно строго ограничить возможности програамы.
По схожим причинам опен-сорсная игра Battle for Wesnoth в свое время убрала возможность скриптовать расширения на питоне в пользу собственного декларативного языка.
UFO just landed and posted this here
С презентации Java Virtual Machine во второй половине 90-х прошло уже достаточно много времени, и можно с уверенностью сказать, что интерпретаторы байт-кодов — не будущее, а настоящее.
В 90-х это была новинка, в 2000-х настоящее а сейчас это уже прошлое. Настоящее — jit-компиляторы.
Я вас удивлю, возможно, но интерпретаторы байт-кодов ортогональны just-in-time компиляции. С выполнением исключительно jit-компилированного кода (в динамических языках так точно) закончили к концу девяностых по целому ряду причин. Могу углубиться в детали, если интересно.
Обычно есть основной интерпретатор, начинающий работать сходу, и сбоку отдельный jit-компилятор, так или иначе выделяющий куски байт-кода, которые имеет смысл подменить на лету на машинный код.
Если уж на то пошло, то последнее веяние — мета-трейсинг в стиле того, что делает проект PyPy в своем RPython. Вот здесь обзорный пост гляньте.
Обычно есть основной интерпретатор, начинающий работать сходу, и сбоку отдельный jit-компилятор, так или иначе выделяющий куски байт-кода, которые имеет смысл подменить на лету на машинный код.
Если уж на то пошло, то последнее веяние — мета-трейсинг в стиле того, что делает проект PyPy в своем RPython. Вот здесь обзорный пост гляньте.
Есть ещё такая интересная штука, как специализация языков, и с помощью нее из интерпретатора и специализированные можно комплилятор получить)
> С выполнением исключительно jit-компилированного кода (в динамических языках так точно) закончили к концу девяностых по целому ряду причин.
Насколько я в курсе, дотнет сделан именно так: «основной интерпретатор» вообще не существует, любая функция (метод) переводится в JIT по первому использованию, но может быть обновлена потом. Во всяком случае, в книгах пишется именно так. А он только начинался в девяностых.
Прошу уточнить: это книги врут, или вы имеете в виду что-то немного другое?
> Могу углубиться в детали, если интересно.
Да, интересно.
Насколько я в курсе, дотнет сделан именно так: «основной интерпретатор» вообще не существует, любая функция (метод) переводится в JIT по первому использованию, но может быть обновлена потом. Во всяком случае, в книгах пишется именно так. А он только начинался в девяностых.
Прошу уточнить: это книги врут, или вы имеете в виду что-то немного другое?
> Могу углубиться в детали, если интересно.
Да, интересно.
Признаться, конкретно про .NET я мало что знаю. Но про Smalltalk/SELF, JVM, luajit, PyPy, разные реализации JS читал ключевые работы авторов.
История выглядит так, насколько помню сходу:
1. Сначала (8о-е, 90-е, начало нулевых) получили распространение интерпретаторы с jit-ом, предварительно компилировавшим весь код (Smalltalk/SELF, JVM) метод за методом по мере работы программы.
В среднем такой код работал быстро, но долго разогревался, т.е. первое время ощутимо тупил т.к. каждый метод во время первого вызова сначала нужно скомпилировать. Для разовых запусков методов это часто выходило медленней, чем просто чтение байт-кода. Проблему решали по-разному, но в итоге пришли к другой модели.
2. Стали (JVM, ранние jit в Джаваскрипте, т.е. середина нулевых) делать так: код интерпретируется, но помечаются «горячие» методы, которые потом и компилируются тяжелым комплилятором.
3. Появились (поздние нулевые, Firefox, luajit, PyPy) трассирующие jit-компиляторы, которые ищут «горячие» циклы и компилируют именно их, сначала же все работает с простого интерпретатора.
4. Наши дни. Самые развитые виртуальные (Firefox, V8) машины имеют несколько уровней компиляции. Базовый — байткод, потом «легкий» компилятор и для самых «горячих» методов/трасс — тяжелый компилятор. Код подменяется на лету, по мере сбора статистики.
5. Совсем последние новости: трассирующие jit-компиляторы выходят из моды.
Конечно, в менее крупных проектах такое зверство — каскад компиляторов — малополезно и очень трудоемко, и используется метод, указанный вами: предкомпиляция всех вызываемых методов.
Надеюсь, утолил ваше любопытство :-) Опять же, деталей не знаю, но могу предполжить, что .NET прошел схожие этапы в развитии.
История выглядит так, насколько помню сходу:
1. Сначала (8о-е, 90-е, начало нулевых) получили распространение интерпретаторы с jit-ом, предварительно компилировавшим весь код (Smalltalk/SELF, JVM) метод за методом по мере работы программы.
В среднем такой код работал быстро, но долго разогревался, т.е. первое время ощутимо тупил т.к. каждый метод во время первого вызова сначала нужно скомпилировать. Для разовых запусков методов это часто выходило медленней, чем просто чтение байт-кода. Проблему решали по-разному, но в итоге пришли к другой модели.
2. Стали (JVM, ранние jit в Джаваскрипте, т.е. середина нулевых) делать так: код интерпретируется, но помечаются «горячие» методы, которые потом и компилируются тяжелым комплилятором.
3. Появились (поздние нулевые, Firefox, luajit, PyPy) трассирующие jit-компиляторы, которые ищут «горячие» циклы и компилируют именно их, сначала же все работает с простого интерпретатора.
4. Наши дни. Самые развитые виртуальные (Firefox, V8) машины имеют несколько уровней компиляции. Базовый — байткод, потом «легкий» компилятор и для самых «горячих» методов/трасс — тяжелый компилятор. Код подменяется на лету, по мере сбора статистики.
5. Совсем последние новости: трассирующие jit-компиляторы выходят из моды.
Конечно, в менее крупных проектах такое зверство — каскад компиляторов — малополезно и очень трудоемко, и используется метод, указанный вами: предкомпиляция всех вызываемых методов.
Надеюсь, утолил ваше любопытство :-) Опять же, деталей не знаю, но могу предполжить, что .NET прошел схожие этапы в развитии.
Как в микроконтроллер воткнуть jit-компилятор?
Зачем?
чтобы JS исполнять
mjs берите. Он заточен для контроллеров.
Дальше было бы интересно почитать про JIT и про трансляцию байт-кода в машинный :)
Ох, про jit рассказать можно, но там много кода, или библиотек, а мне хотелось бы делать что-то с конкретными примерами без внешних зависимостей и легко портируемое.
Думаю, следующий пост будет про те вещи, которые можно сделать в рамках простого Си и трех сотен строк. Уверяю вас, кой-какие приемы неплохо работают и по старинке, без непосредственно руками вбитого машинного кода :-)
Думаю, следующий пост будет про те вещи, которые можно сделать в рамках простого Си и трех сотен строк. Уверяю вас, кой-какие приемы неплохо работают и по старинке, без непосредственно руками вбитого машинного кода :-)
Да, я понимаю, что в JIT очень много кода. Мои эксперименты с JIT с ипользованием библиотек показали, что овчинка выделки не стоит. Если вы занимались этой темой, было бы интересно почитать про ваш опыт, без погружения в код…
Неплохо — это хорошо, но не великолепно ;)
Неплохо — это хорошо, но не великолепно ;)
Скажем так, jit игрушечный я делал, и некоторые из ключевых исследований читал. В бою не пригодилось. Причины:
1. Красиво и эффективно сделать jit-компиляцию сложно.
Я тут где-то писал, что, например, для Емакса уже было несколько попыток, но выхлоп был очень слабый. Разработчики PostgreSQL, недавно внедрившие llvm-jit, хвастаются, что скорость увеличилась на 10-15% в подходящих случаях. Для них это много, но я могу убиться об стену, но начальству не смогу продать два-три месяца разработки ради такой разницы.
2. Применимость в бытовом программировании маленькая.
Задачи такие встречаются редко, и они далеко всегда критичны.
Другое дело, что если не уметь делать, то и не пригодится никогда. По себе и своим коллегам знаю :-) Бывало и так: «Нормально, что мы в кластере молотим данные десять минут», когда я на одной машине за секунды делаю.
А вот простенький интерпретатор действительно раза три был очень нужен.
1. Красиво и эффективно сделать jit-компиляцию сложно.
Я тут где-то писал, что, например, для Емакса уже было несколько попыток, но выхлоп был очень слабый. Разработчики PostgreSQL, недавно внедрившие llvm-jit, хвастаются, что скорость увеличилась на 10-15% в подходящих случаях. Для них это много, но я могу убиться об стену, но начальству не смогу продать два-три месяца разработки ради такой разницы.
2. Применимость в бытовом программировании маленькая.
Задачи такие встречаются редко, и они далеко всегда критичны.
Другое дело, что если не уметь делать, то и не пригодится никогда. По себе и своим коллегам знаю :-) Бывало и так: «Нормально, что мы в кластере молотим данные десять минут», когда я на одной машине за секунды делаю.
А вот простенький интерпретатор действительно раза три был очень нужен.
«С презентации Java Virtual Machine во второй половине 90-х прошло уже достаточно много времени, и можно с уверенностью сказать, что интерпретаторы байт-кодов — не будущее, а настоящее»
Словно бы мы говорим не о 90-х, а о 60-х годах! В 60-е годы языковые ВМ только развивались и за их использование еще нужно было кого-то агитировать. К середине 70-х такие решения уже окончательно стали частью арсенала рядовых разработчиков. Можно вспомнить, например, статью J. Bell «Threaded Code» (1973) или учебник Вирта «Алгоритмы + структуры данных = программы» (1976), где был описан интерпретатор ВМ PL/0.
Вспомните также многочисленные игры конца 70-х и начала 80-х со встроенным интерпретатором байткода. Вспомните опередившую свое время систему Visi On. А уже в 80-х использованием языковой ВМ уже никого нельзя было удивить.
Исторический контекст важно учитывать и если у этой заметки будет продолжение на тему JIT, то нелишне будет и ознакомиться со статьей «A Brief History of Just-In-Time»: eecs.ucf.edu/~dcm/Teaching/COT4810-Spring2011/Literature/JustInTimeCompilation.pdf
Словно бы мы говорим не о 90-х, а о 60-х годах! В 60-е годы языковые ВМ только развивались и за их использование еще нужно было кого-то агитировать. К середине 70-х такие решения уже окончательно стали частью арсенала рядовых разработчиков. Можно вспомнить, например, статью J. Bell «Threaded Code» (1973) или учебник Вирта «Алгоритмы + структуры данных = программы» (1976), где был описан интерпретатор ВМ PL/0.
Вспомните также многочисленные игры конца 70-х и начала 80-х со встроенным интерпретатором байткода. Вспомните опередившую свое время систему Visi On. А уже в 80-х использованием языковой ВМ уже никого нельзя было удивить.
Исторический контекст важно учитывать и если у этой заметки будет продолжение на тему JIT, то нелишне будет и ознакомиться со статьей «A Brief History of Just-In-Time»: eecs.ucf.edu/~dcm/Teaching/COT4810-Spring2011/Literature/JustInTimeCompilation.pdf
Не только ее читал, но и изрядную долю статей в библиографии :-) Это лучший обзор на тему. Плюс вам в карму за упоминание.
И совершенно согласен с вами насчет того, что и виртуальные машины, и компиляция на лету (aka jit) — технологии старые.
Помнится, известнейшая игра Another World была со встроенной виртуальной машиной; многие — почти все? — квесты от LucasGames использовали виртуальную машину. Infocom для своих текстовых игр тоже держали специальный движок с виртуальной машиной.
Однако же, средний потребитель софта до Джавы кушал именно программы, собранные из Си или Паскаля, компилировавшихся в машинный код.
И совершенно согласен с вами насчет того, что и виртуальные машины, и компиляция на лету (aka jit) — технологии старые.
Помнится, известнейшая игра Another World была со встроенной виртуальной машиной; многие — почти все? — квесты от LucasGames использовали виртуальную машину. Infocom для своих текстовых игр тоже держали специальный движок с виртуальной машиной.
Однако же, средний потребитель софта до Джавы кушал именно программы, собранные из Си или Паскаля, компилировавшихся в машинный код.
А знакомы ли Вы с системой META II (1964)? Такие известные личности, как Д. Кнут, А. Кэй или Д. Армстронг (автор Erlang) отзывались о META II очень положительно.
META II это генератор компиляторов, который написан на себе самом и порождает код для стековой VM. Оригинальная статья о META II в числе моих самых любимых: www.ibm-1401.info/Meta-II-schorre.pdf
P.S. Когда-то у меня была идея написать краткий вводный курс по компиляторам-интерпретаторам с разбором всего двух систем: META II и Forth.
META II это генератор компиляторов, который написан на себе самом и порождает код для стековой VM. Оригинальная статья о META II в числе моих самых любимых: www.ibm-1401.info/Meta-II-schorre.pdf
P.S. Когда-то у меня была идея написать краткий вводный курс по компиляторам-интерпретаторам с разбором всего двух систем: META II и Forth.
Гм. Нет, не знаком. Я за последние месяцы множество статей перепахал, в том числе и Форту, но сознательно раньше конца семидесятых уже не копал — надо ж где-то заканчивать. Я ж не преподаватель :-) Но внесту в очередь на прочтение, пока драйв и интерес есть.
Про Форт же, да, конечно. Я так понимаю, что по поводу быстрых интерпретаторов именно байт-кода все было сделано еще в 70-е. Почти все интересные работы 2000-х ссылаются на идею «шитого» кода именно на примере Форта.
Про Форт же, да, конечно. Я так понимаю, что по поводу быстрых интерпретаторов именно байт-кода все было сделано еще в 70-е. Почти все интересные работы 2000-х ссылаются на идею «шитого» кода именно на примере Форта.
Да, причем некоторые из этих древних техник до сих пор недоступны в рамках стандартного Си. В частности, в рамках интерпретатора шитого кода можно было бы избавиться от конструкции switch с применением вычислимого goto. Но такой вариант является использованием нестандартного gcc-расширения.
Поделюсь еще одной малоизвестной статьей. На сей раз достаточно свежей. Ее автор, В. Макаров (известный разработчик в gcc-сообществе) сравнивает регистровые и стековые ВМ, пишет о шитом коде и т.д. уже с современных позиций: arxiv.org/pdf/1604.01290.pdf
Поделюсь еще одной малоизвестной статьей. На сей раз достаточно свежей. Ее автор, В. Макаров (известный разработчик в gcc-сообществе) сравнивает регистровые и стековые ВМ, пишет о шитом коде и т.д. уже с современных позиций: arxiv.org/pdf/1604.01290.pdf
О, очень интересно, спасибо большое, сейчас прям и распечатаю. Эту прочитаю срочно!
Я как раз бился над вычисляемым goto в си, для того чтобы прыгнуть в нужное место раскрученного цикла и сравниться с ручным асмом. Оказалось это можно, примерно вот так:
Но от компилятора сильно зависит, нужны нестандартные расширения или нет. MSVC, например, нужно было default: __assume(0);, чтобы он понял что остальные варианты switch недоступны и range проверка не нужна.
int p = (n/8) & 7;
switch(p)
{
case 0: do { do_some_part_job;
case 7: do_some_part_job;
case 6: do_some_part_job;
case 5: do_some_part_job;
case 4: do_some_part_job;
case 3: do_some_part_job;
case 2: do_some_part_job;
case 1: do_some_part_job;
} while(--n > 0);
break;
}
Но от компилятора сильно зависит, нужны нестандартные расширения или нет. MSVC, например, нужно было default: __assume(0);, чтобы он понял что остальные варианты switch недоступны и range проверка не нужна.
Ну да :) Не замечал, чтобы были проблемы с портируемостью. Да и куда деваться, выигрыш был слишком существенен чтобы игнорировать, а вызов асм функции сбивает оптимизирующий компилятор еще больше + он не может переделать ей ABI, перемапить регистры итд. Так что хорошо еще что не на асме =)
Я пробовал rust еще, но на нем так же не получается догнать асм + у него пока нет alloca и другие проблемы.
Я пробовал rust еще, но на нем так же не получается догнать асм + у него пока нет alloca и другие проблемы.
Прочитал Макарова о его языке программировании и всяких техниках интерпретации.
Ну что ж. Джентельмен серьезный :-)
Выжимка для самого себя по поводу статьи:
1. Уже не так важно, как именно оформлен главный цикл интерпретатора.
2. Правильная регистровая машина может быть в разы быстрее стековой.
3. Возможно быстро и легко сделать портативный jit-компилятор.
4. Чем меньше работает диспетчер — тем лучше; «склеивать» инструкции хорошо.
5. Дальнейшие улучшения идут за счет техник, специфичных для динамических языков.
Вообще, у него там совсем маньячный подход, т.е. он действительно много приемов использует.
Ну что ж. Джентельмен серьезный :-)
Выжимка для самого себя по поводу статьи:
1. Уже не так важно, как именно оформлен главный цикл интерпретатора.
2. Правильная регистровая машина может быть в разы быстрее стековой.
3. Возможно быстро и легко сделать портативный jit-компилятор.
4. Чем меньше работает диспетчер — тем лучше; «склеивать» инструкции хорошо.
5. Дальнейшие улучшения идут за счет техник, специфичных для динамических языков.
Вообще, у него там совсем маньячный подход, т.е. он действительно много приемов использует.
В работах Чарльза Мура(создателя Forth-а) где-то в конце 2000-х был интересный быстрый компилятор стекового языка colorForth, там были и исходники.
Сам язык и система программирования для него — довольно авангардные и необычные.
Настолько, что статьи и описания идей не многим удалось понять — отворачивались раньше, т.к. новизны было слишком много и слишком уж радикальные решения. Смею думать, несколько идей я уловил, и они мне очень понравились. Давно уже хочу об этом пару статей написать…
Я переработал идеи, но за несколько редких подходов законченной реализации нет. Сейчас думаю сделать очередной подход…
Вот тут о Мете еще интереснее: www.bayfronttechnologies.com/mc_tutorial.html
Исполнение прямо в браузере плюс подробное руководство, как расширить метакомпилятор
Исполнение прямо в браузере плюс подробное руководство, как расширить метакомпилятор
Да, это хорошее руководство. Кстати, для любого интересующегося программиста посоветую полезное упражнение: реализовать META II на вашем любимом языке. Так, чтобы код системой порождался для вашего же языка.
А вот еще замечательная статья, которую Вы, возможно, не видели: www.vpri.org/pdf/tr2010003_PEG.pdf
Ian Piumarta — один из разработчиков, участвовавших в проекте STEPS Алана Кэя. И его система из статьи мне нравится своим изяществом значительно больше, чем известная oMeta.
Кстати, один из вариантов META II использовался для создания знаменитой «The Mother of All Demos» (1968). И примечателен сам подход: создание сложной системы в нотациях множества DSL. Только в те времена их называли SPL — special purpose languages. Воистину, новое — хорошо забытое старое.
А вот еще замечательная статья, которую Вы, возможно, не видели: www.vpri.org/pdf/tr2010003_PEG.pdf
Ian Piumarta — один из разработчиков, участвовавших в проекте STEPS Алана Кэя. И его система из статьи мне нравится своим изяществом значительно больше, чем известная oMeta.
Кстати, один из вариантов META II использовался для создания знаменитой «The Mother of All Demos» (1968). И примечателен сам подход: создание сложной системы в нотациях множества DSL. Только в те времена их называли SPL — special purpose languages. Воистину, новое — хорошо забытое старое.
А
главная функция с assert-ами
где?
В коде на Гитхабе, там в самом начале ссылка есть. Полные листинги с тестами очень длинные выходили.
Возможно, не стоило их здесь упоминать. :-)
Возможно, не стоило их здесь упоминать. :-)
Сколько процентов проигрывает стековая машина нативному коду?
Сколько процентов проигрывает регистровая?
Сколько процентов проигрывает регистровая?
А это смотря как сделать.
Эти примеры будут, конечно, раз в сто медленней. Там ж на полезную нагрузку каждой инструкции (скажем, операции сложения) еще есть декодер инструкции, диспетчер инструкций, работа со стеком… Наугад можно сказать, что сверху десяток машинных инструкций плюс проблемы предсказателя переходов.
Это если машина низкоуровневая, в машинах языков высокого уровня всяких дополнительных затрат еще поболее будет: динамическая типизация, позднее связывание и все такое.
Всякие там дополнительные приемы могут эти затраты снизить с 10-20 инструкций на один байт-код в среднем до 5-10 в самых быстрых из языков с виртуальной машиной. Это я так, не считая.
Эти примеры будут, конечно, раз в сто медленней. Там ж на полезную нагрузку каждой инструкции (скажем, операции сложения) еще есть декодер инструкции, диспетчер инструкций, работа со стеком… Наугад можно сказать, что сверху десяток машинных инструкций плюс проблемы предсказателя переходов.
Это если машина низкоуровневая, в машинах языков высокого уровня всяких дополнительных затрат еще поболее будет: динамическая типизация, позднее связывание и все такое.
Всякие там дополнительные приемы могут эти затраты снизить с 10-20 инструкций на один байт-код в среднем до 5-10 в самых быстрых из языков с виртуальной машиной. Это я так, не считая.
Если важна скорость, то я думаю легко сделать простенький компилятор байткода в машинный код. Особенно если сразу сделать байткод виртуальной машины максимально близким к целевому ассемблеру.
Ну… Можно и так, но это, в сущности, и есть aot- или jit-компиляция. Компиляцию наперед сделать можно, но в языках высокого уровня профита будет мало, т.к. они и так время по большей части в телах инструкций проводят.
В рассылке Емакса уже три захода была на jit-компиляцию публикаовалось, и только последний хоть какие-то результаты показал.
Опять же, серьезный оптимизирующий компилятор — штука сложная.
Словом, в общем случае я голосую за простенькие специализированные виртуалочки.
В рассылке Емакса уже три захода была на jit-компиляцию публикаовалось, и только последний хоть какие-то результаты показал.
Опять же, серьезный оптимизирующий компилятор — штука сложная.
Словом, в общем случае я голосую за простенькие специализированные виртуалочки.
Вот немного устаревший бенчмарк разных встраиваемых языков:
github.com/r-lyeh-archived/scriptorium
github.com/r-lyeh-archived/scriptorium
Ещё хотелось бы понять, чем байткод отличается от шитого кода? Что из них быстрее работает?
«Шитый» код — способ прохода по программе. Подвидов «шитого» кода — масса.
Стандартный подход к интерпретатору — здоровенный «switch» от байта.
Но в «шитом» коде можно, например, превратить массив байт в массив указателей на функции, которые потом последовательно вызывать. Другой вариант — массив меток, к которым переходить при помощи goto.
Где-то до начала последнего десятилетия это очень даже имело смысл, но есть исследования, показывающие, что сейчас процессоры научились хорошо предсказывать ветвления через switch. Основная проблема метода — может понадобиться ассемблер, т.е. это плохо портируется.
Стандартный подход к интерпретатору — здоровенный «switch» от байта.
Но в «шитом» коде можно, например, превратить массив байт в массив указателей на функции, которые потом последовательно вызывать. Другой вариант — массив меток, к которым переходить при помощи goto.
Где-то до начала последнего десятилетия это очень даже имело смысл, но есть исследования, показывающие, что сейчас процессоры научились хорошо предсказывать ветвления через switch. Основная проблема метода — может понадобиться ассемблер, т.е. это плохо портируется.
Всегда интересовало, какой с какой целью в виртуальные машины добавляют опкод NOP?
Что бы выровнять функции по границе слова, например. Или что бы заменить их потом на какой-нибуть DBG_STOP и проконтолировать переход на неправильный адрес.
Да по-разному, это типа такой костыль.
Пример первый, случайный. Есть функция, которая ничего не делает. Если язык интерпретируемый, то часто бывает так, что у нее должен быть хоть какой-то байт-код. NOP сюда вполне походит.
Пример второй, реалистичный. У вас байт-код, где есть безусловные переходы по каким-либо адресам, то есть в нем можно найти: JUMP. Вы хотите убрать какие-то инструкции до указанного адреса, но тогда надо менять адреса у JUMP-ов. Заменяете инстркции на NOP — и все хорошо.
Пример третий, хитрый. В некоторых архитектурах чтение байтов по адресами, не выровненным по длине машинного слова, либо запрещено, либо работает неэффективно. NOP-ами можно сделать выравнивание.
Пример первый, случайный. Есть функция, которая ничего не делает. Если язык интерпретируемый, то часто бывает так, что у нее должен быть хоть какой-то байт-код. NOP сюда вполне походит.
Пример второй, реалистичный. У вас байт-код, где есть безусловные переходы по каким-либо адресам, то есть в нем можно найти: JUMP. Вы хотите убрать какие-то инструкции до указанного адреса, но тогда надо менять адреса у JUMP-ов. Заменяете инстркции на NOP — и все хорошо.
Пример третий, хитрый. В некоторых архитектурах чтение байтов по адресами, не выровненным по длине машинного слова, либо запрещено, либо работает неэффективно. NOP-ами можно сделать выравнивание.
UFO just landed and posted this here
UFO just landed and posted this here
А какие именно мультистековые машины вы имеете в виду? Те, что разделяют стеки функций и вычислений?
UFO just landed and posted this here
Вы говорите про математические модели, я, признаться, в них не очень разбираюсь, так как универ давно уже не посещал. :-)
Я же говорю про практические виртуальные машины и их устройство. Они, разумеется, базируются на математических моделях, но вот прям знак равенства проводить не стоит.
С практической стороны могу сказать следующее:
1. Стек явный или неявный нужен в любом случае, без этого чуть ли не подавляющее большинство алгоритмов работать не может, это вы в той же книге можете найти.
2. В виртуальных машинах «регистровость» или «стековость» характеризует виртуальных набор инструкций, используемых для вычисления выражений или, скажем, передачу аргументов при вызове функции.
3. Байт-код от регистровости зависит сильно. Это и есть самая большая разница. Одно дело, когда надо делать PUSH 1,PUSH 2,ADD, другое — ADD r1,r2,r3.
4. Вычислительная способность регистровых и стековых машин не особо отличаются.
Два стека действительно часто используются. Но у нас ж в наличии и так есть условно бесконечная лента памяти, поэтому разницы в вычислительных возможностях это не делает.
Я же говорю про практические виртуальные машины и их устройство. Они, разумеется, базируются на математических моделях, но вот прям знак равенства проводить не стоит.
С практической стороны могу сказать следующее:
1. Стек явный или неявный нужен в любом случае, без этого чуть ли не подавляющее большинство алгоритмов работать не может, это вы в той же книге можете найти.
2. В виртуальных машинах «регистровость» или «стековость» характеризует виртуальных набор инструкций, используемых для вычисления выражений или, скажем, передачу аргументов при вызове функции.
3. Байт-код от регистровости зависит сильно. Это и есть самая большая разница. Одно дело, когда надо делать PUSH 1,PUSH 2,ADD, другое — ADD r1,r2,r3.
4. Вычислительная способность регистровых и стековых машин не особо отличаются.
Два стека действительно часто используются. Но у нас ж в наличии и так есть условно бесконечная лента памяти, поэтому разницы в вычислительных возможностях это не делает.
UFO just landed and posted this here
В реальных процессорах я про два стека не слышал. В x86 стек один точно.
Насчет переполнения стека… Тут сильно от языка зависит. В приличных языках это вообще невозможно :-) кадр каждой функции аллоцируется один раз и не меняется во время работы функции.
Да, второй стек в виртуальных машинах обычно делают для кадров функций и удобства работы с ними: прохода вверх по всему стеку и т.д…
Насчет переполнения стека… Тут сильно от языка зависит. В приличных языках это вообще невозможно :-) кадр каждой функции аллоцируется один раз и не меняется во время работы функции.
Да, второй стек в виртуальных машинах обычно делают для кадров функций и удобства работы с ними: прохода вверх по всему стеку и т.д…
UFO just landed and posted this here
UFO just landed and posted this here
Ага, SECD и его потомков… Немало.
Есть еще WAM, раз уж на то пошло, и многие другие.
Надо будет как-нибудь провести исследование самых влиятельных из популярных абстрактных машин и написать сюда статеечку.
Есть еще WAM, раз уж на то пошло, и многие другие.
Надо будет как-нибудь провести исследование самых влиятельных из популярных абстрактных машин и написать сюда статеечку.
Опять же, это вотчина Форта. Есть форт-процессоры с двумя аппаратными стеками (возвратов и вычислений). Для каждого типа данных можно заводить свой стек. Собственно, даже на x86 есть еще и FPU-стек.
UFO just landed and posted this here
Ага, так многие разработчики архитектур или расширений к наборам инструкций и проверяют свои идеи: берут какой-нибудь эмулятор подходящий, приписывают к нему обработчики новых инструкций и смотрят, что на выходе.
Эмулятор это зачастую, собственно, банальный интерпретатор байт-кода, только байт-код повторяет код машинный.
Эмулятор это зачастую, собственно, банальный интерпретатор байт-кода, только байт-код повторяет код машинный.
Да, кстати, вы правы, про FPU я как-то забыл. Сто лет эти инструкции в ассемблере не видел :-)
Думаю, влияние взаимное.
Разработчики процессоров подстраиваются под популярные виртуальные машины, типа JVM или Python VM, и наоборот, разработчики виртуальных машин стремятся оптимально «железный» процессор использовать.
Ну… Я очень люблю Си, но это не значит, что я не знаю, про его фундаментальные проблемы :-)
Разработчики процессоров подстраиваются под популярные виртуальные машины, типа JVM или Python VM, и наоборот, разработчики виртуальных машин стремятся оптимально «железный» процессор использовать.
Ну… Я очень люблю Си, но это не значит, что я не знаю, про его фундаментальные проблемы :-)
Если весь код выполняется императивно, то нужды в нескольких стеках (именно стеках операндов) кмк, нет. Это имеет смысл если мы вводим параллельные вычисления.
UFO just landed and posted this here
Sign up to leave a comment.
Интерпретаторы байт-кодов своими руками