PATTERN Cited by 1 source

VM + AST dual-interpreter fallback¶

Problem¶

A statically-typed VM is fast because it eliminates runtime type dispatching. But some operations have value-dependent types — the compile-time type assumption fails on specific runtime values. Canonical example (SQL):

-BIGINT_MIN = -9223372036854775808 should produce DECIMAL, not BIGINT, because |MIN_INT64| exceeds the BIGINT range.

You could re-introduce runtime type switches to handle these cases, but that defeats the whole point of static specialization.

Solution¶

Keep the AST interpreter alive permanently as a deoptimization fallback. When a specialized VM instruction detects a value-dependent type promotion, it sets a sentinel error (vm.err = errDeoptimize) and the VM loop hands the expression off to the AST interpreter — which always type-switches at runtime and handles every edge case correctly.

func (c *compiler) emitNeg_i() {
    c.emit(func(vm *VirtualMachine) int {
        arg := vm.stack[env.vm.sp-1].(*evalInt64)
        if arg.i == math.MinInt64 {
            vm.err = errDeoptimize   // ← bail to AST
        } else {
            arg.i = -arg.i
        }
        return 1
    })
}

The rest of the system treats this fallback as first-class: the AST interpreter is not legacy code to be deleted someday, it's an operational asset.

Why keep the AST interpreter (not just any fallback)¶

Vitess's three reasons (Source: sources/2025-04-05-planetscale-faster-interpreters-in-go-catching-up-with-cpp):

Deoptimization fallback — the motivating use case described above.
One-shot evaluation — for single-pass uses like constant folding inside the query planner, compile-then- execute on the VM is more expensive than walking the AST directly. The AST interpreter wins on expressions evaluated exactly once.
Fuzz-oracle sibling — two independent interpreters for the same language enable differential fuzzing. Every disagreement between VM output and AST interpreter output is a bug in one of them (or, for Vitess, sometimes a bug in MySQL's C++ reference implementation that gets upstreamed).

Canonical instance¶

Vitess evalengine is the canonical wiki instance. The evalengine ships two coexisting interpreters:

The VM — fast, callback- slice design with static type specialization.
The AST interpreter — original Vitess evaluation engine, now primarily a deoptimization + one-shot + fuzz-oracle target.

"The code for the AST interpreter can never be removed from Vitess. But this is, overall, not a bad thing. Just like most advanced language runtimes keep their virtual machine interpreter despite having a JIT compiler, having access to our classic AST interpreter gives us versatility."

Relationship to JIT deoptimization¶

This pattern mirrors the standard JIT architecture, just one layer down:

Layer	Optimised path	Fallback on invalidation
JIT	Native code	Bytecode VM
Statically-typed VM	Specialized opcodes	AST interpreter
AST interpreter	Direct tree walk	— (baseline)

Every tier speculates on runtime state and bails out to the next tier when the speculation fails. The pattern generalises.

Properties¶

Property	Value
Normal path performance	VM-class (Vitess: catches up with MySQL C++)
Fallback path performance	AST-interpreter-class (much slower)
Deoptimization trigger cost	Single flag check + loop exit + handoff
Correctness guarantee	AST interpreter handles every edge case
Maintenance cost	Two implementations must stay in sync on correctness

When to use¶

Statically-typed VM + occasional value-dependent promotions. The pattern is designed for this exact situation.
JIT-tiered runtimes. Same structure with native-code + bytecode-VM layers.
Any optimisation that speculates on runtime invariants and needs a correctness-preserving fallback.

Caveats¶

You now maintain two implementations. Every new opcode needs both a specialized closure and an AST interpreter handler, and they must agree on semantics. Vitess turns this cost into an asset via differential fuzzing (patterns/fuzz-ast-vs-vm-oracle), but the cost is real.
Deoptimization triggers must be exhaustive. Every value- dependent type promotion must have a check in the specialized opcode; a missed case produces silently wrong results.
Fallback overhead discourages deopt-heavy workloads. If deoptimization fires on a meaningful fraction of executions, you don't reach the VM's peak performance. Profile workloads to ensure deopt is rare.
The AST interpreter must be correct. It's the ground-truth reference; bugs in the AST interpreter propagate to the fuzz-oracle role and erode correctness guarantees.

Seen in¶

sources/2025-04-05-planetscale-faster-interpreters-in-go-catching-up-with-cpp — canonical wiki instance. Vitess evalengine keeps the AST interpreter permanently alongside the VM; deoptimization on value-dependent promotions (BIGINT_MIN negation) falls back to AST evaluation.