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

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

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