Всем привет! Сегодня я расскажу о своём пет-проекте на Go - Tokype, покажу результаты бенчмарков, а также раскрою его главный секрет.
Tokype - это интерпретатор, который парсит код в AST и выполняет его, обходя узлы дерева. Обычно чистые AST выполняются дольше, чем языки с байт-кодом (например, Python, Lua, PHP) или JIT-компиляцией (LuaJIT, Java, JavaScript, C#).
Мой язык сначала был медленным. Он мог выполнять код в 3-5 раз медленнее Python (прошлые тесты я не могу предоставить. Их результаты потерялись). Я не умел и не умею делать компилятор байт-кода или JIT-компилятор, поэтому я пошёл другим путём.
Справка для тех, кто не знает, что такое байт-код, JIT-компилятор, а также что делают оптимизаторы в компиляторах.
Байт-код компилятор
Сейчас многие языки используют байт-код компиляторы (у Lua - luac, у Erlang - erlc, у Java - javac). Они превращают код в байты. Этот байт-код выполняется в виртуальной машине языка программирования, что делает код быстрее, но не настолько, чтобы выдавать скорость компилируемых языков (вроде C++ или Go).
JIT-компиляторы
JIT-компиляторы - это очень мощная оптимизация для интерпретаторов. JIT (Just-In-Time) компилирует байт-код в машинный код, что делает код быстрее, но он компилирует не всё, только “горячие зоны” (циклы, часто вызываемые функции). Это даёт высокий прирост скорости выполнения. Но чтобы получить максимальную скорость, JIT надо “разогреть”, тогда он даст высокую оптимизацию.
Оптимизаторы кода в компиляторах
Оптимизатор - это главный помощник компиляторов, чтобы они давали высокую производительность. Он берёт ваш код, переписывает его алгоритмически, делая его эффективнее для процессора.
Что входит в этот оптимизатор:
Инлайнинг функций:
Вместо того чтобы вызывать мелкие функции, оптимизатор убирает вызов и вместо этого вставляет блок функции в место вызова.
Удаление мёртвого кода:
Если в коде есть условия, которые никогда не выполнятся, оптимизатор просто удалит это условие. То же самое происходит с переменными, которые нигде не используются.
Развёртывание циклов:
Вместо того чтобы гонять процессор, оптимизатор просто копирует тело цикла и вставляет его столько раз, сколько выполняется цикл (например, 4 раза). Это убирает лишние переходы.
Свёртка констант:
Оптимизатор видит выражение (например, 7 + 6 + 5). Он не будет заставлять процессор это считать, а вместо этого сам всё посчитает и вставит ответ вместо выражения (в нашем случае - 18).
Поскольку я не умею делать компиляторы байт-кода и JIT, я подумал: “А можно ли встроить оптимизатор компиляторов в интерпретатор? И какую скорость тогда получит мой Tokype?”
Я начал придумывать ему название. Я вспомнил, что в V8 есть TurboFan, и я решил сделать название тоже забавным. Я придумал TitanJerboa. Jerboa (тушканчик) я выбрал потому, что тушканчик - это быстрый зверёк из семейства тушканчиковых, а Titan (титан) я выбрал для солидности.
Что входит в TitanJerboa?
constantFold (свёртывание констант)
Самая базовая, но очень полезная оптимизация. Если в коде есть выражение, которое можно вычислить прямо сейчас - зачем вычислять его в рантайме?
Было:
x = 7 + 6 + 5
y = x * 2 + 10
Стало:
x = 18
y = 46
Как это работает:
func (o *Optimizer) evaluateConstant(expr ast.Expression) ast.Expression {
tempEnv := evalut.NewEnvironment()
result := evalut.Eval(expr, tempEnv)
if !o.hasVariables(expr) {
return o.valueToLiteral(result)
}
return nil
}
То есть всё, что можно посчитать на этапе анализа - считается. Это касается не только арифметики, но и логических выражений, строковых конкатенаций и так далее.
optimizeControlFlow (оптимизация if/elif/else, а также for/while)
Эта оптимизация смотрит на if/elif/else и циклы. Если условие вычисляется в константу, зачем тащить в исполняемый код все ветки? Оставляем только ту, которая реально сработает.
Как это выглядит в коде:
func (o *Optimizer) simplifyIf(ifExpr *ast.IfExpression) ast.Node {
result := evalut.Eval(ifExpr.Condition, tempEnv)
if result.Type == value.ValBool && !o.hasVariables(ifExpr.Condition) {
if result.Bool {
return ifExpr.Consequence
} else {
return ifExpr.Else
}
}
return ifExpr
}
То есть если условие всегда истинно или всегда ложно, мы просто заменяем весь if на одну из его веток. В рантайме интерпретатор даже не увидит, что там был какой-то выбор. С циклами аналогично: если условие заведомо ложно, цикл превращается в пустой блок.
removeDeadCode (удаление мёртвого кода)
Здесь всё просто. Если код никогда не достижим (например, после return или внутри условия, которое всегда false), он удаляется.
optimizeCollections (оптимизация списков)
Представьте, что вы заполняете список в цикле:
arr = []
for i = 1, 1000000:
push(arr, 42)
end
Вместо того чтобы выполнять миллион итераций, оптимизатор замечает этот паттерн и превращает его в одно действие:
arr = repeat(42, 1000000)
Как это реализовано:
func (o *Optimizer) optimizeListCreation(forStmt *ast.ForStatement) ast.Node {
if len(forStmt.Body.Statements) == 1 {
call, ok := forStmt.Body.Statements[0].(*ast.CallExpression)
if ok && call.Function.Value == "push" {
count := endVal.Value - startVal.Value + 1
return &ast.CallExpression{
Function: &ast.Identifier{Value: "repeat"},
Arguments: []ast.Expression{value, &ast.IntegerLiteral{Value: count}},
}
}
}
return forStmt
}
Сложность падает с O(n) до O(1). Вот это я называю оптимизацией!
foldArithmeticProgression (сворачивание арифметических прогрессий)
Если вы в цикле считаете сумму чисел от 1 до N, зачем гонять процессор через все итерации? Формула Гаусса была придумана не зря.
Было:
sum = 0
for i = 1, 1000000:
sum = sum + i
end
Стало:
sum = 500000500000
Интерпретатор даже не увидит цикл - он получит готовое число.
mergeNestedLoop (объединение вложенных циклов)
Вложенные циклы - это боль. Особенно когда они оба итерируются по константам.
Было:
for i = 1, 1000:
for j = 1, 1000:
sum = sum + j
end
end
Стало:
for j = 1, 1000000:
sum = sum + j
end
Реализация:
func (o *Optimizer) mergeNestedLoop(outerLoop *ast.ForStatement) ast.Node {
innerLoop := outerLoop.Body.Statements[0].(*ast.ForStatement)
outerCount := outerEnd - outerStart + 1
innerCount := innerEnd - innerStart + 1
totalCount := outerCount * innerCount
newCondition := &ast.InfixExpression{
Left: &ast.Identifier{Value: innerLoop.Initialization.Name.Value},
Operator: "<=",
Right: &ast.IntegerLiteral{Value: totalCount},
}
innerLoop.Condition = newCondition
return innerLoop
}
Вместо миллиона итераций получаем… ну, технически всё ещё миллион, но с одним циклом вместо двух. На практике это даёт прирост за счёт уменьшения накладных расходов на переходы между циклами.
inlineFunctionCalls (инлайнинг функций)
Вызов функции - это дорого. Особенно если функция маленькая и вызывается часто. Инлайнинг заменяет вызов функции на её тело.
Было:
funct add(a, b):
return a + b
end
add(5, 3)
Стало:
return 5 + 3
А потом в дело вступает свёртка констант, и мы получаем:
return 8
В результате интерпретатор даже не знает, что в коде была функция - он просто выполняет её тело как обычные инструкции. Прирост скорости может быть огромным, особенно в циклах.
removeEmptyFunctions (Удаление пустых функций)
Всё просто: если функция внутри пустая, она удаляется.
funct empty():
end
Такую функцию просто вырезаем из программы. Зачем хранить то, что не делает ничего полезного?
Это всё даёт максимальную скорость! Но из-за этого мой оптимизатор может перед началом притормозить запуск скрипта, чтобы всё посчитать, оптимизировать и так далее. Все эти оптимизации работают не по отдельности, а каскадом. Сначала инлайнинг, потом свёртка констант, потом удаление мёртвого кода, потом оптимизация циклов.
P.S. Он всё считает и оптимизирует ДО начала запуска кода.
Результаты бенчмарков
И теперь мы подошли к самому главному - бенчмаркам.
Бенчмарк 1:
funct main():
n = 10000000
start = get_time()
a = 1
b = 2
sum = 0
for i = 1, n:
sum = sum + a * b + i
end
print(sum)
stop = get_time()
print("Time: " + (stop - start) + " sec")
end
main()
Терминал:
50000025000000
Time: 0 sec
Бенчмарк 2:
funct main():
n = 1000000
start = get_time()
sum = 0
for i = 1, n:
sum = sum + i
end
print(sum)
stop = get_time()
print("Time: " + (stop - start) + " sec")
end
main()
Терминал:
500000500000
Time: 0 sec
Бенчмарк 3:
funct main():
n = 1000
start = get_time()
sum = 0
for i = 1, n:
for j = 1, n:
sum = sum + i * j
end
end
print(sum)
stop = get_time()
print("Time: " + (stop - start) + " sec")
end
main()
Терминал:
250500250000
Time: 0 sec
Бенчмарк 4:
funct main():
n = 1000
start = get_time()
a = 0
b = 0
c = 0
for i = 1, n:
for j = 1, n:
a = i + j
b = i * j
c = a + b
end
end
print(c)
stop = get_time()
print("Time: " + (stop - start) + " sec")
end
main()
Терминал:
1002000
Time: 0 sec
Да, все бенчмарки показывают 0 секунд. Это не потому, что интерпретатор супербыстрый, а потому что оптимизатор вырезал все циклы ещё до запуска.
Я рассказал почти всё о своём языке. Больше можно узнать в README в моём репозитории GitHub. А также мой язык унаследовал несколько функций из Go (например, многопоточность, +Inf / -Inf, NaN).
Надеюсь, вы оцените мой проект.
К версии 0.0.3 я хочу добавить:
Импорт соседних файлов.
Импорт библиотек.
Встроенные библиотеки.
Сделать стабильнее.
Добавить значение Null.