sean butler

On VO, a dynamic programming language with an interesting set of features.

TL;DR; AST walking interpreters can be slow. Gets 3-4 times faster than a naive implementation. Scroll down to near the bottom for the data/charts.

Intro

VO is a minimal expression-oriented scripting language with a tree-walking interpreter written in c++. Tree-walkers can be straightforward to build and provide many opportunities especially for runtime flexability. They do however pay a performance tax, especially in hot loops. Also dynamic dispatch, heap allocs and pointer jumps all slow us down on modern hardware.

The Benchmark Suite

We started with 6 benchmarks, but VO’s dev environment currently has 9 benchmark programs each exercising distinct interpreter stress points.

The timings taken are averaged over the iteration count built into each benchmark. Also, we reran the original unoptimized binary against the expanded benchmark suite so that numbers are directly comparable across the whole progression.

The Optimisations

Fixing the Dispatch Chain

The interpreter’s central eval() function identified AST node types with eleven sequential dynamic_cast calls:

if (auto* e = dynamic_cast<IntLiteral*>(node)) { ... }
else if (auto* e = dynamic_cast<BinaryExpr*>(node)) { ... }
else if (auto* e = dynamic_cast<Identifier*>(node)) { ... }
// ... eight more

dynamic_cast against a class hierarchy walks the RTTI table at runtime [1]. Even when it succeeds on the first try, it is doing string comparisons on mangled type names under the hood. When it fails, each cast walks the full inheritance chain before returning null. With eleven candidates and a mixed workload, the average cost was roughly five failed casts per node evaluation and eval() is called for every single AST node in every expression!

The fix: store a small ExprKind / StmtKind enum in the base class, set once at construction, and dispatch via switch + static_cast:

switch (node->kind) {
    case ExprKind::IntLiteral: {
        auto* e = static_cast<IntLiteral*>(node);
        ...
    }
    // ...
}

static_cast is zero-cost in the sense that it is a compile-time pointer adjustment with no runtime check [2]. A switch over a dense enum is typically lowered to a jump table or equivalent branch dispatch, and the whole dispatch becomes a single indexed jump rather than a RTTI walk.[3]

We gained about ~65% on sum. Clearly this slowdown has been dominating the runtime. All other benchmarks improved by similar proportions: fib_recursive dropped from 5442 ms to 2034 ms, fib_iterative from 6590 ms to 1927 ms.

The dispatch mechanism is so pervasive in an AST walker that fixing it once fixes everything.

Environment Lookup

Environment lookup (get / set) climb the parent chain recursively. Recursion here is pure overhead: stack frame setup, return address push, with no actual benefit from all this infrastructure. Converting to an iterative loop shaves some off any benchmark that touches many variables.

Fallthrough Numeric Checks

The binary operator handler for +, -, * had a fast path for integer operands, followed by a is_numeric() call on both values to handle mixed int/float. The problem is, the fast path fell through to the is_numeric() check even when both operands were already handled. Adding an early return (or early throw) after the int-int branch means the mixed-numeric path is never reached for integer operands. A one-line change, 4% improvement on sum.

Unnecessary Conditional Environment Allocation

Every if branch previously allocated a new Environment object, even for branches like:

if x > 0 { x = x - 1 }

This branch contains no let or const declarations, so a new scope is unnecessary as x resolves to the parent env either way. The fix is a simple static analysis pass at parse time (or a flag set during construction): if the block contains no declarations, the branch evaluator reuses the parent environment pointer directly.

Environment allocation involves a heap allocation plus an unordered_map construction. On tight loops with conditional branches, this is called millions of times. The ~10–15% improvement is consistent across all compute-heavy benchmarks.

Call Dispatch

call_value() used the same pattern as the old eval(): sequential is_function(), is_builtin(), is_proto() checks. Converting to a switch on Value::Kind gives the same jump-table win as the expression dispatch fix, scoped to call sites. The gains are smaller here because calls are less frequent than node evaluation, but fib_recursive dropped ~4.5% and proto_chain ~5.5%.

Note:

Smaller nodes mean better cache utilization therefore more nodes fit in L1/L2, giving us fewer cache misses. So the rest of the optimisations were really focussed on trying to shrink the AST node size rather than find more optimal execution paths.

Removing the virtual destructor

Every class with a virtual function carries an 8-byte vtable pointer in each instance. The AST nodes had virtual destructors as a safety measure. Once RTTI was no longer needed (no more dynamic_cast), the virtual destructor became the only remaining virtual function. Removing it eliminated the vtable pointer from every AST node (8 bytes per node times millions of nodes).

Op enum for BinaryExpr/UnaryExpr

Storing the operator as std::string is expensive. A std::string on a 64-bit platform with SSO is 32 bytes, and it owns a heap allocation for strings longer than the SSO buffer. Operators like "+", "-", "*" are short enough to fit in SSO, but the string object itself still occupies 32 bytes.

Replacing std::string op with an Op enum (4 bytes) cuts the node sizes significantly:

BinaryExpr at 44 bytes fits comfortably in a single cache line (64 bytes). At 72 bytes it spilled into a second line on every access.

TypeKind enum

Optional type annotations were stored as optional<string> (40 bytes). Replaced with optional<TypeKind> (2 bytes). Type annotations are not read during evaluation currently they are only relevant to a future type-checker so the benchmarks didnt change. The structural gain flows into all the node sizes above.

String Interning

At parse time, every identifier string is looked up in a global InternTable and replaced with a uint32_t ID. The InternTable is a flat unordered_map<string, uint32_t> with a reverse vector<string> for lookup by index.

The payoff is twofold:

1. Node size: Identifier shrinks from 40 bytes (contains a std::string) to 8 bytes (contains a uint32_t plus alignment). MemberExpr drops from 56 to 24 bytes.

2. Environment lookup: Environment maps names to values. Before interning, every lookup hashed a std::string, at minimum one strlen, one FNV/MurmurHash call over the full string bytes. After interning, lookups hash a uint32_t. On modern hardware, integer hashing is a single multiply orders of magnitude fewer instructions per lookup.

Actual gains from interning:

The benchmarks that see the largest gains from interning are those with the most variable lookups per iteration.

Results

Full checkpoint progression (times in ms):

You can see the dispatch chain fix delivered the overwhelming majority of the gain (roughly 3–3.5× on its own). All of the subsequent smaller improvements and bug fixes add up to another 10–20% on top.

Future Work

The interpreter is now roughly 4× faster than it was originally. There is still plenty more work to do though, both local small speedups and bugs in the original system.

One possible future optimisation that interests me currently is Hot-subgraph compaction. That is at runtime, track which sub-trees of the AST are evaluation hot spots (tight loop bodies, recursive function bodies) and compact those sub-trees into contiguous memory regions with a custom layout optimized for the eval order. Its somewhat similar to what JIT compilers do with code layout but not usually applied to interpreters with AST.

The speed-ups so far have come as expected from fixing avoidable overhead in the core interpretation functioality that affects everything else: the representation and dispatch layers. The next level of optimisation gets into memory layout and allocation strategy. Which to my mind is way more interesting, especially as VO becomes a AST rewriting interpreter.

References

• [1] cppreference.com, “dynamic_cast” and “RTTI” entries: https://en.cppreference.com/w/cpp/language/dynamic_cast and https://en.cppreference.com/w/cpp/language/typeid
• [2] cppreference.com, “static_cast” entry: https://en.cppreference.com/w/cpp/language/static_cast
• [3] LLVM project, “SwitchInst” / lowering behavior for dense enums: https://llvm.org/docs/CodeGenerator.html and https://llvm.org/docs/Passes.html