Skip to content
Tutorials Center
My learning

Topics

Lesson 50 of 61 ยท Code Generation and Runtimes

Interpreters, JIT and Ahead-of-Time Compilation

Compare tree-walking interpreters, bytecode VMs, just-in-time and ahead-of-time compilers, and run a tiny tiered JIT with guards and an AOT inliner in Python.

Once a compiler front end has understood a program, there is still a question left: when and how does the program actually run? There is no single answer. A language implementation can walk the syntax tree, run bytecode on a virtual machine, translate hot code to machine code while the program is running, or translate everything to machine code before the program ever starts. Real systems often combine several of these.

In this lesson you will meet the four strategies, see why each exists, and run a small model of each in Python: a tree-walking interpreter that counts its own work, a tiered runtime that "JIT-compiles" hot functions and falls back when its assumptions break, and an ahead-of-time compiler that inlines and folds code before anything runs.

The spectrum of execution strategies

Imagine the same program executed four ways. They differ in how much work happens before the program starts, and how much each step costs while it runs.

Strategy Work before running Cost per step Examples
Tree-walking interpreter parse only high: one dispatch per AST node early Ruby, many small scripting languages, shell
Bytecode interpreter parse and compile to bytecode medium: one dispatch per instruction CPython, Lua, PHP, the Ruby VM
JIT compiler bytecode; machine code is made on demand low for hot code JVM, V8 (JavaScript), .NET, PyPy, LuaJIT
AOT compiler translate the whole program to machine code lowest C, C++, Rust, Go, Swift

None of these is "the best". Each trades startup time, peak speed, memory use and implementation effort in a different way.

Tree-walking interpreters

The simplest way to run a program is to evaluate the AST directly. Each node type gets a function that evaluates its children and combines the results. The lesson on abstract syntax trees shows how to build the tree, and the toy-language projects at the end of this track evaluate it exactly this way.

The following evaluator runs a recursive fib function. Its only extra feature is a counter that records how many nodes it visited, which is a measure of how much dispatch work the interpreter did.

Python A tree-walking evaluator that counts its work

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Computing fib(15) visits 17,755 nodes, and fib(5) needs only 133. The work grows with the recursion, as it must, but notice what each visit costs: a kind comparison chain, a recursive call, a dictionary lookup for the variable. The program itself is tiny; the interpreter spends most of its time deciding what to do rather than doing it.

Tree-walking has real advantages. It is the easiest design to write and debug, error messages can point at exact tree nodes, and startup is instant because nothing is compiled. It is slower mainly because the work is spread over many small heap-allocated nodes: each step follows pointers around memory, and the interpreter re-examines every node every time it passes through, even inside a loop that runs a million times. A bytecode VM removes much of that by flattening the tree into a compact array of instructions.

Just-in-time compilation

The key observation behind a just-in-time (JIT) compiler is that most of a program's time is spent in a tiny part of its code: the hot loops and the frequently called functions. Compiling everything to optimized machine code at startup would waste time on code that runs once. So a JIT starts by interpreting, counts how often each function or loop runs, and compiles only the hot parts while the program is still running.

Because compilation is expensive, production JITs use tiers:

flowchart LR
    A["Interpreter<br/>(starts at once, slow)"] -->|"warm: some calls"| B["Baseline JIT<br/>(fast to compile, simple code)"]
    B -->|"hot: many calls"| C["Optimizing JIT<br/>(slow to compile, fast code)"]
    C -->|"guard fails: deoptimize"| A

Code climbs through the tiers as it gets hotter and falls back to the interpreter when a guess turns out wrong.

The optimizing tier can generate much better code than an ahead-of-time compiler in one special way: it has seen the program run. If a function has only ever received integers, the JIT can speculate that this will stay true and generate integer-only code. To keep that speculation safe, it inserts a cheap guard at the entry: "are all arguments integers?" If a guard fails, the runtime performs a deoptimization: it throws away the specialized code (or just skips it for this call) and continues in the interpreter, which handles every case. The same idea works for the class of an object in a method call, which is why JITs for dynamic languages can approach the speed of static ones.

The next example is a miniature tiered runtime. A function starts in the tree-walking interpreter. After three calls it is "compiled", which in our model means generating Python source from the tree and loading it with exec, in place of the machine code a real JIT would emit. Calls are guarded by the assumption "all arguments are int".

Python A tiered runtime with a guard

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Follow the output. The first fib(10) starts in the interpreter. On the third call the counter reaches the threshold, the runtime prints the generated code, and from then on the recursion runs as compiled code. Only 26 nodes were interpreted in total, compared with 1,591 for a full interpreted fib(10). The second fib(10) visits no nodes at all. The last line passes a float: the guard on the entry fails three times (once for each call with a non-integer argument), the calls are served by the interpreter, and the answer is still correct. A real JIT's machine code, specialized for integer registers, could not have handled the float, which is exactly why the guard is there. Our generated Python would happily accept floats, so treat the guard in this model as the shape of the idea.

Method JITs and tracing JITs

