Expression Language (DSL): AST Optimizations and Virtual Machine
published: ⏰ 16In the previous article, I showed an example of a simple DSL for formula calculation and query filter. More complex scenarios require extended syntax, certain optimization techniques, and a lightweight VM. That’s what this article covers.
Introduction
A basic formula interpreter is enough for simple computations, but real-world tasks demand more: conditional logic, the ability to combine expressions into blocks, handling different data types, and, critically, high performance. The main goal is creating an expression language with syntax and features tailored to a specific project. It must also support native compilation (GraalVM), meaning bytecode generation and reflection are forbidden and not used. At the same time, we need to maintain maximum performance as close to native as possible.
I won’t overload this article with all the code this time, since it’s quite extensive now. Instead, I’ll use simplified pseudocode.
Here’s what I’ll cover:
- Extended grammar with blocks (
{...}), conditional constructs, and a ternary operator. - A type system with safe value casting.
- An 8-pass AST optimization pipeline with fixed-point convergence.
- A stack-based bytecode VM to eliminate the overhead of recursive tree traversal.
Grammar
The extended expression language supports arithmetic, comparisons, logical operations, conditional constructs, and function calls. The formal BNF description:
<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_]*The entry point is either a single expression or a block { ... }. Blocks allow grouping multiple statements separated by semicolons. Inside a block, return expr; triggers an early exit.
Operator Precedence
| Priority | Operators | Associativity |
|---|---|---|
| 1 | || | left |
| 2 | && | left |
| 3 | ? : | right |
| 4 | ==, != | left |
| 5 | <, >, <=, >= | binary |
| 6 | +, - | left |
| 7 | *, /, % | left |
| 8 | -, ! (unary) | right |
Expression Examples
// Simple arithmetic expression
2 * x + y / 3.14
// Conditional logic with ternary operator
status == "active" ? price * discount : price
// Block with if/else and early return
{
if (count > 0) {
return total / count;
} else {
return 0;
}
}
// Condition chain via else if
if (level == "high") {
priority = 1;
} else if (level == "medium") {
priority = 2;
} else {
priority = 3;
}
// Function call with object field access
statistics.probeBytesPerSecond * duration / 1024.0Type System
All values in the expression language are wrapped in ExpressionValue — a unified wrapper type that provides safe handling of different data types:
| Type | Description |
|---|---|
| BOOL | Boolean value |
| INT8..64 | Integer (8/16/32/64 bit) |
| FLOAT32 | Single-precision floating-point number |
| FLOAT64 | Double-precision floating-point number |
| STRING | String value |
| NULL | Null value |
| VOID | No result (for blocks without return) |
| OBJECT | Arbitrary Java object |
Two modes of value access:
// Safe casting -- returns default value on type mismatch
double d = value.toDouble(0.0); // 0.0 if the value is not numeric
String s = value.toString(""); // "" if the value is null or void
// Strict access -- throws exception on type mismatch
int i = value.asInt32(); // error if type is not INT*
boolean b = value.asBoolean(); // error if type is not BOOLArithmetic operations automatically cast values to FLOAT64 for simplicity. Comparison operators (< > <= >=) work only with numeric values. Equality (== !=) supports cross-type comparison with special semantics for null.
AST Nodes
The approach is very similar to the one described in the previous article. The compiler builds a tree from several node types:
| Node Class | Description |
|---|---|
NumberNode | Numeric literal |
StringNode | String literal |
BooleanNode | Boolean literal (true/false) |
NullNode | Null literal |
VariableNode | Variable reference |
RefNode | Object reference by string key (ref "key") |
BinaryOpNode | Binary operator |
UnaryOpNode | Unary operator (-, !) |
TernaryNode | Ternary condition (? :) |
IfElseNode | Block if/else construct |
FunctionCallNode | Function call |
SwitchNode | Optimized switch (from ternary chain) |
BlockNode | Expression block |
ReturnNode | Early exit from block |
Each node implements the evaluate(ExpressionContext ctx) interface, which returns an ExpressionValue. Example tree structure for 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 Optimization Pipeline
After the tree is built, an optimization pipeline runs. The key idea is fixed-point convergence: passes execute cyclically until the tree stops changing structurally. By default, 3 iterations, but the loop may terminate earlier upon AST stabilization.
// Pseudocode of optimization orchestrator
Node optimize(Node ast, OptimizationOptions options) {
Node current = ast;
for (int i = 0; i < options.maxPasses; i++) {
Node previous = deepCopy(current);
// Apply all enabled passes sequentially
for (OptimizationPass pass : options.enabledPasses) {
current = pass.optimize(current);
}
// Check structural equality -- if tree hasn't changed, exit
if (AstComparator.equals(previous, current)) {
break;
}
}
return current;
}Usually one pass is enough. I haven’t seen more iterations in my test cases.
Cascading Optimization Effect
The main value of fixed-point iteration is cascading execution. One pass can “prepare” the AST for a subsequent optimization:
- Constant folding evaluates
2 + 3→5, turningif (2 + 3 > 4)intoif (true) - Dead branch elimination sees
if (true) { A } else { B }and replaces it with justA - Dead code removal cleans up remaining unreachable branches
Without cyclic execution, each pass would only work on the original tree, missing opportunities for further simplification.
Optimization Passes
Constant Folding
Evaluates constant expressions at compile time. Handles arithmetic (+ - * / %), logical (&& ||), and comparison operators (== != < > <= >=).
| Stage | Result |
|---|---|
| Expression | 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 |
The constant part 2 + 3 * (4 + 6) / 5 is folded to 8.0, and y * 0 is removed by algebraic simplification on the same iteration.
Algebraic Simplify
Applies mathematical simplifications: x*1 → x, x/1 → x, x+0 → x, x-0 → x, x*0 → 0, 0*x → 0.
| Stage | Result |
|---|---|
| Expression | 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 |
A single pass significantly reduced the number of nodes in the tree.
Short Circuit
Collapses logical expressions with a known result. For &&: if left operand is false → entire expression is false; if true → right side. For \|\|: if left operand is true → entire expression is true; if false → right side.
| Stage | Result |
|---|---|
| Expression | 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 Elimination
Removes unreachable branches in conditional constructs.
| Stage | Result |
|---|---|
| Expression | {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 |
Constant folding turns if(true) into a guaranteed-true branch and if(false) into null. Dead code removal eliminates unreachable instructions after an early return. Result: three statements reduced to one.
Switch Table
Transforms sequential equality checks on the same expression. Conversion condition: all conditions must be == comparisons against the same operand (c). The switch node compiles to a series of DUP/EQ/TERNARY_BRANCH with a shared discriminant.
| Stage | Result |
|---|---|
| Expression | {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
Substitutes known variable values into expressions.
| Stage | Result |
|---|---|
| Expression | (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. The remaining part (z-3)+3 is not folded on the first iteration but may be handled in subsequent passes with additional rules.
Common Subexpression Elimination
Detects repeated computations and transforms them using the distributive law.
| Stage | Result |
|---|---|
| Expression | (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 is transformed to (x+y)*(z+w) via the distributive law. The expression (a*b) is not combined because the operands differ (/c and *v).
Dead Code Removal
Removes instructions unreachable after an early return.
| Stage | Result |
|---|---|
| Expression | {if (true) {return 42;} if (false) {return x + y;} return z;} |
| After CONSTANT_FOLDING + DEAD_CODE | {{return 42.0}} |
if(false) is replaced with null, and return z is removed as unreachable code after a block with an unconditional return. Especially effective in combination with dead branch elimination — once unreachable branches are removed, remaining instructions that never execute can be cleaned up.
Bytecode Virtual Machine
Recursive AST traversal via Node.evaluate() works correctly, but the overhead of Java virtual calls accumulates for deeply nested trees. The alternative is compiling the optimized AST into a linear bytecode (IR) program and executing it with a stack-based VM.
VM Architecture
As a custom VM, I use a stack machine with linear instruction execution. The program data are stored in arrays:
- byte tags (opcodes),
- int operands, constant pools (
double[],String[],Object[]), - variable and function name tables.
The execution stack is a primitive double[128] with an additional byte[128] for value types. This eliminates object allocation during execution:
// VM structure (based on ExpressionVm.java)
class ExpressionVm {
byte[] tags; // instruction opcodes (0–28)
int[] operands; // operand for each instruction
double[] constants; // numeric constant pool
String[] strings; // string literal pool
Object[] objects; // object pool (for ref expressions)
String[] varNames; // variable name table → index for LOAD_VAR
String[] fnNames; // function name table → index for CALL_FN
double[] stack = new double[128]; // value stack
byte[] types = new byte[128]; // stack element types
// Inline cache: reuses resolved variables on repeated calls with the same context
ExpressionContext cachedCtx;
double[] cachedVarValues;
byte[] cachedVarTypes;
}Stack value types are encoded as bytes: T_DOUBLE=0, T_BOOL=1, T_STRING=2, T_NULL=3, T_VOID=4, T_OBJECT=5.
Instruction Set
All opcodes are byte constants (0–28), allowing direct switch-dispatch without enum overhead. Instructions are grouped by category:
| Category | Opcodes |
|---|---|
| Literals | PUSH_DOUBLE, PUSH_BOOL, PUSH_NULL, PUSH_STRING, PUSH_OBJ |
| Variables | LOAD_VAR |
| Stack | DUP, POP |
| Arithmetic | ADD (+string concatenation), SUB, MUL, DIV, MOD |
| Comparison | EQ, NEQ, LT, GT, LTE, GTE |
| Logic | AND, OR, NOT, NEG |
| Branching | TERNARY_BRANCH, JUMP |
| Functions | CALL_FN (operand: fnIdx << 16 | argCount) |
| Return & Block | RETURN_VALUE, STRING_CONCAT, BLOCK_END |
AST to Bytecode Compilation
The inner Compiler class traverses the optimized tree and generates instructions, maintaining constant, string, variable name, and function pools:
// Compiler pseudocode (based on ExpressionVm.Compiler)
class Compiler {
List<Integer> tags; // opcode sequence
List<Integer> operands; // operands
Map<Double, Integer> constantPool; // number pool → index
Map<String, Integer> stringPool; // string pool → index
Map<ObjectValue, Integer> objectPool; // object (ref) pool → index
Map<String, Integer> varPool; // variable names → index
Map<String, Integer> fnPool; // function names → index
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, etc.
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);
}
// ... remaining nodes: 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); // placeholder
emit(tern.getTrueBranch());
int jumpIdx = operands.size();
tags.add(JUMP);
operands.add(-1); // placeholder
int falseStart = tags.size();
operands.set(branchIdx, falseStart); // patch branch target
emit(tern.getFalseBranch());
operands.set(jumpIdx, tags.size()); // patch jump to end
}
}The key point is branch address patching. When generating TERNARY_BRANCH, the target PC is not yet known, so a -1 placeholder is set and filled with the real index after compiling the then-branch.
Inline Cache
To speed up variable access, the VM uses an inline cache based on context object identity:
// Pseudocode (based on ExpressionVm.execute)
ExpressionValue execute(ExpressionContext ctx) {
if (cacheValid && ctx == cachedCtx) {
// Same context object -- reuse resolved variables, skip HashMap lookup
varValues = cachedVarValues;
varTypes = cachedVarTypes;
} else {
// Resolve all variables once via HashMap → array
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 -- similar mapping to stack type + pool index
default:
varValues[i] = v.toDouble();
varTypes[i] = T_DOUBLE;
}
}
cachedCtx = ctx;
cachedVarValues = varValues;
cachedVarTypes = varTypes;
cacheValid = true;
}
}Variables are resolved once at the start of execution via HashMap name lookup, then all subsequent accesses go through direct array index access (LOAD_VAR). On repeated calls with the same context object, the indexed variables are reused.
Execution
The VM execution loop is a linear instruction traversal without recursion. The stack uses primitive double[] + byte[] for types, with no object allocation. Something similar was done in C++ back in the day, but with assembly inline optimizations. Here it’s pure Java.
// Pseudocode (based on 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]; // variable index in resolved array
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 concatenation via string pool indices with deduplication
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 -- same pattern: pop two operands → operation → push result
// ... EQ, NEQ, LT, GT, LTE, GTE -- comparison with type awareness (NULL, VOID, strings, objects)
// ... AND, OR, NOT, NEG -- logical operations
case TERNARY_BRANCH: {
--sp; // pop condition
if (stack[sp] == 0.0) {
pc = operands[pc]; // jump to else-branch
} else {
pc++; // fall through to then-branch
}
break;
}
case JUMP:
pc = operands[pc];
break;
case CALL_FN: {
int encoded = operands[pc];
int fnIdx = encoded >>> 16;
int argCount = encoded & 0xFFFF;
// Pop arguments from stack in reverse order (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);
// Map result to stack type (BOOL→1.0/0.0, STRING→pool index, etc.)
pushResult(result, sp); // see ExpressionVm.java:551-583
pc++;
break;
}
case RETURN_VALUE: {
ExpressionValue ret = toFormulaValue(stack[sp - 1], types[sp - 1]);
ctx.setReturn(ret); // set return value for early block exit
return ret;
}
}
}
// If execution reaches the end without RETURN -- return top stack element
return toFormulaValue(stack[sp - 1], types[sp - 1]);
}The absence of recursion eliminates call frame overhead and reduces memory consumption for deep trees. The primitive double[] stack avoids object allocation on every computation.
Performance Benchmarks
To evaluate optimization and VM effectiveness, JMH benchmarks are used with five expression patterns. Configuration: 3 warmup + 5 measurement iterations, 3 forks, -Xms256m -Xmx256m.
Compared modes:
| Mode | Description |
|---|---|
native | Native Java code (reference) |
ast | AST evaluation with optimizations |
ast_no_opt | AST evaluation without optimizations |
vm | Bytecode VM with optimizations |
vm_no_opt | Bytecode VM without optimizations |
Test expressions:
| Name | Expression |
|---|---|
simpleArithmetic | 2 + 3 * (4 * 5) — all constants, fully foldable |
variableArithmetic | (x + y) * z - w / v — variables, no constants to fold |
complexOptimizable | 2 + 3*(4+6)/5 + (x+y)*z + (x+y)*w + a*1 + b*0 + (x+5)-5 — many optimizable patterns |
simpleConditional | {if (x > 5) {return 10;} return 20;} — condition with variable |
complexConditional | if/else-if chain on c==1..5, each branch returns arithmetic |
Results (ns/op, lower is better)
| Expression | 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 |
Constant folding gives the biggest win. On simpleArithmetic (2 + 3 * (4 * 5)), optimizations fold the entire expression into a single constant 62. The VM becomes one PUSH_DOUBLE, and AST mode (3.3 ns/op) nearly catches native code (2.7 ns/op). Without optimizations (ast_no_opt), each execution traverses a full tree of 8 nodes — 35 ns/op, a 10x difference.
Variables are the bottleneck for AST. On variableArithmetic, AST mode (61.8 ns/op) barely benefits from optimizations (64.0 ns/op without them), since there are no constants to fold and virtual calls to Node.evaluate() on every tree node create significant overhead. The VM (26.7 ns/op) is 2.3x faster than AST thanks to linear execution and a primitive stack.
Complex expressions. complexOptimizable contains constant subexpressions (a*1, b*0, (x+5)-5), common subexpressions ((x+y) appears twice), and algebraic identities. Optimizations shrink the tree, but remaining variables keep AST expensive (166 ns/op). The VM handles it better (52.7 ns/op), and without optimizations both modes degrade sharply: ast_no_opt — 278 ns/op, vm_no_opt — 88 ns/op.
VM is more stable on conditionals. On simpleConditional, the VM (21.8 ns/op) is faster than AST (27.5 ns/op), and optimizations have almost no effect (28.5 ns/op without them) — the condition depends on a variable and can’t be folded.
Condition chain optimization. On complexConditional (if/else-if chain c==1..5), switch table optimization transforms the tree into a switch node, speeding up AST from 91.7 to 39.3 ns/op (2.3x). But VM without optimizations (49.9 ns/op) is still faster than optimized AST — linear bytecode execution compensates for the lack of switch optimization.
Conclusion
Bottom line: if you need your own expression language, you’ll have to implement optimizations for speed, and they do help. The biggest boost comes from converting AST to IR+VM. Although the VM loses to AST in some scenarios, it’s worth considering interpreter-level heuristics to determine when AST execution is better without the VM.