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

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

• Лексические пространства имен (замыкания)
• Динамически растущий стек вызовов
• ] Медленный целочисленный тип (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 аргументов из стека и помещает их список обратно в стек, инструкция argsизвлекает из этого списка и помещает каждый элемент обратно в стек. . Это делается, во-первых, для проверки того, что функции вызываются с правильным количеством аргументов, а во-вторых, чтобы иметь возможность вызывать функции с переменными списками аргументов (например, (defun f x:xs)). Удаление этого, а также добавление инструкции sto* , которая заменяет sto ; rcl , я могу сократить его до 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с неявными переходами и блочной семантикой, аналогичной .sub. ( пример кода)

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

Все это есть на гитхабе