Expression Language (DSL): AST Optimizations and Virtual Machine

published: ⏰ 16

In 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:

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_]*

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

PriorityOperatorsAssociativity
1||left
2&&left
3? :right
4==, !=left
5<, >, <=, >=binary
6+, -left
7*, /, %left
8-, ! (unary)right

Expression Examples

JavaScript
// 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.0

Type System

All values in the expression language are wrapped in ExpressionValue — a unified wrapper type that provides safe handling of different data types:

TypeDescription
BOOLBoolean value
INT8..64Integer (8/16/32/64 bit)
FLOAT32Single-precision floating-point number
FLOAT64Double-precision floating-point number
STRINGString value
NULLNull value
VOIDNo result (for blocks without return)
OBJECTArbitrary Java object

Two modes of value access:

Java
// 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 BOOL

Arithmetic 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 ClassDescription
NumberNodeNumeric literal
StringNodeString literal
BooleanNodeBoolean literal (true/false)
NullNodeNull literal
VariableNodeVariable reference
RefNodeObject reference by string key (ref "key")
BinaryOpNodeBinary operator
UnaryOpNodeUnary operator (-, !)
TernaryNodeTernary condition (? :)
IfElseNodeBlock if/else construct
FunctionCallNodeFunction call
SwitchNodeOptimized switch (from ternary chain)
BlockNodeExpression block
ReturnNodeEarly 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.

Java
// 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:

  1. Constant folding evaluates 2 + 3 → 5, turning if (2 + 3 > 4) into if (true)
  2. Dead branch elimination sees if (true) { A } else { B } and replaces it with just A
  3. 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 (== != < > <= >=).

StageResult
Expression2 + 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 2no 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.

StageResult
Expressiona * 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 2no 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.

StageResult
Expressionfalse && 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 2no changes, fixed-point reached

Dead Branch Elimination

Removes unreachable branches in conditional constructs.

StageResult
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 2no 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.

StageResult
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 2no changes, fixed-point reached

Constant Propagation

Substitutes known variable values into expressions.

StageResult
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 2no 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.

StageResult
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 2no 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.

StageResult
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:

Java
// 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:

CategoryOpcodes
LiteralsPUSH_DOUBLE, PUSH_BOOL, PUSH_NULL, PUSH_STRING, PUSH_OBJ
VariablesLOAD_VAR
StackDUP, POP
ArithmeticADD (+string concatenation), SUB, MUL, DIV, MOD
ComparisonEQ, NEQ, LT, GT, LTE, GTE
LogicAND, OR, NOT, NEG
BranchingTERNARY_BRANCH, JUMP
FunctionsCALL_FN (operand: fnIdx << 16 | argCount)
Return & BlockRETURN_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:

Java
// 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:

Java
// 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.

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:

ModeDescription
nativeNative Java code (reference)
astAST evaluation with optimizations
ast_no_optAST evaluation without optimizations
vmBytecode VM with optimizations
vm_no_optBytecode VM without optimizations

Test expressions:

NameExpression
simpleArithmetic2 + 3 * (4 * 5) — all constants, fully foldable
variableArithmetic(x + y) * z - w / v — variables, no constants to fold
complexOptimizable2 + 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
complexConditionalif/else-if chain on c==1..5, each branch returns arithmetic

Results (ns/op, lower is better)

Expressionnativeastast_no_optvmvm_no_opt
simpleArithmetic2.7133.32234.99014.02322.527
variableArithmetic2.68661.84764.01526.65427.958
complexOptimizable2.691166.360278.46552.72988.356
simpleConditional3.12327.46528.53621.79822.973
complexConditional3.20339.33491.70963.38649.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.

Java Antlr Dsl Parser Expression Optimization Vm Bytecode