How Computers Run Programs
From source code to electrons: the CPU's fetch-execute loop, the memory hierarchy, compiled versus interpreted languages, and how the call stack tracks function calls.
beginner40 min#cpu#memory-hierarchy#compilation#interpreter#call-stack
Prerequisites: Big-O and Complexity Analysis
Why it matters
Every performance question, every confusing crash, and every "why is this language faster?" debate comes back to the same machine model. Knowing roughly what the CPU, memory, and call stack are doing explains why arrays beat linked lists in practice, why deep recursion crashes, why Python is slower than C, and why a program that fits in cache can run ten times faster than one that does not. You do not need to design chips. A good mental model is enough.
Intuition
Think of a chef (the CPU) in a kitchen. The chef follows a recipe one instruction at a time. Ingredients the chef is holding right now are the registers. The cutting board beside them is the cache. The fridge across the room is RAM. The warehouse across town is the disk. The chef works fast, but every trip to a farther place costs far more time, so a good kitchen keeps what you need close.
A function call is like pausing a recipe to follow a sub-recipe: you put a sticky note on the current page ("resume at step 7"), start the sub-recipe, and when it ends you pick the note back up. A stack of sticky notes, one per unfinished recipe, is the call stack.
How it works
The CPU's loop
A processor does one thing, forever: fetch the next instruction from memory, decode what it means, execute it (arithmetic, move data, jump), and repeat. A program counter register holds the address of the next instruction. Instructions are tiny: add two registers, load a value from an address, compare, branch. Billions run each second, and modern cores overlap them in a pipeline and run several at once.
The memory hierarchy
Faster memory is smaller and more expensive, so computers stack several levels.
level typical size typical access time
registers a few hundred B under 1 ns
L1 cache tens of KB about 1 ns
L2 / L3 cache MBs to tens MB 3 to 20 ns
RAM GBs about 100 ns
SSD hundreds of GB about 100,000 ns
network / disk far larger milliseconds
The numbers are rough and vary by hardware, but the ratios matter: RAM is around a hundred times slower than the nearest cache. Data moves in blocks called cache lines (commonly 64 bytes). Reading a[0] pulls a[1] through a[15] into the cache for free, which is why walking an array in order is fast, and why chasing pointers around memory is slow. This property is called locality.
From source to execution
- Compiled languages (C, C++, Rust, Go) are translated ahead of time into machine code for a specific CPU. At run time the CPU executes that code directly. You pay the translation cost once, and the result is fast.
- Interpreted languages read the program at run time. CPython first compiles source into bytecode, a compact instruction set for a virtual machine, then a loop in C fetches and executes each bytecode instruction. That extra layer is the main reason plain Python is slower than C.
- JIT compilation (V8 for JavaScript, the JVM) starts by interpreting, watches which code is hot, and compiles that part to machine code while the program runs. This gets close to compiled speed for many workloads.
The line is blurry: almost every language uses some mix. What matters is how many layers sit between your code and the CPU.
The call stack
Each time a function is called, the runtime pushes a stack frame holding its parameters, local variables, and the return address. When the function returns, its frame is popped and execution continues from the saved address. Because frames are pushed and popped in last-in, first-out order, a simple stack is all you need. The stack has a fixed size, typically a megabyte or a few. Recursing too deeply overflows it: a stack overflow. Python raises a RecursionError at about 1000 frames by default; JavaScript throws a RangeError at roughly ten thousand, depending on the engine.
| Operation | Time | Notes |
|---|---|---|
| Register access | about 1 cycle | Fastest, tiny |
| L1 cache hit | about 4 cycles | Per cache line of 64 bytes |
| RAM access (cache miss) | about 200+ cycles | Why locality matters |
| Function call + return | O(1) | Push and pop one frame |
| Recursion depth d | O(d) stack space | One frame per active call |
Code: a tiny stack machine and a visible call stack
A virtual machine is a loop that fetches an instruction, executes it, and moves on. The version below runs (2 + 3) * 4 as stack instructions, which is the same idea as bytecode. The second part records the call stack as a recursive factorial goes down, printing it when the deepest call is reached.
def run(program):
stack = []
for op, *arg in program:
if op == "push":
stack.append(arg[0])
elif op == "add":
b, a = stack.pop(), stack.pop()
stack.append(a + b)
elif op == "mul":
b, a = stack.pop(), stack.pop()
stack.append(a * b)
else:
raise ValueError("unknown op " + op)
return stack.pop()
# (2 + 3) * 4 as stack-machine instructions
print(run([("push", 2), ("push", 3), ("add",), ("push", 4), ("mul",)]))
call_stack = []
def fact(n):
call_stack.append(f"fact({n})")
if n <= 1:
print(" > ".join(call_stack))
result = 1
else:
result = n * fact(n - 1)
call_stack.pop()
return result
print(fact(4))function run(program) {
const stack = [];
for (const [op, arg] of program) {
if (op === "push") stack.push(arg);
else if (op === "add") {
const b = stack.pop(), a = stack.pop();
stack.push(a + b);
} else if (op === "mul") {
const b = stack.pop(), a = stack.pop();
stack.push(a * b);
} else throw new Error("unknown op " + op);
}
return stack.pop();
}
// (2 + 3) * 4 as stack-machine instructions
console.log(run([["push", 2], ["push", 3], ["add"], ["push", 4], ["mul"]]));
const callStack = [];
function fact(n) {
callStack.push(`fact(${n})`);
let result;
if (n <= 1) {
console.log(callStack.join(" > "));
result = 1;
} else {
result = n * fact(n - 1);
}
callStack.pop();
return result;
}
console.log(fact(4));Both versions print:
20
fact(4) > fact(3) > fact(2) > fact(1)
24
The middle line is the call stack at its deepest: four frames waiting, the last one about to return. Each frame is popped on the way back as the products are computed.
The call stack while running fact(4). The stack grows to four frames, then shrinks as each call returns. Index 0 is the bottom of the stack.
Common pitfalls
- Assuming all memory accesses cost the same: the same
O(n)loop can differ by 10x depending on whether it walks memory in order or jumps around. Big-O hides this. - Unbounded recursion: a missing or wrong base case, or recursing on large input, overflows the stack. Convert to a loop with an explicit stack, or raise limits only as a last resort.
- Thinking "interpreted" means "slow in every case": work done inside native libraries (NumPy, regex, sorting built-ins) runs at C speed. Keep hot loops out of pure Python.
- Believing compiled code is always faster: a poor algorithm in C loses to a good one in Python. Choose the algorithm first.
- Ignoring I/O: a disk or network call costs millions of CPU cycles. Batching requests often matters more than micro-optimizing code.
Practice
Order the memory levels easy
Hint
Think of size and speed: smaller is faster.
Show solution
From fastest to slowest: registers, L1 cache, L2/L3 cache, RAM, SSD, network. Each step down gives more capacity and costs more latency. Programs run fast when the data they touch most is found in the closest levels.
Why is summing a 2D array row by row faster than column by column? medium
Hint
Arrays of arrays store each row contiguously. What does a cache line grab?
Show solution
A row is contiguous, so reading it in order uses every byte of each fetched cache line. Walking down a column jumps by a whole row each step, so each access can land on a different cache line and load 64 bytes to use 8. Both are O(n * m), but the column order can be several times slower on large arrays. The same total work, different locality.
Extend the stack machine medium
Hint
Pop two values, apply the operation, push the result, just like add.
Show solution
Add a sub instruction and evaluate 10 - (2 + 3). Program: push 10, push 2, push 3, add, sub. Careful with order: for sub the first value popped is the right operand, so compute a - b where b is popped first. The result is 5. This is exactly how expression evaluation works in many bytecode VMs.
Estimate how deep you can recurse hard
Hint
Stack size divided by frame size gives the number of frames.
Show solution
Suppose the stack is 8 MB and a frame uses about 100 bytes: roughly 8,000,000 / 100 = 80,000 frames. In Python each frame is larger and the interpreter imposes its own limit near 1000, so a recursive sum over a list of 10,000 items fails even though memory is available. The fix is an iterative loop or an explicit stack, giving the same O(n) time with O(1) or heap-allocated space instead of call-stack space.
Interview questions
- What happens when you call a function? Arguments and a return address are pushed as a frame; control jumps to the function; on return the frame is popped and execution resumes after the call.
- Why is array traversal faster than linked-list traversal? Arrays are contiguous, so cache lines and prefetching help. List nodes are scattered, so each hop may be a cache miss.
- Compiled versus interpreted? Compiled code is translated to machine code ahead of time; interpreters execute at run time through bytecode or the source. JIT blends both.
- What causes a stack overflow, and how do you avoid it? Too many nested calls, usually runaway or very deep recursion. Fix the base case, iterate, or use an explicit stack.
Interviewers look for: a clear mental model rather than memorized trivia, and the ability to connect hardware facts (caches, stack size) to practical consequences.
Quick check
Which change most likely speeds up a loop over a huge array on real hardware, without changing its Big-O?
Finished this lesson?
Further resources
- Central processing unit (Wikipedia) (article)
- Memory hierarchy (Wikipedia) (article)
- Call stack (Wikipedia) (article)