Most JITs compile whole methods or functions, as in the model above. A tracing JIT works differently. When a loop becomes hot, it records the exact sequence of operations executed during one iteration, across function calls and all, and compiles that straight-line trace. Every branch taken along the way becomes a guard: "this if still goes the same way". A failed guard exits the trace and returns to the interpreter. Tracing produces very tight code for loops that behave consistently, and it powers LuaJIT and PyPy. It struggles when a loop has many unpredictable branches, which is why mainstream JavaScript engines went the method-JIT route.

Ahead-of-time compilation

An ahead-of-time (AOT) compiler does all the translation before the program is delivered. What ships is a ready-to-run machine-code file. There is no warm-up, startup is fast, and the program needs no compiler or VM at run time. The compiler can also spend as long as it likes, since compile time is not part of any user's wait. Whole-program techniques that would be too slow for a JIT are fair game: inlining, constant folding across functions, and removing dead code.

The costs are a separate build step, one binary per platform, and less information. A JIT sees real data types and branch frequencies; an AOT compiler must guess unless you give it a profile (profile-guided optimization) from a trial run.

This example is an AOT compiler in miniature. It translates a whole program into Python source text, optionally inlining small non-recursive functions and folding constants first, and then runs the finished module without any interpreter for the tree.

Python Ahead-of-time: inline, fold, then generate code

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compare the two outputs. Both give 80, but with optimizations on, the call dist2(3, 4) in result has been inlined twice (dist2 into main, then sq into dist2) and the arithmetic (3 * 3) + (4 * 4) folded to 25. The generated dist2 function also lost its calls to sq. The recursive fib is deliberately not inlined, because replacing a call with the body of a function that calls itself would never stop. Real compilers apply the same idea with limits: they inline small functions, unroll recursion only a few levels and stop at a size budget.

Self-interpreters

A self-interpreter (also called a meta-circular interpreter) is an interpreter for a language that is itself written in that language. It sounds circular, but it is a useful trick: it shows that the language is expressive enough to describe its own semantics, it is a compact way to experiment with new features, and a language can be bootstrapped with it (compare bootstrapping and cross-compilers). Famous examples are eval written in Lisp, and Python implementations such as PyPy, whose interpreter is written in a restricted Python (RPython).

The interpreter below runs a small subset of Python, written in Python. Python's ast module gives us the syntax tree, so we only write the evaluator. It runs a Fibonacci program that contains no Python knowledge except our own rules for assignment, while, comparison and print.

Python A tiny Python interpreter written in Python

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output is the first ten Fibonacci numbers. Our interpreter is tiny because it borrows the host's parser, integers and print; a full self-interpreter has to define those itself or lean on a small kernel. A real caveat: an interpreter running on top of another interpreter is slow (here two levels), which is why self-hosted languages are usually paired with a JIT or a compiler.

Hybrids are the norm

Real implementations blend all of the above:

  • Java: javac compiles ahead of time to bytecode, the JVM interprets it and JIT-compiles the hot methods in tiers. GraalVM Native Image can also compile a whole application ahead of time.
  • JavaScript (V8): parses to bytecode, runs it in an interpreter, and promotes hot functions to a baseline and then an optimizing compiler with type-feedback guards.
  • .NET: JIT by default, with a NativeAOT mode for fast startup.
  • Android: apps are compiled ahead of time, JIT-compiled while they run, and re-optimized in the background using the recorded profile.
  • CPython: bytecode interpreter with adaptive instructions, and an experimental JIT in recent versions.

When you choose how to run a language you are building, start with a tree-walker, move to bytecode when speed matters, and add JIT or AOT only when you have measurements that demand it.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does a JIT compiler wait before compiling a function?

    Most code runs rarely. Counting executions and compiling only the hot parts avoids paying compile time for code that would not repay it.
  2. 2. What does a guard in speculative JIT code do?

    Guards make speculation safe. If an argument has a type the optimized code did not expect, the runtime deoptimizes and continues in a general version.
  3. 3. Which is a typical advantage of ahead-of-time compilation over a JIT?

    AOT moves all compilation to build time. The trade-offs are a build per platform and less run-time information (unless profile-guided optimization is used).
  4. 4. Why does the AOT example refuse to inline fib into itself?

    Each inlined copy of a recursive body contains another call to the same function, so unlimited inlining never terminates. Compilers inline recursion only to a fixed depth or not at all.

Summary

  • A language can be run by a tree-walking interpreter, a bytecode VM, a JIT compiler or an ahead-of-time compiler; most real systems combine them.
  • Tree-walking is the simplest design but pays a dispatch per node, which is why it is slowest.
  • A JIT interprets first, counts executions, and compiles hot code in tiers, using guards and deoptimization to keep speculation safe.
  • Tracing JITs record and compile the path through a hot loop; method JITs compile whole functions.
  • An AOT compiler translates everything before the program runs, giving fast startup and whole-program optimization, but less run-time information.
  • Inlining plus constant folding is a classic optimization pair: inlining exposes constants, folding computes them.

Next: Project: An Expression Calculator Compiler