Каковы некоторые очевидные оптимизации для виртуальной машины, реализующей функциональный язык?

Question

Я работаю над промежуточным языком и виртуальной машиной для запуска функционального языка с парой "проблемных" свойств:

• Лексические пространства имен (замыкания)
• Динамически растущий стек вызовов
• Медленный целочисленный тип (bignums)

Промежуточный язык основан на стеке, с простой хеш-таблицей для текущего пространства имен. Чтобы вы могли понять, как это выглядит, вот функция McCarthy91:

# McCarthy 91: M(n) = n - 10 if n > 100 else M(M(n + 11))
.sub M
    args
    sto n

    rcl n
    float 100
    gt
    .if
        .sub
            rcl n
            float 10
            sub
        .end
        .sub
            rcl n
            float 11
            add
            list 1
            rcl M
            call-fast
            list 1
            rcl M
            tail
        .end
    call-fast
.end

"Большая петля" проста:

• получить инструкцию
• увеличить указатель инструкции (или счетчик программы)
• оценить инструкцию

Вместе с sto, rcl и многое другое, есть три инструкции для вызовов функций:

• call копирует пространство имен (глубокая копия) и помещает указатель инструкций в стек вызовов
• call-fast то же самое, но создает только поверхностную копию
• tail это в основном "гото"

Реализация действительно проста. Чтобы дать вам лучшее представление, вот случайный фрагмент из середины "большого цикла" (обновлено, см. Ниже)

    } else if inst == 2 /* STO */ {
        local[data] = stack[len(stack) - 1]
        if code[ip + 1][0] != 3 {
            stack = stack[:len(stack) - 1]
        } else {
            ip++
        }
    } else if inst == 3 /* RCL */ {
        stack = append(stack, local[data])
    } else if inst == 12 /* .END */ {
        outer = outer[:len(outer) - 1]
        ip = calls[len(calls) - 1]
        calls = calls[:len(calls) - 1]
    } else if inst == 20 /* CALL */ {
        calls = append(calls, ip)
        cp := make(Local, len(local))
        copy(cp, local)
        outer = append(outer, &cp)
        x := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        ip = x.(int)
    } else if inst == 21 /* TAIL */ {
        x := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        ip = x.(int)

Проблема заключается в следующем: вызов McCarthy91 16 раз со значением -10000 занимает, почти не имеет значения, 3 секунды (после оптимизации глубокой копии, которая добавляет почти секунду).

Мой вопрос: каковы некоторые общие методы оптимизации интерпретации такого рода языка? Есть ли низко висящие фрукты?

Я использовал срезы для своих списков (аргументы, различные стеки, срез карт для пространств имен, ...), поэтому я делаю такие вещи повсюду: call_stack[:len(call_stack) - 1], Прямо сейчас, я действительно понятия не имею, какие фрагменты кода делают эту программу медленной. Любые советы будут оценены, хотя я в основном ищу общие стратегии оптимизации.

В сторону:

Я могу немного сократить время выполнения, обойдя мои соглашения о вызовах. list <n> инструкция выбирает n аргументов стека и помещает их список обратно в стек, args инструкция выскакивает из этого списка и помещает каждый элемент обратно в стек. Это, во-первых, для проверки того, что функции вызываются с правильным количеством аргументов, и, во-вторых, для возможности вызова функций с переменными списками аргументов (т.е. (defun f x:xs)). Удаление этого, а также добавление инструкции sto* <x>, который заменяет sto <x>; rcl <x>Я могу получить до 2 секунд. Все еще не блестящий, и я должен иметь это list/args бизнес в любом случае.:)

Еще один в стороне (это длинный вопрос, который я знаю, извините):

Профилирование программы с помощью pprof сказало мне очень мало (я новичок в Go, если это не очевидно):-). Это первые три пункта, о которых сообщает pprof:

  16   6.1%   6.1%       16   6.1% sweep               pkg/runtime/mgc0.c:745
   9   3.4%   9.5%        9   3.4% fmt.(*fmt).fmt_qc   pkg/fmt/format.go:323
   4   1.5%  13.0%        4   1.5% fmt.(*fmt).integer  pkg/fmt/format.go:248

Это изменения, которые я сделал до сих пор:

• Я удалил хеш-таблицу. Вместо этого я сейчас передаю только указатели на массивы и эффективно копирую локальную область видимости только тогда, когда это необходимо.
• Я заменил имена команд на целочисленные коды операций. Раньше я тратил немало времени на сравнение строк.
• call-fast инструкция пропала (ускорение больше не поддается измерению после других изменений)
• Вместо инструкций "int", "float" и "str" ​​у меня есть только один eval и я оцениваю константы во время компиляции (компиляция байт-кода, который есть). затем eval просто толкает ссылку на них.
• После изменения семантики .ifЯ мог бы избавиться от этих псевдофункций. это снег .if, .else а также .endif, с неявным gotos и блочной семантикой, аналогичной .sub, ( пример кода)

