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

  1. Lexing (scanning) splits the characters into tokens: price, *, qty, +, 5. Whitespace and comments disappear.
  2. Parsing applies the grammar and builds an abstract syntax tree (AST) that records structure and precedence. Python's own ast module shows it for total = price * qty + 5: an Assign whose value is an Add of a Mult (price, qty) and the constant 5. The multiplication is lower in the tree because it binds tighter, so the tree needs no parentheses.
  3. 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".
  4. Intermediate representation (IR) and optimisation rewrite the program into a simpler form where it is easier to improve (see below).
  5. 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

ApproachWhat happensExamplesStart-upSpeed once running
Ahead-of-time (AOT) compilerall of the program is translated to machine code before it runsC, C++, Rust, Goinstantoften the fastest, but see 3.1
Interpreterthe program is executed directly from the tree or from bytecode, instruction by instructionCPython, Ruby (MRI), shellsinstantusually the slowest per instruction, but see 3.1
Just-in-time (JIT) compilerstarts by interpreting; finds the hot code at run time and compiles that to machine codeJavaScript (V8), Java (HotSpot), .NET, PyPyslow warm-upclose 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.

LayerWhat it isWho defines itExamples
Language semanticswhat a program means: which results and effects are guaranteed, and what is left undefined or unspecifieda specification or standardthe C standard, the Java Language Specification, ECMAScript, the Python language reference
Intermediate form (bytecode)the instructions a compiler front end produces for a virtual machinesometimes a specification, sometimes a private detailJVM bytecode and WebAssembly are specified; CPython's bytecode and V8's Ignition bytecode are internal
Runtime implementationthe program that executes it: interpreter, JIT, garbage collector, standard library, optimisereach vendor or projectCPython, 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 flagsDoes 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:

CPythonInstructionsDifferences
3.1128the list comprehension is a separate nested function (MAKE_FUNCTION, PRECALL)
3.1246comprehensions are inlined (LOAD_FAST_AND_CLEAR, LIST_APPEND, END_FOR)
3.1347new 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 }.

  1. A tree-walking interpreter evaluates the AST directly: a recursive call and a switch for every node.
  2. A bytecode virtual machine: the tree is flattened once into 22 instructions and a loop runs them on a stack.
  3. Compiled C for the same loop.
ImplementationTimeRelative
tree walker2.3 to 2.4 s1
bytecode VM1.55 to 1.6 s1.4 to 1.6 times faster
compiled to machine code0.08 sabout 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:

Implementation1,000 iterations1 million100 million1 billion
C (gcc -O2)0.001 s0.006 s0.51 s5.0 s
Java (HotSpot, JIT)0.037 s0.045 s0.62 s5.1 s
Node.js (V8, JIT)0.031 s0.034 s0.60 s5.8 s
Java with only its interpreter (-Xint)0.033 s0.055 s2.3 s22.6 s
Python 3.13 (interpreter)0.014 s0.116 s11.0 s104.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:

IntegersC insertion sortPython sorted()
20,0000.039 s0.004 s
100,0001.19 s0.029 s
400,00016.7 s0.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 siteC (indirect call, gcc -O2)Java (HotSpot, after warm-up)
11.62 ns0.77 ns
21.76 ns1.07 ns
41.97 ns4.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 loopAOT 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 requirementsprefer 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 networknone 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:

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:

SituationTime per call
first call (cold)3 to 4.5 ms
second callabout 1 ms
after warm-upabout 0.4 ms
same code, the array now mixes five different object shapes1.0 to 1.7 ms (2.5 to 4 times slower)
back to objects of one shapestill 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):

BatchesClasses seen at the call siteTime per call
1 to 610.76 to 1.03 ns (the first batch includes the warm-up)
7 to 1020.87 to 1.01 ns
11 to 1643.7 to 5.5 ns (4 to 6 times slower)
17 to 201 again4.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

8. Common mistakes

9. Things to mention in an interview

Quick recap

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

Practise this topic: CS Fundamentals

More guides