Комментарии 107
Спасибо за статью! Можете рассказать почему решили делать свой байткод а не интерпритатор без компиляции?
В байт-коде легче отвязать всякий синтаксический мусор от того, что реального происходит за кадром.
Ну и… Работает значительно быстрее.
Виртуальную машину будете свою реализовывать? Если да, то смотрели ли в сторону готовых GraalVM либо LLVM ?
При чем здесь GraalVM или LLVM? У нас относительно небольшой движок регулярных выражений, а не новый язык программирования, упаси боже. Использоваться он будет использоваться в контексте, о котором я расскажу, вероятно, в другой статье.
Регулярные выражения будут компилироваться в байт-код, который будет интерпретироваться маленькой виртуальной машинкой. Последняя — часть специализированной поисковой системы, пока еще только находящейся на этапе работающего прототипа.
У LLVM низкий порог вхождения, есть оптимизатор, интерпретатор и JIT. Это лучше велосипедов даже для не очень больших проектов, мне кажется.
От статьи больше вреда, чем пользы.
Я понимаю интерес, например, PostgreSQL, которые ведут борьбу за любые проценты при вычислении выражений в запросах, но в данном проекте это смысла не имеет точно.
А когда смысл начнет иметь, то, признаться, я все равно бы взял что-то чуть более легковесное, вроде замечательной libjit.
Обратите внимание, статья о том, как виртуальные машины устроены, а не о том, какой just-in-time компилятор стоит использовать.
Я могу переформулировать свой вопрос.
Было интересно почему вы решили писать свою виртуальную машину а не взять готовую, поэтому и вспомнил LLVM и GraalVM которые должны, в моем представлении, помогать в таких случаях.
LLVM это вообще не виртуальная машина в традиционном смысле слова, а фреймворк — и очень хороший фреймворк! — для компиляции промежуточного представления кода в нативный код. В сравнении с бэкэндом GCC сам фреймворк действительно проще. Но объективно это огромный проект в сотни тысяч строк, использовать который не так уж и дешево в смысле времени и нервов.
GraalVM это дальнейшая эволюция JVM. Мне даже страшно думать о том, чтобы мои 500-1000 строк кода заменять на JVM-подобную махину.
Приведенные же в статье примеры — маленькие машинки.
Такие машинки есть в ядре Линукса,
Можете поделиться ссылкой? очень интересно почитать.
Спасибо, ради этого ответа я вас и мучал вопросами, не знал просто как лучше спросить.
Прежде чем я почешу голову и залезу в старые заметки, можно вопрос? А почему именно интерпретатор, а не просто какой-нибудь маленький компилятор в бинарный код для микроконтроллера?
У них был вроде еще один, проще. Компилятор основан на LCC.
Собственно, LCC можно переделать под любую виртуальную машину. Бэкэнды там делаются легко, виртуальную машину тоже возможно наклепать.
Но я бы взял готовую, ту, что выше.
tcc смотрели?
Интерпретационные языки, чем замечательны, так это тем, что не сводят сложные функции и синтаксис к байт-коду. Интерпретатор интерпритирует код, используя оптимизированный код для конкретной платформы. Да, бывает так, что парсер сначала переводит файл со скриптом в оптимизированную форму (p-код) для последующей ускоренной интерпритации. Но это совсем иное, чем компиляция в байт-код. Как минимум, такое упрощение чаще всего обратимо, а концепция интерпретатора не нарушается.
В общем, все здорово, но не ясно зачем это, если не ответить на ключевой вопрос — какие задачи будет решать виртуальная машина и какую архитектуру при этом будет иметь.
Сводят. Все современные интерпретируемым языки типа Python, Java — сводят, и ещё как! Есть лексер-парсер-транслятор в байт-код, и есть собственно какой-нибудь CPython, который этот байт-код выполняет.
У функций в питоне можно в runtime посмотреть (а на самом деле даже и создать функцию из байт-кода) байт-код функции через объект func.code
Интерпретаторы байт-кодов — техника, которая может быть к месту, а может быть не к месту. Вероятные причины применения байт-кодов я указал, их много.
Насчет «совсем иное, чем компиляция в байт-код» и компиляции я вас не понял, возможно, либо мне, либо вам надо определения глянуть.
«Обратимость». Характерный байт-код языков программирования сильно теряет по сравнению с самим языком, и именно поэтому его легче выполнять интерпретатору, т.к. в нем меньше всяких деталей. Машинный код по сравнению с языком Си, например, очень сильно теряет в выразительности и подробностях. Что вы имеете в виду, когда говорите, что «оно чаще всего обратимо»?
— при трансляции в байт-код, происходит фактически компиляция, что с одной стороны позволяет использовать механизмы оптимизации, но с другой, устраняет саму суть языка из которого сгенерирован этот самый байт-код;
— при трансляции в P-код (в моем понимании), происходит кодирование синтаксиса языка. Ну к примеру, функция заменяется ее уникальным кодом, параметры кодируются в бинарное представление, а строковые константы оформляются ссылками в оптимизированную область памяти. При этом, обратная трансляция может восстановить исходный код. В этом случае синтаксис языка сохраняется даже на уровне интерпретации.
И если вариант 2 мне в целом понятен как «быстрое решение для простых задач». То вариант 1 мне кажется чрезмерным, т.к. требует больше телодвижений и должен быть оправдан уникальными свойствами виртуальной машины.
Надеюсь так яснее.
Я сомневаюсь, что тот p-код был вот прям очень высокоуровневым, и из него можно было полность исходный код восстановить.
Байт-код в современном понимании потому и используется, что его легко и генерировать, и интерпретировать. Вариант 1 на практике делается очень несложно. В примерах статьи я за часа три-четыре сделал 5(!) виртуальных машинок. Уверяю вас, компиляторы в коды для этих машин из несложных языков я сделаю каждый за те же полдня.
Более того, избавление от синтаксических деталей языка все только упрощает. Сложно добавить jit-компиляцию, это да, хотя и тут все сильно зависит от языка.
Конкретный пример из личного опыта.
Работал я как-то в одной игровой конторе, делающей популярную онлайн-игру. Игра состоит из матчей, в процессе и финале каждого из которых надо обсчитывать сотни мелких условий, типа кому медальку дать, кого оштрафовать и т.д.
Условия эти формируются гейм-дизайнерами в виде XML-описаний, или, если условия хитрые, пишутся программистами. Сначала мы компилировали XML в язык программирования (Питон), и вкладывали в проект. Но потом выяснилось, что дизы хотят другой формат, и хотят легко код подменять чуть ли не лету.
Так вот. За месяц работы одного программиста система была переделана на виртуальную машинку, понимающую байт-код. Логику условий можно было писать на чем угодно — специальном языке, XML или генерить прямиком при помощи GUI — и больше не трогать программистов. Опять же, байт-код легко подменить без перезапуска кластера…
Профит со всех сторон.
Ну я все же пока радикально не утвердился в верности "новой" терминологии. Потрачу время на поиск "истины".
Со слов "это сделать просто", на моей памяти, начиналось оч много великов.
В остальном, посмотрим, по следующим статьям, чем же плохи остальные реализации и почему нужно ваять что-то свое.
Так вот. За месяц работы одного программиста система была переделана на виртуальную машинку, понимающую байт-код. Логику условий можно было писать на чем угодно — специальном языке, XML или генерить прямиком при помощи GUI — и больше не трогать программистов. Опять же, байт-код легко подменить без перезапуска кластера…
А в чем плюс по сравнению с иcпользованием, например, lua? А то месяц работы программиста — не очень много, но ощутимо.
В общем-то, никто против Луа, или любого другого такого же языка программирования, ничего не имел. Дело было не том, что нужен был еще один язык, а в том, что была плюс минус-понятная абстрактная машина, в термины которогой надо было разные языки переводить.
Но там и так логика на Питоне была, т.е. уже был простой язык. Задача была несколько другая: найти формат, куда можно компилировать разные мини-языки.
Но там и так логика на Питоне была, т.е. уже был простой язык. Задача была несколько другая: найти формат, куда можно компилировать разные мини-языки.
Знаете все равно не понятно, зачем следовало создавать виртуальную машину, когда можно было бы все в тот же питон перегонять.
Возможно какой-нибудь наглядный кейс из той задачи, дал бы некое прояснение)
2. В питон трудно компилировать.
3. Питон — и его программы — слишком много чего умеет, а в собственной виртуалке можно строго ограничить возможности програамы.
По схожим причинам опен-сорсная игра Battle for Wesnoth в свое время убрала возможность скриптовать расширения на питоне в пользу собственного декларативного языка.
С презентации Java Virtual Machine во второй половине 90-х прошло уже достаточно много времени, и можно с уверенностью сказать, что интерпретаторы байт-кодов — не будущее, а настоящее.
В 90-х это была новинка, в 2000-х настоящее а сейчас это уже прошлое. Настоящее — jit-компиляторы.
Обычно есть основной интерпретатор, начинающий работать сходу, и сбоку отдельный jit-компилятор, так или иначе выделяющий куски байт-кода, которые имеет смысл подменить на лету на машинный код.
Если уж на то пошло, то последнее веяние — мета-трейсинг в стиле того, что делает проект PyPy в своем RPython. Вот здесь обзорный пост гляньте.
Есть ещё такая интересная штука, как специализация языков, и с помощью нее из интерпретатора и специализированные можно комплилятор получить)
Насколько я в курсе, дотнет сделан именно так: «основной интерпретатор» вообще не существует, любая функция (метод) переводится в JIT по первому использованию, но может быть обновлена потом. Во всяком случае, в книгах пишется именно так. А он только начинался в девяностых.
Прошу уточнить: это книги врут, или вы имеете в виду что-то немного другое?
> Могу углубиться в детали, если интересно.
Да, интересно.
История выглядит так, насколько помню сходу:
1. Сначала (8о-е, 90-е, начало нулевых) получили распространение интерпретаторы с jit-ом, предварительно компилировавшим весь код (Smalltalk/SELF, JVM) метод за методом по мере работы программы.
В среднем такой код работал быстро, но долго разогревался, т.е. первое время ощутимо тупил т.к. каждый метод во время первого вызова сначала нужно скомпилировать. Для разовых запусков методов это часто выходило медленней, чем просто чтение байт-кода. Проблему решали по-разному, но в итоге пришли к другой модели.
2. Стали (JVM, ранние jit в Джаваскрипте, т.е. середина нулевых) делать так: код интерпретируется, но помечаются «горячие» методы, которые потом и компилируются тяжелым комплилятором.
3. Появились (поздние нулевые, Firefox, luajit, PyPy) трассирующие jit-компиляторы, которые ищут «горячие» циклы и компилируют именно их, сначала же все работает с простого интерпретатора.
4. Наши дни. Самые развитые виртуальные (Firefox, V8) машины имеют несколько уровней компиляции. Базовый — байткод, потом «легкий» компилятор и для самых «горячих» методов/трасс — тяжелый компилятор. Код подменяется на лету, по мере сбора статистики.
5. Совсем последние новости: трассирующие jit-компиляторы выходят из моды.
Конечно, в менее крупных проектах такое зверство — каскад компиляторов — малополезно и очень трудоемко, и используется метод, указанный вами: предкомпиляция всех вызываемых методов.
Надеюсь, утолил ваше любопытство :-) Опять же, деталей не знаю, но могу предполжить, что .NET прошел схожие этапы в развитии.
Думаю, следующий пост будет про те вещи, которые можно сделать в рамках простого Си и трех сотен строк. Уверяю вас, кой-какие приемы неплохо работают и по старинке, без непосредственно руками вбитого машинного кода :-)
Неплохо — это хорошо, но не великолепно ;)
1. Красиво и эффективно сделать jit-компиляцию сложно.
Я тут где-то писал, что, например, для Емакса уже было несколько попыток, но выхлоп был очень слабый. Разработчики PostgreSQL, недавно внедрившие llvm-jit, хвастаются, что скорость увеличилась на 10-15% в подходящих случаях. Для них это много, но я могу убиться об стену, но начальству не смогу продать два-три месяца разработки ради такой разницы.
2. Применимость в бытовом программировании маленькая.
Задачи такие встречаются редко, и они далеко всегда критичны.
Другое дело, что если не уметь делать, то и не пригодится никогда. По себе и своим коллегам знаю :-) Бывало и так: «Нормально, что мы в кластере молотим данные десять минут», когда я на одной машине за секунды делаю.
А вот простенький интерпретатор действительно раза три был очень нужен.
Словно бы мы говорим не о 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 для своих текстовых игр тоже держали специальный движок с виртуальной машиной.
Однако же, средний потребитель софта до Джавы кушал именно программы, собранные из Си или Паскаля, компилировавшихся в машинный код.
META II это генератор компиляторов, который написан на себе самом и порождает код для стековой VM. Оригинальная статья о META II в числе моих самых любимых: www.ibm-1401.info/Meta-II-schorre.pdf
P.S. Когда-то у меня была идея написать краткий вводный курс по компиляторам-интерпретаторам с разбором всего двух систем: META II и Forth.
Про Форт же, да, конечно. Я так понимаю, что по поводу быстрых интерпретаторов именно байт-кода все было сделано еще в 70-е. Почти все интересные работы 2000-х ссылаются на идею «шитого» кода именно на примере Форта.
Поделюсь еще одной малоизвестной статьей. На сей раз достаточно свежей. Ее автор, В. Макаров (известный разработчик в gcc-сообществе) сравнивает регистровые и стековые ВМ, пишет о шитом коде и т.д. уже с современных позиций: arxiv.org/pdf/1604.01290.pdf
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 проверка не нужна.
Я пробовал rust еще, но на нем так же не получается догнать асм + у него пока нет alloca и другие проблемы.
Ну что ж. Джентельмен серьезный :-)
Выжимка для самого себя по поводу статьи:
1. Уже не так важно, как именно оформлен главный цикл интерпретатора.
2. Правильная регистровая машина может быть в разы быстрее стековой.
3. Возможно быстро и легко сделать портативный jit-компилятор.
4. Чем меньше работает диспетчер — тем лучше; «склеивать» инструкции хорошо.
5. Дальнейшие улучшения идут за счет техник, специфичных для динамических языков.
Вообще, у него там совсем маньячный подход, т.е. он действительно много приемов использует.
Сам язык и система программирования для него — довольно авангардные и необычные.
Настолько, что статьи и описания идей не многим удалось понять — отворачивались раньше, т.к. новизны было слишком много и слишком уж радикальные решения. Смею думать, несколько идей я уловил, и они мне очень понравились. Давно уже хочу об этом пару статей написать…
Я переработал идеи, но за несколько редких подходов законченной реализации нет. Сейчас думаю сделать очередной подход…
Исполнение прямо в браузере плюс подробное руководство, как расширить метакомпилятор
А вот еще замечательная статья, которую Вы, возможно, не видели: 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 в самых быстрых из языков с виртуальной машиной. Это я так, не считая.
В рассылке Емакса уже три захода была на jit-компиляцию публикаовалось, и только последний хоть какие-то результаты показал.
Опять же, серьезный оптимизирующий компилятор — штука сложная.
Словом, в общем случае я голосую за простенькие специализированные виртуалочки.
github.com/r-lyeh-archived/scriptorium
Ещё хотелось бы понять, чем байткод отличается от шитого кода? Что из них быстрее работает?
Стандартный подход к интерпретатору — здоровенный «switch» от байта.
Но в «шитом» коде можно, например, превратить массив байт в массив указателей на функции, которые потом последовательно вызывать. Другой вариант — массив меток, к которым переходить при помощи goto.
Где-то до начала последнего десятилетия это очень даже имело смысл, но есть исследования, показывающие, что сейчас процессоры научились хорошо предсказывать ветвления через switch. Основная проблема метода — может понадобиться ассемблер, т.е. это плохо портируется.
Пример первый, случайный. Есть функция, которая ничего не делает. Если язык интерпретируемый, то часто бывает так, что у нее должен быть хоть какой-то байт-код. NOP сюда вполне походит.
Пример второй, реалистичный. У вас байт-код, где есть безусловные переходы по каким-либо адресам, то есть в нем можно найти: JUMP. Вы хотите убрать какие-то инструкции до указанного адреса, но тогда надо менять адреса у JUMP-ов. Заменяете инстркции на NOP — и все хорошо.
Пример третий, хитрый. В некоторых архитектурах чтение байтов по адресами, не выровненным по длине машинного слова, либо запрещено, либо работает неэффективно. NOP-ами можно сделать выравнивание.
Я же говорю про практические виртуальные машины и их устройство. Они, разумеется, базируются на математических моделях, но вот прям знак равенства проводить не стоит.
С практической стороны могу сказать следующее:
1. Стек явный или неявный нужен в любом случае, без этого чуть ли не подавляющее большинство алгоритмов работать не может, это вы в той же книге можете найти.
2. В виртуальных машинах «регистровость» или «стековость» характеризует виртуальных набор инструкций, используемых для вычисления выражений или, скажем, передачу аргументов при вызове функции.
3. Байт-код от регистровости зависит сильно. Это и есть самая большая разница. Одно дело, когда надо делать PUSH 1,PUSH 2,ADD, другое — ADD r1,r2,r3.
4. Вычислительная способность регистровых и стековых машин не особо отличаются.
Два стека действительно часто используются. Но у нас ж в наличии и так есть условно бесконечная лента памяти, поэтому разницы в вычислительных возможностях это не делает.
Насчет переполнения стека… Тут сильно от языка зависит. В приличных языках это вообще невозможно :-) кадр каждой функции аллоцируется один раз и не меняется во время работы функции.
Да, второй стек в виртуальных машинах обычно делают для кадров функций и удобства работы с ними: прохода вверх по всему стеку и т.д…
Эмулятор это зачастую, собственно, банальный интерпретатор байт-кода, только байт-код повторяет код машинный.
Разработчики процессоров подстраиваются под популярные виртуальные машины, типа JVM или Python VM, и наоборот, разработчики виртуальных машин стремятся оптимально «железный» процессор использовать.
Ну… Я очень люблю Си, но это не значит, что я не знаю, про его фундаментальные проблемы :-)
Интерпретаторы байт-кодов своими руками