Advanced VM Implementation and Optimization

Once a VM works, you make it faster by measuring what it actually does: which instructions run most, which pairs of instructions follow each other, where time and memory go.

Learning Objectives

Profile a VM: instruction frequency analysis; apply instruction fusion, superinstructions, quickening/adaptive specialisation, inline caches, constant-pool deduplication, stack caching.

Choose value representations (tagged integers, NaN-boxing), object headers and metadata, hidden classes; design dispatch tables and computed-goto dispatch.

Apply register allocation, basic blocks and CFGs, SSA-based optimisation, liveness, dead-code elimination, constant propagation, escape analysis, inlining and deoptimisation metadata; integrate GC, fast allocation and concurrency; manage code caches and executable memory; debug optimised code; test optimisations with differential testing; avoid benchmark pitfalls; and know when not to optimise.

Plain-Language Explanation

Once a VM works, you make it faster by measuring what it actually does: which instructions run most, which pairs of instructions follow each other, where time and memory go. Then you combine common pairs into single instructions, specialise instructions for the types they see, store values more compactly, and — only where the measurements justify it — add compiler optimisations.

Precise Technical Explanation

VM profiling methodology Count executed instructions per opcode and per pair, measure time per benchmark with repeats, and profile the VM itself with a native profiler; optimise the top items only.

Bytecode instruction frequency analysis Static (in compiled code) versus dynamic (executed) frequencies; dynamic pair frequencies reveal fusion candidates.

