Какие стратегии отправки кода операции используются в эффективных интерпретаторах?

Question

Какие методы способствуют эффективной отправке кода операции, чтобы сделать быстрый переводчик? Существуют ли какие-то методы, которые хорошо работают только на современном оборудовании, и другие, которые больше не работают из-за аппаратных достижений? Какие компромиссы должны быть достигнуты между простотой реализации, скоростью и переносимостью?

Я рад, что реализация Python на C наконец-то выходит за рамки простой switch (opcode) {...} реализации для отправки кода операции в непрямой поток в качестве опции времени компиляции, но я менее рад, что им потребовалось 20 лет, чтобы туда добраться. Возможно, если мы документируем эти стратегии в стеке потока, следующий язык станет быстрее.

Answer 1

Существует несколько документов по различным видам отправки:

M. Антон Эртл и Дэвид Грегг, Оптимизация точности косвенного прогнозирования ветвления в интерпретаторах виртуальных машин , в материалах конференции ACM SIGPLAN 2003 по разработке и внедрению языков программирования (PLDI 03), стр. 278-288, Сан-Диего, Калифорния, июнь 2003 года.

M. Антон Эртль и Дэвид Грегг, Поведение эффективных интерпретаторов виртуальных машин на современных архитектурах , в трудах 7-й Европейской конференции по параллельным вычислениям (Europar 2001), с. 403-412, LNCS 2150, Манчестер, август 2001

Отличное резюме дает Юньхэ Ши в своей докторской диссертации .

Кроме того, кто-то обнаружил новую технику несколько лет назад, которая является действующей ANSI C.

Answer 2

Перед тем, как начать что-либо, проверьте Lua .

Это маленький (150 Кб), чистый ANSI C, работает на любом, имеющем C-компилятор. Очень быстро.

И самое главное - исходный код чистый и читаемый. Стоит проверить.

Answer 3

Непрямая многопоточность - это стратегия, в которой каждая реализация кода операции имеет свой собственный JMP для следующего кода операции. Патч к интерпретатору Python выглядит примерно так:

add:
    result = a + b;
    goto *opcode_targets[*next_instruction++];

opcode_targets отображает инструкцию в байт-коде языка в ячейку памяти реализации кода операции. Это быстрее, потому что предиктор ветвления процессора может делать разные предсказания для каждого байт-кода, в отличие от оператора switch, который имеет только одну инструкцию ветвления.

Компилятор должен поддерживать вычисленное goto, чтобы это работало, что в основном означает gcc.

Прямая многопоточность аналогична, но при прямой многопоточности массив кодов операций заменяется указателями на вложения кода операции следующим образом:

goto *next_opcode_target++;

Эти методы полезны только потому, что современные процессоры конвейерны и должны очищать свои конвейеры (медленно) в неправильно предсказанной ветви. Разработчики процессоров используют прогнозирование ветвлений, чтобы избежать необходимости частой очистки конвейера, но предсказание ветвлений работает только для ветвей, которые с большей вероятностью выберут определенный путь.

Answer 4

Своевременная компиляция - это единица.

Answer 5

Один большой выигрыш - хранить исходный код в промежуточной форме, а не повторять лексический анализ и анализ во время выполнения.

Это может варьироваться от простого хранения токенов до многопоточного кода в стиле Forth и до JIT-компиляции.

Answer 6

Я нашел сообщение в блоге о реализации многопоточного интерпретатора, которое было полезно.

Автор описывает GCC-потоки на основе меток, а также как это сделать в Visual Studio с использованием встроенного ассемблера.

http://abepralle.wordpress.com/2009/01/25/how-not-to-make-a-virtual-machine-label-based-threading/

Результаты интересные. Он сообщает об улучшении производительности на 33% при использовании GCC, но неожиданно реализация встроенной сборки Visual Studio в 3 раза медленнее!

Answer 7

Вопрос немного расплывчатый. Но, кажется, вы спрашиваете о написании переводчика.

Интерпретаторы обычно используют традиционные компоненты синтаксического анализа: лексер, синтаксический анализатор и абстрактное синтаксическое дерево (AST). Это позволяет конструктору читать и интерпретировать допустимый синтаксис и строить древовидную структуру команд со связанными операторами, параметрами и т. Д.

Оказавшись в форме AST, весь ввод токенизируется, и интерпретатор может начать выполнение с обхода дерева.

Существует много вариантов, но недавно я использовал ANTLR в качестве генератора синтаксических анализаторов, который может создавать синтаксические анализаторы на различных целевых языках, включая C / C ++ и C #.

Answer 8

Бенчмаркинг - это хорошая техника для быстрого достижения чего-либо на данной платформе. Тестируйте, улучшайте, тестируйте снова, улучшайте.

Не думаю, что вы можете получить лучший ответ. Есть много методов, чтобы сделать переводчиков. Но я даю вам совет: не делайте компромиссов, просто выберите то, что вам действительно нужно, и преследуйте эти цели.