How Computers Work: CPU, Memory Hierarchy & Caches
Every program you will ever write — a Python script, a React app, a Go microservice, a database — eventually becomes a stream of very simple instructions executed by a piece of silicon that can do roughly four things: move numbers around, add them, compare them, and jump somewhere else. Everything else is layers built on top.
You can write useful software for years without knowing what happens underneath. But sooner or later you hit something that only makes sense if you do: a loop that gets 6x faster when you sort its input first, a matrix multiply that gets 10x faster when you swap two for lines, two threads that slow each other down while touching different variables, or a sum of money that comes out as 0.30000000000000004. This page is the mental model that explains all of those.
This is lesson 1 of the CS Core Fundamentals course. Later lessons (object-oriented programming, data structures and algorithms, operating systems, concurrency, networks, databases) all assume the picture built here: data is bits, the CPU executes instructions, and memory is a hierarchy where distance is time.
How to read this page
No prior hardware knowledge is assumed. Each section starts with the plain idea and then goes one level deeper. If a section gets heavy, skim the tables and come back later — the "Why this matters" section near the end pulls the practical lessons together.
Part 1 — Everything Is Bits
A computer stores and processes bits: values that are either 0 or 1, physically represented as a voltage being low or high, a capacitor being charged or not, or a magnetic region pointing one way or the other. Bits on their own mean nothing. Meaning comes from an agreed encoding — a rule for how a pattern of bits maps to a number, a letter, a colour or an instruction.
| Unit | Size | Can represent |
|---|---|---|
| bit | 1 bit | 2 values (0, 1) |
| nibble | 4 bits | 16 values — one hex digit (0–F) |
| byte | 8 bits | 256 values — the smallest addressable unit of memory |
| word | 32 or 64 bits | The CPU's "natural" size; 64 bits on modern machines |
| KiB / MiB / GiB | 2^10 / 2^20 / 2^30 bytes | Memory sizes (a "KB" in marketing is often 1000) |
A useful habit: think in hexadecimal when looking at raw memory. One hex digit is exactly 4 bits, so a byte is always two hex digits: 0xFF = 1111 1111 = 255.
Unsigned integers
An unsigned integer is plain binary place value. The 8-bit pattern 0100 1101 is:
0×128 + 1×64 + 0×32 + 0×16 + 1×8 + 1×4 + 0×2 + 1×1 = 77
With n bits you can represent 0 to 2^n − 1. A uint8 holds 0–255, a uint32 holds 0–4,294,967,295, a uint64 holds 0 to about 1.8 × 10^19.
When you exceed the maximum, the value wraps around — 255 + 1 in 8 bits is 0, because the carry out of the top bit simply has nowhere to go. This is not a bug in the hardware; it is arithmetic modulo 2^n.
Signed integers and two's complement
How do you store −5? Almost every machine since the 1970s uses two's complement: the top bit has a negative weight. In 8 bits, the place values are −128, 64, 32, 16, 8, 4, 2, 1.
To negate a number: flip every bit, then add 1.
5 = 0000 0101
flip = 1111 1010
+1 = 1111 1011 = -128 + 64 + 32 + 16 + 8 + 2 + 1 = -5
Why this scheme won:
- One adder does everything. Adding
0000 0101(5) and1111 1011(−5) gives1 0000 0000; drop the carry and you get 0. The CPU does not need separate circuits for signed and unsigned addition. - Only one zero. Older schemes (sign-magnitude, ones' complement) had both +0 and −0.
- Range is asymmetric: an
int8holds −128 to +127. That asymmetry is whyabs(INT_MIN)overflows in C, Java and Go.
Overflow is language-dependent
In C and C++, signed overflow is undefined behaviour — the compiler may assume it never happens and optimise accordingly. Go and Java wrap silently. Rust panics in debug builds and wraps in release builds (use checked_add, wrapping_add or saturating_add to say what you mean). The hardware always wraps; the language decides what that means.
Floating point, and why 0.1 + 0.2 != 0.3
Integers cannot hold 3.14 or 6.02 × 10^23. For that, CPUs implement IEEE 754 floating point, which is scientific notation in binary. A 64-bit double splits its bits into:
| Field | Bits | Meaning |
|---|---|---|
| Sign | 1 | 0 = positive, 1 = negative |
| Exponent | 11 | Power of two, stored with a bias of 1023 |
| Mantissa (fraction) | 52 | The significant digits, with an implicit leading 1 |
The value is (−1)^sign × 1.fraction × 2^(exponent − 1023). That gives about 15–17 significant decimal digits and a range up to about 1.8 × 10^308. A 32-bit float has 8 exponent bits and 23 mantissa bits — about 7 decimal digits.
Here is the catch. In decimal, 1/3 cannot be written exactly — it is 0.3333… forever. In binary, 1/10 cannot be written exactly either. 0.1 in binary is 0.0001100110011001100… repeating. The double stores the nearest representable value, which is very slightly more than 0.1. Same for 0.2. Add the two rounded values and round again, and you land on the representable number just above 0.3, not the one closest to 0.3:
package main
import "fmt"
func main() {
a, b := 0.1, 0.2
fmt.Println(a+b == 0.3) // false
fmt.Printf("%.17f\n", a+b) // 0.30000000000000004
fmt.Printf("%.17f\n", 0.3) // 0.29999999999999999
}
This is not a Go bug, a JavaScript bug or a Python bug. Every language that uses hardware doubles prints the same thing. Practical consequences:
- Never compare floats with
==. Compare with a tolerance:math.Abs(a-b) < 1e-9(or a relative tolerance for large values). - Never store money in floats. Store integer cents (or the smallest currency unit), or use a decimal type (
decimal.Decimalin Python,BigDecimalin Java,NUMERICin SQL). - Addition is not associative.
(a + b) + ccan differ froma + (b + c). This is why a parallel sum can give a slightly different answer from a sequential one, and why compilers will not reorder float maths unless you pass flags like-ffast-math. - IEEE 754 also defines special values:
+Inf,−Inf, andNaN(not a number).NaN != NaNis true — the only value not equal to itself.
Endianness — which byte comes first
A 32-bit integer occupies four bytes. In what order are they stored in memory? Take 0x12345678:
| Address | Big-endian | Little-endian |
|---|---|---|
base + 0 | 12 | 78 |
base + 1 | 34 | 56 |
base + 2 | 56 | 34 |
base + 3 | 78 | 12 |
- Little-endian (least significant byte at the lowest address): x86-64, and ARM as almost always configured. This is what your laptop and nearly every server does.
- Big-endian ("network byte order"): the order used in TCP/IP headers and many file formats.
You rarely see endianness until you read raw bytes — parsing a binary file format, writing a network protocol, or reading a hex dump. Then it matters a lot:
#include <stdio.h>
#include <stdint.h>
int main(void) {
uint32_t x = 0x12345678;
uint8_t *p = (uint8_t *)&x;
printf("%02x %02x %02x %02x\n", p[0], p[1], p[2], p[3]);
// On x86-64 or ARM64: 78 56 34 12
return 0;
}
Go makes the choice explicit and portable with binary.BigEndian.Uint32(buf) and binary.LittleEndian.Uint32(buf); Rust has u32::from_be_bytes and u32::from_le_bytes.
Characters, Unicode and UTF-8
Text is numbers too. Unicode assigns every character a code point: A is U+0041, é is U+00E9, € is U+20AC, 😀 is U+1F600. There are over 150,000 assigned characters, so a code point needs up to 21 bits.
UTF-8 is the encoding that turns code points into bytes, and it is what the web, Linux, Go and Rust use by default. It is variable-length:
| Code point range | Bytes | Example | Encoded bytes |
|---|---|---|---|
| U+0000 – U+007F | 1 | A (U+0041) | 41 |
| U+0080 – U+07FF | 2 | é (U+00E9) | C3 A9 |
| U+0800 – U+FFFF | 3 | € (U+20AC) | E2 82 AC |
| U+10000 – U+10FFFF | 4 | 😀 (U+1F600) | F0 9F 98 80 |
Two clever properties: plain ASCII text is already valid UTF-8 (backwards compatible), and you can always find the start of a character by looking at the top bits of a byte, so a corrupted byte damages one character, not the rest of the string.
The consequence for programmers: byte length is not character length. In Go, len("héllo") is 6, not 5; you need utf8.RuneCountInString. In Rust, "héllo".len() is also 6 and you cannot index a String by integer because position 2 might be the middle of a character. JavaScript strings are UTF-16 internally, so "😀".length is 2. Even "character" is ambiguous — a single visible emoji like a family or a flag can be several code points glued together.
The big idea of Part 1
The same 32 bits 0x41200000 are the integer 1,092,616,192, the float 10.0, the four bytes 00 00 20 41 in memory on your laptop, or, read byte by byte as text, two NUL characters followed by a space and A. Bits have no type. Types are a promise your program makes about how to interpret them. Type confusion bugs, buffer overflows and serialization bugs are all failures of that promise.
Part 2 — The von Neumann Model
In 1945 John von Neumann described a design that almost every computer still follows: instructions and data live in the same memory, and a processing unit fetches instructions from that memory one after another and executes them.
flowchart LR
subgraph CPU["CPU"]
CU["Control unit<br/>(decodes instructions)"]
ALU["ALU<br/>(arithmetic & logic)"]
REG["Registers<br/>(tiny, ultra-fast storage)"]
CU --> ALU
ALU <--> REG
end
MEM["Main memory<br/>holds BOTH code and data"]
IO["I/O devices<br/>disk, network, keyboard, GPU"]
CPU <-->|"address + data bus"| MEM
CPU <--> IO
The pieces:
- Memory is a giant array of bytes, each with a numeric address. Your program's machine code, its variables, its heap and its stack all live there.
- The CPU contains a control unit (reads and decodes instructions), an ALU (arithmetic logic unit — does addition, subtraction, AND/OR/XOR, shifts, comparisons), and registers (a few dozen named storage slots inside the chip itself).
- I/O devices let the computer talk to the outside world.
The stored-program idea is profound: because code is just bytes in memory, a program can load another program and run it. That is what an operating system, a compiler, a JIT and a virus all do.
It also creates the von Neumann bottleneck: the CPU can compute far faster than it can fetch from memory. Most of the cleverness in modern CPUs — caches, pipelines, prefetchers, out-of-order execution — exists to hide that gap. Keep that in mind; it is the theme of the rest of this page.
Part 3 — What a CPU Actually Does
The fetch-decode-execute cycle
At its heart, a CPU runs one loop, forever, from the moment it is powered on:
flowchart TD
F["FETCH<br/>read the instruction at the address in the program counter"]
D["DECODE<br/>work out the operation and its operands"]
E["EXECUTE<br/>ALU computes, or memory is read or written"]
W["WRITE BACK<br/>store the result in a register"]
N["Advance program counter<br/>(or jump if it was a branch)"]
F --> D --> E --> W --> N --> F
A special register, the program counter (called RIP on x86-64, PC on ARM), holds the address of the next instruction. Normally it advances to the next instruction after each one. A branch or jump instruction overwrites it, which is how if, loops and function calls are implemented.
Registers
Registers are the CPU's working hands. Every computation happens in registers: to add two numbers in memory, the CPU loads them into registers, adds the registers, and (maybe) stores the result back.
| Architecture | General-purpose integer registers | Notable special registers |
|---|---|---|
| x86-64 | 16 × 64-bit (rax, rbx, rcx, rdx, rsi, rdi, rbp, rsp, r8–r15) | rip (program counter), rsp (stack pointer), rflags (condition flags) |
| ARM64 (AArch64) | 31 × 64-bit (x0–x30) | pc, sp, xzr (always reads as zero), NZCV flags |
Plus vector registers for floating point and SIMD (16–32 registers of 128 to 512 bits). That is the entire "fastest memory" on the chip — a few hundred bytes to a few kilobytes. Compilers spend a lot of effort on register allocation: deciding which variables live in registers and which have to "spill" to memory.
Instruction sets: x86-64 vs ARM, CISC vs RISC
An instruction set architecture (ISA) is the contract between software and hardware: the list of instructions, registers and memory rules a CPU promises to support. Software compiled for one ISA does not run on another without translation (that is what Apple's Rosetta 2 does for x86 apps on ARM Macs).
| x86-64 (Intel, AMD) | ARM64 (Apple M-series, AWS Graviton, phones) | |
|---|---|---|
| Design philosophy | CISC — complex instruction set | RISC — reduced instruction set |
| Instruction length | Variable, 1 to 15 bytes | Fixed, 4 bytes |
| Memory operands | Arithmetic can read memory directly (add rax, [rbx]) | Load/store architecture: only ldr/str touch memory |
| Decoding | Hard — must find where each instruction starts | Easy — every instruction is 4 bytes |
| History | 1978 (8086), backwards-compatible ever since | 1985, redesigned cleanly as AArch64 in 2011 |
| Where you see it | Most servers and PCs | Phones, tablets, Macs, increasingly cloud servers |
The CISC/RISC distinction is blurrier than it used to be. Modern x86 chips decode their complex instructions into simple internal micro-operations (µops) and execute those on a RISC-like core. The real modern differences are decode complexity, power efficiency, memory-ordering rules (ARM is weaker-ordered, which matters for concurrent code — see later lessons) and ecosystem.
From C to assembly
Let's see what the compiler actually produces. Here is a tiny C function:
// sum.c
long sum(const long *a, long n) {
long s = 0;
for (long i = 0; i < n; i++)
s += a[i];
return s;
}
Compile it with gcc -O1 -S sum.c (or paste it into Compiler Explorer) and you get roughly this x86-64 assembly (Intel syntax):
sum: ; a in rdi, n in rsi (System V calling convention)
test rsi, rsi ; is n <= 0?
jle .Lzero ; then return 0
lea rdx, [rdi+rsi*8] ; rdx = end pointer = a + n*8 bytes
xor eax, eax ; s = 0 (xor with itself is the idiom for zero)
.Lloop:
add rax, [rdi] ; s += *a (x86 can add straight from memory)
add rdi, 8 ; a++ (8 bytes per long)
cmp rdi, rdx ; reached the end?
jne .Lloop ; no: go round again
ret ; result is returned in rax
.Lzero:
xor eax, eax
ret
And the same function for ARM64 (aarch64-linux-gnu-gcc -O1 -S):
sum: // a in x0, n in x1
cmp x1, 0
ble .Lzero
add x2, x0, x1, lsl 3 // x2 = a + n*8
mov x1, 0 // s = 0
.Lloop:
ldr x3, [x0], 8 // load *a into x3, then a += 8
add x1, x1, x3 // s += x3 (ARM adds registers only)
cmp x0, x2
bne .Lloop
mov x0, x1 // return value goes in x0
ret
.Lzero:
mov x0, 0
ret
Things worth noticing:
- Your variables became registers.
slives inrax/x1,idisappeared entirely — the compiler turned the index into a moving pointer. - A loop is just a compare and a conditional jump backwards. There is no
forin hardware. - Arguments arrive in registers according to a calling convention (
rdi,rsi,rdx… on Linux x86-64;x0–x7on ARM64), and the return value goes back inrax/x0. - At
-O2or-O3the compiler would go further and vectorise the loop with SIMD to add 2–8 numbers per instruction (more on that below).
The full pipeline from text to running instructions looks like this:
flowchart LR
SRC["sum.c<br/>source code"] --> CC["Compiler<br/>parse, optimise"]
CC --> ASM["sum.s<br/>assembly"]
ASM --> AS["Assembler"]
AS --> OBJ["sum.o<br/>machine code bytes"]
OBJ --> LD["Linker<br/>joins objects and libraries"]
LD --> EXE["Executable<br/>(ELF, Mach-O, PE)"]
EXE --> LOAD["OS loader<br/>maps it into memory"]
LOAD --> RUN["CPU fetches<br/>and executes"]
Interpreted and JIT-compiled languages (Python, JavaScript, Java) take a different route to the same destination — eventually something is a stream of machine instructions. Compiler & Interpreter Basics covers that path in depth.
Clock speed vs IPC
A CPU's clock is an oscillator that ticks billions of times per second; each tick (a cycle) is a step in which circuits can do some work. A 4 GHz CPU has a cycle time of 0.25 nanoseconds — light travels about 7.5 cm in that time.
It is tempting to think "higher GHz = faster", but performance is really:
time = instructions × (cycles per instruction) × (seconds per cycle)
= instructions ÷ IPC ÷ clock frequency
IPC (instructions per cycle) is the number of instructions the CPU completes per tick, on average. A modern core can retire 4–8 instructions per cycle at peak, but real programs often achieve 0.5–2 because the CPU spends cycles waiting — mostly for memory.
Clock speeds stopped rising around 2005 (roughly 3–5 GHz) because power and heat grow faster than frequency — the end of "Dennard scaling". Since then, performance has come from higher IPC and more cores. That is why a 3.5 GHz chip from 2024 crushes a 3.8 GHz chip from 2006: same clock, several times the IPC, many more cores.
You can measure IPC on Linux:
$ perf stat -e cycles,instructions,branches,branch-misses,cache-misses ./myprogram
Performance counter stats for './myprogram':
4,812,331,207 cycles
11,203,544,019 instructions # 2.33 insn per cycle
2,104,882,113 branches
3,190,447 branch-misses # 0.15% of all branches
18,402,931 cache-misses
An IPC above ~2 means the CPU is busy doing work. An IPC below ~0.5 usually means it is stalled on memory or mispredicted branches — and that is your cue to look at data layout, not at the algorithm's big-O.
Part 4 — How Modern CPUs Go Fast
A naive CPU would do fetch, decode, execute and write-back for one instruction before starting the next. Real CPUs overlap and parallelise almost everything.
Pipelining
Think of a laundry: washing, drying and folding one load takes three hours, but you do not wait three hours before starting the next wash. While load 1 dries, load 2 washes. A CPU pipeline does the same with instruction stages:
| Cycle | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Instr 1 | Fetch | Decode | Execute | Memory | Write | ||
| Instr 2 | Fetch | Decode | Execute | Memory | Write | ||
| Instr 3 | Fetch | Decode | Execute | Memory | Write | ||
| Instr 4 | Fetch | Decode | Execute | Memory |
Each instruction still takes 5 cycles from start to finish (latency), but once the pipeline is full, one instruction completes every cycle (throughput). Modern cores have pipelines of roughly 12–20 stages.
Hazards — when the pipeline stalls
Overlapping instructions works only if they do not depend on each other. Hazards are the cases where they do:
| Hazard | Example | Fix used by hardware |
|---|---|---|
| Data hazard | add rax, rbx then mul rcx, rax — the second needs the first's result | Forwarding (pass the result straight from the ALU output to the next instruction), otherwise stall |
| Structural hazard | Two instructions need the same unit (e.g. one divider) in the same cycle | Duplicate units; stall otherwise |
| Control hazard | A conditional branch — which instruction comes next isn't known until the comparison finishes | Branch prediction + speculative execution |
Control hazards are the big one. With a 15-stage pipeline, waiting for every branch to resolve would waste ~15 cycles each time, and typical code has a branch every 5–7 instructions.
Branch prediction
So the CPU guesses. A branch predictor remembers the history of each branch (and patterns across branches) and predicts whether it will be taken. The CPU starts executing down the predicted path speculatively. If the guess was right, no time is lost. If it was wrong, the speculative work is thrown away and the pipeline restarts from the correct path — a misprediction costs roughly 15–20 cycles on modern cores.
Modern predictors are astonishingly good — often over 95–99% accurate on normal code — because most branches are predictable: loop conditions are "taken" until the last iteration, error checks are almost never taken. But they cannot predict randomness.
The famous sorted-vs-unsorted benchmark
This experiment became one of the most-viewed questions in Stack Overflow history ("Why is processing a sorted array faster than processing an unsorted array?", 2012). Sum only the elements ≥ 128 of a large array of random bytes:
// branch.c — gcc -O1 branch.c -o branch && ./branch
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N (1 << 24)
static int cmp(const void *a, const void *b) {
return *(const int *)a - *(const int *)b;
}
static long run(const int *data) {
long sum = 0;
for (int rep = 0; rep < 20; rep++)
for (int i = 0; i < N; i++)
if (data[i] >= 128) // the branch in question
sum += data[i];
return sum;
}
int main(void) {
int *data = malloc(N * sizeof(int));
for (int i = 0; i < N; i++) data[i] = rand() % 256;
clock_t t = clock();
long s1 = run(data);
printf("unsorted: %.2fs (sum %ld)\n", (double)(clock() - t) / CLOCKS_PER_SEC, s1);
qsort(data, N, sizeof(int), cmp);
t = clock();
long s2 = run(data);
printf("sorted: %.2fs (sum %ld)\n", (double)(clock() - t) / CLOCKS_PER_SEC, s2);
free(data);
return 0;
}
Typical result at -O1 on a modern x86 laptop (exact numbers vary by machine):
unsorted: 1.95s (sum 32212...)
sorted: 0.33s (sum 32212...) <- same sum
Same data, same work, same answer — roughly 6x faster sorted. With random data, the if is a coin flip, so the predictor is wrong about half the time. With sorted data, the branch is "not taken" for the first half and "taken" for the second half — trivially predictable.
Two twists make the lesson sharper:
- At
-O2/-O3, GCC and Clang often replace the branch with a conditional move (cmov) or vectorise the loop, and the difference disappears. Check withperf stat -e branch-missesbefore assuming. - You can remove the branch yourself:
sum += data[i] & -(data[i] >= 128);computes the same thing with no jump at all. Branchless code trades a few extra instructions for zero mispredictions.
$ perf stat -e branches,branch-misses ./branch
# unsorted phase alone: ~25% of all branches mispredicted
# sorted phase alone: <0.1%
Out-of-order and superscalar execution
Two more tricks multiply throughput:
- Superscalar: the core has many execution units (several integer ALUs, load/store units, floating-point/vector units, a branch unit) and can issue several instructions in the same cycle. A modern core can start 6–10 µops per cycle.
- Out-of-order (OoO) execution: instead of strictly following program order, the CPU looks ahead through a window of hundreds of upcoming instructions (the reorder buffer, ~200–600+ entries on recent designs) and executes whichever ones have their inputs ready. If instruction 3 is waiting on a slow memory load, instructions 4–40 that do not depend on it run in the meantime. Results are retired (made visible) in the original program order, so the program cannot tell.
flowchart LR
FE["Front end<br/>fetch + decode<br/>into micro-ops"] --> RN["Rename<br/>map to physical registers"]
RN --> ROB["Reorder buffer<br/>hundreds of in-flight ops"]
ROB --> SCH["Scheduler<br/>issue when inputs ready"]
SCH --> ALU1["Int ALU"]
SCH --> ALU2["Int ALU"]
SCH --> LSU["Load/Store"]
SCH --> VEC["FP / SIMD"]
ALU1 --> RET["Retire<br/>in program order"]
ALU2 --> RET
LSU --> RET
VEC --> RET
This is why "count the instructions" is a poor performance model on modern hardware. What matters is dependency chains (a long chain of instructions that each need the previous result cannot be overlapped) and memory stalls (a cache miss can take longer than the whole reorder buffer can cover).
A tiny example of dependency chains in practice: summing an array with one accumulator creates a chain where every add waits for the previous one. Using four accumulators (s0 += a[i]; s1 += a[i+1]; …) creates four independent chains the CPU can run in parallel — often 2–4x faster for floating-point sums, which the compiler will not do for you without -ffast-math because it changes rounding.
SIMD — one instruction, many numbers
SIMD (single instruction, multiple data) instructions operate on a wide register holding several values at once:
| Extension | Register width | Floats (32-bit) per op | Where |
|---|---|---|---|
| SSE | 128 bits | 4 | All x86-64 |
| AVX2 | 256 bits | 8 | Most x86 since ~2013 |
| AVX-512 | 512 bits | 16 | Many server x86, recent AMD |
| NEON | 128 bits | 4 | All ARM64 |
| SVE / SVE2 | 128–2048 bits (scalable) | 4–64 | Newer ARM servers |
Scalar: a0+b0 → 1 result per instruction
AVX2: [a0 a1 a2 a3 a4 a5 a6 a7]
+ [b0 b1 b2 b3 b4 b5 b6 b7] → 8 results per instruction
Compilers auto-vectorise simple loops at -O2/-O3 when they can prove it is safe. You can also write SIMD explicitly — Rust has portable SIMD and std::arch intrinsics, C has <immintrin.h>. SIMD is how libraries like NumPy, simdjson, video codecs and database engines (DuckDB, ClickHouse) get their speed: they process data in batches of columns, not one row at a time.
// Rust: the iterator version is easy for LLVM to auto-vectorise.
pub fn dot(a: &[f32], b: &[f32]) -> f32 {
a.iter().zip(b).map(|(x, y)| x * y).sum()
}
// Build with: RUSTFLAGS="-C target-cpu=native" cargo build --release
// (float sums still need explicit chunking to vectorise fully — see the
// multiple-accumulator note above)
Part 5 — The Memory Hierarchy
Here is the central problem. A core can execute several instructions per nanosecond. A trip to main memory (DRAM) takes around 80–100 nanoseconds — hundreds of cycles during which, without help, the core would sit idle. Memory speed has improved far more slowly than CPU speed for decades (the "memory wall").
The solution is a hierarchy: small, fast, expensive memory close to the core, backed by progressively larger, slower, cheaper layers.
flowchart TD
R["Registers<br/>~1 KB, 0 to 1 cycle"]
L1["L1 cache<br/>32 to 64 KB per core, ~1 ns"]
L2["L2 cache<br/>1 to 2 MB per core, ~3 to 5 ns"]
L3["L3 cache<br/>tens of MB shared, ~10 to 40 ns"]
RAM["Main memory, DRAM<br/>16 GB to TBs, ~80 to 100 ns"]
SSD["NVMe SSD<br/>TBs, ~20 to 100 microseconds"]
NET["Network / other machines<br/>0.5 ms in a datacenter, 150 ms across the world"]
R --> L1 --> L2 --> L3 --> RAM --> SSD --> NET
Real latency numbers
| Level | Typical size | Latency | In 4 GHz cycles | If 1 cycle were 1 second |
|---|---|---|---|---|
| Register | ~1 KB | ~0.25 ns | 1 | 1 second |
| L1 data cache | 32–64 KB per core | ~1 ns | ~4–5 | 4 seconds |
| L2 cache | 1–2 MB per core | ~3–5 ns | ~12–16 | 15 seconds |
| L3 cache | 16–100+ MB shared | ~10–40 ns | ~40–150 | 1–2 minutes |
| DRAM | 16 GB – several TB | ~80–100 ns | ~350 | 6 minutes |
| NVMe SSD read | TBs | ~20–100 µs | ~100,000 | 1–4 days |
| HDD seek | TBs | ~5–10 ms | ~30,000,000 | about a year |
| Datacenter round trip | — | ~0.5 ms | ~2,000,000 | 3 weeks |
| US to Europe round trip | — | ~80–150 ms | ~500,000,000 | 16 years |
The rightmost column is the one to remember. To a CPU, a cache miss to DRAM is like stopping work to wait six minutes. A disk read is like waiting days. A cross-continent network call is like waiting a decade and a half. Every performance intuition in software engineering follows from that table.
Check your own machine
$ lscpu
Architecture: x86_64
Model name: AMD EPYC 7R13 Processor
CPU(s): 16
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Caches (sum of all):
L1d: 256 KiB (8 instances)
L1i: 256 KiB (8 instances)
L2: 4 MiB (8 instances)
L3: 32 MiB (1 instance)
NUMA:
NUMA node(s): 1
$ getconf LEVEL1_DCACHE_LINESIZE
64
$ lstopo --of console # from the hwloc package: draws sockets, caches, cores, PCI devices
lstopo (or lstopo topo.png for an image) is the best way to see how cores share caches on a given machine. On macOS, sysctl -a | grep cache shows similar information.
SRAM vs DRAM
Why not just make all memory as fast as L1? Because the two kinds of memory are physically different:
| SRAM (caches) | DRAM (main memory) | |
|---|---|---|
| Cell | ~6 transistors forming a latch | 1 transistor + 1 capacitor |
| Speed | Very fast (sub-ns to a few ns) | Slower (tens of ns plus controller overhead) |
| Density | Low — large area per bit | High — very small per bit |
| Cost per bit | High | Low |
| Refresh needed | No — holds state while powered | Yes — capacitors leak; refreshed every ~64 ms |
| Where | On the CPU die | Separate DIMMs or packages next to the CPU |
A DRAM read also involves opening a "row" of the chip into a row buffer before reading the column — which is why sequential DRAM access (staying in an open row) is much cheaper than random access. Both kinds lose their contents when the power goes off; that is why we also need storage.
Cache lines — memory moves in 64-byte chunks
Caches never fetch a single byte. They move memory in fixed blocks called cache lines, which are 64 bytes on essentially every x86-64 and most ARM64 chips (Apple M-series uses 128-byte lines at some levels).
When you read one int at address 1000, the CPU fetches the whole 64-byte line containing it (addresses 960–1023). The next 15 ints are now in L1 for free.
Locality: why caches work at all
Caches only help because real programs are predictable in two ways:
- Temporal locality — if you used something recently, you will probably use it again soon (loop counters, a hot function, the top of the stack, a frequently read config object).
- Spatial locality — if you used address X, you will probably use X+8, X+16… soon (walking an array, reading a struct's fields one after another).
The hardware also has prefetchers that spot patterns — "this program is reading addresses 64 bytes apart, going up" — and fetch lines before you ask for them. Sequential access through an array is the best case: the prefetcher keeps ahead of you and you almost never wait for DRAM. Following pointers through a linked list scattered across the heap is the worst case: each node is at an unpredictable address, so each step can be a full DRAM miss.
That is the real reason a Vec/slice/array usually beats a linked list in practice, even for operations where the linked list has better big-O.
The row-major vs column-major benchmark
C, C++, Go, Rust and NumPy (by default) store 2-D arrays in row-major order: row 0's elements, then row 1's, and so on. Walking along a row is sequential in memory; walking down a column jumps by a whole row each step.
// matrix.c — gcc -O2 matrix.c -o matrix && ./matrix
#include <stdio.h>
#include <time.h>
#define N 4096
static int m[N][N]; // 64 MiB — far bigger than any cache
int main(void) {
long sum = 0;
clock_t t = clock();
for (int i = 0; i < N; i++) // row by row: sequential addresses
for (int j = 0; j < N; j++)
sum += m[i][j];
printf("row-major: %.3fs\n", (double)(clock() - t) / CLOCKS_PER_SEC);
t = clock();
for (int j = 0; j < N; j++) // column by column: stride of 16 KiB
for (int i = 0; i < N; i++)
sum += m[i][j];
printf("column-major: %.3fs\n", (double)(clock() - t) / CLOCKS_PER_SEC);
return (int)(sum & 1);
}
Typical output:
row-major: 0.012s
column-major: 0.180s
Identical arithmetic, the same 16.7 million additions — and the column-order loop is commonly 10–20x slower. In the row-major loop each 64-byte line delivers 16 useful ints and the prefetcher streams ahead. In the column-major loop every access lands on a different line 16 KiB away; by the time you come back to use the neighbouring element of that line, it has long been evicted.
You can watch it happen:
$ perf stat -e L1-dcache-loads,L1-dcache-load-misses ./matrix
The same idea in Go — the loop order is the whole difference:
// Good: inner loop walks contiguous memory.
for i := range grid {
for j := range grid[i] {
total += grid[i][j]
}
}
Column-major languages exist
Fortran, MATLAB, Julia and R store matrices column-major, so there the opposite loop order is fast. NumPy lets you choose (order="C" or order="F"). The rule is not "rows first", it is "make the innermost loop walk adjacent memory".
Cache associativity — where a line is allowed to live
A cache is not a free-for-all where any line can go anywhere; searching every slot on every access would be too slow. Instead, the address decides where a line may go.
A memory address is split into three parts:
63 12 11 6 5 0
+----------------------------------+-----------+-----------+
| tag | index | offset |
+----------------------------------+-----------+-----------+
which line is this? which set? which byte
in the 64 B line?
- Offset (6 bits for 64-byte lines) picks the byte within the line.
- Index picks a set — a small group of slots.
- Tag is stored alongside the line so the cache can tell which of the many possible addresses is actually there.
| Organisation | A line can go… | Trade-off |
|---|---|---|
| Direct-mapped | Exactly one slot | Fast and simple, but two hot addresses that map to the same slot keep evicting each other |
| N-way set-associative | Any of N slots in its set | The common design: L1 is typically 8–12 way, L2/L3 often 8–16+ way |
| Fully associative | Any slot | No conflicts but expensive; used for tiny structures like the TLB |
Example: a 48 KiB, 12-way L1 with 64-byte lines has 48 × 1024 / 64 = 768 lines, in 768 / 12 = 64 sets. So the index is 6 bits (bits 6–11 of the address), and addresses 4 KiB apart map to the same set.
That leads to a practical trap: power-of-two strides. Walk a matrix whose rows are exactly 4,096 bytes wide down a column and every access lands in the same set. Only 12 lines fit in it, so you get "conflict misses" even though the cache as a whole is nearly empty. Padding each row by one cache line (making it 4,160 bytes) often fixes a mysterious slowdown. When the cache is full, a replacement policy (an approximation of least recently used) decides which line in the set to evict.
Writes, coherence and false sharing
Writes go into the cache too. Most caches are write-back: the modified ("dirty") line is written to the next level only when it is evicted.
With multiple cores, each with its own L1 and L2, there is a problem: if core 0 and core 1 both cache the same line and core 0 writes to it, core 1's copy is stale. A cache coherence protocol (MESI and its variants: Modified, Exclusive, Shared, Invalid) solves it — before a core writes a line, it must take exclusive ownership, which invalidates every other core's copy.
Coherence works on whole cache lines, which causes false sharing: two threads updating different variables that happen to sit in the same 64-byte line force that line to bounce between cores on every write, even though the threads never touch each other's data.
// Bad: both counters share one cache line; two goroutines hammering
// c.a and c.b will slow each other down dramatically.
type Counters struct {
a int64
b int64
}
// Better: pad so each counter has its own line.
type PaddedCounters struct {
a int64
_ [56]byte
b int64
_ [56]byte
}
Rust offers crossbeam_utils::CachePadded<T>, C++17 has std::hardware_destructive_interference_size, and Java has @Contended. Locks, atomics and memory ordering — the other half of this story — are covered in Kernel Synchronization and in the concurrency lesson of this course.
Part 6 — Multicore, Hyper-Threading and NUMA
Multicore
Since clocks stopped getting faster, chips got wider: a modern desktop CPU has 8–24 cores, a server CPU 64–192. Each core is a complete CPU — its own pipeline, registers, L1 and (usually) L2 — and the cores share an L3 and the memory controllers.
More cores only help if your program has parallel work. A single-threaded program on a 64-core machine uses one core. That is why concurrency is a full lesson later in this course, and why the operating system's scheduler matters so much (see CPU Scheduling & Context Switching).
Hyper-threading (SMT)
Simultaneous multithreading — Intel calls it Hyper-Threading — lets one physical core run two hardware threads at once. The core duplicates the architectural state (registers, program counter) but shares the execution units and caches. When one thread stalls on a cache miss, the other thread's instructions keep the execution units busy.
- The OS sees two "logical CPUs" per core (
Thread(s) per core: 2inlscpu). - The gain is typically 10–30% more throughput per core, not 2x — and it can be negative for workloads that compete for the same cache or units.
- Two threads on sibling hyper-threads share L1 and L2, which matters for both performance and security (some side-channel attacks work across siblings, which is why some cloud providers never put two customers on sibling threads).
NUMA — not all RAM is equally close
On multi-socket servers (and some large single-socket chips), each CPU socket has its own memory controllers and RAM. A core can access the other socket's memory, but it must cross an interconnect, so it is slower.
flowchart LR
subgraph N0["NUMA node 0"]
C0["Socket 0<br/>cores 0 to 31"]
M0["Local RAM<br/>~90 ns"]
C0 --- M0
end
subgraph N1["NUMA node 1"]
C1["Socket 1<br/>cores 32 to 63"]
M1["Local RAM<br/>~90 ns"]
C1 --- M1
end
C0 <-->|"interconnect<br/>remote access ~140 ns+"| C1
This is NUMA (non-uniform memory access). Remote access is typically 1.5–2x slower and shares limited interconnect bandwidth. Linux tries to allocate memory on the node where the thread runs ("first touch"), but a thread that migrates to the other socket — or a big buffer allocated by one thread and used by another — ends up paying remote latency.
$ numactl --hardware # nodes, their CPUs, memory, and the distance matrix
$ numactl --cpunodebind=0 --membind=0 ./server # pin a process to one node
$ numastat -p $(pgrep postgres) # where a process's memory actually lives
Databases, JVMs and high-throughput servers often have NUMA-awareness settings for exactly this reason. Virtual Memory covers how the kernel places pages across nodes.
Part 7 — Storage, I/O and How Devices Connect
The CPU and RAM are not the whole computer. Disks, network cards, GPUs and USB devices all need to exchange data with them.
Buses and PCIe
A bus is a shared communication path. Early PCs had one shared bus for everything; modern systems use point-to-point links:
- Memory channels connect the CPU's built-in memory controller directly to DRAM (DDR5 delivers roughly 40–60 GB/s per channel; servers have 8–12 channels).
- PCI Express (PCIe) connects high-speed devices — NVMe SSDs, network cards, GPUs. PCIe is organised in lanes; a device uses x1, x4, x8 or x16 lanes. A PCIe 4.0 lane carries about 2 GB/s each way, so an x4 NVMe drive tops out around 7–8 GB/s and an x16 GPU around 32 GB/s. Each PCIe generation roughly doubles per-lane speed.
- A chipset (platform controller hub) hangs slower devices — SATA, USB, audio — off a link to the CPU.
$ lspci -tv # the PCIe tree: which devices hang off which root ports
$ lsblk -d -o NAME,ROTA,TRAN,SIZE,MODEL # disks: ROTA=0 means SSD, TRAN shows nvme/sata/usb
Memory-mapped I/O, interrupts and DMA
How does the CPU talk to a device? Devices expose control registers that appear at physical addresses — memory-mapped I/O — so the CPU (in practice, the kernel driver) configures a device with ordinary load and store instructions to special addresses.
Then two mechanisms keep the CPU from babysitting every byte:
- Interrupts: instead of the CPU repeatedly asking "are you done yet?" (polling), the device raises an electrical signal when something happens — a packet arrived, a disk read finished. The CPU pauses what it is doing, runs the kernel's interrupt handler, and resumes.
- DMA (direct memory access): the device itself copies data straight into or out of RAM, without the CPU moving each byte. The driver says "read blocks 1000–1007 into this buffer at physical address X", the SSD's DMA engine does it, then raises an interrupt.
sequenceDiagram
participant App as Application
participant K as Kernel driver
participant SSD as NVMe SSD
participant RAM as RAM
App->>K: read(fd, buf, 4096)
K->>SSD: write command to device queue (MMIO doorbell)
Note over App,K: thread sleeps, CPU runs other work
SSD->>RAM: DMA the 4 KiB block directly into memory
SSD->>K: interrupt - command complete
K->>App: wake thread, read() returns 4096
This is the hardware foundation of every "I/O-bound" discussion you will have: while the SSD or NIC is working, the CPU is free to run other threads, which is what async runtimes and event loops exploit. The full story — interrupt controllers, NAPI, io_uring, IOMMUs and driver models — is in Interrupts, DMA & Device Drivers, and storage specifically in I/O & Storage.
Storage is a different world
| HDD | SATA SSD | NVMe SSD | DRAM | |
|---|---|---|---|---|
| Random 4 KiB read latency | ~5–10 ms | ~100 µs | ~20–100 µs | ~0.1 µs |
| Sequential throughput | ~150–250 MB/s | ~550 MB/s | ~3–14 GB/s | ~50+ GB/s per channel |
| Random IOPS | ~100–200 | ~100 K | ~500 K – 1.5 M+ | — |
| Survives power loss | Yes | Yes | Yes | No |
SSDs closed most of the gap with spinning disks, but storage is still hundreds to thousands of times slower than RAM, and every write that must survive a crash has to wait for the device (see Page Cache & fsync). That is why the OS caches file data in RAM, why databases have buffer pools, and why "keep the working set in memory" is the first rule of database performance.
Part 8 — From Power-On to Running Code
When you press the power button, there is no operating system and no RAM contents — just a CPU that starts executing at a fixed address wired into the hardware. Briefly:
flowchart LR
P["Power on<br/>CPU resets"] --> FW["Firmware<br/>UEFI or BIOS in flash"]
FW --> POST["Init RAM, CPUs,<br/>PCIe, find boot disk"]
POST --> BL["Bootloader<br/>GRUB, systemd-boot"]
BL --> KER["Kernel<br/>sets up memory, drivers"]
KER --> INIT["init / systemd<br/>PID 1"]
INIT --> SVC["Services and<br/>your program"]
- The CPU starts in a simple mode and runs firmware (UEFI on modern machines) from a flash chip on the motherboard.
- Firmware trains the memory controllers (RAM is unusable until it does), initialises CPUs and enumerates PCIe devices.
- It finds a bootloader on a disk and runs it; the bootloader loads the kernel into RAM.
- The kernel switches the CPU into 64-bit mode with virtual memory, brings up the other cores, loads drivers and mounts the root filesystem.
- It starts the first user-space process (
init, usually systemd), which starts everything else — eventually including your program, which the OS loads, maps into memory, and jumps to.
Every step is the same fetch-decode-execute loop from Part 3, running ever more capable code. The detailed walkthrough — firmware, Secure Boot, initramfs, systemd targets and how to debug a slow boot — is in The Boot Process.
Part 9 — Why This Matters for Software Engineers
You do not need to write assembly to benefit from any of this. You need a handful of habits.
Latency numbers every programmer should know
Popularised by Jeff Dean and Peter Norvig; the exact numbers drift with hardware, but the ratios have stayed remarkably stable for twenty years:
| Operation | Approximate time | Relative to an L1 hit |
|---|---|---|
| L1 cache reference | 1 ns | 1x |
| Branch mispredict | 3–5 ns | ~4x |
| L2 cache reference | 4 ns | ~4x |
| Mutex lock/unlock (uncontended) | 15–25 ns | ~20x |
| L3 cache reference | 10–40 ns | ~10–40x |
| Main memory reference | 100 ns | 100x |
| Compress 1 KB with a fast compressor (Snappy/LZ4) | 1–2 µs | ~1,500x |
| Read 1 MB sequentially from RAM | 10–50 µs | ~25,000x |
| Random 4 KB read from NVMe SSD | 20–100 µs | ~50,000x |
| Read 1 MB sequentially from NVMe SSD | 100–300 µs | ~200,000x |
| Round trip within a datacenter | 500 µs | 500,000x |
| HDD seek | 5–10 ms | ~7,000,000x |
| Packet round trip California to Netherlands | 150 ms | 150,000,000x |
Use this table for back-of-envelope estimates. If a request handler makes 30 sequential database calls at 0.5 ms each, it cannot be faster than 15 ms no matter how optimised the code is. If your hot loop does a hash-map lookup that misses cache every time, you are paying ~100 ns per iteration — 10 million iterations is a full second.
Data-oriented design
Data-oriented design is the practice of organising data around how it is accessed, so the cache and prefetcher work for you. The classic example is array of structs (AoS) vs struct of arrays (SoA):
// Array of structs: each particle's fields are together.
struct Particle { x: f32, y: f32, z: f32, vx: f32, vy: f32, vz: f32, mass: f32, alive: bool }
let particles: Vec<Particle> = /* ... */;
// Updating only positions drags mass and alive through the cache too.
// Struct of arrays: each field is a contiguous array.
struct Particles {
x: Vec<f32>, y: Vec<f32>, z: Vec<f32>,
vx: Vec<f32>, vy: Vec<f32>, vz: Vec<f32>,
}
// The position update now streams through exactly the bytes it needs,
// and the loops are trivial for the compiler to vectorise with SIMD.
The same principle explains, at a much larger scale, why columnar databases (ClickHouse, DuckDB, BigQuery, Parquet files) are dramatically faster for analytics: SUM(price) reads one tightly packed column instead of every byte of every row.
Practical habits that follow from this page:
- Prefer contiguous containers (arrays, slices,
Vec,std::vector) over pointer-chasing ones (linked lists, trees of individually allocated nodes) unless you have measured a reason. - Make the innermost loop walk adjacent memory.
- Keep hot data small. Smaller structs, smaller integers where appropriate, fewer pointers — more items per cache line.
- Avoid unpredictable branches in hot loops, or make the data predictable (sort, partition, batch by type).
- Batch work. Processing 1,000 items in one call beats 1,000 calls of one item — at every level, from SIMD to database round trips.
- Watch out for false sharing in per-thread counters and per-core structures.
- Measure, do not guess.
perf stat(IPC, cache misses, branch misses) tells you which of these problems you actually have. For language-specific tools see Profiling.
War Story (illustrative)
A team's Go service computed per-tenant usage totals with a map[string]*Usage, where each Usage was a separately allocated struct holding a dozen counters. A nightly aggregation over 40 million events took 90 seconds, and CPU profiles showed nothing obviously expensive — just "map access" and "runtime.memmove" spread everywhere. perf stat told the real story: an IPC of 0.4 and a cache-miss rate far above normal, so the CPU was mostly waiting on memory. The fix was boring: assign each tenant a small integer ID once, store counters in a flat []Usage slice indexed by that ID, and sort events by tenant before aggregating. Same algorithm, same big-O. The job dropped to 11 seconds and IPC rose above 2. Nothing about the logic changed — only where the bytes lived.
Spectre and Meltdown in one paragraph
In January 2018, researchers disclosed Meltdown and Spectre, a family of attacks that turned the speed tricks on this page into security holes. Speculative execution (Part 4) runs instructions before the CPU knows whether they should run; if they should not, the results are discarded — but their side effects on the cache are not. An attacker can trick the CPU into speculatively reading a secret (kernel memory for Meltdown, another part of the same process for Spectre), using it to index an array, and then measure which cache line became fast to access — revealing the secret one byte at a time through timing. The fixes cost real performance: kernel page-table isolation (KPTI) made system calls slower, compilers emit "retpolines" and speculation barriers, browsers reduced timer precision and isolated sites into separate processes, and new CPUs added hardware mitigations. The lesson for every engineer: performance optimisations leak information, and "the results were thrown away" is not the same as "nothing happened".
Microbenchmarks lie easily
The benchmarks on this page are deliberately simple so you can run them. Real measurements need care: the compiler may optimise away work whose result you never use, CPU frequency scaling and turbo change between runs, the first run warms caches for the second, and other processes compete for the machine. Run several times, use the result, and prefer tools built for it (Google Benchmark, Go's testing.B, Rust's criterion, hyperfine for whole programs).
Summary
| Concept | One-line takeaway |
|---|---|
| Bits and encodings | Bits have no type; integers wrap, floats round, text is variable-length bytes |
| Two's complement | One adder handles signed and unsigned; ranges are asymmetric |
| IEEE 754 | 0.1 is not representable — compare with tolerances, keep money in integers |
| Endianness | x86 and ARM are little-endian; networks are big-endian |
| von Neumann model | Code and data share memory; the CPU–memory gap is the central problem |
| Fetch-decode-execute | The CPU is a loop over instructions; if and loops are jumps |
| ISA | x86-64 (CISC) and ARM64 (RISC) — both decode to simple internal ops |
| Performance | time = instructions ÷ IPC ÷ frequency; most code is limited by memory stalls |
| Pipelining and prediction | Predictable branches are free, random ones cost ~15–20 cycles each |
| Out-of-order and SIMD | Independent work runs in parallel; batches of data run in one instruction |
| Memory hierarchy | Each level is ~3–10x slower than the one above; DRAM is ~100 ns |
| Cache lines | Memory moves in 64-byte chunks; locality is everything |
| Multicore and NUMA | More cores need parallel work; remote memory is slower |
| I/O | Devices use DMA and interrupts so the CPU can do other work |
Where to Go Next
- Compiler & Interpreter Basics — how source code becomes the machine instructions you saw here, including JIT compilation in V8.
- Runtime Internals — how language runtimes (garbage collectors, schedulers, event loops) sit on top of this hardware.
- OS Internals — the operating system layer: processes, scheduling, system calls, file systems and more. The natural next stop in this course.
- Virtual Memory — how every process gets its own private address space on top of the physical memory hierarchy, and what the TLB is.
Later lessons in CS Core Fundamentals build directly on this one: data structures (why arrays beat linked lists in practice), operating systems (what the kernel does with all this hardware), concurrency (cache coherence, atomics and memory ordering), networks (the slowest level of the hierarchy) and databases (buffer pools, columnar storage and why disk layout matters).