После реализации лексера, парсера и компилятора байт-кода скорость немного понизилась, но не сильно. Вычисление MC(-10000) 16 раз позволяет оценить 4,2 миллиона инструкций байт-кода за 1,2 секунды. Вот пример кода, который он генерирует (из этого).

Все это на GitHub

Answer 1

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

• Реализация функциональных языков: учебник Саймона Пейтона Джонса и Дэвида Лестера. Опубликовано Prentice Hall, 1992.
• Практические основы языков программирования, Роберт Харпер

Answer 2

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

(Да, ваша операция захвата стека с использованием кусочков массива выглядит подозрительно. Вы должны убедиться, что они действительно имеют ожидаемую алгоритмическую сложность, или же использовать выделенную структуру данных (... стек). Я обычно опасаюсь использовать все для этой цели используется структура данных, такая как списки Python или хеш-таблицы PHP, потому что они не обязательно предназначены для правильной обработки этого конкретного варианта использования, но может случиться так, что срезы гарантируют O(1) стоимость нажатия и удаления при любых обстоятельствах.)

Лучший способ обработки сред, если их не нужно преобразовывать, - это использовать числовые индексы вместо переменных (индексы де Брюйна (0 для последней переменной) или уровни де Брюйна (0 для связанной переменной) first). Таким образом, вы можете хранить только динамически изменяемый массив для среды и получать к нему очень быстрый доступ. Если у вас есть первоклассные замыкания, вам также потребуется захватить среду, которая будет более дорогостоящей: вам придется скопировать часть его в выделенной структуре, или используйте неизменяемую структуру для всей среды. Только эксперимент покажет, но мой опыт показывает, что стремление к быстрой изменяемой структуре среды и более высокая стоимость строительства замыкания лучше, чем иметь неизменяемая структура с большим количеством бухгалтерии все время, конечно, вы должны сделать анализ использования, чтобы захватить только необходимые переменные в ваших замыканиях.

Наконец, после того, как вы вычеркнули источники неэффективности, связанные с вашими алгоритмическими решениями, горячая область будет:

• сборка мусора (определенно сложная тема; если вы не хотите стать экспертом по сборке мусора, вам следует серьезно подумать о повторном использовании существующей среды выполнения); возможно, вы используете GC вашего основного языка (выделение кучи на вашем интерпретируемом языке преобразуется в выделение кучи на языке реализации с тем же временем жизни), в показанном вами фрагменте кода неясно; эта стратегия хороша, чтобы получить что-то достаточно эффективное простым способом

• реализация чисел; Есть все виды хаков, чтобы быть эффективными, когда целые числа, которыми вы манипулируете, на самом деле маленькие. Лучше всего повторно использовать работу людей, которые вложили в это массу усилий, поэтому я настоятельно рекомендую вам повторно использовать, например, библиотеку GMP. С другой стороны, вы также можете повторно использовать поддержку языка хоста для bignum, если она есть, в вашем случае пакет math / big для Go.

• низкоуровневый дизайн вашей петли интерпретатора. На языке с "простым байт-кодом", таким как ваш (каждая инструкция байт-кода переводится в небольшое количество собственных инструкций, в отличие от сложных байт-кодов, имеющих высокоуровневую семантику, такую ​​как байт-код Parrot), фактическое "зацикливание и диспетчеризация байт-кодов" "код может быть узким местом. Было проведено довольно много исследований о том, как лучше всего написать такие циклы диспетчеризации байт-кода, чтобы избежать каскада if/then/else (таблицы переходов), извлечь выгоду из прогнозирования ветвлений хост-процессора, упростить поток управления и т. Д. Это называется многопоточным кодом, и существует множество (довольно простых) различных техник: прямая многопоточность, непрямая многопоточность... Если вы хотите изучить некоторые исследования, есть, например, работа Антона Эртля "Структура и производительность". Efficient Interpreters в 2003 году и более поздние потоки контекста: гибкая и эффективная техника диспетчеризации для интерпретаторов виртуальных машин. Преимущества этих методов, как правило, довольно чувствительны к процессору, поэтому вы должны сами проверить различные возможности.

Хотя работа STG интересна (и книга Пейтона-Джонса о реализации языка программирования превосходна), она в некоторой степени ориентирована на ленивую оценку. Что касается разработки эффективного байт-кода для строгих функциональных языков, я приведу ссылку на работу Ксавье Лероя 1990 года на машине ZINC: эксперимент ZINC: экономичная реализация языка ML, который был новаторской работой по внедрению языков ML, и все еще используется в реализации языка OCaml: есть и байт-код и собственный компилятор, но байт-код все еще использует прославленную машину ZINC.