Язык выражений (DSL): оптимизации AST и виртуальная машина
опубликовано: ⏰ 19В прошлой статье показывал пример простого DSL для расчёта формулы и фильтра для запросов. Для более сложных сценариев требуется расширенный синтаксис, применение определённых техник оптимизации и простая VM. Об этом далее.
Введение
Простого интерпретатора формул достаточно для базовых вычислений, но реальные задачи требуют большего: условной логики, возможности комбинировать выражения в блоки, работы с разными типами данных и, что критично, высокой производительности. Основная цель – создание языка выражений с синтаксисом и фичами под конкретный проект. Также необходима поддержка компиляции в нативное представление (GraalVM), то есть генерация байткода и использование рефлексии запрещено и не используется. При этом необходимо сохранить максимальную производительность, близкую к нативной, насколько это возможно.
Нагружать статью всем кодом в этот раз не стану, так как он теперь довольно объёмный. Вместо него будет упрощённый псевдокод.
Что приведу в качестве примера:
- Расширенную грамматику с блоками({…}), условными конструкциями и тернарным оператором.
- Систему типов с безопасным приведением значений.
- Конвейер из 8 проходов оптимизаций AST с фиксированной точкой сходимости.
- Стековую виртуальную машину для устранения накладных расходов рекурсивного обхода дерева.
Грамматика
Расширенный язык выражений поддерживает арифметику, сравнения, логические операции, условные конструкции и вызовы функций. Формальное описание в виде BNF:
<expression> → <block> EOF
| <ternary-expression> EOF
<or-expression> → <and-expression> ("||" <and-expression>)*
<and-expression> → <equality-expression> ("&&" <equality-expression>)*
<ternary-expression> → <or-expression> ("?" <or-expression> ":" <ternary-expression>)?
<equality-expression> → <relational-expression> (("==" | "!=") <relational-expression>)*
<relational-expression> → <additive-expression> (("<" | ">" | "<=" | ">=") <additive-expression>)?
<additive-expression> → <multiplicative-expression> (("+" | "-") <multiplicative-expression>)*
<multiplicative-expression> → <unary-expression> (("*" | "/" | "%") <unary-expression>)*
<unary-expression> → ("-" | "!") <unary-expression>
| <if-else-expression>
<if-else-expression> → <member-access>
| "if" "(" <expression-inner> ")" <block> ("else" (<block> | <if-else-expression>))?
<member-access> → <primary> ("." <member-segment>)*
<grouped-expression>→ "(" <expression-inner> ")"
<primary> → <grouped-expression>
| <function-call>
| <ref-expression>
| <number>
| <string-literal>
| "true" | "false"
| "null"
| <identifier>
<ref-expression> → "ref" <string-literal>
<member-segment> → <identifier> ("(" [<expression-inner> ("," <expression-inner>)*] ")")?
<function-call> → <identifier> "(" [<expression-inner> ("," <expression-inner>)*] ")"
<block> → "{" (<block-item>+ | <expression-inner>) "}"
<block-item> → <if-else-expression> ";"?
| "return" <expression-inner> ";"
| <expression-inner> ";"
<expression-inner> → <ternary-expression>
<number> → <digit>+ ["." <digit>+ ] ([eE] [-|+] <digit>+)?
<string-literal> → '"' <chars> '"' | '\'' <chars> '\''
<identifier> → [a-zA-Z_] [a-zA-Z0-9_]*Точка входа – либо одиночное выражение, либо блок { ... }. Блоки позволяют объединять несколько инструкций, разделённых точкой с запятой. Внутри блока return expr; инициирует ранний выход.
Приоритет операторов
| Приоритет | Операторы | Ассоциативность |
|---|---|---|
| 1 | || | левая |
| 2 | && | левая |
| 3 | ? : | правая |
| 4 | ==, != | левая |
| 5 | <, >, <=, >= | бинарная |
| 6 | +, - | левая |
| 7 | *, /, % | левая |
| 8 | -, ! (унарные) | правая |
Примеры выражений
// Простое арифметическое выражение
2 * x + y / 3.14
// Условная логика с тернарным оператором
status == "active" ? price * discount : price
// Блок с if/else и ранним возвратом
{
if (count > 0) {
return total / count;
} else {
return 0;
}
}
// Цепочка условий через else if
if (level == "high") {
priority = 1;
} else if (level == "medium") {
priority = 2;
} else {
priority = 3;
}
// Вызов функции с доступом к полям объекта
statistics.probeBytesPerSecond * duration / 1024.0Система типов
Все значения в языке выражений оборачиваются в ExpressionValue – единый тип-обёртка, обеспечивающий безопасную работу с данными разных типов:
| Тип | Описание |
|---|---|
| BOOL | Логическое значение |
| INT8..64 | Целочисленные (8/16/32/64 бита) |
| FLOAT32 | Число с плавающей точкой одинарной точности |
| FLOAT64 | Число с плавающей точкой двойной точности |
| STRING | Строковое значение |
| NULL | Пустое значение |
| VOID | Отсутствие результата (для блоков без return) |
| OBJECT | Произвольный объект Java |
Два режима доступа к значению:
// Безопасное приведение -- возвращает значение по умолчанию при несовпадении типа
double d = value.toDouble(0.0); // 0.0 если значение не числовое
String s = value.toString(""); // "" если значение null или void
// Строгий доступ -- выбрасывает исключение при несовпадении типа
int i = value.asInt32(); // ошибка, если тип не INT*
boolean b = value.asBoolean(); // ошибка, если тип не BOOLАрифметические операции автоматически приводят значения к FLOAT64 для упрощения. Операторы сравнения (< > <= >=) работают только с числовыми значениями. Равенство (== !=) поддерживает межтиповое сравнение со специальной семантикой для null.
Узлы AST
Подход очень похож на тот, который описывался в предыдущей статье. Компилятор строит дерево из нескольких типов узлов:
| Класс узла | Описание |
|---|---|
NumberNode | Числовой литерал |
StringNode | Строковый литерал |
BooleanNode | Булевый литерал (true/false) |
NullNode | Литерал null |
VariableNode | Ссылка на переменную |
RefNode | Ссылка на объект по строковому ключу (ref "key") |
BinaryOpNode | Бинарный оператор |
UnaryOpNode | Унарный оператор (-, !) |
TernaryNode | Тернарное условие (? :) |
IfElseNode | Блочная конструкция if/else |
FunctionCallNode | Вызов функции |
SwitchNode | Оптимизированный switch (из цепочки тернариев) |
BlockNode | Блок выражений |
ReturnNode | Ранний выход из блока |
Каждый узел реализует интерфейс evaluate(ExpressionContext ctx), который возвращает ExpressionValue. Пример структуры дерева для выражения if (x > 10) { return x * 2; } else { return 0; }:
BlockNode
└── IfElseNode
├── condition: BinaryOpNode(>, VariableNode("x"), NumberNode(10))
├── thenBody: BlockNode
│ └── ReturnNode → BinaryOpNode(*, VariableNode("x"), NumberNode(2))
└── elseBody: BlockNode
└── ReturnNode → NumberNode(0)Конвейер оптимизаций AST
После построения дерева запускается конвейер оптимизаций. Ключевая идея – фиксированная точка сходимости (fixed-point): проходы выполняются циклически до тех пор, пока дерево не перестанет меняться структурно. По умолчанию 3 итерации, но цикл может завершиться раньше при стабилизации AST.
// Псевдокод оркестратора оптимизаций
Node optimize(Node ast, OptimizationOptions options) {
Node current = ast;
for (int i = 0; i < options.maxPasses; i++) {
Node previous = deepCopy(current);
// Применяем все включённые проходы последовательно
for (OptimizationPass pass : options.enabledPasses) {
current = pass.optimize(current);
}
// Проверяем структурное равенство -- если дерево не изменилось, выходим
if (AstComparator.equals(previous, current)) {
break;
}
}
return current;
}Обычно достаточно одного прохода. На своих тестовых примерах не видел большего числа итераций.
Каскадный эффект оптимизаций
Главная ценность фиксированной точки – каскадное выполнение итераций. Один проход может “подготавливать” AST для последующей оптимизации:
- Свёртка констант вычисляет
2 + 3→5, что превращает условиеif (2 + 3 > 4)вif (true) - Удаление ветвлений видит
if (true) { A } else { B }и заменяет на простоA - Удаление мёртвого кода убирает оставшиеся недостижимые ветви
Без циклического выполнения каждый проход работал бы только на исходном дереве, упуская возможности для дальнейших упрощений.
Проходы оптимизации
Свёртка констант (Constant Folding)
Вычисляет выражения из констант на этапе компиляции. Обрабатывает арифметические (+ - * / %), логические (&& ||) и сравнения (== != < > <= >=).
| Этап | Результат |
|---|---|
| Выражение | 2 + 3 * (4 + 6) / 5 + x * 10 + y * 0 |
| INITIAL AST | (((2.0 PLUS ((3.0 MUL (4.0 PLUS 6.0)) DIV 5.0)) PLUS (x MUL 10.0)) PLUS (y MUL 0.0)) |
| Pass 1 – CONSTANT_FOLDING | ((8.0 PLUS (x MUL 10.0)) PLUS (y MUL 0.0)) |
| Pass 1 – ALGEBRAIC_SIMPLIFY | (8.0 PLUS (x MUL 10.0)) |
| Pass 2 | no changes, fixed-point reached |
Константная часть 2 + 3 * (4 + 6) / 5 свёрнута в 8.0, а y * 0 удалён алгебраическим упрощением на той же итерации.
Алгебраическое упрощение (Algebraic Simplify)
Применяет математические упрощения: x*1 → x, x/1 → x, x+0 → x, x-0 → x, x*0 → 0, 0*x → 0.
| Этап | Результат |
|---|---|
| Выражение | a * 1 + b * 0 + c - 0 + v / 1 + w * 1 |
| INITIAL AST | (((((a MUL 1.0) PLUS (b MUL 0.0)) PLUS c) MINUS 0.0) PLUS (v DIV 1.0)) PLUS (w MUL 1.0)) |
| Pass 1 – ALGEBRAIC_SIMPLIFY | (((a PLUS c) PLUS v) PLUS w) |
| Pass 2 | no changes, fixed-point reached |
Одно прохождение значительно сократило количество узлов в дереве.
Короткое замыкание (Short Circuit)
Сворачивает логические выражения с известным результатом. Для &&: если левый операнд false → всё выражение false; если true → правая часть. Для ||: если левый операнд true → всё выражение true; если false → правая часть.
| Этап | Результат |
|---|---|
| Выражение | false && x > y || true && a < b || false && z != w |
| INITIAL AST | (((false AND (x GT y)) OR (true AND (a LT b))) OR (false AND (z NEQ w))) |
| Pass 1 – ALGEBRAIC_SIMPLIFY | (((false AND (x GT y)) OR (a LT b)) OR (false AND (z NEQ w))) |
| Pass 1 – DEAD_CODE | ((false OR (a LT b)) OR false) |
| Pass 1 – SHORT_CIRCUIT + DEAD_BRANCH | (((a LT b) ? true : false) ? true : false) |
| Pass 2 | no changes, fixed-point reached |
Удаление ветвлений (Dead Branch)
Убирает недостижимые ветви в условных конструкциях.
| Этап | Результат |
|---|---|
| Выражение | {if (true) {return 42;} if (false) {return x + y;} return z;} |
| INITIAL AST | {if(true){{return 42.0}}; if(false){{return (x PLUS y)}}; return z} |
| Pass 1 – CONSTANT_FOLDING | {{return 42.0}; null; return z} |
| Pass 1 – DEAD_CODE | {{return 42.0}} |
| Pass 2 | no changes, fixed-point reached |
Свёртка констант превращает if(true) в заведомо истинную ветвь и if(false) в null. Удаление мёртвого кода убирает недостижимые инструкции после раннего возврата. Итог: блок из трёх инструкций → одна.
Таблица сравнений (Switch Table)
Преобразует последовательные проверки на равенство одного выражения. Условие конвертации: все условия должны быть сравнениями == на один и тот же операнд (c). Switch-узел компилируется в серию DUP/EQ/TERNARY_BRANCH с общим дискриминантом.
| Этап | Результат |
|---|---|
| Выражение | {if (c == 1) {return a + b;} else if (c == 2) {return a - b;} else if (c == 3) {return a * b;} else if (c == 4) {return a / b;} else if (c == 5) {return x + y;} return z;} |
| INITIAL AST | {if((c EQ 1.0)){{return(a PLUS b)}}else{if((c EQ 2.0)){{return(a MINUS b)}}else{...}}}; return z} |
| Pass 1 – SWITCH_TABLE | {switch(c){case 1.0:{return(a PLUS b)} case 2.0:{return(a MINUS b)} ... default:null}; return z} |
| Pass 2 | no changes, fixed-point reached |
Распространение констант (Constant Propagation)
Подставляет известные значения переменных в выражения.
| Этап | Результат |
|---|---|
| Выражение | (x + 5) - 5 + (y * 2) / 2 + (z - 3) + 3 |
| INITIAL AST | (((((x PLUS 5.0) MINUS 5.0) PLUS ((y MUL 2.0) DIV 2.0)) PLUS (z MINUS 3.0)) PLUS 3.0) |
| Pass 1 – CONSTANT_PROPAGATION | (((x PLUS y) PLUS (z MINUS 3.0)) PLUS 3.0) |
| Pass 2 | no changes, fixed-point reached |
(x+5)-5 → x, (y*2)/2 → y. Оставшаяся часть (z-3)+3 не свёрнута на первой итерации, но может быть обработана в последующих проходах при наличии дополнительных правил.
Устранение общих подвыражений (Common Subexpression)
Обнаруживает повторяющиеся вычисления и преобразует их через распределительный закон.
| Этап | Результат |
|---|---|
| Выражение | (x + y) * z + (x + y) * w + (a * b) / c + (a * b) * v |
| INITIAL AST | (((((x PLUS y) MUL z) PLUS ((x PLUS y) MUL w)) PLUS ((a MUL b) DIV c)) PLUS ((a MUL b) MUL v)) |
| Pass 1 – COMMON_SUBEXPRESSION | ((((x PLUS y) MUL (z PLUS w)) PLUS ((a MUL b) DIV c)) PLUS ((a MUL b) MUL v)) |
| Pass 2 | no changes, fixed-point reached |
(x+y)*z + (x+y)*w преобразовано в (x+y)*(z+w) через распределительный закон. Выражение (a*b) не объединено, так как операнды разные (/c и *v).
Удаление мёртвого кода (Dead Code)
Убирает инструкции, недостижимые после раннего возврата.
| Этап | Результат |
|---|---|
| Выражение | {if (true) {return 42;} if (false) {return x + y;} return z;} |
| После CONSTANT_FOLDING + DEAD_CODE | {{return 42.0}} |
if(false) заменён на null, а return z удалён как недостижимый код после блока с безусловным возвратом. Особенно эффективен в сочетании с удалением ветвлений – когда недостижимые ветви удалены, остаются инструкции, которые никогда не выполняются.
Виртуальная машина
Рекурсивный обход AST через Node.evaluate() работает корректно, но накладные расходы на виртуальные вызовы Java накапливаются для деревьев с большой глубиной. Альтернатива – компиляция оптимизированного AST в последовательный набор кодом (IR) и выполнение её на VM.
Архитектура VM
В качестве самописной VM использую стековую машину с линейным выполнением инструкций. Все данные программы хранятся в отдельных массивах:
- байтовые теги (опкоды),
- int-операнды, пулы констант (
double[],String[],Object[]) - таблицы имён переменных и функций.
Стек выполнения – примитивный double[128] с дополнительным byte[128] для типов значений. Это исключает аллокацию объектов во время исполнения:
// Структура VM (на основе ExpressionVm.java)
class ExpressionVm {
byte[] tags; // опкоды инструкций (0–28)
int[] operands; // операнд для каждой инструкции
double[] constants; // пул числовых констант
String[] strings; // пул строк-литералов
Object[] objects; // пул объектов (для ref-выражений)
String[] varNames; // таблица имён переменных → индекс для LOAD_VAR
String[] fnNames; // таблица имён функций → индекс для CALL_FN
double[] stack = new double[128]; // стек значений
byte[] types = new byte[128]; // типы элементов стека
// Inline-кэш: переиспользует resolved-переменные при повторном вызове с тем же контекстом
ExpressionContext cachedCtx;
double[] cachedVarValues;
byte[] cachedVarTypes;
}Типы значений в стеке кодируются байтами: T_DOUBLE=0, T_BOOL=1, T_STRING=2, T_NULL=3, T_VOID=4, T_OBJECT=5.
Набор инструкций
Все опкоды – байтовые константы (0–28), что позволяет использовать прямой switch-dispatch без enum-оверхеда. Инструкции сгруппированы по категориям:
| Категория | Опкоды |
|---|---|
| Литералы | PUSH_DOUBLE, PUSH_BOOL, PUSH_NULL, PUSH_STRING, PUSH_OBJ |
| Переменные | LOAD_VAR |
| Стек | DUP, POP |
| Арифметика | ADD (+конкатенация строк), SUB, MUL, DIV, MOD |
| Сравнение | EQ, NEQ, LT, GT, LTE, GTE |
| Логика | AND, OR, NOT, NEG |
| Ветвления | TERNARY_BRANCH, JUMP |
| Функции | CALL_FN (операнд: fnIdx << 16 | argCount) |
| Возврат и блок | RETURN_VALUE, STRING_CONCAT, BLOCK_END |
Компиляция AST в байткод
Внутренний класс Compiler обходит оптимизированное дерево и генерирует инструкции, поддерживая пулы констант, строк, имён переменных и функций:
// Псевдокод компилятора (на основе ExpressionVm.Compiler)
class Compiler {
List<Integer> tags; // последовательность опкодов
List<Integer> operands; // операнды
Map<Double, Integer> constantPool; // пул чисел → индекс
Map<String, Integer> stringPool; // пул строк → индекс
Map<ObjectValue, Integer> objectPool; // пул объектов (ref) → индекс
Map<String, Integer> varPool; // имена переменных → индекс
Map<String, Integer> fnPool; // имена функций → индекс
void emit(Node node) {
if (node instanceof NumberNode nn) {
tags.add(PUSH_DOUBLE);
operands.add(getConstantIndex(nn.getValue()));
} else if (node instanceof VariableNode vn) {
tags.add(LOAD_VAR);
operands.add(getVarIndex(vn.getName()));
} else if (node instanceof BinaryOpNode bin) {
emit(bin.getLeft());
emit(bin.getRight());
tags.add(mapToOpcode(bin.getOp())); // ADD, SUB, EQ и т.д.
operands.add(0);
} else if (node instanceof TernaryNode tern) {
emitTernary(tern);
} else if (node instanceof FunctionCallNode fc) {
for (var arg : fc.getArguments()) emit(arg);
int fnIdx = getFnIndex(fc.getName());
tags.add(CALL_FN);
operands.add((fnIdx << 16) | (fc.getArguments().length & 0xFFFF));
} else if (node instanceof ReturnNode rn) {
emit(rn.getExpression());
tags.add(RETURN_VALUE);
operands.add(0);
}
// ... остальные узлы: BooleanNode→PUSH_BOOL, StringNode→PUSH_STRING,
// NullNode→PUSH_NULL, RefNode→PUSH_OBJ, IfElseNode, BlockNode, SwitchNode
}
void emitTernary(TernaryNode tern) {
emit(tern.getCondition());
int branchIdx = operands.size();
tags.add(TERNARY_BRANCH);
operands.add(-1); // заглушка
emit(tern.getTrueBranch());
int jumpIdx = operands.size();
tags.add(JUMP);
operands.add(-1); // заглушка
int falseStart = tags.size();
operands.set(branchIdx, falseStart); // патчим переход
emit(tern.getFalseBranch());
operands.set(jumpIdx, tags.size()); // патчим jump к концу
}
}Ключевой момент – подмена адресов переходов. При генерации TERNARY_BRANCH целевой PC ещё неизвестен, поэтому ставится заглушка -1, которая заполняется реальным индексом после компиляции then-ветви.
Inline cache
Для ускорения доступа к переменным VM использует inline cache, основанный на соглашении, что контекст не меняется:
// Псевдокод (на основе ExpressionVm.execute)
ExpressionValue execute(ExpressionContext ctx) {
if (cacheValid && ctx == cachedCtx) {
// Тот же объект контекста -- переиспользуем resolved-переменные, пропускаем HashMap
varValues = cachedVarValues;
varTypes = cachedVarTypes;
} else {
// Разрешаем все переменные один раз через HashMap → массив
for (int i = 0; i < varNames.length; i++) {
ExpressionValue v = ctx.getVariable(varNames[i]);
switch (v.getType()) {
case BOOL:
varValues[i] = v.asBoolean() ? 1.0 : 0.0;
varTypes[i] = T_BOOL;
break;
case STRING:
int sIdx = indexOfString(v.asString());
if (sIdx < 0) sIdx = addDynamicString(v.asString());
varValues[i] = (double) sIdx;
varTypes[i] = T_STRING;
break;
// ... NULL, VOID, OBJECT -- аналогично маппинг в тип стека + индекс пула
default:
varValues[i] = v.toDouble();
varTypes[i] = T_DOUBLE;
}
}
cachedCtx = ctx;
cachedVarValues = varValues;
cachedVarTypes = varTypes;
cacheValid = true;
}
}Переменные индексируются один раз в начале выполнения, затем все обращения идут через прямой доступ к массиву по индексу (LOAD_VAR). При повторном вызове с тем же объектом контекста индексированные переменные переиспользуются.
Выполнение
Цикл выполнения VM – линейный обход инструкций без рекурсии. Стек – примитивные double[] + byte[] для типов, без аллокации объектов. Что-то похожее когда-то делал на C++, но с ассемблерными вставками для ускорения. Здесь чистая Java.
// Псевдокод (на основе ExpressionVm.execute)
ExpressionValue execute(ExpressionContext ctx) {
int sp = 0; // stack pointer
int pc = 0; // program counter
while (pc < tags.length) {
switch (tags[pc]) {
case PUSH_DOUBLE:
stack[sp] = constants[operands[pc]];
types[sp] = T_DOUBLE;
sp++;
pc++;
break;
case LOAD_VAR: {
int vi = operands[pc]; // индекс переменной в resolved-массиве
stack[sp] = varValues[vi];
types[sp] = varTypes[vi];
sp++;
pc++;
break;
}
case ADD: {
int tb = --sp, ta = --sp;
if (types[tb] == T_STRING && types[ta] == T_STRING) {
// Конкатенация строк через индексы в string pool с дедупликацией
String concat = getStringAt((int) stack[ta]) + getStringAt((int) stack[tb]);
int idx = indexOfString(concat);
if (idx < 0) idx = addDynamicString(concat);
stack[sp] = (double) idx;
types[sp] = T_STRING;
} else {
stack[sp] = stack[ta] + stack[tb];
types[sp] = T_DOUBLE;
}
sp++;
pc++;
break;
}
// ... SUB, MUL, DIV, MOD -- аналогичный шаблон: pop два операнда → операция → push результат
// ... EQ, NEQ, LT, GT, LTE, GTE -- сравнение с учётом типов (NULL, VOID, строки, объекты)
// ... AND, OR, NOT, NEG -- логические операции
case TERNARY_BRANCH: {
--sp; // pop condition
if (stack[sp] == 0.0) {
pc = operands[pc]; // переход к else-ветви
} else {
pc++; // продолжаем к then-ветви
}
break;
}
case JUMP:
pc = operands[pc];
break;
case CALL_FN: {
int encoded = operands[pc];
int fnIdx = encoded >>> 16;
int argCount = encoded & 0xFFFF;
// Снимаем аргументы со стека в обратном порядке (LIFO)
ExpressionValue[] args = new ExpressionValue[argCount];
for (int i = argCount - 1; i >= 0; i--) {
int idx = --sp;
args[i] = toFormulaValue(stack[idx], types[idx]);
}
ExpressionValue result = ctx.findFunction(fnNames[fnIdx]).call(args);
// Маппинг результата в тип стека (BOOL→1.0/0.0, STRING→index пула, и т.д.)
pushResult(result, sp); // см. ExpressionVm.java:551-583
pc++;
break;
}
case RETURN_VALUE: {
ExpressionValue ret = toFormulaValue(stack[sp - 1], types[sp - 1]);
ctx.setReturn(ret); // устанавливаем return-значение для раннего выхода из блока
return ret;
}
}
}
// Если выполнение дошло до конца без RETURN -- возвращаем верхний элемент стека
return toFormulaValue(stack[sp - 1], types[sp - 1]);
}Отсутствие рекурсии устраняет накладные расходы на создание фреймов вызова и снижает потребление памяти для глубоких деревьев. Примитивный стек double[] исключает аллокацию объектов при каждом вычислении.
Бенчмарки производительности
Для оценки эффективности оптимизаций и VM используются JMH-бенчмарки с пятью паттернами выражений. Конфигурация: 3 warmup + 5 measurement, 3 fork, -Xms256m -Xmx256m.
Сравниваются режимы:
| Режим | Описание |
|---|---|
native | Нативный Java-код (референс) |
ast | Оценка AST с оптимизациями |
ast_no_opt | Оценка AST без оптимизаций |
vm | VM байткода с оптимизациями |
vm_no_opt | VM без оптимизаций |
Тестовые выражения:
| Имя | Выражение |
|---|---|
simpleArithmetic | 2 + 3 * (4 * 5) – все константы, полностью сворачивается |
variableArithmetic | (x + y) * z - w / v – переменные, нет констант для фолдинга |
complexOptimizable | 2 + 3*(4+6)/5 + (x+y)*z + (x+y)*w + a*1 + b*0 + (x+5)-5 – множество оптимизируемых паттернов |
simpleConditional | {if (x > 5) {return 10;} return 20;} – условие с переменной |
complexConditional | if/else-if цепочка на c==1..5, каждая ветвь возвращает арифметику |
Результаты (ns/op, ниже – лучше)
| Выражение | native | ast | ast_no_opt | vm | vm_no_opt |
|---|---|---|---|---|---|
simpleArithmetic | 2.713 | 3.322 | 34.990 | 14.023 | 22.527 |
variableArithmetic | 2.686 | 61.847 | 64.015 | 26.654 | 27.958 |
complexOptimizable | 2.691 | 166.360 | 278.465 | 52.729 | 88.356 |
simpleConditional | 3.123 | 27.465 | 28.536 | 21.798 | 22.973 |
complexConditional | 3.203 | 39.334 | 91.709 | 63.386 | 49.873 |
Свёртка констант даёт максимальный выигрыш. На simpleArithmetic (2 + 3 * (4 * 5)) оптимизации сворачивают всё выражение в единственную константу 62. В результате VM – это один PUSH_DOUBLE, и режим AST (3.3 ns/op) практически догоняет нативный код (2.7 ns/op). Без оптимизаций (ast_no_opt) каждое выполнение проходит через полный обход дерева из 8 узлов – 35 ns/op, разница в 10x.
Переменные – это узкое место AST. На variableArithmetic режим AST (61.8 ns/op) почти не выигрывает от оптимизаций (64.0 ns/op без них), так как нет констант для свёртки, а виртуальные вызовы Node.evaluate() на каждом узле дерева создают значительные накладные расходы. VM (26.7 ns/op) в 2.3x быстрее AST за счёт линейного выполнения и примитивного стека.
Сложные выражения. complexOptimizable содержит константные подвыражения (a*1, b*0, (x+5)-5), общие подвыражения ((x+y) встречается дважды) и алгебраические тождества. Оптимизации сокращают дерево, но оставшиеся переменные делают AST дорогой (166 ns/op). VM справляется лучше (52.7 ns/op), а без оптимизаций оба режима резко деградируют: ast_no_opt – 278 ns/op, vm_no_opt – 88 ns/op.
VM стабильнее на условных конструкциях. На simpleConditional VM (21.8 ns/op) быстрее AST (27.5 ns/op), а оптимизации практически не влияют на результат (28.5 ns/op без них) – условие зависит от переменной, его нельзя свернуть.
Оптимизация цепочек условий. На complexConditional (цепочка if/else-if c==1..5) оптимизация таблицы переключений преобразует дерево в switch-узел, что ускоряет AST с 91.7 до 39.3 ns/op (2.3x). Но VM без оптимизаций (49.9 ns/op) всё ещё быстрее оптимизированного AST – линейное выполнение байткода компенсирует отсутствие switch-оптимизации.
Заключение
Что по итогу. Если нужен свой язык выражений, то придётся делать оптимизации для ускорения и они действительно помогают. Самый большой буст – это конверсия AST в IR+VM. Хотя VM в некоторых сценариях и проигрывает AST, тут можно подумать над эвристиками на уровне интерпретатора для определения случаев, когда AST лучше выполнять без VM.