Всем привет!
Продолжаю пилить свою имплементацию Scheme R5RS на Java.
В качестве тестов беру примеры кода из Интернета.
Где-то месяц назад взял следующий замечательный пример: https://rosettacode.org/wiki/Integer_roots#Scheme
Тут и internal definitions, и много вычислений, и большие числа, и рекурсия.
Изначально оно падало почти мгновенно со StackOverflowError (что логично). Реализовал tail-call optimizations, падать перестало.
Теперь результат немного не совпадает из-за того, что в некоторых местах теряется точность (вообще, числа в Java реализованы кривовато ИМХО), но это ладно.
Еще оно работает существенно медленнее Racket и Guile.
Я, конечно, и не ожидал супер производительности, но всё же решил запустить профайлер и по возможности увеличить производительность.
В результате работы профайлера выяснилось, что как минимум 2 вещи существенно снижают производительность:
1) Вызовы процедур
2) Частые environment lookups
1) Вызовы процедур
Одно из очевидных решений - инлайнить некоторые процедуры.
Так, например, делают и Racket, и Guile.
Что-то вроде:
(define (test n) (zero? n)) => (define (test n) (= n 0))
Попытался это реализовать, вроде, получилось, но как-то кривовато.
Вопрос:
Есть ли какие-нибудь алгоритмы для этого дела?
Как определить когда можно инлайнить, а когда нельзя?
Например:
(define (t n)
(zero? n) ;; можно инлайнить
'(zero? n)) ;; нельзя инлайнить
Можно ли как-то статически определить, что перед нами вызов функции, а не quoted form или еще что-нибудь?
В данный момент я просто рекурсивно пробегаю по всем формам в теле функции, и если какой-нибудь элемент совпадает с телом функции, которую можно инлайнить, то я подменяю вызов функции на ее тело (попутно подставляя правильные имена аргументов). Все quoted/quasiquoted формы пропускаю.
Оно, вроде, и работает, но не уверен, что оно будет работать всегда правильно. Плюс, каждый раз приходится создавать кучу новых объектов, потому что списки в Java копируются как shallow copies, а мне здесь всегда нужна deep copy (потому что я не могу менять тело той функции, которую инлайню).
Racket пишут, что они это делают на этапе компиляции - как они это делают?
У меня компиляции нет, ее заменяет вычисление lambda.
2) Частые environment lookups
На пальцах я понимаю, почему оно работает не так шустро и чисто теоретически представляю, как это исправить.
На практике же ничего не получается.
Допустим, есть простая функция:
(define (perf n)
(if (zero? n)
"DONE"
(perf (- n 1))))
У меня, когда вычисляется ее тело, то evaluator на каждой итерации постоянно забирает из окружения символы if, zero?, n и perf.
Более того, для всех символов, кроме perf, он всегда делает по 2 lookup'а: сначала пытается найти в локальном окружении, не находит, потом поднимается выше и находит их в глобальном окружении.
Итого, даже если вычислить (perf 1), то lookups будут примерно такие (воспроизвожу по памяти):
Lookups:
perf
if (miss!)
if
zero? (miss!)
zero?
n
perf
- (miss!)
n
if (miss!)
if
zero? (miss!)
zero?
n
(здесь я еще опускаю lookups, которые делаются для тела zero?: = и n)
Видно, что многие lookups являются лишними и можно бы их прокешировать.
Но как?
Во-первых, что и как кешировать?
Во-вторых, как при этом не поломать lexical scope?