Replacing a frequent sequence by one instruction (GET_LOCAL; GET_LOCAL → GET_LOCAL2 a b; CPython 3.13's LOAD_FAST_LOAD_FAST is exactly this).

General term for fused instructions chosen from profiles; fewer dispatches at the cost of a larger instruction set.

Quickening / adaptive opcode specialization Rewriting an instruction in place after execution, based on observed operands (BINARY_OP → BINARY_OP_ADD_INT, Module 19), with a guard and a fallback.

Per-site caches of lookup results (globals, attributes, method targets) stored next to the instruction (CPython's inline cache entries after specialised instructions).

Constant pools and deduplication Merge equal constants (MiniLang reuses existing entries); intern strings; share immutable constant objects.

Operand stack caching Keep the top of stack in a machine register/local variable (Module 9).

Efficient value representation Avoid allocating every number: unboxed doubles, tagged small integers, NaN-boxing.

Tagged integers and NaN-boxing concepts Tagged pointers: use low bits of aligned pointers as a tag; small integers are stored shifted with a tag bit (V8 Smis). NaN-boxing: store pointers and small values inside the unused payload bits of IEEE-754 quiet NaNs, so every value fits in 64 bits and doubles need no boxing (LuaJIT, JavaScriptCore, SpiderMonkey's variant).

Object headers and runtime metadata Each object carries a header (type/class pointer, GC bits, hash, lock state) — smaller headers mean less memory (Project Lilliput shrinks HotSpot headers).

Hidden classes / shapes (engine-specific) Shared layout descriptors enabling inline caches (Module 20).

Dispatch table design Dense opcode numbering, handler tables, keeping hot handlers small and cache-friendly.

Computed-goto dispatch and portability caveats Per-handler indirect jumps (Module 9's real measurement); GCC/Clang extension, so keep a switch fallback.

In a VM compiler (virtual registers) or a JIT (machine registers): linear scan or graph colouring.

Basic blocks and control-flow graphs Units for analysis and optimisation (Module 10).

Optimisations over SSA: propagation, value numbering, range analysis.

Backward data-flow analysis: which values may be used later — drives register reuse and GC stack maps.

Remove instructions whose results are never used and unreachable blocks.

Replace uses of variables with their constant values; combined with folding and branch simplification.

Non-escaping objects can be stack-allocated or scalar-replaced (Module 16).

Biggest JIT win; needs heuristics on size and frequency.

Per guard: how to rebuild interpreter frames (bytecode offset, where each local lives).

Garbage collector integration Stack maps for precise roots, barriers emitted by the compiler, safepoint polls in loops.

Allocation fast paths Inline bump-pointer allocation in compiled code (Module 14).

Concurrent execution and synchronization Thread-safe inline caches and code patching; GIL-free designs need atomic reference counts or biased counting.

Code cache management Evict or flush cold compiled code; avoid fragmentation.

Instruction cache and executable memory New code must be visible to the instruction cache (explicit flushes on ARM); W^X switching costs.

Debugging optimized code Keep metadata to map machine state back to source; offer a no-optimisation mode.

Correctness tests for optimizations Every optimisation must preserve behaviour — test with the unoptimised path as the oracle.

Differential testing against a reference interpreter The reference (tree-walker) defines expected output; Module 23's harness is the template.

Measuring the wrong thing (dead code, constant inputs the optimiser folds), too few runs, ignoring warm-up, reporting averages of skewed distributions.

When not to optimize When the VM is not the bottleneck (I/O, libraries), when complexity outweighs gains, when correctness or security would suffer, or when no measurement shows a problem.

Why It Matters in Real Systems

CPython 3.11's ~25% speed-up came from exactly these techniques (specialisation, inline caches, cheaper frames); LuaJIT's speed rests on NaN-boxing and tracing.

Key Terms

Fused instruction replacing a frequent sequence In-place specialisation of executed instructions Encoding values in NaN payload bits

Small integer stored with tag bits in a word Whether a value may still be used

Syntax or Instruction Format

No dedicated source syntax; this is a runtime or architecture concept. Example fused instruction: ADD_LOCALS a b = GET_LOCAL a; GET_LOCAL b; ADD.

Complete Example

Dynamic instruction and pair frequencies of the MiniLang VM running a recursive Fibonacci — the profile that suggests superinstructions (Node.js 24, the course's MiniLang module):

Fusing a frequent sequence into a superinstruction in a small Python VM: same results, fewer dispatches (CPython 3.13.1; dispatch counts are exact, times are one real run):

NaN-boxing: a 64-bit word that is either a real double or, inside a quiet-NaN pattern, a tagged 32-bit integer (CPython 3.13.1 using struct to manipulate the bits):

import { runSource } from "file:///D:/Projects/EngineerHub/src/cs/tracks/runtimes/minilang/minilang.ts";

const r = runSource("fun fib(n) { if (n < 2) return n; return fib(n - 1) + fib(n - 2); } print(fib(10));", { trace: true, maxSteps: 1_000_000 });
const ops = r.trace.map((s) => s.instr.split(" ")[0]);
const count = (keys) => { const m = new Map(); for (const k of keys) m.set(k, (m.get(k) ?? 0) + 1); return [...m].sort((a, b) => b[1] - a[1]); };
console.log("output:", r.output[0], "| instructions executed:", r.executed, "| traced:", ops.length);
console.log("top opcodes:", count(ops).slice(0, 6).map(([k, v]) => `${k} ${(100 * v / ops.length).toFixed(1)}%`).join(", "));
const pairs = ops.slice(1).map((op, i) => `${ops[i]} → ${op}`);
console.log("top pairs:");
for (const [k, v] of count(pairs).slice(0, 5)) console.log(`  ${k.padEnd(28)} ${v}`);

output: 55 | instructions executed: 2126 | traced: 2126
top opcodes: GET_LOCAL 20.8%, CONSTANT 16.7%, GET_GLOBAL 8.3%, CALL 8.3%, LESS 8.3%, JUMP_IF_FALSE 8.3%
top pairs:
  GET_LOCAL → CONSTANT         353
  CALL → GET_LOCAL             177
  CONSTANT → LESS              177
  LESS → JUMP_IF_FALSE         177
  JUMP_IF_FALSE → POP          177

import time


def run(code, n_iter):
    total, dispatches = 0, 0
    for _ in range(n_iter):
        stack, local = [], [3, 4]
        for op, a, b in code:
            dispatches += 1
            if op == "LOAD":
                stack.append(local[a])
            elif op == "ADD":
                right, left = stack.pop(), stack.pop()
                stack.append(left + right)
            elif op == "LOAD_LOAD_ADD":                       # superinstruction: LOAD a; LOAD b; ADD
                stack.append(local[a] + local[b])
            elif op == "MUL_CONST":
                stack.append(stack.pop() * a)
        total += stack.pop()
    return total, dispatches


plain = [("LOAD", 0, 0), ("LOAD", 1, 0), ("ADD", 0, 0), ("MUL_CONST", 10, 0)]
fused = [("LOAD_LOAD_ADD", 0, 1), ("MUL_CONST", 10, 0)]
for name, code in (("plain", plain), ("fused", fused)):
    best = float("inf")
    for _ in range(5):
        t = time.perf_counter()
        result = run(code, 200_000)
        best = min(best, time.perf_counter() - t)
    print(f"{name}: result {result[0]}, {result[1]:,} dispatches, best of 5: {best * 1000:.0f} ms")

plain: result 14000000, 800,000 dispatches, best of 5: 112 ms
fused: result 14000000, 400,000 dispatches, best of 5: 77 ms

import math, struct

QNAN = 0x7FF8_0000_0000_0000           # quiet-NaN bit pattern
TAG_INT = 0x0001_0000_0000_0000         # one of the free payload bits marks "this is an int"


def box_double(x):
    return struct.unpack("<Q", struct.pack("<d", x))[0]


def box_int(i):
    return QNAN | TAG_INT | (i & 0xFFFF_FFFF)


def is_int(bits):
    return (bits & (QNAN | TAG_INT)) == (QNAN | TAG_INT)


def unbox(bits):
    if is_int(bits):
        raw = bits & 0xFFFF_FFFF
        return raw - (1 << 32) if raw & 0x8000_0000 else raw
    return struct.unpack("<d", struct.pack("<Q", bits))[0]


for value, bits in [(3.75, box_double(3.75)), (42, box_int(42)), (-7, box_int(-7)), (float("nan"), box_double(float("nan")))]:
    back = unbox(bits)
    print(f"{value!r:>6} → 0x{bits:016X} → is_int={is_int(bits)!s:<5} → {back!r}")
print("a boxed int is still a NaN when read as a double:", math.isnan(struct.unpack("<d", struct.pack("<Q", box_int(42)))[0]))

3.75 → 0x400E000000000000 → is_int=False → 3.75
    42 → 0x7FF900000000002A → is_int=True  → 42
    -7 → 0x7FF90000FFFFFFF9 → is_int=True  → -7
   nan → 0x7FF8000000000000 → is_int=False → nan
a boxed int is still a NaN when read as a double: True

Line-by-Line Explanation

Profile: GET_LOCAL, CONSTANT and the comparison/arithmetic opcodes dominate, and GET_LOCAL → CONSTANT and similar pairs repeat on every call — candidates for fused instructions (GET_LOCAL_CONSTANT) or specialised compare-and-branch instructions.

Fusion: the fused program does the same arithmetic with half the dispatches; in a Python-hosted VM the per-dispatch overhead is large, so the time drops noticeably (numbers are one run on the build machine).

NaN-boxing: ordinary doubles are their own bit patterns; integers live in the payload of a quiet NaN with a tag bit; a real NaN (canonical quiet NaN without the tag bit) stays distinguishable from boxed integers. Real engines must canonicalise NaNs produced by arithmetic so they never collide with tags.

Step-by-Step Runtime Behavior

Quickening in a VM: execute generic ADD → observe int + int → rewrite the instruction to ADD_INT with a guard → next execution checks the guard and adds directly → on guard failure rewrite back to generic.

Common Misconceptions

"More opcodes always mean a faster VM." Larger handler code can hurt instruction caches; fuse only what profiles justify.

"NaN-boxing is free." It costs bit manipulation and constrains pointer sizes (48-bit address spaces).

"Optimisations do not need tests." They are the most bug-prone part of a VM.

Common Bugs and Failure Modes

Fused instructions with wrong semantics at block boundaries (a jump target inside the fused sequence), specialisation guards that miss a case, NaN collisions with tags, stale inline caches after shape changes, code-cache exhaustion.

Corrected or Safer Patterns

Fuse only within basic blocks, guard every specialisation, canonicalise NaNs, invalidate caches on shape/prototype changes, differential-test optimised against unoptimised execution.

Debugging and Inspection Techniques

Per-opcode counters, pair histograms, specialisation statistics (CPython's --enable-pystats builds), native profilers on the VM binary.

Performance Considerations

Dispatch, value representation and memory locality dominate interpreters; JITs dominate peak performance; measure before and after every change.

Security Considerations

Specialisation and JIT bugs can become type confusion; keep guards strict and test them with adversarial inputs.

Portability and Version Caveats

Computed goto and NaN-boxing assumptions (address width) are platform-specific; keep portable fallbacks.

Real-World Use Cases

CPython's specialising interpreter, LuaJIT's value representation, V8's Smis and hidden classes, HotSpot's compressed oops and headers.

Best Practices

Profile → hypothesise → change one thing → measure → differential-test → keep or revert; document each optimisation's invariants.

Exercises

E1 · Beginner. Why does fusing LOAD; LOAD; ADD reduce dispatches by two per occurrence?

Answer: Three instructions become one: two fewer fetch–decode–dispatch cycles each time the sequence runs.

E2 · Intermediate. Why must a fused sequence not span a jump target?

Answer: A jump into the middle would land inside the fused instruction, skipping the earlier parts; fusion is only valid inside one basic block.

E3 · Advanced challenge. Sketch quickening for MiniLang's GET_GLOBAL.

Answer: After the first execution, rewrite GET_GLOBAL n to GET_GLOBAL_CACHED n slot, caching the global's storage slot (globals table index) and a version number of the globals table; on execution check the version and read the slot directly; if globals were redefined (version changed), fall back to the generic lookup and re-cache.

Quiz

? What does instruction-pair frequency analysis reveal?
+ Sequences worth fusing into superinstructions. :: Frequent pairs cost frequent dispatches.
- Memory leaks. :: Use heap tools.
- Syntax errors. :: No.
- Which functions are recursive. :: Not directly.

? In NaN-boxing, where do non-double values live?
+ In the unused payload bits of quiet-NaN bit patterns. :: With tag bits to tell types apart.
- In a separate heap object always. :: That is boxing.
- In the exponent of normal doubles. :: Normal doubles are left intact.
- In CPU registers only. :: No.

? When should you NOT optimise a VM? (select all that apply)
+ When profiles show the time is spent elsewhere (I/O, libraries) :: No benefit.
+ When the change would make correctness or security harder to guarantee for little gain :: Not worth it.
- When a benchmark shows a real, repeatable bottleneck :: That is when you should.
+ When no measurement shows a problem :: Measure first.

Summary and Key Takeaways

Advanced VM work is measurement-driven: profile opcode and pair frequencies, then apply fusion, quickening, inline caches, compact value representations and compiler optimisations — each guarded, differential-tested and justified by numbers.