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

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

• Лексические пространства имен (закрытие)
• Динамически растущий стек вызовов
• Медленный целочисленный тип (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 - это в основном "goto"

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

    } 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, если это не очевидно):-). Это верхние 3 элемента, о которых сообщает 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. (некоторый пример кода)

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

Все дело в github

Ответы

Ответ 1

Есть исследования, посвященные десятилетиям, которые вы можете оптимизировать:

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

Ответ 2

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

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

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

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

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

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

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

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