CS Fundamentals Trainer · Guides
Compilers, interpreters and language runtimes
From source text to running code: lexing, parsing, optimisation, bytecode machines and just-in-time compilation, with a tree walker, a bytecode VM and compiled code measured side by side.
38 min read
Every program you write is text, and a processor runs neither Python nor Java nor TypeScript. Something has to turn the text into actions, and the choices made there decide how fast the program starts, how fast it runs, what errors you see and when, and why the same code can be 30 times slower in one language than another. That "something" is a compiler, an interpreter or, in most modern languages, a mixture of both: a language runtime. This guide follows a program through the stages, builds the same loop three ways to measure the difference, and shows how a just-in-time compiler warms up and what makes it slow down again. The scripts are in the appendix.
It builds on operating systems (what a process is), the memory hierarchy (why layout matters) and garbage collection (another thing a runtime does).
1. From text to action: the stages
Diagram: The stages that turn source text into something that runs
- Lexing (scanning) splits the characters into tokens:
price,*,qty,+,5. Whitespace and comments disappear. - Parsing applies the grammar and builds an abstract syntax tree (AST) that records structure and precedence. Python's own
astmodule shows it fortotal = price * qty + 5: anAssignwhose value is anAddof aMult(price, qty) and the constant 5. The multiplication is lower in the tree because it binds tighter, so the tree needs no parentheses. - Analysis resolves names to declarations, checks types in a statically typed language, and reports the errors that stop the build: "undefined variable", "cannot add string to int".
- Intermediate representation (IR) and optimisation rewrite the program into a simpler form where it is easier to improve (see below).
- Code generation emits either machine code for a real CPU or bytecode for a virtual one.
The first three stages, the front end, are about the language; the last two, the back end, are about the target. Splitting them, as LLVM does, means that N languages and M processors need N front ends and M back ends, not N × M compilers.
2. Three ways to run a program
| Approach | What happens | Examples | Start-up | Speed once running |
|---|---|---|---|---|
| Ahead-of-time (AOT) compiler | all of the program is translated to machine code before it runs | C, C++, Rust, Go | instant | often the fastest, but see 3.1 |
| Interpreter | the program is executed directly from the tree or from bytecode, instruction by instruction | CPython, Ruby (MRI), shells | instant | usually the slowest per instruction, but see 3.1 |
| Just-in-time (JIT) compiler | starts by interpreting; finds the hot code at run time and compiles that to machine code | JavaScript (V8), Java (HotSpot), .NET, PyPy | slow warm-up | close to AOT, sometimes better |
"Compiled language" and "interpreted language" are properties of an implementation, not of a language: JavaScript has interpreters and JIT compilers, and C has interpreters. Most real systems combine stages: Java compiles to bytecode once (javac), then the JVM interprets that bytecode and JIT-compiles the hot methods; Python compiles source to bytecode (the .pyc files) and interprets it; TypeScript is compiled to JavaScript and the JavaScript is then JIT-compiled.
2.1 Three different things: the language, its bytecode and its runtime
The words "Python", "Java" or "C" are used for three layers that people mix up, and many wrong beliefs about performance and behaviour come from the mix-up.
| Layer | What it is | Who defines it | Examples |
|---|---|---|---|
| Language semantics | what a program means: which results and effects are guaranteed, and what is left undefined or unspecified | a specification or standard | the C standard, the Java Language Specification, ECMAScript, the Python language reference |
| Intermediate form (bytecode) | the instructions a compiler front end produces for a virtual machine | sometimes a specification, sometimes a private detail | JVM bytecode and WebAssembly are specified; CPython's bytecode and V8's Ignition bytecode are internal |
| Runtime implementation | the program that executes it: interpreter, JIT, garbage collector, standard library, optimiser | each vendor or project | CPython, PyPy; HotSpot, OpenJ9, GraalVM; V8, SpiderMonkey; GCC, Clang |
Three measurements make the difference concrete.
1. The same C source, different answers. In C, signed integer overflow is undefined behaviour: the standard lets the compiler assume it never happens. I wrote an overflow check, a + b < a, and ran it with a = INT_MAX, b = 1:
| Implementation and flags | Does INT_MAX + 1 overflow? |
|---|---|
gcc 13, -O0, -O1 and -O2 | "no" (the compiler assumed no overflow, so a + b < a became b < 0) |
gcc 13, -O2 -fwrapv (asks for wrap-around) | "yes" |
clang 18, -O0 | "yes" |
clang 18, -O2 | "no" |
Java, in the interpreter (-Xint), the C1 compiler and the default JIT | "yes", always (the language defines the wrap-around) |
The language did not change; the implementation chose among behaviours the language allowed. A program that relies on undefined behaviour is correct only by accident, and it can break on a compiler upgrade or a flag change. Java, whose specification leaves no such freedom here, gave one answer in every mode: the JIT may change speed, never meaning. Tools such as -fsanitize=undefined exist to find these cases.
2. The same Python function, different bytecode. I compiled one function with three installed CPython versions and listed its instructions:
| CPython | Instructions | Differences |
|---|---|---|
| 3.11 | 28 | the list comprehension is a separate nested function (MAKE_FUNCTION, PRECALL) |
| 3.12 | 46 | comprehensions are inlined (LOAD_FAST_AND_CLEAR, LIST_APPEND, END_FOR) |
| 3.13 | 47 | new combined instructions (LOAD_FAST_LOAD_FAST, STORE_FAST_LOAD_FAST) |
Python programs behave the same on all three, but the bytecode is not part of the language and changes between releases; code that parses .pyc files or dis output breaks on upgrade. JVM bytecode, by contrast, is a published format with a specification that many languages compile to (Java, Kotlin, Scala), which is why they can share one runtime.
3. The same program, one runtime, different speeds. The behaviour above does not depend on the execution strategy; the speed does, by large factors (next sections): the HotSpot interpreter, its first compiler tier and its optimising compiler are three implementation choices for the same language and bytecode.
A useful question to ask about any surprising behaviour is: is this guaranteed by the language, or is it this implementation? Iteration order of Python's dict is guaranteed (since 3.7); the moment a finalizer runs, the speed of a call, the layout of objects and the result of an undefined operation are not. Test on more than one compiler or version where you can, turn on warnings and sanitizers, and write to the specification, not to what one implementation happens to do.
3. Measuring the three: a tree walker, bytecode and compiled code
To see the difference I wrote one small language (integers, +, *, %, <, assignment and while) and ran the same program three ways in C: s = 0; i = 0; while (i < 50,000,000) { s = s + (i*i) % 7; i = i + 1 }.
- A tree-walking interpreter evaluates the AST directly: a recursive call and a
switchfor every node. - A bytecode virtual machine: the tree is flattened once into 22 instructions and a loop runs them on a stack.
- Compiled C for the same loop.
| Implementation | Time | Relative |
|---|---|---|
| tree walker | 2.3 to 2.4 s | 1 |
| bytecode VM | 1.55 to 1.6 s | 1.4 to 1.6 times faster |
| compiled to machine code | 0.08 s | about 30 times faster |
All three produced the same result. The tree walker follows pointers all over memory and makes a function call per node; the bytecode loop reads instructions from a compact array, which is friendlier to the CPU cache and its branch predictor. But even the bytecode machine still decodes and dispatches every instruction, about 17 per iteration, 850 million in total, while the compiled loop is a handful of machine instructions. This is the fundamental cost of interpretation: an overhead per operation, which you pay for every step. (Interpreters written with care get the dispatch cost down, and real interpreters like CPython add tricks, but the order of magnitude remains.)
How a stack machine works
A stack machine has no named registers; every instruction takes its operands from a stack and pushes its result. It is easy to generate code for, and the bytecode is compact. Step through the compilation of 2 + 3 * 4 and then of (2 + 3) * 4:
Interactive animation: bytecode vm
Both expressions have the same numbers and operators, but different trees, different bytecode and different results (14 and 20). Precedence is not something the machine knows; it is decided entirely by the parser and compiled away into the order of the instructions. This is the JVM's model as well (Java bytecode is a stack machine), whereas the Lua VM and Android's Dalvik use register machines, which need fewer instructions but longer ones.
What CPython really runs
Python prints its own bytecode with the dis module. For def f(price, qty): return price * qty + 5 it is:
LOAD_FAST_LOAD_FAST price, qty → BINARY_OP * → LOAD_CONST 5 → BINARY_OP + → RETURN_VALUE
five working instructions (six with the RESUME marker at the start), the same shape as the machine above. The cost hides in BINARY_OP: Python is dynamically typed, so + has to find out at run time whether it is adding integers, floats, strings or lists (the same function returned 3, 3.5, 'ab' and [1, 2] for different arguments). Three million calls of such an addition through a function took about 0.25 s, roughly 80 ns each, against a fraction of a nanosecond for the same addition compiled. Recent CPython versions speed this up with a specialising adaptive interpreter: after seeing that an instruction always receives integers, it rewrites it to a faster integer-only form (with a guard to fall back). It is the same idea that JITs use, one level lower.
3.1 Which is fastest? It depends on the job
The table in section 2 is a rule of thumb, and the measurements in section 3 are for one loop. Neither category (ahead-of-time compiled, JIT-compiled, interpreted) is the fastest in general. Four more measurements, each of which reverses the simple ranking in some situation:
1. The job's length decides who wins. The same loop (s = (s*31 + i) % 1000003) in five implementations, timing the whole process, start-up included:
| Implementation | 1,000 iterations | 1 million | 100 million | 1 billion |
|---|---|---|---|---|
C (gcc -O2) | 0.001 s | 0.006 s | 0.51 s | 5.0 s |
| Java (HotSpot, JIT) | 0.037 s | 0.045 s | 0.62 s | 5.1 s |
| Node.js (V8, JIT) | 0.031 s | 0.034 s | 0.60 s | 5.8 s |
Java with only its interpreter (-Xint) | 0.033 s | 0.055 s | 2.3 s | 22.6 s |
| Python 3.13 (interpreter) | 0.014 s | 0.116 s | 11.0 s | 104.8 s |
For a tiny job the JIT languages lose to a plain interpreter (Python: 14 ms, Node and Java: 31 to 37 ms), because the runtime itself takes 30 ms to start; C needs 1 ms. For a long job the JIT catches up completely (Java within 2% of C at a billion iterations, Node within 17%), because the hot loop is compiled to machine code. Two other things stand out: the interpreted category is not one speed, since HotSpot's own interpreter ran this loop about 4.5 times slower than C while CPython was about 21 times slower; and the loop is dominated by one division, a case where a JIT has little to improve. Other loops would give other ratios.
2. The algorithm usually matters more than the category. A correct insertion sort in C (-O2), O(n²), against Python's built-in sorted(), which is Timsort running in C inside the interpreter:
| Integers | C insertion sort | Python sorted() |
|---|---|---|
| 20,000 | 0.039 s | 0.004 s |
| 100,000 | 1.19 s | 0.029 s |
| 400,000 | 16.7 s | 0.11 s |
The "slow" interpreted language is 150 times faster at 400,000 elements, because it spends its time in a well-designed routine written in a compiled language. Most Python programs that perform well do so for this reason: the interpreter does the orchestration and compiled libraries do the work. The reverse also happens: a Python loop doing per-element work that a library could do for the whole array is where the 20-fold gap above appears.
3. A JIT can beat ahead-of-time code, because it knows how the program behaves. A loop calls one of several small functions through a table that is built at run time. An ahead-of-time compiler cannot inline a call it cannot predict; the JVM observes which classes arrive at the call site and inlines them:
| Distinct targets at the call site | C (indirect call, gcc -O2) | Java (HotSpot, after warm-up) |
|---|---|---|
| 1 | 1.62 ns | 0.77 ns |
| 2 | 1.76 ns | 1.07 ns |
| 4 | 1.97 ns | 4.31 ns |
With one or two targets the JIT's speculation won by up to a factor of two; with four it lost by more than a factor of two, because the call site became "megamorphic" and could no longer be inlined. This is the nature of speculative optimisation: it is fast when the program behaves the way it did while being profiled. Ahead-of-time compilers can use profile-guided optimisation (compile, run a representative workload, recompile with the recorded profile) to recover much of this, at the price of needing a representative workload.
4. What you pay for the JIT. Start-up (point 1), memory for the compiler and its profile data, compilation work on the same cores as your application, and variable performance over time, which the next section measures. Platforms where these matter prefer ahead-of-time compilation or snapshotting (Go, GraalVM native images, ahead-of-time modes of .NET, snapshot and restore of a warmed-up JVM).
So the honest ranking is a set of conditions rather than an order:
| If the job is... | then usually |
|---|---|
| short-lived (a command, a function invocation, a script) | an ahead-of-time program or a lightweight interpreter wins; JIT start-up and warm-up dominate |
| long-running and CPU-bound in a hot loop | AOT and JIT are close; the JIT may win when the behaviour is predictable at run time, and lose when it is not |
| mostly calls into optimised libraries (sorting, regular expressions, arrays, cryptography) | the language of the glue barely matters; the library and the algorithm do |
| latency-sensitive with tight tail requirements | prefer predictable performance: AOT, or a JIT that is warmed up and does not deoptimise under your traffic |
| a program whose bottleneck is I/O, a database or the network | none of this matters; measure first |
4. What an optimiser does
When I compiled printf("%d\n", SQUARE(n) * 8) with n = 12, gcc -O0 generated about 43 lines of assembly that really multiply at run time. With -O2 the compiler had already computed 12 × 12 × 8 and the program contained the constant 1152. The common transformations:
- Constant folding and propagation: compute at compile time whatever is already known.
- Dead-code elimination: drop what can never run or whose result is never used.
- Inlining: replace a call with the body of the function. It removes the call cost and, more importantly, lets the other optimisations see across the boundary. It is the most important one.
- Loop optimisations: moving unchanging calculations out of a loop, unrolling, and vectorising to use SIMD instructions.
- Register allocation and instruction scheduling: keep values in CPU registers and order instructions to fit the pipeline.
- Escape analysis (as in the JVM and Go): an object that never leaves a function can be placed on the stack or removed entirely, which is why a first version of my garbage-collection test, a Java loop that allocated 4 GB of throw-away arrays, finished in 63 ms: the compiler removed the allocations (garbage collection).
Optimisers must preserve the program's observable behaviour, and the definition of that is the language's rules, including undefined behaviour in C and C++, which lets the compiler assume it never happens and can turn a latent bug into a surprising result. For a benchmark this means: check that the thing you measure still exists after optimisation. My compiled loop uses a volatile counter; without it the compiler may replace the whole loop by a formula and report an absurdly small time.
The stages of the C toolchain can be run one by one: the preprocessor (gcc -E: pasting #included headers and expanding macros: a 3-line program became 816 lines), the compiler proper (-S: assembly), the assembler (-c: an object file in a relocatable ELF format) and the linker (resolving references between object files and libraries into an executable of about 16 KB here). Linking can be static (the library code is copied in) or dynamic (resolved when the program starts, so one copy of the library is shared and a vulnerability fix needs no rebuild). Go and Rust prefer static linking, which is why their binaries are easy to put in a minimal container image.
5. Just-in-time compilation: warm-up and deoptimisation
A JIT starts by running code in a slow, cheap tier and profiles it. When a function or loop becomes hot, it compiles that part with an optimising compiler, using what it has seen. V8 has the Ignition interpreter, then the Sparkplug and Maglev compilers, then TurboFan; HotSpot has an interpreter, the C1 compiler and the C2 compiler. The profile allows speculative optimisation: "this + has only ever seen integers", "this property access has only seen objects of one shape", so it compiles a fast version with a guard that checks the assumption. If a guard fails, the runtime deoptimises, throwing the compiled code away and going back to the slow tier.
I measured both effects with a JavaScript function that sums the x field of 200,000 objects, in Node.js 22:
| Situation | Time per call |
|---|---|
| first call (cold) | 3 to 4.5 ms |
| second call | about 1 ms |
| after warm-up | about 0.4 ms |
| same code, the array now mixes five different object shapes | 1.0 to 1.7 ms (2.5 to 4 times slower) |
| back to objects of one shape | still about 1.0 to 1.3 ms |
Three things to learn from it. First, warm-up is real: the first calls were roughly 10 times slower than the steady state, which matters for short-lived processes, serverless functions and the first requests after a deploy (rolling updates send traffic to cold instances; a canary or a warm-up request helps). Second, type stability matters: V8 gives each object a hidden "shape" (the order in which properties were added), and a property access that sees one shape is a fast offset load, while one that sees many (a megamorphic access) must do a slower lookup. {x, y} and {y, x} are different shapes. Third, the slowdown is sticky: after the code had seen many shapes, it did not go back to the fast version when the data became uniform again. The practical advice is to create objects of the same kind the same way (the same properties in the same order, initialised in the constructor) and to keep types in hot code consistent.
JIT-compiled code can occasionally beat ahead-of-time code because it optimises for the behaviour it actually sees (for example inlining the one implementation of an interface that is ever used), but it pays in warm-up time, in memory for the compiler and the profile data, and in less predictable performance. Some platforms therefore prefer ahead-of-time compilation (Go; GraalVM native images; AOT modes of .NET), and WebAssembly was designed as a compact, typed target that a browser can compile quickly.
Deoptimisation in the JVM: speed that depends on what the program has done so far
Section 5 measured V8 on mixed object shapes. The JVM does the same with classes. In one JVM and one hot loop, I changed which classes reached the call site from section 3.1 (300 million calls per batch; time per call):
| Batches | Classes seen at the call site | Time per call |
|---|---|---|
| 1 to 6 | 1 | 0.76 to 1.03 ns (the first batch includes the warm-up) |
| 7 to 10 | 2 | 0.87 to 1.01 ns |
| 11 to 16 | 4 | 3.7 to 5.5 ns (4 to 6 times slower) |
| 17 to 20 | 1 again | 4.1 to 5.7 ns: it did not recover |
When a fourth class arrived, the assumption behind the inlined code ("only these classes ever occur here") became false, so the JVM deoptimised: it threw away the compiled method and went back to a slower tier, then recompiled with the new, wider profile. Going back to a single class did not restore the fast version in the time I measured; the profile had recorded that this site is megamorphic. Real services see this as performance that changes after a particular request mix or a code path is first used, and as the first minutes after a deploy being different from the following hours. You can watch it happen: HotSpot's -XX:+PrintCompilation prints made not entrant when compiled code is discarded; V8 has --trace-opt and --trace-deopt.
Practical consequences: warm up an instance before it receives full traffic (a canary and a gradual ramp, or replay of representative requests); keep hot paths type-stable (the same shapes and classes), and be careful with generic code that funnels many types through one hot call; benchmark after warm-up and also during it; and when predictable latency matters more than peak speed, consider ahead-of-time compilation, or measure whether a warmed JIT stays warm under your real traffic.
6. Static and dynamic typing, from the compiler's point of view
In a statically typed language the compiler knows the type of every expression before the program runs, so it can emit a direct integer addition, lay objects out in memory with fixed field offsets and report type errors at build time. In a dynamically typed language that knowledge is not available until run time, which is why a JIT needs to rediscover it with profiling and guards. This is only a part of the debate between them (flexibility, speed of development, tooling), but it explains why gradual typing systems (TypeScript, Python type hints) mostly help the programmer and tools, while the runtime still has to check types, unless the language is compiled with the types being part of its semantics.
7. Where the idea shows up in everyday work
- Regular expressions, SQL and templates are small languages that get compiled to an internal form and then run. A prepared statement or a precompiled regex avoids doing the front end again on every use (indexing and query plans).
- Configuration and rules languages, expression engines, spreadsheet formulas and query filters in an API are interpreters. Building one with a hand-written parser and a tree walker is a normal weekend project, and a bytecode step is a later optimisation.
- Build tools and bundlers (
tsc, esbuild, the Go and Rust compilers) are compilers with caches; their speed depends on the pipeline stages and on incremental work. - Security: parsers are where untrusted text first meets your program, and many injection bugs are two languages mixed in one string (SQL injection). Compilers also produce the binaries whose provenance matters in supply-chain attacks (see CI/CD).
8. Common mistakes
- Saying that a language "is interpreted" or "is compiled" as if it were a fixed property.
- Benchmarking a JIT-compiled language on a single cold run, or an AOT language in a loop whose result is unused, and drawing conclusions.
- Optimising the code before measuring where the time goes; most of the time is in a few places.
- Assuming that a faster language fixes a slow design: 30 times from the language does not recover a quadratic algorithm (complexity).
- Mixing object shapes and types in hot paths of a dynamic language.
- Ignoring start-up and warm-up costs in serverless functions, command-line tools and freshly deployed instances.
- Relying on undefined behaviour in C or C++.
- Parsing structured data with regular expressions or string splitting when a real parser exists.
9. Things to mention in an interview
- The pipeline: lexer, parser (AST), analysis, IR and optimisation, code generation; front end and back end.
- Compiler against interpreter against JIT, and that "compiled" is a property of the implementation.
- Why a bytecode VM is faster than a tree walker, and why compiled code is faster still (dispatch overhead per operation); in my test about 1.5 times and 30 times.
- Stack machines against register machines, and what
disorjavapshow. - Common optimisations (constant folding, inlining, dead code elimination, escape analysis) and why inlining matters most.
- JIT: tiers, profiling, speculation with guards, deoptimisation, warm-up, hidden classes and monomorphic against megamorphic.
- Static against dynamic linking; what happens between
gcc -Eand an executable. - Start-up and warm-up costs in real deployments.
Quick recap
- A program passes through lexing, parsing, analysis, optimisation and code generation; the front end is about the language, the back end about the target.
- Interpreters pay a dispatch cost per operation. For the same loop, a bytecode machine was about 1.5 times faster than a tree walker and compiled code about 30 times faster.
- Optimisers do work at compile time (the compiler turned 12 × 12 × 8 into the constant 1152); check that your benchmark still measures something.
- A JIT profiles, compiles the hot code speculatively and deoptimises when its guesses fail. In V8 a cold call was about 10 times slower than a warm one, and mixing object shapes made the function 2.5 to 4 times slower and it stayed slow.
- Plan for warm-up and start-up in deployments, keep types and shapes consistent in hot code, and measure before you optimise.
Appendix: the experiment code
Four files: a C program with three ways to run one loop (interp.c, build with gcc -O2), a Python script that prints a syntax tree and bytecode (pyvm.py, Python 3.13), a shell script that runs the C compiler stage by stage (stages.sh, GCC) and a JavaScript file for Node.js 22 (jit.js). Times are from single runs on a small virtual machine and vary between runs and machines; the ratios (the bytecode machine is about 1.5 times faster than the tree walker, compiled code is 30 times faster) were stable across the runs I made, and the JIT figures are given as ranges. The compiled version uses a volatile counter so that the compiler cannot replace the loop by a formula, which would not be a fair comparison. The animation compiles and runs real expressions with a few lines of TypeScript, but it is a model, not CPython.
interp.c: a tree walker, a bytecode machine and compiled code for the same loop
// interp.c: the same loop run three ways: walking a syntax tree, running bytecode, and as compiled C.
// s = 0; i = 0; while (i < N) { s = s + (i * i) % 7; i = i + 1 }
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
enum { NUM, VAR, ADD, MUL, MOD, LT, ASSIGN, WHILE, SEQ };
typedef struct Node { int kind; long val; struct Node *a, *b; } Node;
static long vars[2]; // 0 = s, 1 = i
static Node *mk(int k, long v, Node *a, Node *b) { Node *n = malloc(sizeof *n); *n = (Node){k, v, a, b}; return n; }
// ---- 1. tree walker: one recursive call per node, a switch on the node kind
static long eval(Node *n) {
switch (n->kind) {
case NUM: return n->val;
case VAR: return vars[n->val];
case ADD: return eval(n->a) + eval(n->b);
case MUL: return eval(n->a) * eval(n->b);
case MOD: return eval(n->a) % eval(n->b);
case LT: return eval(n->a) < eval(n->b);
case ASSIGN: return vars[n->val] = eval(n->a);
case WHILE: while (eval(n->a)) eval(n->b); return 0;
case SEQ: eval(n->a); return eval(n->b);
}
return 0;
}
// ---- 2. bytecode: the tree is flattened once into a linear array, then run by a loop with a stack
enum { PUSH, LOAD, STORE, OP_ADD, OP_MUL, OP_MOD, OP_LT, JZ, JMP, HALT };
typedef struct { int op; long arg; } Ins;
static Ins code[64]; static int ncode;
static int emit(int op, long arg) { code[ncode] = (Ins){op, arg}; return ncode++; }
static void gen(Node *n) {
switch (n->kind) {
case NUM: emit(PUSH, n->val); break;
case VAR: emit(LOAD, n->val); break;
case ADD: gen(n->a); gen(n->b); emit(OP_ADD, 0); break;
case MUL: gen(n->a); gen(n->b); emit(OP_MUL, 0); break;
case MOD: gen(n->a); gen(n->b); emit(OP_MOD, 0); break;
case LT: gen(n->a); gen(n->b); emit(OP_LT, 0); break;
case ASSIGN: gen(n->a); emit(STORE, n->val); break;
case SEQ: gen(n->a); gen(n->b); break;
case WHILE: { int top = ncode; gen(n->a); int jz = emit(JZ, 0); gen(n->b); emit(JMP, top); code[jz].arg = ncode; break; }
}
}
static void run(void) {
long st[32]; int sp = 0, pc = 0;
for (;;) {
Ins in = code[pc++];
switch (in.op) {
case PUSH: st[sp++] = in.arg; break;
case LOAD: st[sp++] = vars[in.arg]; break;
case STORE: vars[in.arg] = st[--sp]; break;
case OP_ADD: sp--; st[sp-1] += st[sp]; break;
case OP_MUL: sp--; st[sp-1] *= st[sp]; break;
case OP_MOD: sp--; st[sp-1] %= st[sp]; break;
case OP_LT: sp--; st[sp-1] = st[sp-1] < st[sp]; break;
case JZ: if (!st[--sp]) pc = in.arg; break;
case JMP: pc = in.arg; break;
case HALT: return;
}
}
}
// ---- 3. native: what a compiler produces for the same program
static long native(long n) { long s = 0; for (volatile long i = 0; i < n; i++) s += (i * i) % 7; return s; }
static double now(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec + t.tv_nsec / 1e9; }
int main(int argc, char **argv) {
long N = atol(argv[1]);
Node *prog = mk(SEQ, 0, mk(ASSIGN, 0, mk(NUM, 0, 0, 0), 0), mk(SEQ, 0, mk(ASSIGN, 1, mk(NUM, 0, 0, 0), 0),
mk(WHILE, 0, mk(LT, 0, mk(VAR, 1, 0, 0), mk(NUM, N, 0, 0)),
mk(SEQ, 0, mk(ASSIGN, 0, mk(ADD, 0, mk(VAR, 0, 0, 0), mk(MOD, 0, mk(MUL, 0, mk(VAR, 1, 0, 0), mk(VAR, 1, 0, 0)), mk(NUM, 7, 0, 0))), 0),
mk(ASSIGN, 1, mk(ADD, 0, mk(VAR, 1, 0, 0), mk(NUM, 1, 0, 0)), 0)))));
double t = now(); vars[0] = vars[1] = 0; eval(prog); double t1 = now() - t; long r1 = vars[0];
ncode = 0; gen(prog); emit(HALT, 0);
t = now(); vars[0] = vars[1] = 0; run(); double t2 = now() - t; long r2 = vars[0];
t = now(); long r3 = native(N); double t3 = now() - t;
printf("N=%ld results equal: %s (%ld bytecode instructions in the program)\n", N, (r1 == r2 && r2 == r3) ? "yes" : "NO", (long)ncode);
printf("tree walker: %.2f s bytecode VM: %.2f s compiled: %.2f s\n", t1, t2, t3);
printf("bytecode is %.1fx faster than the tree walker; compiled code is %.0fx faster than the tree walker\n", t1 / t2, t1 / t3);
return 0;
}
pyvm.py: the syntax tree and bytecode of a Python function
import ast, dis, time
src = "total = price * qty + 5"
print("1. source -> syntax tree")
print(ast.dump(ast.parse(src), indent=2)[:600])
def f(price, qty):
return price * qty + 5
print("\n2. the bytecode CPython runs for f(price, qty) = price * qty + 5")
dis.dis(f)
print(" instructions:", len(list(dis.get_instructions(f))))
print("\n3. a dynamically typed '+' must check the types every time")
def add(a, b): return a + b
for a, b in ((1, 2), (1.5, 2), ("a", "b"), ([1], [2])):
print(f" add({a!r}, {b!r}) = {add(a, b)!r}")
n = 3_000_000
t = time.perf_counter()
for i in range(n): add(i, 1)
print(f" {n:,} int additions through a function call: {time.perf_counter() - t:.2f} s")
stages.sh: the stages of a C compiler, one at a time
# the stages of a C compiler, one at a time
cat > hello.c <<'C'
#include <stdio.h>
#define SQUARE(x) ((x) * (x))
int main(void) { int n = 12; printf("%d\n", SQUARE(n) * 8); return 0; }
C
gcc -E hello.c | wc -l | sed 's/^/preprocessed lines (the header is pasted in): /'
gcc -S -O0 hello.c -o hello_O0.s; grep -c '^\s' hello_O0.s | sed 's/^/assembly lines at -O0: /'
gcc -S -O2 hello.c -o hello_O2.s; grep -E 'imul|sal|shl|\$1152|\$144' hello_O2.s | head -3 | sed 's/^/at -O2 the multiplication is already done by the compiler: /'
gcc -c hello.c -o hello.o && file hello.o | cut -d, -f1-2
gcc hello.o -o hello && ls -l hello | awk '{print "linked program: " $5 " bytes"}' && ./hello
jit.js: JIT warm-up and changing object shapes in V8
// jit.js: V8 warms up, then slows down when the types change (run with: node jit.js)
function sumX(points) { let s = 0; for (let i = 0; i < points.length; i++) s += points[i].x; return s; }
const mk = (shape, n) => Array.from({ length: n }, (_, i) => shape(i));
const A = (i) => ({ x: i, y: 1 }); // one object shape
const B = (i) => ({ y: 1, x: i }); // same fields, different order: a different hidden class
const C = (i) => ({ x: i, y: 1, z: 2 });
const D = (i) => ({ a: 1, x: i });
const E = (i) => ({ b: 1, c: 2, x: i });
const N = 200000;
function time(label, arr, reps) {
const t = process.hrtime.bigint(); let r = 0;
for (let k = 0; k < reps; k++) r += sumX(arr);
const ms = Number(process.hrtime.bigint() - t) / 1e6;
console.log(`${label.padEnd(44)} ${(ms / reps).toFixed(3)} ms per call`);
return r;
}
const mono = mk(A, N);
console.log("1. warm-up: the same call repeated on the same shape");
for (const reps of [1, 1, 1, 1, 5, 50, 200]) time(`call batch of ${reps}`, mono, reps);
console.log("2. the same code with objects of several shapes mixed in one array");
const mixed = mono.map((p, i) => [A, B, C, D, E][i % 5](i));
time("five shapes (megamorphic)", mixed, 100);
console.log("3. back to a single shape");
time("one shape again", mono, 100);
Semantics against implementation: undefined behaviour in C, defined behaviour in Java, and bytecode that changes between Python versions
ub.c (build with gcc -O0, -O2, -O2 -fwrapv, and with clang), Ub.java (JDK 21; run with -Xint, -XX:TieredStopAtLevel=1 and the defaults) and bc.py (run with each Python version you have).
#include <limits.h>
#include <stdio.h>
/* Signed overflow is undefined behaviour in C: the compiler may assume it never happens, and then "a + b < a" means just "b < 0". */
int add_overflows(int a, int b) { return a + b < a; }
int main(int argc, char **argv) {
int a = INT_MAX, b = 1; /* decided at run time so that the compiler cannot fold the call away */
if (argc > 5) a = 0;
printf("does INT_MAX + 1 overflow? the check says: %s\n", add_overflows(a, b) ? "yes" : "no");
return 0;
}
public class Ub {
static boolean addOverflows(int a, int b) { return a + b < a; }
public static void main(String[] args) {
int a = Integer.MAX_VALUE, b = 1; if (args.length > 5) a = 0;
System.out.println("does Integer.MAX_VALUE + 1 overflow? the check says: " + (addOverflows(a, b) ? "yes" : "no") + " (Java defines the wrap-around, so every implementation agrees)");
}
}
import dis, sys
def f(prices, qty):
total = 0
for p in prices:
total += p * qty
return [round(total, 2)] + [x for x in prices if x > 1]
ops = [i.opname for i in dis.get_instructions(f)]
print(f"Python {sys.version.split()[0]}: {len(ops)} instructions; first ones: {' '.join(ops[:9])}")
print(f" opcodes used: {sorted(set(ops))}")
Whole-process time of the same loop in five implementations
Put the four sources and the driver in one folder and run python3 cross.py; it needs gcc, a JDK, Node.js and Python, and the billion-iteration Python run takes about two minutes.
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) { long n = atol(argv[1]); long s = 0; for (long i = 0; i < n; i++) s = (s * 31 + i) % 1000003; printf("%ld\n", s); return 0; }
public class Loop { public static void main(String[] a) { long n = Long.parseLong(a[0]), s = 0; for (long i = 0; i < n; i++) s = (s * 31 + i) % 1000003; System.out.println(s); } }
const n = Number(process.argv[2]); let s = 0; for (let i = 0; i < n; i++) s = (s * 31 + i) % 1000003; console.log(s);
import sys
n = int(sys.argv[1]); s = 0
for i in range(n): s = (s * 31 + i) % 1000003
print(s)
"""Total wall-clock time of whole processes (start-up included) for the same loop in an AOT-compiled language, a JIT, a bytecode interpreter and a JVM running only its interpreter."""
import statistics, subprocess, sys, time
subprocess.run(["gcc", "-O2", "-o", "loop_c", "loop.c"], check=True)
env = {"JAVA_TOOL_OPTIONS": "", "PATH": "/usr/bin:/bin:/usr/local/bin"}
subprocess.run(["javac", "Loop.java"], check=True, env=env, capture_output=True)
impls = {"C (gcc -O2)": ["./loop_c"], "Java (HotSpot JIT)": ["java", "Loop"], "Java -Xint (interpreter only)": ["java", "-Xint", "Loop"],
"Node.js (V8 JIT)": ["node", "loop.js"], "Python 3.13 (interpreter)": ["python3", "loop.py"]}
sizes = [1_000, 1_000_000, 100_000_000, 1_000_000_000]
LIMIT = 40 # do not run anything that is expected to take longer than this many seconds
print(f"{'':<32}" + "".join(f"{n:>16,}" for n in sizes) + " (iterations; seconds for the whole process)")
answers = {}
slow = set()
for name, cmd in impls.items():
row = []
for n in sizes:
if name in slow: row.append("not run"); continue
reps = 5 if n <= 1_000_000 else 1
ts = []
for _ in range(reps):
t = time.perf_counter(); out = subprocess.run(cmd + [str(n)], capture_output=True, text=True, env={**env}).stdout.strip(); ts.append(time.perf_counter() - t)
answers.setdefault(n, set()).add(out)
m = statistics.median(ts); row.append(f"{m:.3f}")
if m * (sizes[min(sizes.index(n) + 1, len(sizes) - 1)] / n) > LIMIT * 4 and n != sizes[-1]: slow.add(name)
print(f"{name:<32}" + "".join(f"{x:>16}" for x in row))
print("all implementations printed the same answer for each size:", all(len(v) == 1 for v in answers.values()))
An ahead-of-time sort with the wrong algorithm against sorted()
Build with gcc -O2 -o insertion insertion.c, then run ./insertion 100000 and python3 sorted_py.py 100000.
/* A correct, ahead-of-time compiled sort with the wrong algorithm for the job: insertion sort, O(n^2). */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(int argc, char **argv) {
long n = atol(argv[1]); int *a = malloc(n * sizeof(int)); unsigned x = 12345;
for (long i = 0; i < n; i++) { x = x * 1103515245u + 12345u; a[i] = x >> 8; }
struct timespec t0, t1; clock_gettime(CLOCK_MONOTONIC, &t0);
for (long i = 1; i < n; i++) { int v = a[i]; long j = i - 1; while (j >= 0 && a[j] > v) { a[j + 1] = a[j]; j--; } a[j + 1] = v; }
clock_gettime(CLOCK_MONOTONIC, &t1);
printf("C insertion sort of %ld integers (gcc -O2): %.3f s (sorted: %d)\n", n, (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9, a[0] <= a[n / 2] && a[n / 2] <= a[n - 1]);
}
import random, sys, time
n = int(sys.argv[1]); r = random.Random(1); a = [r.randrange(1 << 24) for _ in range(n)]
t = time.perf_counter(); b = sorted(a); dt = time.perf_counter() - t
print(f"Python sorted() of {n} integers: {dt:.3f} s (sorted: {b == sorted(b)})")
Inlining and deoptimisation: C function pointers against a JVM call site
Build with gcc -O2 -o dispatch_c dispatch.c, run ./dispatch_c 4 1000000000; java Dispatch 4 1000000000 runs the Java version and java Dispatch phases 300000000 the deoptimisation experiment.
/* A loop that calls one of several small functions through a table that is only known at run time. An ahead-of-time compiler cannot inline them. */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static int inc(int x) { return x + 1; }
static int dbl(int x) { return x * 2 + 1; }
static int xr(int x) { return x ^ 0x5555; }
static int neg(int x) { return -x + 3; }
int main(int argc, char **argv) {
int variants = atoi(argv[1]); long n = atol(argv[2]);
int (*all[4])(int) = {inc, dbl, xr, neg}; int (*seq[1024])(int);
for (int i = 0; i < 1024; i++) seq[i] = all[i % variants];
struct timespec a, b; clock_gettime(CLOCK_MONOTONIC, &a);
int s = 1; for (long i = 0; i < n; i++) s = seq[i & 1023](s);
clock_gettime(CLOCK_MONOTONIC, &b);
printf("C, %d function(s) in the table: %.2f ns per call (%d)\n", variants, ((b.tv_sec - a.tv_sec) * 1e9 + (b.tv_nsec - a.tv_nsec)) / n, s & 1);
}
public class Dispatch {
interface Op { int apply(int x); }
static final class Inc implements Op { public int apply(int x) { return x + 1; } }
static final class Dbl implements Op { public int apply(int x) { return x * 2 + 1; } }
static final class Xr implements Op { public int apply(int x) { return x ^ 0x5555; } }
static final class Neg implements Op { public int apply(int x) { return -x + 3; } }
static final Op[] ALL = {new Inc(), new Dbl(), new Xr(), new Neg()};
static Op[] seq(int variants) { Op[] s = new Op[1024]; for (int i = 0; i < 1024; i++) s[i] = ALL[i % variants]; return s; }
static int run(Op[] seq, long n, int s) { for (long i = 0; i < n; i++) s = seq[(int) (i & 1023)].apply(s); return s; }
public static void main(String[] args) {
long n = Long.parseLong(args[1]);
if (args[0].equals("phases")) {
// one JVM, one hot loop; the set of classes the call site sees changes while the program runs
int s = 1; int[] schedule = {1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1};
System.out.println("batch classes seen at the call site ns per call");
for (int b = 0; b < schedule.length; b++) {
Op[] sq = seq(schedule[b]); long t = System.nanoTime(); s = run(sq, n, s); double ns = (System.nanoTime() - t) / (double) n;
System.out.printf("%5d %29d %12.2f%n", b + 1, schedule[b], ns);
}
System.out.println("(" + (s & 1) + ")");
} else {
int variants = Integer.parseInt(args[0]); Op[] sq = seq(variants); int s = 1;
for (int w = 0; w < 5; w++) s = run(sq, n / 5, s); // warm-up, discarded
long t = System.nanoTime(); s = run(sq, n, s);
System.out.printf("Java, %d class(es) at the call site: %.2f ns per call (%d)%n", variants, (System.nanoTime() - t) / (double) n, s & 1);
}
}
}
Sources
- Alfred Aho, Monica Lam, Ravi Sethi and Jeffrey Ullman, Compilers: Principles, Techniques, and Tools ("the Dragon Book", 2nd ed., Pearson, 2006).
- Robert Nystrom, Crafting Interpreters (2021), which builds both a tree-walking interpreter and a bytecode virtual machine.
- Keith Cooper and Linda Torczon, Engineering a Compiler (Morgan Kaufmann, 3rd ed., 2022).
- Python documentation:
astanddis, and the CPython developer guide, Design of CPython's compiler and the specializing adaptive interpreter (PEP 659). - V8 team blog: Launching Ignition and TurboFan, Fast properties in V8 (hidden classes) and Sparkplug.
- Oracle, The Java Virtual Machine Specification (Java SE 21), and the HotSpot tiered compilation notes.
- GCC documentation, Overall options (
-E,-S,-c) and Optimize options. - WebAssembly: specification and introduction; and Chris Lattner and Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation (CGO 2004).
- ISO C standard (undefined behaviour) and the GCC and Clang documentation for
-fwrapvand-fsanitize=undefined; John Regehr, A Guide to Undefined Behavior in C and C++. - The Java Language Specification and the Java Virtual Machine Specification (JVM bytecode); Python documentation,
dis("CPython implementation detail": the bytecode may change between versions). - OpenJDK, HotSpot compiler documentation and
-XX:+PrintCompilation; V8,--trace-deoptand the optimisation pipeline.
Practise this topic: CS Fundamentals