The Engineer's Mill

Bases, bits and bytes

A number written in base b has digits worth powers of b, so 2026 is $2\cdot {10}^3+0\cdot {10}^2+2\cdot 10+6$ in decimal and 11111101010 in binary. Hardware uses base 2 because a wire is easiest to read as one of two states. People write binary in hexadecimal, base 16, because each hex digit stands for exactly four bits, a nibble, so 0x7EA is 0111 1110 1010 at a glance. Eight bits make a byte, the smallest unit memory is addressed in, and a word is the natural width of the processor's registers, now almost always 64 bits.

With n bits there are $2^n$ patterns. Read as unsigned integers they stand for 0 to $2^n-1$, and arithmetic on them is arithmetic modulo $2^n$: add 1 to the largest value and you get 0, exactly the clock arithmetic of The Engineer's Compass, chapter 5.

Two's complement

For signed integers, every modern processor uses two's complement. The top bit's weight is negative: in n bits it's worth $-2^{n-1}$ instead of $+2^{n-1}$, and the other bits keep their usual positive weights. In 8 bits, 10000000 is −128, 11111111 is −128 + 127 = −1, and 01111111 is +127. The range is $-2^{n-1}$ to $2^{n-1}-1$, one more negative number than positive. Equivalently, the pattern for −x is the unsigned number $2^n-x$, which is why the representation lines up so neatly with modular arithmetic.

To negate a two's complement number, invert every bit and add 1: inverting gives $(2^n-1)-x$, and adding 1 gives $2^n-x$ (exercise 1.2). There's one zero, unlike older sign-and-magnitude schemes with a +0 and a −0. Most importantly, the hardware that adds unsigned numbers adds signed ones correctly too, because both are arithmetic modulo $2^n$. The processor doesn't need to know which reading you intend. Only comparisons, division, widening and overflow detection differ. The asymmetry has one sharp edge: the most negative number has no positive partner, so negating −128 in 8 bits gives −128 again, and abs(INT_MIN) in C is negative.

Overflow

An unsigned sum overflows when it carries out of the top bit. A signed sum overflows when two operands of the same sign produce a result of the other sign. In 8 bits, 100 + 50 gives the pattern 10010110, which is 150 unsigned and −106 signed. Languages disagree about what to do. C and C++ make signed overflow undefined behaviour, so compilers may assume it never happens and delete checks that rely on it, while unsigned overflow wraps by definition. Java and Go wrap signed integers silently. Rust panics in debug builds and wraps in release builds unless you ask for checked arithmetic. Python's integers grow without limit, so the only overflow is running out of memory.

Wrap-around has caused famous failures. In 2006 Joshua Bloch reported that the binary search in Java's standard library, and in many textbooks, computed its midpoint as (low + high) / 2. With arrays of over a billion elements, the sum overflows 32 bits and becomes negative. The fix is low + (high - low) / 2, and the example reproduces both. Systems that store time as a signed 32-bit count of seconds since 1970 run out on 19 January 2038 at 03:14:07 UTC, one second before they jump back to December 1901. And in 1996 the first Ariane 5 rocket was lost about forty seconds after launch, when a conversion of a 64-bit floating-point value into a 16-bit signed integer overflowed in software reused from Ariane 4, whose slower trajectory had never produced values that large.

Shifts, widening and division

Shifting left by k multiplies by $2^k$, dropping bits that fall off the top. Shifting right comes in two kinds. A logical shift fills with zeros, which suits unsigned values. An arithmetic shift copies the sign bit, so −20 >> 2 is −5, which suits signed values. Widening a signed value to more bits needs sign extension, copying the top bit into the new bits, so that −1 in 8 bits stays −1 in 32. Integer division of negative numbers differs too. Python's // and >> round down, so −7 // 2 is −4, while C, Java and Go round integer division towards zero, giving −3. Ported code that relies on either behaviour breaks quietly.

Byte order

A 32-bit value occupies four bytes, and machines disagree about their order. Little-endian machines, which include x86 and almost all ARM systems, store the least significant byte first, so 0x12345678 sits in memory as 78 56 34 12. Big-endian order, 12 34 56 78, is the convention for network protocols, where it's called network byte order, and for many file formats. Byte order never matters inside a program's own arithmetic. It matters the moment bytes cross a boundary: written to a file, sent over a network, or read from a memory dump. Then the format, not the machine, must say which order it uses, and code must convert explicitly, as Python's struct and int.from_bytes do.

Bits, run

The example converts between bases, encodes and decodes 8-bit two's complement, detects overflow, compares shifts and division rules, shows both byte orders, reproduces the midpoint and 2038 bugs in 32-bit arithmetic, and counts set bits with a classic trick.

import struct
from datetime import datetime, timedelta, timezone

# 1. One number, four bases
n = 2026
print(f"{n} = 0b{n:b} = 0o{n:o} = 0x{n:X}; as 4 bytes, big-endian: {n.to_bytes(4, 'big').hex(' ')}")

# 2. Two's complement in 8 bits: the bit pattern of -x is (2^8 - x)
BITS = 8
def encode(x): return x & ((1 << BITS) - 1)                  # keep the low 8 bits
def decode(u): return u - (1 << BITS) if u & (1 << (BITS - 1)) else u
for x in (5, -5, 127, -128, -1):
    print(f"{x:>5} -> {encode(x):08b} (0x{encode(x):02X}) -> {decode(encode(x)):>5}")
print(f"negate 5 by inverting and adding 1: ~00000101 + 1 = {encode(~5 + 1):08b} = {decode(encode(~5 + 1))}")
print(f"negating -128 gives {decode(encode(128))}: there is no +128 in 8 bits")

# 3. Overflow: the same adder, read two ways
def add8(a, b):
    s = encode(a + b)
    signed_overflow = (a >= 0) == (b >= 0) and (decode(s) >= 0) != (a >= 0)   # same signs in, other sign out
    return s, signed_overflow
s, ov = add8(100, 50)
print(f"\n100 + 50 in 8 bits = {s:08b}: unsigned {s}, signed {decode(s)}, signed overflow: {ov}")
s, ov = add8(-100, -50)
print(f"-100 + -50 in 8 bits = {s:08b}: signed {decode(s)}, signed overflow: {ov}")
print(f"0xFF read as unsigned is {0xFF}, read as signed is {decode(0xFF)}")

# 4. Shifts: arithmetic shifts keep the sign; integer division rounds differently in different languages
x = -20
print(f"\n-20 = {encode(x):08b}; arithmetic >> 2 = {encode(x >> 2):08b} ({x >> 2}); "
      f"logical >> 2 = {encode(x) >> 2:08b} ({encode(x) >> 2})")
print(f"-7 >> 1 = {-7 >> 1} and -7 // 2 = {-7 // 2} (round down); C's -7 / 2 is -3 (round towards zero)")

# 5. Byte order
v = 0x12345678
print(f"\n0x12345678 little-endian: {struct.pack('<I', v).hex(' ')}   big-endian: {struct.pack('>I', v).hex(' ')}")

# 6. Real overflow bugs, reproduced in 32-bit arithmetic
def i32(x): x &= 0xFFFFFFFF; return x - (1 << 32) if x >> 31 else x
lo, hi = 1_500_000_000, 1_600_000_000
print(f"binary search midpoint in 32-bit ints: (lo + hi) / 2 = {i32(lo + hi) // 2:,};  lo + (hi - lo) / 2 = {lo + (hi - lo) // 2:,}")
epoch = datetime(1970, 1, 1, tzinfo=timezone.utc)
last = epoch + timedelta(seconds=2 ** 31 - 1)
wrapped = epoch + timedelta(seconds=i32(2 ** 31))
print(f"a signed 32-bit time_t ends at {last:%Y-%m-%d %H:%M:%S} UTC; one second later it reads {wrapped:%Y-%m-%d %H:%M:%S}")

# 7. Bit tricks
def popcount(x):
    c = 0
    while x: x &= x - 1; c += 1                                # clears the lowest set bit each time
    return c
print(f"\npopcount(2026) = {popcount(2026)} (bin(2026).count('1') = {bin(2026).count('1')});  "
      f"powers of two below 70: {[k for k in range(1, 70) if k & (k - 1) == 0]}")

2026 = 0b11111101010 = 0o3752 = 0x7EA; as 4 bytes, big-endian: 00 00 07 ea
    5 -> 00000101 (0x05) ->     5
   -5 -> 11111011 (0xFB) ->    -5
  127 -> 01111111 (0x7F) ->   127
 -128 -> 10000000 (0x80) ->  -128
   -1 -> 11111111 (0xFF) ->    -1
negate 5 by inverting and adding 1: ~00000101 + 1 = 11111011 = -5
negating -128 gives -128: there is no +128 in 8 bits

100 + 50 in 8 bits = 10010110: unsigned 150, signed -106, signed overflow: True
-100 + -50 in 8 bits = 01101010: signed 106, signed overflow: True
0xFF read as unsigned is 255, read as signed is -1

-20 = 11101100; arithmetic >> 2 = 11111011 (-5); logical >> 2 = 00111011 (59)
-7 >> 1 = -4 and -7 // 2 = -4 (round down); C's -7 / 2 is -3 (round towards zero)

0x12345678 little-endian: 78 56 34 12   big-endian: 12 34 56 78
binary search midpoint in 32-bit ints: (lo + hi) / 2 = -597,483,648;  lo + (hi - lo) / 2 = 1,550,000,000
a signed 32-bit time_t ends at 2038-01-19 03:14:07 UTC; one second later it reads 1901-12-13 20:45:52

popcount(2026) = 8 (bin(2026).count('1') = 8);  powers of two below 70: [1, 2, 4, 8, 16, 32, 64]

The last line uses the identity that x & (x - 1) clears the lowest set bit of x. Subtracting 1 turns the lowest 1 into 0 and the zeros below it into ones, and the & then erases all of them. Repeating it until x is zero counts the set bits, and x is a power of two exactly when one application gives zero. Bit tricks like these are the vocabulary of hash functions, compression and the flags fields of network headers. Processors also offer them as single instructions such as popcnt.

The layout

The IEEE 754 double, Python's float and JavaScript's only number type, packs a number into 64 bits: a sign bit s, an 11-bit exponent e and a 52-bit fraction f. For normal numbers the value is

The leading 1 before the binary point isn't stored, since every normal number has one, so the 52 stored bits give 53 bits of precision. The exponent is stored with a bias of 1023 so that it can be compared as an unsigned number. The 32-bit single format has 8 exponent bits and 23 fraction bits, about 7 significant decimal digits against the double's 15 to 17.

Why 0.1 + 0.2 isn't 0.3

The double stored for 0.1 is exactly 0.1000000000000000055511151231257827…, slightly too large, and the ones for 0.2 and 0.3 are rounded too. IEEE 754 guarantees that each basic operation is correctly rounded: the result is the exact result of the stored inputs, rounded to the nearest double, with ties going to the even neighbour. The sum of the stored 0.1 and 0.2 rounds to a double one step above the double stored for 0.3, so they differ by $2^{-54}$, and Python prints 0.30000000000000004. The arithmetic was as accurate as it could be. The inputs weren't the numbers you typed. So never compare floating-point results with ==. Compare with a tolerance suited to the problem, as math.isclose does with a relative tolerance by default.

Precision, and gaps that grow

The distance from a double to the next one is its unit in the last place, or ulp. Near 1 it's $2^{-52}\approx 2.2\times {10}^{-16}$, the machine epsilon. Near a million it's about ${10}^{-10}$, and above $2^{53}\approx 9\times {10}^{15}$ it's 2 or more, so doubles stop representing every integer. The example shows $2^{53}+1$ rounding to $2^{53}$. That matters outside numerical code. JavaScript stores every number as a double, so 64-bit identifiers sent as JSON numbers lose their low digits in a browser, which is why APIs send large IDs as strings. Single precision runs out of integers at $2^{24}=\mathrm{16,777,216}$, which is why games with large worlds see objects jitter far from the origin.

Rounding accumulates, and order matters

Each operation rounds, and errors build up over many operations. Addition isn't associative: $({10}^{16}+1)-{10}^{16}$ is 0, because adding 1 to ${10}^{16}$ falls within half an ulp and is rounded away, while $({10}^{16}-{10}^{16})+1$ is 1. Adding 0.1 ten million times in a loop gives 999,999.99984, off by about $1.6\times {10}^{-4}$, because each small addend loses its low bits against the growing total. Kahan summation carries the lost low-order bits in a separate correction variable and adds them back, and Python's math.fsum goes further, tracking partial sums exactly and rounding once at the end. Both give 1,000,000.0. Order dependence has a practical consequence: a parallel sum, which adds in whatever order the threads finish, can give slightly different results on every run.

Special values

An exponent of all ones encodes infinity, when the fraction is zero, or NaN, "not a number", when it isn't. Overflow produces ±∞, and invalid operations such as ∞ − ∞ or 0/0 produce NaN, which then propagates through every later operation. NaN is unequal to everything, including itself, which breaks sorting and hash tables (The Engineer's Compass, chapter 4). There are two zeros, +0 and −0, equal under == but distinguishable by their sign, so 1/−0 is −∞. An exponent of all zeros encodes subnormal numbers, which fill the gap between the smallest normal double, about $2.2\times {10}^{-308}$, and zero. That's gradual underflow, and on some processors arithmetic on subnormals is much slower than normal arithmetic.

Catastrophic cancellation

Subtracting two nearly equal numbers cancels their shared leading digits and leaves only the low digits, which are the ones carrying rounding error. For small x, cos x is very close to 1, so $1-\cos x$ keeps hardly any correct digits. At x = ${10}^{-8}$, cos x rounds to exactly 1 and $(1-\cos x)/x^2$ comes out as 0 instead of 0.5. The identity $1-\cos x=2{\sin }^2(x/2)$ computes the same quantity without subtracting, and stays accurate. The same issue makes the textbook formula for variance, the mean of the squares minus the square of the mean, useless for data with a large mean and a small spread (exercise 2.3). The general cure is algebraic: rearrange the formula so it doesn't subtract nearly equal quantities.

Floats, measured

The example decodes the fields of three doubles, shows the exact stored value of 0.1, measures the gaps between doubles at four magnitudes, compares three ways of summing, exercises the special values, and computes $(1-\cos x)/x^2$ both ways.

import math, struct
from decimal import Decimal
from fractions import Fraction

# 1. The bits of a double: 1 sign bit, 11 exponent bits, 52 fraction bits
def fields(x):
    b = struct.unpack(">Q", struct.pack(">d", x))[0]
    return b >> 63, (b >> 52) & 0x7FF, b & ((1 << 52) - 1)
for x in (1.0, -2.5, 0.1):
    s, e, f = fields(x)
    print(f"{x:>5}: sign {s}  exponent {e:011b} ({e} - 1023 = {e - 1023:>3})  fraction {f:013X} (hex)")
print(f"0.1 is stored as exactly {Decimal(0.1)}")

# 2. Why 0.1 + 0.2 != 0.3
print(f"\n0.1 + 0.2 = {0.1 + 0.2!r}; == 0.3: {0.1 + 0.2 == 0.3}; nearest doubles differ by {Fraction(0.1 + 0.2) - Fraction(0.3)}")
print(f"math.isclose(0.1 + 0.2, 0.3): {math.isclose(0.1 + 0.2, 0.3)}")

# 3. The gaps between doubles grow with their size
for x in (1.0, 1e6, 1e16, 2.0 ** 53):
    print(f"next double after {x:>22,.1f} is {math.ulp(x):.3g} away")
print(f"2^53 + 1 = {2 ** 53 + 1:,} becomes {float(2 ** 53 + 1):,.0f} as a double")
f32 = struct.unpack("f", struct.pack("f", 16_777_217.0))[0]
print(f"in single precision, 16,777,217 becomes {f32:,.0f}")

# 4. Addition is not associative, and summation order matters
print(f"\n(1e16 + 1) - 1e16 = {(1e16 + 1) - 1e16};  (1e16 - 1e16) + 1 = {(1e16 - 1e16) + 1}")
naive = 0.0
for _ in range(10_000_000): naive += 0.1
def kahan(values):
    total = c = 0.0
    for v in values:
        y = v - c; t = total + y
        c = (t - total) - y; total = t                         # c recovers the low bits lost in the addition
    return total
print(f"adding 0.1 ten million times: naive {naive!r}, Kahan {kahan(0.1 for _ in range(10_000_000))!r}, "
      f"math.fsum {math.fsum(0.1 for _ in range(10_000_000))!r}")

# 5. Special values
inf, nan = float("inf"), float("nan")
print(f"\ninf - inf = {inf - inf}; nan == nan: {nan == nan}; -0.0 == 0.0: {-0.0 == 0.0}, "
      f"but copysign(1, -0.0) = {math.copysign(1, -0.0)}")
print(f"largest double {1.7976931348623157e308:.6e}; smallest normal {2.2250738585072014e-308:.6e}; "
      f"smallest subnormal {5e-324:.1e}; 5e-324 / 2 = {5e-324 / 2}")

# 6. Catastrophic cancellation, and an algebraically identical formula that avoids it
for x in (1e-4, 1e-6, 1e-8):
    bad = (1 - math.cos(x)) / x ** 2
    good = 2 * math.sin(x / 2) ** 2 / x ** 2
    print(f"(1 - cos x)/x^2 at x = {x:.0e}: direct {bad:.10f}, rewritten {good:.10f} (true limit 0.5)")

  1.0: sign 0  exponent 01111111111 (1023 - 1023 =   0)  fraction 0000000000000 (hex)
 -2.5: sign 1  exponent 10000000000 (1024 - 1023 =   1)  fraction 4000000000000 (hex)
  0.1: sign 0  exponent 01111111011 (1019 - 1023 =  -4)  fraction 999999999999A (hex)
0.1 is stored as exactly 0.1000000000000000055511151231257827021181583404541015625

0.1 + 0.2 = 0.30000000000000004; == 0.3: False; nearest doubles differ by 1/18014398509481984
math.isclose(0.1 + 0.2, 0.3): True
next double after                    1.0 is 2.22e-16 away
next double after            1,000,000.0 is 1.16e-10 away
next double after 10,000,000,000,000,000.0 is 2 away
next double after 9,007,199,254,740,992.0 is 2 away
2^53 + 1 = 9,007,199,254,740,993 becomes 9,007,199,254,740,992 as a double
in single precision, 16,777,217 becomes 16,777,216

(1e16 + 1) - 1e16 = 0.0;  (1e16 - 1e16) + 1 = 1.0
adding 0.1 ten million times: naive 999999.9998389754, Kahan 1000000.0, math.fsum 1000000.0

inf - inf = nan; nan == nan: False; -0.0 == 0.0: True, but copysign(1, -0.0) = -1.0
largest double 1.797693e+308; smallest normal 2.225074e-308; smallest subnormal 4.9e-324; 5e-324 / 2 = 0.0
(1 - cos x)/x^2 at x = 1e-04: direct 0.4999999970, rewritten 0.4999999996 (true limit 0.5)
(1 - cos x)/x^2 at x = 1e-06: direct 0.5000444503, rewritten 0.5000000000 (true limit 0.5)
(1 - cos x)/x^2 at x = 1e-08: direct 0.0000000000, rewritten 0.5000000000 (true limit 0.5)

The fields line up with the formula. 1.0 has exponent field 1023, meaning $2^0$, and fraction 0. −2.5 is $-1.25\times 2^1$, with fraction 0x4000000000000, binary .01. 0.1 is $1.6\times 2^{-4}$, whose fraction 0x999999999999A is the repeating pattern 1001 1001… ending in a rounded-up 1010. For money, use integers counting the smallest unit, or a decimal type such as Python's Decimal. Binary floating point can't hold 0.10 exactly, and an accounting system can't round away a cent.

Gates are functions, and wires are variables

A combinational circuit has no memory. Its outputs depend only on its current inputs, so it computes a function, and its truth table describes it completely. Physically, a gate is a handful of transistors, and a modern processor contains billions of them. Two costs matter. Size is the number of gates, which costs chip area and power. Depth is the longest chain of gates from any input to the output. Each gate takes time to settle, so depth sets how long the circuit needs before its output is valid, and therefore, in chapter 5, how fast the clock can tick.

Everything from NAND

NAND is 0 only when both inputs are 1. The Engineer's Compass, exercise 1.3, proved that it can express any boolean function. Here are the constructions, built up so that each gate uses the ones before:

• Not(a) = Nand(a, a), one gate;
• And(a, b) = Not(Nand(a, b)), two gates;
• Or(a, b) = Nand(Not a, Not b), three gates, by De Morgan's law;
• Xor(a, b): with t = Nand(a, b), the result is Nand(Nand(a, t), Nand(b, t)), four gates.

The multiplexer, or Mux, is the gate that makes computers programmable. It takes two data inputs and a selector, and passes through one input or the other: Mux(a, b, sel) = sel ? b : a, four NANDs. Its mirror image, the demultiplexer, routes one input to one of two outputs. Wider versions select among 4, 8 or more inputs and handle whole 16- or 64-bit words at once. A 16-bit And is just 16 Ands side by side: 32 NANDs, still depth 2, because the bits don't interact. Multiplexers are how a CPU chooses which register to read, which ALU function to apply and where the next instruction comes from.

From any truth table to a circuit

Every truth table has a circuit. For each input row where the output is 1, build an And of the inputs, negated where that row has a 0, and Or all of these terms together. This sum of products is correct by construction, and it's how logic synthesis starts, but it's rarely efficient. For the majority function, which is 1 when at least two of three inputs are 1, the sum of products uses 28 NANDs at depth 11, while a hand-designed version uses 6 NANDs at depth 4. Turning a specification into a small, shallow circuit is the job of synthesis tools. Like an optimising compiler, they apply algebraic identities until nothing more can be saved.

Shape matters as much as size. An 8-way Or, which is 1 if any of eight inputs is 1, can be a chain of seven Ors or a balanced tree of seven Ors. Both use 21 NANDs, but the chain is 14 gates deep and the tree only 6. Depth grows linearly in the chain and logarithmically in the tree. The same choice, at the scale of 64-bit additions, decides how fast a processor can add (chapter 4).

Built and checked

The example builds every gate above from a single nand function. Each signal carries its value and its depth, and a counter tracks how many NANDs each evaluation used. Every gate is checked against its full truth table.

from itertools import product

# A signal is (value, depth): depth counts the gates on the longest path from the inputs.
gates_used = 0
def nand(a, b):
    global gates_used; gates_used += 1
    return (1 - (a[0] & b[0]), max(a[1], b[1]) + 1)

def NOT(a): return nand(a, a)
def AND(a, b): return NOT(nand(a, b))
def OR(a, b): return nand(NOT(a), NOT(b))
def XOR(a, b):
    t = nand(a, b)
    return nand(nand(a, t), nand(b, t))
def MUX(a, b, sel): return nand(nand(a, NOT(sel)), nand(b, sel))          # sel ? b : a
def DMUX(x, sel): return AND(x, NOT(sel)), AND(x, sel)

def check(name, circuit, reference, arity):
    global gates_used
    ok, depth = True, 0
    for bits in product((0, 1), repeat=arity):
        gates_used = 0
        out = circuit(*[(b, 0) for b in bits])
        outs = out if isinstance(out, tuple) and isinstance(out[0], tuple) else (out,)
        ok &= tuple(o[0] for o in outs) == tuple(reference(*bits) if isinstance(reference(*bits), tuple) else (reference(*bits),))
        depth = max(depth, max(o[1] for o in outs))
    print(f"   {name:10} {gates_used:2} NANDs   depth {depth}   matches its truth table: {ok}")
print("every gate built from NAND alone:")
check("Not", NOT, lambda a: 1 - a, 1)
check("And", AND, lambda a, b: a & b, 2)
check("Or", OR, lambda a, b: a | b, 2)
check("Xor", XOR, lambda a, b: a ^ b, 2)
check("Mux", MUX, lambda a, b, s: b if s else a, 3)
check("DMux", DMUX, lambda x, s: (x & (1 - s), x & s), 2)

# Any truth table becomes a circuit: OR together one AND term per row that outputs 1
def from_truth_table(table, arity):
    def circuit(*ins):
        terms = []
        for bits in product((0, 1), repeat=arity):
            if table(*bits):
                lits = [x if b else NOT(x) for x, b in zip(ins, bits)]
                t = lits[0]
                for l in lits[1:]: t = AND(t, l)
                terms.append(t)
        out = terms[0]
        for t in terms[1:]: out = OR(out, t)
        return out
    return circuit
majority = lambda a, b, c: int(a + b + c >= 2)
print("\nmajority of three inputs:")
check("from table", from_truth_table(majority, 3), majority, 3)
check("by hand", lambda a, b, c: nand(AND(nand(a, b), nand(a, c)), nand(b, c)), majority, 3)

# Wider gates are copies: a 16-bit AND is 16 Ands side by side, still depth 2
gates_used = 0
word = [AND((1, 0), (b, 0)) for b in (1, 0) * 8]
print(f"\nAnd16: {gates_used} NANDs, depth {max(w[1] for w in word)}")
inputs = [(0, 0)] * 7 + [(1, 0)]
gates_used = 0
acc = inputs[0]
for b in inputs[1:]: acc = OR(acc, b)                                  # a chain of 7 Ors
chain_gates, chain_depth = gates_used, acc[1]
gates_used = 0
level = inputs
while len(level) > 1: level = [OR(level[i], level[i + 1]) for i in range(0, len(level), 2)]
print(f"Or8Way: {chain_gates} NANDs and depth {chain_depth} as a chain; {gates_used} NANDs and depth {level[0][1]} as a balanced tree")

every gate built from NAND alone:
   Not         1 NANDs   depth 1   matches its truth table: True
   And         2 NANDs   depth 2   matches its truth table: True
   Or          3 NANDs   depth 2   matches its truth table: True
   Xor         4 NANDs   depth 3   matches its truth table: True
   Mux         4 NANDs   depth 3   matches its truth table: True
   DMux        5 NANDs   depth 3   matches its truth table: True

majority of three inputs:
   from table 28 NANDs   depth 11   matches its truth table: True
   by hand     6 NANDs   depth 4   matches its truth table: True

And16: 32 NANDs, depth 2
Or8Way: 21 NANDs and depth 14 as a chain; 21 NANDs and depth 6 as a balanced tree

Adding bits

Adding two bits gives a sum bit and a carry: 1 + 1 = 10 in binary, sum 0 carry 1. The sum is a + b mod 2, which is Xor, and the carry is And. That's a half adder. Adding a column of a long sum needs three inputs, the two bits plus the carry from the column to the right, and a full adder does that with two half adders and an Or:

Built from this chapter's gates, a full adder takes 15 NANDs; a hand-optimised one takes 9.

The ripple-carry adder

To add two n-bit numbers, chain n full adders, feeding each one's carry out into the next one's carry in. This ripple-carry adder is exactly schoolbook addition, done in binary.

The example builds an 8-bit ripple adder from NAND gates and checks it on all 65,536 pairs of inputs. Its weakness is depth. Each full adder adds four gates to the carry path, so an 8-bit adder is 34 gates deep and a 64-bit adder 258. Chapter 5 shows that the clock can tick no faster than the slowest such path allows, so a 64-bit ripple adder would cap a processor at a few hundred megahertz.

Computing every carry at once

The way out is to notice when a column decides its carry on its own. A column generates a carry if both its bits are 1, $g_i=a_i{b}_i$, and propagates an incoming carry if exactly one bit is 1, $p_i=a_i\oplus b_i$. Then $c_{i+1}=g_i\vee p_i{c}_i$. Unrolling this shows that every carry is a function of the bits below it, and nothing forces the computation to go column by column:

The pairs (g, p) for adjacent spans of columns combine with an associative operation: a span generates a carry if its upper half generates one, or its upper half propagates and its lower half generates. Associativity means all the prefixes can be computed in a balanced tree, in ${\log }_{2}n$ levels, the same trick as chapter 3's balanced Or. That's a parallel-prefix adder, here the Kogge–Stone design from 1973. The example's table shows the trade. At 64 bits the prefix adder is 28 gates deep against the ripple adder's 258, and it uses three times as many gates, 2,883 against 960. Real processors use prefix adders of various shapes that balance gate count, wiring and depth.

Subtraction for free

Chapter 1 showed that $-y$ is the bitwise inverse of y plus 1, so $x-y=x+\bar{y}+1$. A subtractor is therefore an adder with a row of Xor gates that invert y on demand, and a carry-in of 1 that supplies the "+ 1". One circuit adds and subtracts, signed or unsigned. Comparisons come free too: x < y exactly when x − y is negative, ignoring overflow, so the sign bit of the difference answers the question.

The ALU

An arithmetic logic unit computes one of several functions of its inputs, chosen by control bits. The Hack ALU, designed for Nand2Tetris, does it with six bits applied in order:

• zx zeroes x, and nx then inverts it;
• zy zeroes y, and ny then inverts it;
• f chooses between x + y and x & y;
• no inverts the output.

Two status outputs report whether the result is zero (zr) and whether it's negative (ng). Those few operations produce eighteen useful functions, because inversion and addition combine in clever ways. With $\bar{v}=-v-1$ in two's complement, setting nx, f and no computes $\overline{\stackrel{‾}{x}+y}=-(-x-1+y)-1=x-y$. The example implements the ALU at the word level, runs all 18 control codes from the Nand2Tetris specification on 2,000 random pairs of 16-bit inputs, and checks every result against Python's arithmetic.

import random

# Signals are (value, depth), as in chapter 3, with a gate counter
count = 0
def nand(a, b):
    global count; count += 1
    return (1 - (a[0] & b[0]), max(a[1], b[1]) + 1)
def NOT(a): return nand(a, a)
def AND(a, b): return NOT(nand(a, b))
def OR(a, b): return nand(NOT(a), NOT(b))
def XOR(a, b):
    t = nand(a, b); return nand(nand(a, t), nand(b, t))

def half_adder(a, b): return XOR(a, b), AND(a, b)                          # sum, carry
def full_adder(a, b, c):
    s1, c1 = half_adder(a, b); s, c2 = half_adder(s1, c)
    return s, OR(c1, c2)

def bits(x, n): return [((x >> i) & 1, 0) for i in range(n)]
def value(sig): return sum(b[0] << i for i, b in enumerate(sig))

def ripple_add(a, b):
    carry, out = (0, 0), []
    for x, y in zip(a, b):
        s, carry = full_adder(x, y, carry); out.append(s)
    return out

# 1. An 8-bit ripple-carry adder, checked on all 65,536 input pairs
ok = all(value(ripple_add(bits(x, 8), bits(y, 8))) == (x + y) % 256 for x in range(256) for y in range(256))
print(f"8-bit ripple-carry adder correct for all 65,536 input pairs: {ok}")

# 2. Ripple carry versus a parallel-prefix (Kogge-Stone) adder: gates and depth
def prefix_add(a, b):
    n = len(a)
    g = [AND(x, y) for x, y in zip(a, b)]                                 # generate
    p = [XOR(x, y) for x, y in zip(a, b)]                                 # propagate
    G, P, d = g[:], p[:], 1
    while d < n:                                                         # combine spans of length d
        G = [OR(G[i], AND(P[i], G[i - d])) if i >= d else G[i] for i in range(n)]
        P = [AND(P[i], P[i - d]) if i >= d else P[i] for i in range(n)]
        d *= 2
    return [p[0]] + [XOR(p[i], G[i - 1]) for i in range(1, n)]
print("\n bits   ripple: NANDs  depth    prefix: NANDs  depth")
for n in (8, 16, 32, 64):
    x, y = random.Random(n).getrandbits(n), random.Random(n + 1).getrandbits(n)
    count = 0; r = ripple_add(bits(x, n), bits(y, n)); rc, rd = count, max(s[1] for s in r)
    count = 0; q = prefix_add(bits(x, n), bits(y, n)); qc, qd = count, max(s[1] for s in q)
    assert value(r) == value(q) == (x + y) % 2 ** n
    print(f"{n:5} {rc:13,} {rd:6} {qc:15,} {qd:6}")

# 3. The Hack ALU: six control bits choose among 18 functions of two 16-bit inputs
MASK = 0xFFFF
def alu(x, y, zx, nx, zy, ny, f, no):
    if zx: x = 0
    if nx: x = ~x & MASK
    if zy: y = 0
    if ny: y = ~y & MASK
    out = (x + y) & MASK if f else x & y
    if no: out = ~out & MASK
    return out, int(out == 0), out >> 15                                  # out, zr, ng
def s16(v): return v - 0x10000 if v & 0x8000 else v
table = {"0": "101010", "1": "111111", "-1": "111010", "x": "001100", "y": "110000", "!x": "001101",
         "!y": "110001", "-x": "001111", "-y": "110011", "x+1": "011111", "y+1": "110111", "x-1": "001110",
         "y-1": "110010", "x+y": "000010", "x-y": "010011", "y-x": "000111", "x&y": "000000", "x|y": "010101"}
ref = {"0": lambda x, y: 0, "1": lambda x, y: 1, "-1": lambda x, y: -1, "x": lambda x, y: x, "y": lambda x, y: y,
       "!x": lambda x, y: ~x, "!y": lambda x, y: ~y, "-x": lambda x, y: -x, "-y": lambda x, y: -y,
       "x+1": lambda x, y: x + 1, "y+1": lambda x, y: y + 1, "x-1": lambda x, y: x - 1, "y-1": lambda x, y: y - 1,
       "x+y": lambda x, y: x + y, "x-y": lambda x, y: x - y, "y-x": lambda x, y: y - x,
       "x&y": lambda x, y: x & y, "x|y": lambda x, y: x | y}
rng = random.Random(4)
samples = [(rng.randrange(-32768, 32768), rng.randrange(-32768, 32768)) for _ in range(2000)]
good = 0
for name, code in table.items():
    ctl = [int(c) for c in code]
    good += all(s16(alu(x & MASK, y & MASK, *ctl)[0]) == s16(ref[name](x, y) & MASK) for x, y in samples)
print(f"\nHack ALU: {good} of {len(table)} functions correct on 2,000 random input pairs")
out, zr, ng = alu(5, 5 & MASK, *[int(c) for c in table["x-y"]])
print(f"x - y with x = y = 5: out = {out}, zr = {zr}, ng = {ng};  "
      f"y - x with x = 7, y = 5: out = {s16(alu(7, 5, *[int(c) for c in table['y-x']])[0])}, "
      f"ng = {alu(7, 5, *[int(c) for c in table['y-x']])[2]}")

8-bit ripple-carry adder correct for all 65,536 input pairs: True

 bits   ripple: NANDs  depth    prefix: NANDs  depth
    8           120     34             195     16
   16           240     66             499     20
   32           480    130           1,219     24
   64           960    258           2,883     28

Hack ALU: 18 of 18 functions correct on 2,000 random input pairs
x - y with x = y = 5: out = 0, zr = 1, ng = 0;  y - x with x = 7, y = 5: out = -2, ng = 1

The status flags are how a computer decides anything. Every conditional branch in chapter 7 is a jump taken or not according to zr and ng, the results of an ALU operation such as x − y. Real ALUs add shifts, rotations and comparisons, and processors pair them with separate units for multiplication and division. Multiplying 64-bit integers takes a few cycles on a modern core, using trees of adders working in parallel. Division is iterative and takes tens of cycles, which is why compilers turn division by a constant into a multiplication and a shift whenever they can.

Feedback and the latch

Wire two NAND gates so that each one's output is one of the other's inputs, and leave one input on each free. Call the free inputs $\bar{S}$ and $\bar{R}$; they're active-low, meaning a 0 does something. Pulling $\bar{S}$ to 0 forces the output Q to 1, and the cross-connection then holds it there after $\bar{S}$ returns to 1. Pulling $\bar{R}$ to 0 forces Q to 0, which is also held. With both inputs at 1 the circuit just remembers its last state. That's an SR latch, one bit of memory made of two gates.

The forbidden input is both at 0, which forces both outputs to 1, breaking the rule that they're opposites. Releasing both at once creates a race, and the example's simulation, which updates both gates in lockstep, oscillates for ever. Real gates are never perfectly matched, so the latch eventually falls one way or the other, but it may hover between the two for an unpredictable time first, a condition called metastability. Designs avoid the forbidden input, and synchronise any signal arriving from outside the clock's control.

The clock and the D flip-flop

A latch changes whenever its inputs change, and signals in a real circuit change at different times as they ripple through gates of different depths. The solution is a clock, a signal that alternates between 0 and 1 at a fixed rate, and a D flip-flop that copies its input D to its output Q only at the clock's rising edge. Internally it's two latches in a row, master and slave, alternately enabled by the clock, so the input can never race straight through. Nand2Tetris treats the flip-flop as a primitive with a simple rule: out(t) = in(t − 1), the output during each clock cycle is what the input was during the previous one.

For the sampling to work, D must be stable for a short setup time before the edge and a hold time after it. Meeting those two constraints everywhere on a chip is what timing analysis tools check, and violating them is how metastability gets in.

Registers, RAM and the program counter

A 1-bit register is a flip-flop with a Mux in front. When the load bit is 1 the Mux passes in the new value, and when it's 0 it feeds the flip-flop's own output back, so the bit is kept (exercise 5.1). Sixteen of them side by side make a 16-bit register. A RAM is many registers plus addressing. A DMux routes the load bit to the one register selected by the address, and a Mux selects that register's output. Nand2Tetris builds RAM8 from 8 registers, then RAM64 from 8 RAM8s, and so on up to the 16K-word RAM of the Hack computer, each level using three more address bits. Real memories aren't built from flip-flops. Static RAM, used for caches, takes six transistors per bit, and dynamic RAM, used for main memory, stores each bit as charge on a tiny capacitor with one transistor. That's dense and cheap, but the charge leaks away, so every row must be read and rewritten every few tens of milliseconds, and it's slow to read (chapter 9).

The program counter holds the address of the next instruction. On each cycle it does one of four things, in priority order: reset to 0, load a new address for a jump, increment to the next instruction, or hold. In the example it counts 0, 1, 2, 3, jumps to 100, counts on, and resets. That one register is the whole of a computer's control flow: chapter 7's CPU decides each cycle whether to increment it or load it.

Simulated

The example simulates the SR latch gate by gate, then models flip-flops, a register, an 8-word RAM and the program counter cycle by cycle, and finally turns chapter 4's adder depths into maximum clock rates.

# 1. An SR latch: two NAND gates feeding each other. Inputs are active-low: s=0 sets, r=0 resets.
def nand(a, b): return 1 - (a & b)
def settle(s, r, q, qb):
    for step in range(10):                                     # update both gates at once until nothing changes
        nq, nqb = nand(s, qb), nand(r, q)
        if (nq, nqb) == (q, qb): return q, qb, step
        q, qb = nq, nqb
    return q, qb, None                                         # never settled
q, qb = 0, 1
print("SR latch made of two NANDs:")
for s, r, what in ((0, 1, "set"), (1, 1, "hold"), (1, 0, "reset"), (1, 1, "hold"), (0, 0, "both low"), (1, 1, "release both")):
    q, qb, steps = settle(s, r, q, qb)
    print(f"   s={s} r={r} {what:13} -> Q={q} Q'={qb}" + ("   oscillates: no stable state" if steps is None else ""))

# 2. A clocked D flip-flop: its output is whatever its input was at the previous clock tick
class DFF:
    def __init__(self): self.state = 0
    def tick(self, d): out = self.state; self.state = d; return out
ff, ins = DFF(), [1, 1, 0, 1, 0, 0, 1]
outs = [ff.tick(d) for d in ins]
print(f"\nD flip-flop   in:  {ins}\n              out: {outs}  (one tick later)")

# 3. A register remembers until told to load; a RAM is registers plus address decoding
class Register:
    def __init__(self): self.ff = DFF(); self.value = 0
    def tick(self, x, load):
        self.value = x if load else self.value                 # a Mux in front of the flip-flops
        return self.ff.tick(self.value)
reg = Register()
trace = [(x, load, reg.tick(x, load)) for x, load in ((7, 1), (9, 0), (9, 0), (4, 1), (5, 0), (5, 0))]
print("\nregister (in, load) -> out: " + ", ".join(f"({x},{l})->{o}" for x, l, o in trace))
class RAM8:
    def __init__(self): self.regs = [0] * 8
    def access(self, x, addr, load):
        out = self.regs[addr]                                  # Mux8Way16 selects one register's output
        if load: self.regs[addr] = x                           # DMux8Way routes the load bit to one register
        return out
ram = RAM8()
for addr, x in ((3, 42), (5, 7), (3, 43)): ram.access(x, addr, 1)
print(f"RAM8 after writing 42 to 3, 7 to 5, then 43 to 3: {ram.regs}")

# 4. The program counter: reset beats load beats increment
class PC:
    def __init__(self): self.value = 0
    def tick(self, x=0, load=0, inc=1, reset=0):
        out = self.value
        self.value = 0 if reset else x if load else (self.value + 1) & 0xFFFF if inc else self.value
        return out
pc = PC()
steps = [dict(), dict(), dict(), dict(x=100, load=1), dict(), dict(), dict(reset=1), dict()]
print(f"program counter: {[pc.tick(**s) for s in steps]}   (jump to 100 after step 3, reset after step 6)")

# 5. The clock can tick no faster than the slowest path between two registers
gate_ps = 15                                                   # an illustrative delay per gate, in picoseconds
for name, depth in (("64-bit ripple-carry adder", 258), ("64-bit prefix adder", 28)):
    period = depth * gate_ps
    print(f"{name:26}: {depth:3} gates deep -> {period / 1000:.2f} ns per cycle -> at most {1e6 / period:,.0f} MHz")

SR latch made of two NANDs:
   s=0 r=1 set           -> Q=1 Q'=0
   s=1 r=1 hold          -> Q=1 Q'=0
   s=1 r=0 reset         -> Q=0 Q'=1
   s=1 r=1 hold          -> Q=0 Q'=1
   s=0 r=0 both low      -> Q=1 Q'=1
   s=1 r=1 release both  -> Q=1 Q'=1   oscillates: no stable state

D flip-flop   in:  [1, 1, 0, 1, 0, 0, 1]
              out: [0, 1, 1, 0, 1, 0, 0]  (one tick later)

register (in, load) -> out: (7,1)->0, (9,0)->7, (9,0)->7, (4,1)->7, (5,0)->4, (5,0)->4
RAM8 after writing 42 to 3, 7 to 5, then 43 to 3: [0, 0, 0, 43, 0, 7, 0, 0]
program counter: [0, 1, 2, 3, 100, 101, 102, 0]   (jump to 100 after step 3, reset after step 6)
64-bit ripple-carry adder : 258 gates deep -> 3.87 ns per cycle -> at most 258 MHz
64-bit prefix adder       :  28 gates deep -> 0.42 ns per cycle -> at most 2,381 MHz

How fast can the clock tick?

In a synchronous design every flip-flop updates at the same clock edge, and between edges the combinational logic computes the next values. Those values must settle before the next edge, so the clock period must exceed the delay of the slowest path from one flip-flop to the next, the critical path, plus the setup time. With an illustrative 15 picoseconds per gate, the 64-bit ripple adder's 258-gate path allows at most 258 MHz, while the prefix adder's 28 gates allow about 2.4 GHz. That's why chapter 4's carry trick matters. Designers shorten critical paths with faster circuits, and by splitting long paths into stages separated by registers, which is pipelining (chapter 12).

Clock rates rose for decades and then stopped near 4 to 5 GHz around 2005. The power a chip burns switching its transistors grows with the clock rate and with the square of the supply voltage. Voltages could no longer fall fast enough to compensate, and chips would have melted. Since then, more performance has come from doing more per cycle and from more cores (chapter 15), not from a faster clock.

What an instruction set promises

An instruction set architecture (ISA) specifies the programmer-visible state, meaning the registers, the program counter and memory, and every instruction's effect on it. RISC-V, for example, has 32 integer registers of 32 or 64 bits, named x0 to x31, where x0 always reads as zero. Memory is a large array of bytes, stored little-endian. Everything else is microarchitecture: how many instructions run at once, how big the caches are, how branches are predicted. A cheap microcontroller and a server processor can implement the same ISA and run the same binary, one at a millionth of the other's speed. Three ISAs dominate today: x86-64 in most PCs and servers, ARM64 in phones and Apple's computers, and RISC-V, an open standard designed at Berkeley in 2010 that anyone can implement without a licence.

RISC and CISC

The x86 family is the classic CISC, complex instruction set computer. Its instructions vary from 1 to 15 bytes, and many can read memory, compute and write memory in a single instruction. ret is the single byte C3, mov eax, 1 is 5 bytes, and loading a 64-bit constant takes 10. RISC designs such as ARM64 and RISC-V, reduced instruction set computers, use fixed-size instructions, 4 bytes in RISC-V, and a load/store architecture: only loads and stores touch memory, and arithmetic works only on registers. Fixed sizes make decoding simple, since the processor knows where every instruction starts, and that matters when it wants to decode several per cycle (chapter 14). The old trade-off has mostly dissolved. Modern x86 processors translate each instruction into RISC-like micro-operations internally, while RISC designs added compressed 2-byte forms to recover CISC's code density.

Encoding RISC-V

Every RV32I instruction is 32 bits, in one of six formats. The lowest 7 bits, the opcode, say which format applies, and the fields that name registers sit at the same positions in every format.

Immediates are two's complement and sign-extended to the register width, so addi x6, x0, -1 stores the 12-bit pattern 0xFFF and loads −1. Branch offsets count bytes from the branch itself and are always even, so the lowest bit isn't stored, which lets a 12-bit field reach ±4 KiB. The B-format's odd-looking bit shuffle keeps each immediate bit at the same position as in the S-format, so the hardware needs fewer multiplexers to assemble it.

Encoded and decoded

The example encodes nine RISC-V instructions into machine code, shows each one's fields, and decodes the binary back into assembly. It then encodes some Hack instructions.

# A slice of RISC-V (RV32I): every instruction is 32 bits, in one of six formats
REG = {f"x{i}": i for i in range(32)}
def bits(v, hi, lo): return (v >> lo) & ((1 << (hi - lo + 1)) - 1)
def R(f7, rs2, rs1, f3, rd, op): return f7 << 25 | rs2 << 20 | rs1 << 15 | f3 << 12 | rd << 7 | op
def I(imm, rs1, f3, rd, op): return (imm & 0xFFF) << 20 | rs1 << 15 | f3 << 12 | rd << 7 | op
def S(imm, rs2, rs1, f3, op): return bits(imm, 11, 5) << 25 | rs2 << 20 | rs1 << 15 | f3 << 12 | bits(imm, 4, 0) << 7 | op
def B(imm, rs2, rs1, f3, op):
    return (bits(imm, 12, 12) << 31 | bits(imm, 10, 5) << 25 | rs2 << 20 | rs1 << 15 | f3 << 12
            | bits(imm, 4, 1) << 8 | bits(imm, 11, 11) << 7 | op)
def U(imm, rd, op): return (imm & 0xFFFFF) << 12 | rd << 7 | op

def assemble(line):
    op, args = line.split(None, 1)
    a = [x.strip() for x in args.replace("(", ",").replace(")", "").split(",")]
    if op == "add":  return R(0, REG[a[2]], REG[a[1]], 0, REG[a[0]], 0x33)
    if op == "sub":  return R(0x20, REG[a[2]], REG[a[1]], 0, REG[a[0]], 0x33)
    if op == "addi": return I(int(a[2]), REG[a[1]], 0, REG[a[0]], 0x13)
    if op == "lw":   return I(int(a[1]), REG[a[2]], 2, REG[a[0]], 0x03)
    if op == "sw":   return S(int(a[1]), REG[a[0]], REG[a[2]], 2, 0x23)
    if op == "beq":  return B(int(a[2]), REG[a[1]], REG[a[0]], 0, 0x63)
    if op == "bne":  return B(int(a[2]), REG[a[1]], REG[a[0]], 1, 0x63)
    if op == "lui":  return U(int(a[1], 0), REG[a[0]], 0x37)
    raise ValueError(op)

def sext(v, width): return v - (1 << width) if v >> (width - 1) else v
def disassemble(w):
    op, rd, f3, rs1, rs2, f7 = bits(w, 6, 0), bits(w, 11, 7), bits(w, 14, 12), bits(w, 19, 15), bits(w, 24, 20), bits(w, 31, 25)
    if op == 0x33: return f"{'sub' if f7 == 0x20 else 'add'} x{rd}, x{rs1}, x{rs2}"
    if op == 0x13: return f"addi x{rd}, x{rs1}, {sext(bits(w, 31, 20), 12)}"
    if op == 0x03: return f"lw x{rd}, {sext(bits(w, 31, 20), 12)}(x{rs1})"
    if op == 0x23: return f"sw x{rs2}, {sext(f7 << 5 | rd, 12)}(x{rs1})"
    if op == 0x63:
        imm = bits(w, 31, 31) << 12 | bits(w, 7, 7) << 11 | bits(w, 30, 25) << 5 | bits(w, 11, 8) << 1
        return f"{'bne' if f3 == 1 else 'beq'} x{rs1}, x{rs2}, {sext(imm, 13)}"
    if op == 0x37: return f"lui x{rd}, 0x{bits(w, 31, 12):x}"
    return "?"

program = ["addi x5, x0, 10", "addi x6, x0, -1", "add x7, x5, x6", "sub x8, x5, x6",
           "lw x9, 8(x2)", "sw x9, 12(x2)", "beq x5, x7, -8", "bne x5, x0, 16", "lui x10, 0x12345"]
print(f"{'assembly':20} {'machine code':>12}   {'binary':^39}   decoded")
for line in program:
    w = assemble(line)
    b = f"{w:032b}"
    print(f"{line:20} 0x{w:08X}   {b[:7]} {b[7:12]} {b[12:17]} {b[17:20]} {b[20:25]} {b[25:]}   {disassemble(w)}")
print(f"every instruction round-trips: {all(disassemble(assemble(l)) == l for l in program)}")

# The Hack computer (Nand2Tetris): 16-bit instructions of two kinds
COMP = {"0": "0101010", "1": "0111111", "D": "0001100", "A": "0110000", "M": "1110000",
        "D+A": "0000010", "D+M": "1000010", "D-A": "0010011", "M-1": "1110010"}
DEST = {"": "000", "M": "001", "D": "010", "A": "100", "AM": "101"}
JUMP = {"": "000", "JGT": "001", "JEQ": "010", "JMP": "111"}
def hack(line):
    if line.startswith("@"): return f"0{int(line[1:]):015b}"            # A-instruction: load a constant
    dest, rest = line.split("=") if "=" in line else ("", line)
    comp, jump = rest.split(";") if ";" in rest else (rest, "")
    return "111" + COMP[comp] + DEST[dest] + JUMP[jump]                  # C-instruction: compute, store, jump
print()
for line in ("@21", "D=A", "@5", "D=D+A", "M=D", "D;JGT", "0;JMP"):
    print(f"Hack {line:7} -> {hack(line)}")

assembly             machine code                   binary                    decoded
addi x5, x0, 10      0x00A00293   0000000 01010 00000 000 00101 0010011   addi x5, x0, 10
addi x6, x0, -1      0xFFF00313   1111111 11111 00000 000 00110 0010011   addi x6, x0, -1
add x7, x5, x6       0x006283B3   0000000 00110 00101 000 00111 0110011   add x7, x5, x6
sub x8, x5, x6       0x40628433   0100000 00110 00101 000 01000 0110011   sub x8, x5, x6
lw x9, 8(x2)         0x00812483   0000000 01000 00010 010 01001 0000011   lw x9, 8(x2)
sw x9, 12(x2)        0x00912623   0000000 01001 00010 010 01100 0100011   sw x9, 12(x2)
beq x5, x7, -8       0xFE728CE3   1111111 00111 00101 000 11001 1100011   beq x5, x7, -8
bne x5, x0, 16       0x00029863   0000000 00000 00101 001 10000 1100011   bne x5, x0, 16
lui x10, 0x12345     0x12345537   0001001 00011 01000 101 01010 0110111   lui x10, 0x12345
every instruction round-trips: True

Hack @21     -> 0000000000010101
Hack D=A     -> 1110110000010000
Hack @5      -> 0000000000000101
Hack D=D+A   -> 1110000010010000
Hack M=D     -> 1110001100001000
Hack D;JGT   -> 1110001100000001
Hack 0;JMP   -> 1110101010000111

Read the binary column against the figure. add x7, x5, x6 has funct7 0, rs2 = 6, rs1 = 5, funct3 0, rd = 7 and opcode 0110011, and sub differs only in funct7, 0100000. The ALU's subtract control comes straight from that one bit. lui x10, 0x12345 loads a 20-bit immediate into the upper bits of a register, and an addi fills in the low 12, which is how RISC-V builds 32-bit constants (exercise 6.2).

The Hack instruction set

The Hack computer has 16-bit instructions of just two kinds. An A-instruction, a 0 followed by 15 bits, loads a constant into the A register, as in @21. A C-instruction, 111 followed by 13 bits, computes something with the ALU, stores it, and maybe jumps. The bits are the control signals: one bit chooses whether the ALU's second input is A or M, the memory word at address A; six bits are the ALU's zx, nx, zy, ny, f and no from chapter 4; three bits say which of A, D and M receive the result; and three bits say whether to jump if the result is negative, zero or positive. D=D+A is 1110000010010000, and 0;JMP, an unconditional jump to the address in A, is 1110101010000111. Hack has no call or return instructions and no stack. Nand2Tetris adds those in software, with a virtual machine (chapter 8).

The datapath and the control unit

A processor has two parts. The datapath holds and transforms data: registers, the ALU, memory, and multiplexers that route values between them. The control unit decodes each instruction into the signals that drive the datapath: which inputs the multiplexers select, what the ALU computes, which registers load a new value, and whether the program counter jumps. In most processors the control unit is a substantial circuit. In Hack it's almost nothing, because the C-instruction's bits already are the control signals.

Fetch, decode, execute

Each clock cycle, the Hack CPU does all of the following:

• Fetch: read the instruction at ROM[PC].
• Decode: if the top bit is 0, it's an A-instruction; otherwise split it into the a bit, the six ALU control bits, three destination bits and three jump bits.
• Execute: for an A-instruction, load the constant into A. For a C-instruction, run the ALU on D and either A or M, and store the result in whichever of A, D and M the destination bits name.
• Next: if the jump bits match the ALU's zero and negative flags, load PC from A; otherwise increment it.

Hack is a single-cycle design: one instruction per cycle, and the clock period long enough for the slowest instruction to finish. It's also a Harvard architecture, with separate memories for instructions and data, so fetching and loading never compete. Most computers are von Neumann machines, with one memory holding both, which is what lets a program load another program, or a compiler write machine code. Modern processors are von Neumann outside and split again inside, with separate level-1 caches for instructions and data. Real CPUs also don't finish one instruction before starting the next. They overlap many, which Part IV explains, but the logical cycle stays the same.

An assembler in two passes

Programs are written in assembly, with names instead of numbers, and an assembler translates them into machine code. The difficulty is forward references: @END refers to a label defined later. The standard solution is two passes. The first pass walks the program counting instructions and records the ROM address of every label, which don't take up ROM themselves. The second pass translates each instruction, replacing labels with their addresses and giving every other new symbol, a variable, the next free RAM address from 16 upward. The example's assembler does exactly this in about thirty lines, which is Nand2Tetris project 6.

Programs, run

The example assembles a program that adds the numbers 1 to 100, shows its first machine words and the first eight cycles of execution, and runs it to completion. It then runs a multiplication program, which multiplies by repeated addition because Hack has no multiply instruction, on three pairs of inputs.

# A Hack assembler and a cycle-by-cycle Hack CPU: fetch, decode, execute
COMP = {"0": "0101010", "1": "0111111", "-1": "0111010", "D": "0001100", "A": "0110000", "!D": "0001101",
        "!A": "0110001", "-D": "0001111", "-A": "0110011", "D+1": "0011111", "A+1": "0110111", "D-1": "0001110",
        "A-1": "0110010", "D+A": "0000010", "D-A": "0010011", "A-D": "0000111", "D&A": "0000000", "D|A": "0010101",
        "M": "1110000", "!M": "1110001", "-M": "1110011", "M+1": "1110111", "M-1": "1110010", "D+M": "1000010",
        "D-M": "1010011", "M-D": "1000111", "D&M": "1000000", "D|M": "1010101"}
DEST = {"": 0, "M": 1, "D": 2, "MD": 3, "A": 4, "AM": 5, "AD": 6, "AMD": 7}
JUMP = {"": 0, "JGT": 1, "JEQ": 2, "JGE": 3, "JLT": 4, "JNE": 5, "JLE": 6, "JMP": 7}

def assemble(source):
    lines = [l.split("//")[0].strip() for l in source.splitlines()]
    lines = [l for l in lines if l]
    symbols = {f"R{i}": i for i in range(16)} | {"SCREEN": 16384, "KBD": 24576}
    pc = 0
    for l in lines:                                            # pass 1: labels name ROM addresses
        if l.startswith("("): symbols[l[1:-1]] = pc
        else: pc += 1
    code, next_var = [], 16
    for l in lines:                                            # pass 2: translate, allocating variables from 16
        if l.startswith("("): continue
        if l.startswith("@"):
            s = l[1:]
            if not s.isdigit() and s not in symbols: symbols[s] = next_var; next_var += 1
            code.append(int(s) if s.isdigit() else symbols[s])
        else:
            dest, rest = l.split("=") if "=" in l else ("", l)
            comp, jump = rest.split(";") if ";" in rest else (rest, "")
            code.append(int("111" + COMP[comp] + f"{DEST[dest]:03b}" + f"{JUMP[jump]:03b}", 2))
    return code, symbols

def alu(x, y, zx, nx, zy, ny, f, no):                          # chapter 4's ALU
    if zx: x = 0
    if nx: x = ~x & 0xFFFF
    if zy: y = 0
    if ny: y = ~y & 0xFFFF
    out = (x + y) & 0xFFFF if f else x & y
    return ~out & 0xFFFF if no else out

def run(code, ram, max_cycles=100_000, trace=0):
    A = D = PC = cycles = 0
    while cycles < max_cycles:
        instr = code[PC]; cycles += 1                          # fetch
        if instr >> 15 == 0:                                   # A-instruction: A = constant
            A, PC = instr, PC + 1
        else:                                                  # C-instruction: decode its fields
            a, c = (instr >> 12) & 1, [(instr >> (11 - i)) & 1 for i in range(6)]
            d, j = (instr >> 3) & 7, instr & 7
            out = alu(D, ram[A] if a else A, *c)               # execute: the comp bits drive the ALU directly
            neg, zero = out >> 15, out == 0
            jump = (j & 4 and neg) or (j & 2 and zero) or (j & 1 and not neg and not zero)
            if d & 1: ram[A] = out                             # write M before A changes
            if d & 2: D = out
            next_pc = A if jump else PC + 1
            if d & 4: A = out
            if jump and next_pc == PC - 1 and code[next_pc] == next_pc:
                return cycles                                  # "@HALT, 0;JMP" loops for ever: the program is done
            PC = next_pc
        if cycles <= trace:
            signed = D - 65536 if D & 0x8000 else D
            print(f"   cycle {cycles:2}: next PC = {PC:2}   A = {A:3}   D = {signed:4}")
    return cycles

SUM = """
    @i
    M=1          // i = 1
    @sum
    M=0          // sum = 0
(LOOP)
    @i
    D=M
    @100
    D=D-A
    @END
    D;JGT        // if i > 100, stop
    @i
    D=M
    @sum
    M=D+M        // sum = sum + i
    @i
    M=M+1        // i = i + 1
    @LOOP
    0;JMP
(END)
    @sum
    D=M
    @R0
    M=D          // R0 = sum
(HALT)
    @HALT
    0;JMP
"""
code, symbols = assemble(SUM)
print(f"sum 1..100: {len(code)} instructions; symbols i -> RAM[{symbols['i']}], sum -> RAM[{symbols['sum']}], "
      f"LOOP -> ROM[{symbols['LOOP']}], END -> ROM[{symbols['END']}]")
for addr in range(6): print(f"   ROM[{addr}] = {code[addr]:016b}")
print("first cycles:")
ram = [0] * 32768
cycles = run(code, ram, trace=8)
print(f"R0 = {ram[0]} after {cycles:,} cycles")

MULT = """
    @R2
    M=0          // R2 = 0
(LOOP)
    @R1
    D=M
    @END
    D;JEQ        // while R1 != 0
    @R0
    D=M
    @R2
    M=D+M        // R2 = R2 + R0
    @R1
    M=M-1        // R1 = R1 - 1
    @LOOP
    0;JMP
(END)
    @END
    0;JMP
"""
mcode, _ = assemble(MULT)
for x, y in ((6, 7), (123, 45), (2, 1000)):
    ram = [0] * 32768; ram[0], ram[1] = x, y
    c = run(mcode, ram)
    print(f"multiply {x} x {y} by repeated addition: R2 = {ram[2]:,} in {c:,} cycles")

sum 1..100: 24 instructions; symbols i -> RAM[16], sum -> RAM[17], LOOP -> ROM[4], END -> ROM[18]
   ROM[0] = 0000000000010000
   ROM[1] = 1110111111001000
   ROM[2] = 0000000000010001
   ROM[3] = 1110101010001000
   ROM[4] = 0000000000010000
   ROM[5] = 1111110000010000
first cycles:
   cycle  1: next PC =  1   A =  16   D =    0
   cycle  2: next PC =  2   A =  16   D =    0
   cycle  3: next PC =  3   A =  17   D =    0
   cycle  4: next PC =  4   A =  17   D =    0
   cycle  5: next PC =  5   A =  16   D =    0
   cycle  6: next PC =  6   A =  16   D =    1
   cycle  7: next PC =  7   A = 100   D =    1
   cycle  8: next PC =  8   A = 100   D =  -99
R0 = 5050 after 1,416 cycles
multiply 6 x 7 by repeated addition: R2 = 42 in 92 cycles
multiply 123 x 45 by repeated addition: R2 = 5,535 in 548 cycles
multiply 2 x 1000 by repeated addition: R2 = 2,000 in 12,008 cycles

The trace shows the machine working at the lowest level. Cycles 1 to 4 set i = 1 and sum = 0. In cycle 5, @i puts i's address, 16, into A; in cycle 6, D=M reads RAM[16] into D; and by cycle 8, D holds i − 100 = −99, ready for the jump test. Each loop iteration costs 14 instructions, so the program takes 14 × 100 + 16 = 1,416 cycles (exercise 7.2). The multiplication results show how much an algorithm depends on its inputs: 2 × 1000 takes 12,008 cycles, because the loop counts down the second operand. Swapping the operands would take 32.

Memory-mapped I/O

The Hack computer has no input or output instructions. Instead, part of the data memory is wired to devices. RAM[16384] to RAM[24575] are the 512 × 256 screen, one bit per pixel, so writing a word there turns 16 pixels on or off. RAM[24576] holds the code of the key currently pressed. Reading and writing devices with ordinary loads and stores is called memory-mapped I/O, and real computers use it extensively, as chapter 19 explains.

Reading a function

The example's RISC-V program has a main that calls a function sum(array, n). Reading it needs three pieces of vocabulary. The first is the calling convention, the agreement about registers that lets separately compiled functions call each other. In RISC-V, arguments arrive in a0 to a7 and the result returns in a0. The return address is in ra. The t registers are temporaries a function may overwrite, and the s registers must be preserved. The second is the shape of a loop: a test at the top that branches forward out of the loop, a body, and a jump backwards to the test. The third is address arithmetic. Element i of an array of 4-byte words lives at base + 4i, which the code computes with a shift, slli t2, t1, 2, because shifting left by 2 multiplies by 4.

Calls are two instructions. jal ra, sum jumps to sum and stores the address of the next instruction in ra, and jalr zero, 0(ra) jumps back to it. The example's final register dump shows ra = 12, the byte address of the instruction after the call, since main's instructions sit at addresses 0, 4 and 8.

Patterns to recognise

Compiled code is built from a small set of shapes. Once you know them, a listing reads like a structured program:

• if/else: a compare and a branch forward over the "then" block, and a jump over the "else";
• loops: a backward branch, often with the test moved to the bottom so each iteration takes one branch;
• function prologue and epilogue: lowering sp to make room on the stack, saving ra and any s registers, and restoring them before returning (chapter 18);
• switch: a bounds check and an indirect jump through a table of addresses;
• optimisations: multiplications turned into shifts and adds, loop bodies duplicated (unrolling), and several elements processed per instruction (vectorisation, chapter 15).

Optimisation level changes everything. At -O0 a compiler keeps every variable in memory and reloads it at each use, which is easy to follow and slow. At -O2 variables live in registers, code is reordered and duplicated, and parts of the program disappear because the compiler proved them unnecessary. Read optimised code to learn about performance. Compiler Explorer, at godbolt.org, shows the assembly for any snippet in dozens of languages and compilers side by side, and objdump -d disassembles any binary on your own machine.

Stack machines

A register machine names its operands: add t0, t0, t3 says exactly which registers to use. A stack machine names none. Its instructions take operands from the top of a stack and push results back. To compute (a + b) × c it pushes a and b, adds, which pops two values and pushes their sum, then pushes c and multiplies.

Stack code is compact and easy to generate: a compiler emits it by walking the expression tree in post-order, operands before operators. That's why most virtual machines use it, including the Java Virtual Machine, CPython's bytecode interpreter, WebAssembly, and the Nand2Tetris VM, whose 20-odd commands, push, pop, add, sub, neg, eq, gt, lt, and, or, not, label, goto, if-goto, function, call and return, are what the course's Jack compiler produces. A VM translator, Nand2Tetris projects 7 and 8, turns each VM command into a handful of Hack instructions, and a JIT compiler does the same for the JVM at run time, mapping the top of the stack onto real registers.

Three machines, one loop

The example runs the RISC-V function in a small interpreter, prints the bytecode that CPython compiles the same loop into, and runs a sum of 1 to 100 on a stack VM in the style of Nand2Tetris.

import dis, sys

# 1. A small RISC-V interpreter, enough to run a function that sums an array
ABI = ["zero", "ra", "sp", "gp", "tp", "t0", "t1", "t2", "s0", "s1"] + [f"a{i}" for i in range(8)] \
      + [f"s{i}" for i in range(2, 12)] + ["t3", "t4", "t5", "t6"]
REG = {name: i for i, name in enumerate(ABI)}
PROGRAM = """
main:   addi a0, zero, 256      # a0 = address of the array
        addi a1, zero, 5        # a1 = number of elements
        jal  ra, sum            # call sum(a0, a1); the return address goes in ra
        ebreak                  # stop
sum:    addi t0, zero, 0        # total = 0
        addi t1, zero, 0        # i = 0
loop:   bge  t1, a1, done       # if i >= n, leave the loop
        slli t2, t1, 2          # t2 = i * 4, the byte offset of element i
        add  t2, a0, t2         # t2 = address of element i
        lw   t3, 0(t2)          # t3 = memory[t2]
        add  t0, t0, t3         # total += element
        addi t1, t1, 1          # i += 1
        jal  zero, loop         # jump back (the result address is discarded into zero)
done:   addi a0, t0, 0          # return value in a0
        jalr zero, 0(ra)        # return to the caller
"""
def parse(src):
    instrs, labels = [], {}
    for line in src.splitlines():
        line = line.split("#")[0].strip()
        if not line: continue
        if ":" in line:
            label, line = line.split(":", 1); labels[label.strip()] = len(instrs) * 4; line = line.strip()
        op, *args = line.replace(",", " ").replace("(", " ").replace(")", " ").split()
        instrs.append((op, args))
    return instrs, labels
def execute(instrs, labels, memory):
    x = [0] * 32; pc = 0; count = 0
    def val(a): return int(a) if a.lstrip("-").isdigit() else labels[a]
    while True:
        op, a = instrs[pc // 4]; count += 1; nxt = pc + 4
        if op == "addi": x[REG[a[0]]] = x[REG[a[1]]] + int(a[2])
        elif op == "add": x[REG[a[0]]] = x[REG[a[1]]] + x[REG[a[2]]]
        elif op == "slli": x[REG[a[0]]] = x[REG[a[1]]] << int(a[2])
        elif op == "lw": x[REG[a[0]]] = memory[x[REG[a[2]]] + int(a[1])]
        elif op == "bge": nxt = val(a[2]) if x[REG[a[0]]] >= x[REG[a[1]]] else nxt
        elif op == "jal": x[REG[a[0]]] = pc + 4; nxt = val(a[1])
        elif op == "jalr": x[REG[a[0]]] = pc + 4; nxt = x[REG[a[2]]] + int(a[1])
        elif op == "ebreak": return x, count
        x[0] = 0                                               # register zero is hard-wired to 0
        pc = nxt
instrs, labels = parse(PROGRAM)
memory = {256 + 4 * i: v for i, v in enumerate([3, 1, 4, 1, 5])}
regs, count = execute(instrs, labels, memory)
print(f"RISC-V: sum of [3, 1, 4, 1, 5] = {regs[REG['a0']]} after {count} instructions "
      f"(labels: {labels}); ra = {regs[REG['ra']]}, the address after the call")

# 2. The same function in Python compiles to bytecode for a stack machine
def total(values):
    t = 0
    for v in values:
        t += v
    return t
ops = [ins.opname for ins in dis.get_instructions(total)]
print(f"\nPython {sys.version_info.major}.{sys.version_info.minor} bytecode for the same loop ({len(ops)} instructions):")
print("   " + " ".join(ops))

# 3. A stack virtual machine in the style of Nand2Tetris: no registers, just push, pop and operate
VM = """
push constant 0
pop local 0          // sum = 0
push constant 1
pop local 1          // i = 1
label LOOP
push local 1
push constant 100
gt
if-goto END          // if i > 100, stop
push local 0
push local 1
add
pop local 0          // sum = sum + i
push local 1
push constant 1
add
pop local 1          // i = i + 1
goto LOOP
label END
push local 0
"""
def run_vm(src):
    prog = [l.split("//")[0].split() for l in src.strip().splitlines()]
    labels = {p[1]: i for i, p in enumerate(prog) if p[0] == "label"}
    stack, local, pc, steps = [], [0] * 8, 0, 0
    while pc < len(prog):
        p = prog[pc]; pc += 1; steps += 1
        if p[0] == "push": stack.append(int(p[2]) if p[1] == "constant" else local[int(p[2])])
        elif p[0] == "pop": local[int(p[2])] = stack.pop()
        elif p[0] in ("add", "gt"):
            b, a = stack.pop(), stack.pop(); stack.append(a + b if p[0] == "add" else -1 if a > b else 0)
        elif p[0] == "if-goto":
            if stack.pop(): pc = labels[p[1]]
        elif p[0] == "goto": pc = labels[p[1]]
    return stack[-1], steps
result, steps = run_vm(VM)
print(f"\nstack VM: sum 1..100 = {result} after {steps:,} VM commands")

RISC-V: sum of [3, 1, 4, 1, 5] = 14 after 44 instructions (labels: {'main': 0, 'sum': 16, 'loop': 24, 'done': 52}); ra = 12, the address after the call

Python 3.14 bytecode for the same loop (15 instructions):
   RESUME LOAD_SMALL_INT STORE_FAST LOAD_FAST_BORROW GET_ITER FOR_ITER STORE_FAST LOAD_FAST_BORROW_LOAD_FAST_BORROW BINARY_OP STORE_FAST JUMP_BACKWARD END_FOR POP_ITER LOAD_FAST_BORROW RETURN_VALUE

stack VM: sum 1..100 = 5050 after 1,411 VM commands

The CPython bytecode is a stack program. LOAD_FAST pushes a local variable, BINARY_OP pops two values and pushes the result, and STORE_FAST pops into a local. FOR_ITER and JUMP_BACKWARD are the loop's top and bottom. The exact instruction names change between Python versions, and this listing is from version 3.14. The stack VM takes 1,411 commands for the sum, where the hand-written Hack program of chapter 7 took 1,416 instructions. Translated into Hack, each VM command becomes several Hack instructions, so the VM version would run several times slower. That's the cost of a convenient abstraction, and recovering it is what optimising compilers and JITs are for.

Why a hierarchy

Processor speed grew far faster than memory speed for decades. A modern core can execute several instructions per nanosecond, but a read from main memory, which is DRAM (chapter 5), takes around 100 nanoseconds. That's hundreds of instructions' worth of waiting, a gap often called the memory wall. Caches bridge it by keeping copies of recently used data in small, fast static RAM next to the core. A typical modern processor has a level-1 cache of 32 to 128 KiB per core, a level-2 cache of a few MiB, a level-3 cache of tens of MiB shared between cores, and then many gigabytes of DRAM.

Below memory comes storage. An NVMe solid-state drive answers a random read in tens of microseconds, and a spinning disk needs milliseconds to move its head. Networks add their own scale: a round trip inside a data centre takes about half a millisecond, and one across a continent tens of milliseconds. Jeff Dean's list of "latency numbers every programmer should know" made these numbers famous, and their ratios matter more than their exact values, which keep changing.

Locality

The hierarchy works because real programs have locality. Temporal locality means that data used recently is likely to be used again soon, like a loop counter or the top of the stack. Spatial locality means that data near recently used data is likely to be used soon, like the next element of an array. Caches exploit both. They keep recently used data, and they move memory in fixed-size blocks called cache lines, 64 bytes on most x86 and ARM processors and 128 bytes on Apple's M-series chips, so one miss brings in the neighbours too. Hardware prefetchers watch the stream of misses, recognise sequential and strided patterns, and fetch lines before they're asked for. A program that walks memory in order gets almost every access from cache. A program that jumps around a large data set at random defeats all of it.

Measured on real hardware

The example performs the same work, 4 million reads of 8-byte integers, from arrays of growing size, once in sequential order and once in random order. The work per access is identical. Only where the data sits in the hierarchy changes. Unlike most examples in this volume it measures time, so its output depends on the machine: the run shown was recorded on an Apple M1 Pro laptop, and your numbers will differ.

import random, time
from array import array

# Read 4 million elements from arrays of growing size, in order and in random order.
# The work per access is identical; only where the data sits in the memory hierarchy changes.
ACCESSES = 1 << 22
random.seed(9)
def measure(n_elems, order):
    data = array("q", bytes(8 * n_elems))                  # n 8-byte integers, all zero
    if order == "sequential":
        idx = [i % n_elems for i in range(ACCESSES)]
    else:
        idx = random.choices(range(n_elems), k=ACCESSES)
    best = float("inf")
    for _ in range(3):                                     # keep the fastest of three runs
        t0 = time.perf_counter()
        s = 0
        for i in idx: s += data[i]
        best = min(best, time.perf_counter() - t0)
    return best / ACCESSES * 1e9                           # nanoseconds per access

print(f"{'array size':>12} {'sequential':>12} {'random':>10}   random / sequential")
for size_kib in (16, 256, 4096, 65536, 262144):
    n = size_kib * 1024 // 8
    seq, rnd = measure(n, "sequential"), measure(n, "random")
    label = f"{size_kib // 1024} MiB" if size_kib >= 1024 else f"{size_kib} KiB"
    print(f"{label:>12} {seq:9.1f} ns {rnd:7.1f} ns   {rnd / seq:5.2f}x")

  array size   sequential     random   random / sequential
      16 KiB      19.0 ns    19.8 ns    1.04x
     256 KiB      18.9 ns    19.3 ns    1.02x
       4 MiB      19.3 ns    25.1 ns    1.30x
      64 MiB      19.0 ns    71.4 ns    3.76x
     256 MiB      18.9 ns    80.6 ns    4.26x

Python's interpreter adds about 19 ns to every access, which hides the difference between L1 and L2 entirely: at 16 KiB and 256 KiB both orders cost the same. At 4 MiB, random access starts to cost more, as the data spills out of the closest caches. At 64 MiB and 256 MiB the array no longer fits in any cache, and random access costs about 4 times as much as sequential, adding roughly 50 to 60 ns to each read, most of a trip to DRAM. Sequential access stays at 19 ns even for 256 MiB, because each 128-byte line serves 16 consecutive reads and the prefetcher fetches the next lines ahead of time. In a compiled language, without the interpreter's overhead, the same experiment shows a ratio of tens rather than 4.

Latency and bandwidth

Latency is how long one access takes. Bandwidth is how much data per second the memory system can deliver when many accesses are in flight. They're different limits. A laptop's DRAM delivers tens to hundreds of gigabytes per second, yet any single read still takes around 100 ns. Little's law connects them: the number of requests in flight equals throughput times latency. To use the bandwidth, the processor must keep many misses outstanding at once, which out-of-order cores do (chapter 14), and which a linked-list traversal prevents, because the address of the next node isn't known until the current load finishes. Workloads are accordingly latency-bound, waiting on one access after another, or bandwidth-bound, streaming more data than the memory can deliver. The cures differ, and chapter 20's roofline model tells them apart.

One more cache stands between a program and its data. Programs use virtual addresses, which the hardware translates to physical addresses through page tables kept by the operating system, and a small cache of recent translations, the TLB, makes that fast. Random access across hundreds of megabytes misses in the TLB as well as in the data caches, part of what the example's last rows measure. Stage 05 covers virtual memory in full.

Lines, sets and ways

A cache is divided into lines of, say, 64 bytes, and memory is moved in and out whole lines at a time. To find whether an address is cached, the hardware splits it into three fields. The lowest bits are the offset within the line, 6 bits for 64-byte lines. The next bits, the index, choose a set. The remaining high bits, the tag, identify which of the many memory lines that map to that set is actually there. A set holds several lines, its ways, and the hardware compares the tag against all of them at once.

Associativity is a trade-off. A direct-mapped cache, with one way per set, is fast and simple but suffers when two frequently used addresses map to the same set. A fully associative cache, where any line can go anywhere, avoids that, but comparing every tag at once is too expensive for anything but small structures such as TLBs. Level-1 caches are typically 8- to 12-way, and level-3 caches 12- to 16-way.

The three Cs

Mark Hill's classic classification sorts misses by cause, which tells you how to fix them:

• Compulsory, or cold, misses: the first access to a line can only miss. Prefetching hides them, and larger lines reduce their number.
• Capacity misses: the program's working set is bigger than the cache, so lines are evicted before they're reused. The fix is to use less data at a time, which is what chapter 11's blocking does.
• Conflict misses: the working set would fit, but too many of its lines map to the same set. The fix is to change the addresses, by padding data or changing strides, or to add associativity.

The simulator classifies each miss by also running a fully associative cache of the same size alongside. A miss that the fully associative cache would also have taken, on a line seen before, is capacity. A miss it would have avoided is conflict.

Replacement and the LRU cliff

When a set is full, a new line evicts one of the old ones. Least recently used (LRU) replacement evicts the line untouched for longest, a good bet under temporal locality. It has one pathological case: a loop over data slightly bigger than the cache. Each line is evicted just before the loop comes back for it, so the miss rate jumps from almost nothing to 100% as the array grows past the cache size. In the example, scanning a 32 KiB array repeatedly through a 32 KiB cache misses only on the first pass, 5%, while a 36 KiB array misses on every access. Real caches approximate LRU cheaply with pseudo-LRU bits, and recent designs use adaptive policies that resist such scans.

Writes

A write-back cache updates only its own copy and marks the line dirty, writing it to the next level when it's evicted. A write-through cache sends every write onward immediately. Almost all modern CPU caches are write-back and write-allocate, fetching a line on a write miss so it can be modified in place. With several cores, each with its own caches, a coherence protocol such as MESI keeps the copies consistent. A core that writes a line must first invalidate everyone else's copy. That's invisible to correct programs, but it costs time when two cores keep writing the same line, which is false sharing (chapter 11).

Simulated

The example's cache is set-associative with LRU replacement, 64-byte lines and configurable size and ways. It runs four experiments: a sequential scan, three ways of walking a 512 × 512 matrix, eight addresses that collide in one set, and repeated scans of arrays around the cache size.

from collections import OrderedDict

class Cache:
    """A set-associative cache with LRU replacement. It counts misses and sorts them into the 3 Cs."""
    def __init__(self, size, line=64, ways=8):
        self.line, self.ways, self.sets = line, ways, size // (line * ways)
        self.data = [OrderedDict() for _ in range(self.sets)]
        self.full = OrderedDict(); self.capacity = size // line      # a fully associative twin, same size
        self.seen = set()
        self.hits = self.compulsory = self.capacity_misses = self.conflict = 0
    def access(self, addr):
        block = addr // self.line
        s, tag = self.data[block % self.sets], block // self.sets
        in_full = block in self.full                           # would a perfect-placement cache have hit?
        if in_full: self.full.move_to_end(block)
        else:
            self.full[block] = True
            if len(self.full) > self.capacity: self.full.popitem(last=False)
        if tag in s: s.move_to_end(tag); self.hits += 1; return
        if block not in self.seen: self.compulsory += 1        # first touch ever
        elif not in_full: self.capacity_misses += 1            # even full associativity would miss
        else: self.conflict += 1                               # only placement caused it
        self.seen.add(block)
        s[tag] = True
        if len(s) > self.ways: s.popitem(last=False)           # evict the least recently used line
    def report(self, name):
        n = self.hits + self.compulsory + self.capacity_misses + self.conflict
        m = n - self.hits
        print(f"{name:44} {n:>9,} accesses  miss rate {m / n:6.1%}  "
              f"(compulsory {self.compulsory:,}, capacity {self.capacity_misses:,}, conflict {self.conflict:,})")

KB = 1024
# 1. A sequential scan: one miss per 64-byte line, 16 four-byte integers per line
c = Cache(32 * KB)
for i in range(64 * KB): c.access(4 * i)
c.report("scan 256 KiB of int32 once")

# 2. Row-major versus column-major traversal of a 512 x 512 int32 matrix (1 MiB)
N = 512
for order, pitch in (("row by row", 512), ("column by column", 512), ("column by column, rows padded", 528)):
    c = Cache(32 * KB)
    for a in range(N):
        for b in range(N):
            i, j = (a, b) if order == "row by row" else (b, a)
            c.access(4 * (i * pitch + j))                      # pitch: ints from one row's start to the next
    c.report(f"512x512 matrix, {order}")

# 3. Conflict misses: 8 addresses exactly 32 KiB apart, touched over and over
for ways in (1, 8):
    c = Cache(32 * KB, ways=ways)
    for _ in range(1000):
        for k in range(8): c.access(k * 32 * KB)
    c.report(f"8 addresses 32 KiB apart, {'direct-mapped' if ways == 1 else '8-way'}")

# 4. Working-set size: scan an array repeatedly; LRU falls off a cliff past the cache size
for size in (16, 32, 36, 64):
    c = Cache(32 * KB)
    for _ in range(20):
        for i in range(0, size * KB, 64): c.access(i)
    c.report(f"scan a {size} KiB array 20 times")

scan 256 KiB of int32 once                      65,536 accesses  miss rate   6.2%  (compulsory 4,096, capacity 0, conflict 0)
512x512 matrix, row by row                     262,144 accesses  miss rate   6.2%  (compulsory 16,384, capacity 0, conflict 0)
512x512 matrix, column by column               262,144 accesses  miss rate 100.0%  (compulsory 16,384, capacity 0, conflict 245,760)
512x512 matrix, column by column, rows padded   262,144 accesses  miss rate   6.2%  (compulsory 16,384, capacity 0, conflict 0)
8 addresses 32 KiB apart, direct-mapped          8,000 accesses  miss rate 100.0%  (compulsory 8, capacity 0, conflict 7,992)
8 addresses 32 KiB apart, 8-way                  8,000 accesses  miss rate   0.1%  (compulsory 8, capacity 0, conflict 0)
scan a 16 KiB array 20 times                     5,120 accesses  miss rate   5.0%  (compulsory 256, capacity 0, conflict 0)
scan a 32 KiB array 20 times                    10,240 accesses  miss rate   5.0%  (compulsory 512, capacity 0, conflict 0)
scan a 36 KiB array 20 times                    11,520 accesses  miss rate 100.0%  (compulsory 576, capacity 10,944, conflict 0)
scan a 64 KiB array 20 times                    20,480 accesses  miss rate 100.0%  (compulsory 1,024, capacity 19,456, conflict 0)

The sequential scan misses once per 64-byte line, 1 access in 16, and all of those misses are compulsory. Walking the matrix row by row does the same. Walking it column by column misses on every access, and the simulator calls these misses conflict, not capacity. The 512 lines a column walk touches would fit in the cache's 512 lines. But each row is 512 × 4 = 2,048 bytes, exactly 32 lines, so consecutive elements of a column are 32 lines apart, and with 64 sets they fall into only 2 of them. Sixteen slots for 512 lines means constant eviction. Padding each row to 528 integers makes the stride 33 lines, and since 33 shares no factor with 64, the column now spreads over all 64 sets and the miss rate drops back to 6.2%. The 8-way cache shrugs off eight addresses 32 KiB apart that a direct-mapped cache thrashes on, which is the case for associativity in one line.

Walk memory in the order it's stored

C, C++, Rust, Go, NumPy's default and Python's lists of lists store two-dimensional arrays row-major: each row is contiguous, and moving along a row moves through memory one element at a time. Fortran, MATLAB, Julia and R store them column-major. A loop whose innermost index moves along the contiguous direction uses every byte of every cache line it fetches. A loop whose innermost index moves the other way strides through memory and may use 8 bytes of each 64-byte line. Fixing it is often a matter of swapping two loops, loop interchange, which compilers do automatically only when they can prove it's safe.

Matrix multiplication shows the effect. The textbook loop order, i-j-k, computes each $C_{ij}$ as a dot product of row i of A with column j of B, so its innermost loop walks down a column of B. The order i-k-j instead adds $A_{ik}$ times row k of B into row i of C, so its innermost loop walks along rows of both. Same arithmetic, same result, different access pattern.

Blocking

Even with the right loop order, a large matrix multiplication streams all of B through the cache once for every row of A, because B is too big to stay cached. Blocking, also called tiling, restructures the loops to work on small square tiles. Take a tile of A, a tile of B and a tile of C that fit in cache together, do all the work those three tiles allow, and only then move on.

Inside a tile, every loaded line is reused many times before it's evicted. That's the principle behind every fast linear algebra library. BLAS implementations such as OpenBLAS and Intel's MKL block at several levels at once, for registers, L1, L2 and L3, and add SIMD instructions (chapter 15), which is how they reach close to the processor's peak while a naive triple loop reaches a few percent of it.

Data layout: arrays of structures and structures of arrays

A particle system might store each particle as a record with position, velocity, mass and charge, and keep an array of these records, an array of structures (AoS). A loop that updates every field of one particle at a time likes that layout. A loop that sums just one field over all particles fetches a 64-byte line for each 8-byte value it needs, wasting seven-eighths of the bandwidth. Storing each field in its own array, a structure of arrays (SoA), packs the values the loop needs together. In the example the scan drops from 100,000 misses to 12,500. Game engines built on entity-component systems, and the columnar databases described in The Engineer's Ledger, use the same idea at larger scale.

Pointer chasing

A linked list, a tree of small nodes, or a hash table whose buckets point to chains scatters its data wherever the allocator put it. Every step follows a pointer, the address of the next access isn't known until the current one completes, and the prefetcher can't help. In the example, traversing 100,000 values through a list whose nodes sit at random addresses misses 99,651 times, against 12,500 for an array of the same values. Under a simple model of 1 ns per hit and 100 ns per miss, that's about 100 ns per element against 13. Prefer contiguous containers: arrays and vectors, B-trees with wide nodes, hash tables with open addressing (The Engineer's Workbench, chapter 2), and nodes allocated together from an arena.

False sharing

Caches keep copies coherent a line at a time (chapter 10). If two threads on different cores write to different variables that happen to share a cache line, each write invalidates the other core's copy, and the line bounces between cores, every write costing a coherence round trip. That's false sharing: no data is shared, only the line. Per-thread counters stored next to each other in an array are the classic case. The fix is to pad or align each thread's data to its own line, 64 bytes on most machines and 128 on Apple's, using alignas(64) in C++ or Java's @Contended.

Simulated

The example uses chapter 10's cache to compare three versions of a 96 × 96 matrix multiplication, two layouts for a particle array, and a scattered linked list against an array. A small 8 KiB cache keeps the matrix simulation quick, standing in for a real 32 to 64 KiB level-1 cache facing proportionally larger matrices. It turns miss counts into an average access time with the simple model above.

import random
from collections import OrderedDict

class Cache:                                                   # chapter 10's cache, without the 3C bookkeeping
    def __init__(self, size, line=64, ways=8):
        self.line, self.ways, self.sets = line, ways, size // (line * ways)
        self.data = [OrderedDict() for _ in range(self.sets)]; self.hits = self.misses = 0
    def access(self, addr):
        block = addr // self.line; s, tag = self.data[block % self.sets], block // self.sets
        if tag in s: s.move_to_end(tag); self.hits += 1
        else:
            self.misses += 1; s[tag] = True
            if len(s) > self.ways: s.popitem(last=False)
def amat_ns(c, hit_ns=1, miss_ns=100):                         # average memory access time model
    return (c.hits * hit_ns + c.misses * miss_ns) / (c.hits + c.misses)
KB = 1024

# 1. Matrix multiplication C = A B, n x n doubles: three loop orders and a blocked version
n, BS = 96, 16
A, B, C = 0, 8 * n * n, 16 * n * n                             # base addresses of the three matrices
def run(order):
    c = Cache(8 * KB)                                          # a small cache keeps the simulation quick
    if order == "blocked":
        for ii in range(0, n, BS):
            for kk in range(0, n, BS):
                for jj in range(0, n, BS):
                    for i in range(ii, ii + BS):
                        for k in range(kk, kk + BS):
                            c.access(A + 8 * (i * n + k))
                            for j in range(jj, jj + BS):
                                c.access(B + 8 * (k * n + j)); c.access(C + 8 * (i * n + j))
        return c
    for x in range(n):
        for y in range(n):
            if order == "i-j-k":
                i, j = x, y; c.access(C + 8 * (i * n + j))
                for k in range(n): c.access(A + 8 * (i * n + k)); c.access(B + 8 * (k * n + j))
            else:                                              # i-k-j: the inner loop walks rows of B and C
                i, k = x, y; c.access(A + 8 * (i * n + k))
                for j in range(n): c.access(B + 8 * (k * n + j)); c.access(C + 8 * (i * n + j))
    return c
print(f"multiplying two {n}x{n} matrices of doubles ({3 * 8 * n * n // KB} KiB in all) through an 8 KiB cache:")
base = None
for order in ("i-j-k", "i-k-j", "blocked"):
    c = run(order); t = amat_ns(c)
    base = base or t
    print(f"   {order:8} {c.misses:>9,} misses of {c.hits + c.misses:,}   average access {t:5.2f} ns   speed-up {base / t:4.1f}x")

# 2. Array of structures versus structure of arrays: summing one field of 100,000 particles
count, fields = 100_000, 8                                     # each particle: 8 fields of 8 bytes
aos, soa = Cache(32 * KB), Cache(32 * KB)
for p in range(count):
    aos.access(64 * p + 0)                                     # AoS: particle p's x field, 64 bytes apart
    soa.access(8 * p)                                          # SoA: all x fields packed together
print(f"\nsum one field of {count:,} particles: array of structs {aos.misses:,} misses, struct of arrays {soa.misses:,}")

# 3. A linked list scattered through memory versus the same values in an array
random.seed(11)
nodes = 100_000
slots = random.sample(range(nodes * 4), nodes)                 # each node lands at a random 16-byte slot
ll, arr = Cache(32 * KB), Cache(32 * KB)
for k in range(nodes):
    ll.access(16 * slots[k])                                   # follow the list: wherever the next node is
    arr.access(8 * k)                                          # walk the array: the next 8 bytes
print(f"traverse {nodes:,} values: scattered linked list {ll.misses:,} misses, array {arr.misses:,}")
print(f"   with a 1 ns hit and a 100 ns miss: list {amat_ns(ll):.1f} ns per element, array {amat_ns(arr):.1f} ns")

multiplying two 96x96 matrices of doubles (216 KiB in all) through an 8 KiB cache:
   i-j-k      923,520 misses of 1,778,688   average access 52.40 ns   speed-up  1.0x
   i-k-j      112,896 misses of 1,778,688   average access  7.28 ns   speed-up  7.2x
   blocked     20,022 misses of 1,824,768   average access  2.09 ns   speed-up 25.1x

sum one field of 100,000 particles: array of structs 100,000 misses, struct of arrays 12,500
traverse 100,000 values: scattered linked list 99,651 misses, array 12,500
   with a 1 ns hit and a 100 ns miss: list 99.7 ns per element, array 13.4 ns

Interchanging the loops cuts the misses from 923,520 to 112,896, and blocking cuts them to 20,022, 46 times fewer than the textbook order, with exactly the same arithmetic. The model's speed-ups, 7.2 and 25 times, overstate what real hardware shows, because real processors overlap several misses at once and prefetch the regular streams, which helps the unblocked versions most. Measured speed-ups for blocking large matrix multiplications in compiled code are still typically several-fold, which is the size of the stage's goal. The method generalises. Measure where the misses are, find the loop whose accesses stride or scatter, and change the order or the layout until each fetched line is used fully, and used again before it's evicted.

Five stages

The classic RISC pipeline has five stages, each with a register between it and the next:

• IF, instruction fetch, reads the instruction at PC;
• ID, instruction decode, decodes it and reads its source registers;
• EX, execute, runs the ALU, or computes an address for a load or store;
• MEM accesses data memory, for loads and stores;
• WB, write back, writes the result into the destination register.

Each stage does about a fifth of the work, so the clock can run roughly five times faster than a single-cycle design (chapter 5's exercise 5.3). Every instruction still takes five cycles from start to finish, its latency, but a new one can start every cycle, its throughput. The figure shows a loop's instructions overlapping in a staircase.

Data hazards: forwarding and stalls

A data hazard occurs when an instruction needs a result that an earlier instruction hasn't written back yet. add x6, x6, x5 needs x5 from the load just before it, but the load only writes x5 in its WB stage. The simplest fix is to stall: hold the dependent instruction in decode, inserting bubbles, until the value is in the register file. Without anything better, the example's loop runs at 2.2 cycles per instruction, CPI 2.20, instead of 1.

The better fix is forwarding, or bypassing. The value exists as soon as the ALU computes it, at the end of EX, so wires carry it straight from the pipeline register back to the ALU's input for the next instruction, without waiting for write back. With forwarding, ALU-to-ALU dependences cost nothing. Loads are the exception: a loaded value arrives only at the end of MEM, too late for an instruction in EX the very next cycle, so a load-use dependence still costs one bubble, the one in the figure. The fix for that is software. Move an independent instruction between the load and its use, as the example's reordered loop does, and the bubble disappears. Compilers schedule instructions this way automatically.

Control hazards

A branch decides which instruction comes next, but the pipeline must fetch the next instruction before the branch has been decided, which in this pipeline happens in EX, two stages after fetch. If the processor simply waits, or always fetches the next instruction in memory, every taken branch wastes two cycles. In the example's loop, where 1 instruction in 5 is a taken branch, that costs 0.4 cycles per instruction. The fix is to predict the branch and fetch from the predicted target immediately, discarding the wrong-path instructions if the guess was wrong. Chapter 13 shows how predictors get it right well over 90% of the time.

A third kind, structural hazards, happens when two instructions need the same hardware in the same cycle, for example a single memory port for both fetching instructions and loading data. Separate instruction and data caches and duplicated functional units remove most of them.

Simulated

The example schedules the loop on a five-stage pipeline under four assumptions, prints the pipeline diagram for two of them, and counts cycles over 1,000 iterations.

# A classic 5-stage pipeline: IF (fetch), ID (decode, read registers), EX (ALU), MEM (memory), WB (write back).
# Each instruction: (text, destination register, source registers, kind)
LOOP = [("lw   x5, 0(x10)",   "x5",  ["x10"],       "load"),
        ("add  x6, x6, x5",   "x6",  ["x6", "x5"],  "alu"),
        ("addi x10, x10, 4",  "x10", ["x10"],       "alu"),
        ("addi x11, x11, -1", "x11", ["x11"],       "alu"),
        ("bne  x11, x0, loop", None, ["x11", "x0"], "branch")]
REORDERED = [LOOP[0], LOOP[2], LOOP[3], LOOP[1], LOOP[4]]       # the add moved away from the load it needs

def schedule(program, iterations, forwarding, predict_taken):
    """Return the cycle of each instruction's EX stage, in order of execution."""
    last_writer, ex_cycles, prev_ex = {}, [], 2                 # the first instruction is in EX in cycle 3
    for it in range(iterations):
        for i, (text, dst, srcs, kind) in enumerate(program):
            ex = prev_ex + 1                                   # one instruction enters EX per cycle at best
            for s in srcs:
                if s in last_writer:
                    p_ex, p_kind = last_writer[s]
                    if not forwarding: ex = max(ex, p_ex + 3)  # wait for the producer's write-back
                    elif p_kind == "load": ex = max(ex, p_ex + 2)   # loaded value arrives after MEM
                    else: ex = max(ex, p_ex + 1)               # ALU result forwarded straight to EX
            ex_cycles.append((it, i, ex))
            if dst: last_writer[dst] = (ex, kind)
            prev_ex = ex
            if kind == "branch" and not predict_taken and it < iterations - 1:
                prev_ex = ex + 2                               # taken branch resolved in EX: two fetches wasted
    return ex_cycles

def diagram(program, forwarding, predict_taken):
    sched = schedule(program, 2, forwarding, predict_taken)[:len(program) + 1]
    width = sched[-1][2] + 3
    print(f"   {'':20}" + "".join(f"{c:>4}" for c in range(1, width + 1)))
    for it, i, ex in sched:
        row = [" " * 4] * width
        for stage, offset in (("IF", -2), ("ID", -1), ("EX", 0), ("MEM", 1), ("WB", 2)):
            row[ex + offset - 1] = f"{stage:>4}"
        print(f"   {program[i][0]:20}" + "".join(row))

def cycles(program, n, forwarding, predict_taken):
    return schedule(program, n, forwarding, predict_taken)[-1][2] + 2   # the last instruction's WB

print("one iteration plus the next fetch, no forwarding, branches not predicted:")
diagram(LOOP, False, False)
print("\nwith forwarding and a correct branch prediction:")
diagram(LOOP, True, True)
n = 1000
print(f"\n{n:,} iterations, {5 * n:,} instructions:")
for name, prog, fwd, pred in (("no forwarding, no prediction", LOOP, False, False),
                              ("forwarding, no prediction", LOOP, True, False),
                              ("forwarding, branch predicted", LOOP, True, True),
                              ("forwarding, predicted, reordered", REORDERED, True, True)):
    c = cycles(prog, n, fwd, pred)
    print(f"   {name:34} {c:6,} cycles   CPI {c / (5 * n):.2f}")

one iteration plus the next fetch, no forwarding, branches not predicted:
                          1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17
   lw   x5, 0(x10)       IF  ID  EX MEM  WB                                                
   add  x6, x6, x5                   IF  ID  EX MEM  WB                                    
   addi x10, x10, 4                      IF  ID  EX MEM  WB                                
   addi x11, x11, -1                         IF  ID  EX MEM  WB                            
   bne  x11, x0, loop                                    IF  ID  EX MEM  WB                
   lw   x5, 0(x10)                                                   IF  ID  EX MEM  WB    

with forwarding and a correct branch prediction:
                          1   2   3   4   5   6   7   8   9  10  11  12
   lw   x5, 0(x10)       IF  ID  EX MEM  WB                            
   add  x6, x6, x5               IF  ID  EX MEM  WB                    
   addi x10, x10, 4                  IF  ID  EX MEM  WB                
   addi x11, x11, -1                     IF  ID  EX MEM  WB            
   bne  x11, x0, loop                        IF  ID  EX MEM  WB        
   lw   x5, 0(x10)                               IF  ID  EX MEM  WB    

1,000 iterations, 5,000 instructions:
   no forwarding, no prediction       11,002 cycles   CPI 2.20
   forwarding, no prediction           8,002 cycles   CPI 1.60
   forwarding, branch predicted        6,004 cycles   CPI 1.20
   forwarding, predicted, reordered    5,004 cycles   CPI 1.00

Each improvement removes one source of lost cycles. Forwarding removes the waits for write back, from CPI 2.20 to 1.60. Predicting the branch removes the two wasted fetches per iteration, giving 1.20. Moving the add away from the load removes the last bubble, giving the ideal CPI of 1.00. In the diagrams, the gaps before a stalled instruction's EX stage are its bubbles. Real hardware holds the stalled instruction in its stage rather than fetching it late, but the cycles lost are the same.

Deeper pipelines

More, shorter stages allow a faster clock, and in the early 2000s Intel's Pentium 4 used around 20 to 31 stages to reach high clock rates. The costs grow with depth. Forwarding paths multiply, every register between stages adds overhead (exercise 5.3), and a mispredicted branch throws away more work, because more instructions are in flight when the mistake is discovered. Designs settled at around 14 to 20 stages, with performance coming instead from issuing several instructions per cycle, which is chapter 14's subject.

Why predict

Chapter 12's five-stage pipeline lost two cycles on every taken branch. A real core loses far more. It fetches several instructions per cycle into a pipeline 15 or more stages deep, so by the time a branch is resolved, dozens of later instructions have already been fetched. Stalling at every branch would waste most of that capacity. Predicting the branch and fetching from the guessed target keeps the pipeline full, and as long as the guesses are right the branches cost nearly nothing.

Predictors, from simple to clever

The simplest static rule predicts backward branches taken and forward branches not taken, which suits loops: the branch at the bottom of a loop jumps backwards and is usually taken. Dynamic predictors learn from history. A 1-bit predictor remembers each branch's last outcome and predicts the same again. A 2-bit saturating counter needs two mistakes in a row to change its mind, so the single not-taken exit at the end of a loop doesn't spoil the prediction for the next time the loop runs.

Counters indexed by the branch address alone can't learn patterns such as "taken, not taken, taken, not taken", or "the inner loop exits every tenth time". Global history predictors also look at the outcomes of the last several branches. Gshare, from Scott McFarling in 1993, indexes its counters by the branch address XORed with a register of recent outcomes, so the same branch gets different counters in different contexts. Modern predictors such as TAGE combine several history lengths and reach over 95% accuracy on typical programs. A branch target buffer separately predicts where a taken branch goes, and a small return address stack predicts the targets of function returns.

Measured

The example implements a 1-bit predictor, a 2-bit predictor and gshare with 10 bits of history, and runs each on four branches: a loop that iterates 10 times, entered 1,000 times; an if-test on random bytes; the same test on the same bytes sorted; and a branch that alternates. It then turns accuracy into cycles per instruction for a 4-wide core with a 15-cycle misprediction penalty.

import random

class TwoBit:
    """A table of 2-bit saturating counters: 0-1 predict not taken, 2-3 predict taken."""
    def __init__(self, bits=10): self.t = [1] * (1 << bits); self.mask = (1 << bits) - 1
    def predict(self, pc, hist): return self.t[pc & self.mask] >= 2
    def update(self, pc, hist, taken):
        i = pc & self.mask; self.t[i] = min(3, self.t[i] + 1) if taken else max(0, self.t[i] - 1)
class OneBit(TwoBit):
    def predict(self, pc, hist): return self.t[pc & self.mask] == 1
    def update(self, pc, hist, taken): self.t[pc & self.mask] = int(taken)
class Gshare(TwoBit):
    """2-bit counters indexed by the branch address XORed with the outcomes of recent branches."""
    def predict(self, pc, hist): return self.t[(pc ^ hist) & self.mask] >= 2
    def update(self, pc, hist, taken):
        i = (pc ^ hist) & self.mask; self.t[i] = min(3, self.t[i] + 1) if taken else max(0, self.t[i] - 1)

def accuracy(predictor, trace, hist_bits=10):
    p, hist, right = predictor(), 0, 0
    for pc, taken in trace:
        right += p.predict(pc, hist) == taken
        p.update(pc, hist, taken)
        hist = ((hist << 1) | taken) & ((1 << hist_bits) - 1)
    return right / len(trace)

def report(name, trace):
    print(f"{name:44} " + "  ".join(f"{cls.__name__} {accuracy(cls, trace):6.1%}" for cls in (OneBit, TwoBit, Gshare)))

random.seed(13)
# 1. A loop that runs 10 times, entered 1,000 times: taken nine times, then not taken
loop = [(0x40, i < 9) for _ in range(1000) for i in range(10)]
report("loop branch, 10 iterations per entry", loop)

# 2. if (x >= 128) over 100,000 random bytes, unsorted and sorted
data = [random.randrange(256) for _ in range(100_000)]
report("if x >= 128, random data", [(0x80, x >= 128) for x in data])
report("if x >= 128, the same data sorted", [(0x80, x >= 128) for x in sorted(data)])

# 3. A branch that alternates: taken, not taken, taken, ...
report("alternating branch", [(0xC0, i % 2 == 0) for i in range(10_000)])

# 4. What mispredictions cost: 1 branch per 5 instructions, a 4-wide core, a 15-cycle penalty
def cpi(miss_rate, base=0.25, branch_frac=0.2, penalty=15): return base + branch_frac * miss_rate * penalty
for label, trace in (("random", [(0x80, x >= 128) for x in data]), ("sorted", [(0x80, x >= 128) for x in sorted(data)])):
    miss = 1 - accuracy(TwoBit, trace)
    print(f"cycles per instruction with {label} data: {cpi(miss):.2f}")

# 5. The branch-free version: compute the condition as a number and add it
total_branchy = sum(x for x in data if x >= 128)
total_branchless = sum(x * (x >= 128) for x in data)              # the comparison becomes a 0 or 1 multiplier
print(f"sum of bytes >= 128: with a branch {total_branchy:,}, without {total_branchless:,}")

loop branch, 10 iterations per entry         OneBit  80.0%  TwoBit  90.0%  Gshare  99.8%
if x >= 128, random data                     OneBit  50.2%  TwoBit  50.2%  Gshare  49.8%
if x >= 128, the same data sorted            OneBit 100.0%  TwoBit 100.0%  Gshare 100.0%
alternating branch                           OneBit   0.0%  TwoBit   0.0%  Gshare  99.9%
cycles per instruction with random data: 1.75
cycles per instruction with sorted data: 0.25
sum of bytes >= 128: with a branch 9,570,757, without 9,570,757

Each result has a simple explanation. On the loop, the 1-bit predictor misses twice per entry, at the exit and again at the first iteration of the next entry, for 80%. The 2-bit counter misses only at the exit, for 90%. Gshare sees the history of the last ten outcomes and learns exactly where the exit comes, reaching 99.8%. On random data every predictor scores about 50%, because there's no pattern to learn. On the same data sorted, the branch is not taken for the first half and taken for the second, which every predictor gets almost entirely right. The alternating branch is the 2-bit counter's worst case, always one step behind, at 0%, while gshare's history makes it trivial.

What a misprediction costs

A wrong guess means flushing every instruction fetched after the branch and restarting from the right target, typically 15 to 20 cycles on a modern core. With 1 instruction in 5 a branch, a 50% miss rate costs 0.2 × 0.5 × 15 = 1.5 cycles per instruction, so the example's loop over random data runs at a CPI of 1.75 against 0.25 for sorted data, seven times slower for identical work. In 2012 this became one of Stack Overflow's most famous questions, "Why is processing a sorted array faster than processing an unsorted array?", with exactly this explanation.

The cure for an unpredictable branch is not to branch. Compute the condition as a number and use it arithmetically, as the example's x * (x >= 128) does. Alternatively, use a conditional move, an instruction that selects between two values without changing the flow of control, which compilers emit when they judge a branch unpredictable. Branch-free code always does the work of both sides, so it's slower when the branch would have been predictable. Measure before choosing.

Speculation, and Spectre

Running ahead on a prediction is speculative execution. Instructions on the predicted path execute fully, and their results are kept in the pipeline until the branch is confirmed, then either committed or discarded. Architecturally the discarded work leaves no trace, but microarchitecturally it can: a speculative load still brings its line into the cache. In 2018 Paul Kocher, Jann Horn and colleagues published Spectre. An attacker trains a bounds-check branch to predict "in bounds", then supplies an out-of-bounds index. The processor speculatively reads secret memory and uses it to touch one of 256 cache lines before discovering the mistake, and timing which line is now cached reveals the secret byte. Meltdown, announced at the same time, let unprivileged code read kernel memory through speculative loads past a permission check on many Intel processors.

The defences cost performance and live at every level: speculation barriers and index masking in sensitive code, hardware fixes in new processors, operating-system changes such as separating kernel and user page tables, and browsers isolating each site in its own process. The Engineer's Citadel covers side channels in more depth. The lesson for this chapter is that performance tricks invisible to a program's results can still be visible to an attacker who measures time.

Superscalar, out of order, in-order commit

A superscalar processor issues more than one instruction per cycle. Today's large cores decode 6 to 8 or more per cycle and have several integer ALUs, two or more load and store units, and several floating-point and vector units. An out-of-order core fetches and decodes instructions in program order and places them in a large window, often called the reorder buffer, holding several hundred instructions. Any instruction whose operands are ready goes to a free unit, regardless of where it sits in the program. Finished instructions then retire in program order, which keeps exceptions precise: if an instruction faults, everything before it has completed and nothing after it has changed the architectural state. That in-order retirement is also what makes speculation, chapter 13, safe to undo.

Dependences, true and false

A true dependence, or read-after-write, means an instruction needs a value another computes, and nothing can avoid waiting for it. False dependences come from reusing register names. A write-after-read means an instruction overwrites a register an earlier one still has to read; a write-after-write means two instructions write the same register and the later value must win. Compilers reuse registers constantly, because there are only 32 names, so false dependences are everywhere. Register renaming removes them. The core has a much larger physical register file, often a few hundred registers, and gives every new result a fresh physical register, mapping the architectural name to whichever physical register holds its latest value. In the example, 64 independent load–multiply–add steps that all reuse x5 and x6 take 449 cycles in order and 260 out of order without renaming, but only 71 with it.

Latency, throughput and how many chains

Summing an array with one running total is a single chain of dependent additions, each waiting for the last. With a floating-point add latency of 4 cycles, the core manages one add every 4 cycles however many adders it has. Split the sum into k independent totals that are combined at the end, and k chains run side by side.

How many chains are enough? To keep every adder busy, you need as many additions in flight as latency times throughput, here 4 cycles × 2 adders = 8. That's Little's law again, the same rule as chapter 9's outstanding cache misses. The example's sums of 1,024 floats run at 0.25, 0.5, 1 and then 1.9 adds per cycle for 1, 2, 4 and 8 accumulators, close to the 2-per-cycle limit. Sixteen accumulators are slightly slower, because combining them at the end takes a chain of 15 more adds. Combining them as a tree would fix that (exercise 14.2). Compilers make this transformation for integer sums, but not for floating point without permission such as -ffast-math, because floating-point addition isn't associative (chapter 2), and reordering a sum changes its last bits.

Simulated

The example's core starts each instruction as soon as its inputs are ready and a functional unit of the right kind is free, with 2 floating-point adders, 2 load units, 4 integer ALUs and 1 multiplier. Its window is unlimited, which makes it an upper bound on what real hardware finds.

# An idealised out-of-order core: an instruction starts once its inputs are ready and a unit is free.
LAT = {"fadd": 4, "load": 4, "add": 1, "mul": 3}
UNITS = {"fadd": 2, "load": 2, "add": 4, "mul": 1}               # how many of each can start per cycle

def run(program, rename=True, in_order=False):
    """program: list of (op, dest, sources). Returns the cycle the last result is ready."""
    ready, readers_done, busy, last_start, finish = {}, {}, {}, 0, 0
    for op, dst, srcs in program:
        t = max([ready.get(s, 0) for s in srcs] + [0])           # true dependences (read after write)
        if not rename and dst:                                    # without renaming, also wait for
            t = max(t, readers_done.get(dst, 0), ready.get(dst, 0))   # earlier readers and writers of dst
        if in_order: t = max(t, last_start)                      # in order: never start before an earlier one
        while busy.get((op, t), 0) >= UNITS[op]: t += 1          # find a cycle with a free unit
        busy[(op, t)] = busy.get((op, t), 0) + 1
        last_start = t
        done = t + LAT[op]
        for s in srcs: readers_done[s] = max(readers_done.get(s, 0), t)
        if dst: ready[dst] = done
        finish = max(finish, done)
    return finish

# 1. Summing 1,024 floats: one running total is a chain of dependent adds
N = 1024
print(f"summing {N:,} floats (add latency 4 cycles, 2 adders):")
for k in (1, 2, 4, 8, 16):
    prog = [("fadd", f"acc{i % k}", [f"acc{i % k}"]) for i in range(N)]              # k independent totals
    prog += [("fadd", "acc0", ["acc0", f"acc{j}"]) for j in range(1, k)]             # combine them at the end
    c = run(prog)
    print(f"   {k:2} accumulator{'s' if k > 1 else ' '}: {c:5,} cycles   ({N / c:.2f} adds per cycle)")

# 2. Register renaming: the same register reused for independent work creates false dependences
prog = []
for i in range(64):                                               # each step: load, multiply, add; all reuse x5, x6
    prog += [("load", "x5", [f"p{i}"]), ("mul", "x6", ["x5", "x5"]), ("add", f"s{i}", ["x6"])]
print(f"\n64 independent load-multiply-add steps that all reuse registers x5 and x6:")
print(f"   in order, no renaming:          {run(prog, rename=False, in_order=True):5,} cycles")
print(f"   out of order, no renaming:      {run(prog, rename=False):5,} cycles")
print(f"   out of order, renamed:          {run(prog, rename=True):5,} cycles")

# 3. Pointer chasing: each load needs the previous one's result, so nothing can overlap
print()
for lat, where in ((4, "L1 cache"), (100, "DRAM")):
    LAT["load"] = lat
    chain = [("load", "p", ["p"]) for _ in range(1000)]           # p = *p, a thousand times
    indep = [("load", f"v{i}", ["base"]) for i in range(1000)]    # a thousand loads from known addresses
    print(f"1,000 loads from {where:8} ({lat:3} cycles each): dependent chain {run(chain):7,} cycles, "
          f"independent {run(indep):4,} cycles")

summing 1,024 floats (add latency 4 cycles, 2 adders):
    1 accumulator : 4,096 cycles   (0.25 adds per cycle)
    2 accumulators: 2,052 cycles   (0.50 adds per cycle)
    4 accumulators: 1,036 cycles   (0.99 adds per cycle)
    8 accumulators:   540 cycles   (1.90 adds per cycle)
   16 accumulators:   572 cycles   (1.79 adds per cycle)

64 independent load-multiply-add steps that all reuse registers x5 and x6:
   in order, no renaming:            449 cycles
   out of order, no renaming:        260 cycles
   out of order, renamed:             71 cycles

1,000 loads from L1 cache (  4 cycles each): dependent chain   4,000 cycles, independent  503 cycles
1,000 loads from DRAM     (100 cycles each): dependent chain 100,000 cycles, independent  599 cycles

The last two lines measure memory-level parallelism. A thousand loads from independent addresses overlap almost completely: 503 cycles from L1, and only 599 from DRAM, because in this idealised model all of them can be outstanding at once. A real core tracks a few dozen outstanding misses, so independent DRAM loads take longer than that, but still far less than one by one. A thousand dependent loads, each needing the previous one's result as its address, can't overlap at all: 100,000 cycles from DRAM. Out-of-order hardware is powerless against a dependency chain through memory, which is why chapter 11's linked list is slow on every processor ever built.

SIMD: one instruction, many lanes

A SIMD instruction, single instruction, multiple data, operates on a wide register holding several values, called lanes, at once. A 128-bit register holds four 32-bit floats, and one instruction adds four pairs. x86 has had 128-bit SSE since 1999, 256-bit AVX2 since 2013, and 512-bit AVX-512 on some processors. ARM has 128-bit NEON and the scalable SVE, whose vector length the hardware chooses. Adding two arrays of 1,024 floats takes 1,024 scalar adds, 256 with 128-bit vectors and 64 with 512-bit ones.

SIMD has three requirements. The data must be contiguous, so a vector load can fetch several elements at once, which is another reason for chapter 11's structure-of-arrays layout. The iterations must be independent: a[i] = a[i-1] + b[i] can't run four lanes at once, because each lane needs the previous one's result. And branches become masks. Each lane computes both possibilities and a mask selects the result, so lanes whose condition is false do wasted work, as in the example, where 5 of 8 lanes are useful. Compilers auto-vectorise simple loops that meet these conditions, and libraries such as NumPy, BLAS and image codecs use SIMD intrinsics written by hand.

GPUs

A GPU takes the same idea to an extreme. Thousands of simple lanes are grouped into units of 32 or so, called warps on NVIDIA hardware, which execute the same instruction in lockstep on different data, a model NVIDIA calls SIMT. A GPU keeps tens of thousands of threads in flight to hide memory latency, the throughput strategy of chapter 9 taken as far as it goes, and pairs them with very high memory bandwidth. It excels at large, regular, data-parallel work such as graphics, matrix multiplication and the training of neural networks. It suffers when threads in a warp take different branches, because the warp must run both paths with half its lanes masked off each time.

Multicore

A multicore chip puts several complete cores on one die, sharing the last-level cache and memory. Threads on different cores share memory, and the coherence protocol of chapter 10 keeps their caches consistent, which costs time whenever cores write to the same line. False sharing makes that cost appear where no data is actually shared. In the example's model, two cores each incrementing their own counter cause 200,000 line transfers when the counters sit on one cache line, and 2 when they sit on separate lines. Beyond coherence, parallel programs pay for creating and synchronising threads and for contention on shared locks, so splitting small tasks across cores often makes them slower. Stage 05 covers threads, locks and their bugs.

Amdahl's law

If a fraction p of a program's work can be parallelised perfectly over n processors and the rest stays serial, the speed-up is

which can never exceed $1/(1-p)$, however many processors there are. Gene Amdahl made the argument in 1967. With 90% of the work parallel, 16 cores give a speed-up of 6.4 and no number of cores gives more than 10. The serial part, such as reading input, combining results or a lock everyone needs, dominates as soon as the parallel part has been divided up. Gustafson's law gives the optimistic counterpart: people use more processors to solve bigger problems, and if the parallel part grows with the problem, the serial fraction shrinks, which is how supercomputers stay useful.

Counted

The example counts instructions for SIMD addition at four vector widths, applies a mask in place of a branch, tabulates Amdahl's law, and counts the coherence traffic that false sharing causes.

# 1. SIMD: one instruction applies the same operation to several lanes at once
def simd_add(a, b, lanes):
    out, instructions = [], 0
    for i in range(0, len(a), lanes):
        out += [x + y for x, y in zip(a[i:i + lanes], b[i:i + lanes])]   # one vector instruction
        instructions += 1
    return out, instructions
a, b = list(range(1024)), list(range(1024, 2048))
print("adding two arrays of 1,024 32-bit floats:")
for lanes, name in ((1, "scalar"), (4, "128-bit SIMD (SSE, NEON)"), (8, "256-bit SIMD (AVX2)"), (16, "512-bit SIMD (AVX-512)")):
    out, n = simd_add(a, b, lanes)
    assert out == [x + y for x, y in zip(a, b)]
    print(f"   {name:26} {n:5,} add instructions")

# 2. Branches become masks: every lane computes, and a mask selects the results
xs = [3, -1, 4, -1, 5, -9, 2, 6]
mask = [x > 0 for x in xs]                                         # one vector compare
result = [x * 2 if m else 0 for x, m in zip(xs, mask)]             # compute everywhere, then blend
print(f"\ndouble the positive values with a mask: {xs} -> {result}; lanes doing useful work: {sum(mask)} of {len(xs)}")

# 3. Amdahl's law: the serial part of a program limits the speed-up from more cores
def amdahl(p, n): return 1 / ((1 - p) + p / n)
print("\nspeed-up on n cores when a fraction p of the work runs in parallel:")
print(f"   {'p':>5} " + "".join(f"{n:>8}" for n in (2, 4, 8, 16, 64, 1024)) + "   limit")
for p in (0.5, 0.9, 0.95, 0.99):
    print(f"   {p:>5} " + "".join(f"{amdahl(p, n):8.2f}" for n in (2, 4, 8, 16, 64, 1024)) + f"   {1 / (1 - p):5.0f}x")

# 4. False sharing: two cores each incrementing their own counter, on one cache line or on two
def coherence_traffic(same_line, increments=100_000):
    owner, transfers = {}, 0
    for i in range(increments):
        for core in (0, 1):
            line = 0 if same_line else core                          # which cache line this core's counter is on
            if owner.get(line) != core:                              # the line must move to this core first
                transfers += 1; owner[line] = core
    return transfers
print(f"\n2 cores x 100,000 increments: counters sharing one line need {coherence_traffic(True):,} line transfers, "
      f"counters on separate lines {coherence_traffic(False):,}")

adding two arrays of 1,024 32-bit floats:
   scalar                     1,024 add instructions
   128-bit SIMD (SSE, NEON)     256 add instructions
   256-bit SIMD (AVX2)          128 add instructions
   512-bit SIMD (AVX-512)        64 add instructions

double the positive values with a mask: [3, -1, 4, -1, 5, -9, 2, 6] -> [6, 0, 8, 0, 10, 0, 4, 12]; lanes doing useful work: 5 of 8

speed-up on n cores when a fraction p of the work runs in parallel:
       p        2       4       8      16      64    1024   limit
     0.5     1.33    1.60    1.78    1.88    1.97    2.00       2x
     0.9     1.82    3.08    4.71    6.40    8.77    9.91      10x
    0.95     1.90    3.48    5.93    9.14   15.42   19.64      20x
    0.99     1.98    3.88    7.48   13.91   39.26   91.18     100x

2 cores x 100,000 increments: counters sharing one line need 200,000 line transfers, counters on separate lines 2

The pipeline

Translation from source to machine happens in several steps, and Nand2Tetris builds every one of them. Each stage consumes the previous one's output and produces something closer to the machine.

Lexing and parsing

The lexer, or tokenizer, groups characters into tokens: names, numbers, operators and punctuation, discarding whitespace and comments. A regular expression is often enough, as in the example. The parser checks that the tokens follow the language's grammar and builds an abstract syntax tree (AST), a tree whose nodes are operations and whose leaves are names and constants. Recursive descent is the simplest parsing method: write one function per grammar rule, each calling the functions for the rules it contains. Operator precedence falls out of the structure. An expression is a sum of terms and a term is a product of factors, so expr calls term, which calls factor, and multiplication binds tighter than addition without any special handling. The tree for x = (2 + 3) * y - 4 * 2 is ('-', ('*', ('+', 2, 3), 'y'), ('*', 4, 2)), which makes the order of evaluation explicit.

Analysis and optimisation

Between parsing and code generation, a compiler builds symbol tables, mapping each name to its type and its storage location, such as the example's local slots. It checks types, and transforms the tree. Constant folding evaluates operations whose operands are known at compile time, so (2 + 3) * y - 4 * 2 becomes 5 * y - 8, and the generated code shrinks from 10 VM commands to 6. Real optimisers apply dozens of passes. They remove dead code, reuse common subexpressions, inline small functions, move work out of loops, and turn multiplication by a constant into shifts (chapter 4). They also assign variables to registers, which is graph colouring (The Engineer's Workbench, chapter 8), and schedule instructions around pipeline stalls (chapter 12). Most of a modern compiler is its optimiser, and most of that works on an intermediate representation such as LLVM's IR rather than on the source tree.

Code generation

For a stack machine, code generation is a post-order walk of the tree: emit code for the left operand, then for the right, then the operator. That's exactly the order a stack machine needs, operands pushed before the operation pops them. Control flow becomes labels and jumps. A while loop compiles to a label at the top, the condition, a jump to the end if it's false, the body, and a jump back to the top. Generating code for a register machine adds two harder problems, choosing instructions and allocating registers, which is why many compilers, and Nand2Tetris, first target a stack VM and translate from there.

Compiled and run

The example lexes and parses an assignment, folds its constants and generates VM code before and after folding. It then compiles a while loop that sums 1 to 100 and runs the result on a stack VM.

import re

# 1. Lexing: characters become tokens
def lex(src):
    return re.findall(r"\d+|[A-Za-z_]\w*|<=|[-+*/()=<{};]", src)

# 2. Parsing: tokens become a tree, by recursive descent with one function per precedence level
class Parser:
    def __init__(self, tokens): self.t, self.i = tokens, 0
    def peek(self): return self.t[self.i] if self.i < len(self.t) else None
    def eat(self, tok=None):
        x = self.t[self.i]; self.i += 1
        assert tok is None or x == tok, f"expected {tok}, got {x}"
        return x
    def program(self):
        stmts = []
        while self.peek() not in (None, "}"): stmts.append(self.statement())
        return stmts
    def statement(self):
        if self.peek() == "while":
            self.eat(); cond = self.comparison(); self.eat("{"); body = self.program(); self.eat("}")
            return ("while", cond, body)
        name = self.eat(); self.eat("="); value = self.expr(); self.eat(";")
        return ("let", name, value)
    def comparison(self):
        left = self.expr()
        if self.peek() in ("<", "<="): op = self.eat(); return (op, left, self.expr())
        return left
    def expr(self):                                            # + and - bind loosest
        node = self.term()
        while self.peek() in ("+", "-"): op = self.eat(); node = (op, node, self.term())
        return node
    def term(self):                                            # * and / bind tighter
        node = self.factor()
        while self.peek() in ("*", "/"): op = self.eat(); node = (op, node, self.factor())
        return node
    def factor(self):
        tok = self.eat()
        if tok == "(": node = self.expr(); self.eat(")"); return node
        return int(tok) if tok.isdigit() else tok

# 3. An optimisation pass: fold operations on constants at compile time
def fold(n):
    if not isinstance(n, tuple): return n
    if n[0] == "let": return ("let", n[1], fold(n[2]))
    if n[0] == "while": return ("while", fold(n[1]), [fold(s) for s in n[2]])
    op, a, b = n[0], fold(n[1]), fold(n[2])
    if isinstance(a, int) and isinstance(b, int) and op in "+-*":
        return {"+": a + b, "-": a - b, "*": a * b}[op]
    return (op, a, b)

# 4. Code generation: walk the tree, children first, emitting stack-VM commands
def gen(n, out, slots, labels):
    if isinstance(n, int): out.append(f"push constant {n}")
    elif isinstance(n, str): out.append(f"push local {slots.setdefault(n, len(slots))}")
    elif n[0] == "let":
        gen(n[2], out, slots, labels); out.append(f"pop local {slots.setdefault(n[1], len(slots))}")
    elif n[0] == "while":
        k = len(labels); labels.append(k)
        out.append(f"label TOP{k}"); gen(n[1], out, slots, labels)
        out.append("not"); out.append(f"if-goto END{k}")
        for s in n[2]: gen(s, out, slots, labels)
        out.append(f"goto TOP{k}"); out.append(f"label END{k}")
    else:
        gen(n[1], out, slots, labels); gen(n[2], out, slots, labels)
        out.append({"+": "add", "-": "sub", "*": "mul", "/": "div", "<": "lt", "<=": "le"}[n[0]])

def run_vm(code, nlocals):
    labels = {c.split()[1]: i for i, c in enumerate(code) if c.startswith("label")}
    stack, local, pc, steps = [], [0] * nlocals, 0, 0
    ops = {"add": lambda a, b: a + b, "sub": lambda a, b: a - b, "mul": lambda a, b: a * b,
           "div": lambda a, b: a // b, "lt": lambda a, b: int(a < b), "le": lambda a, b: int(a <= b)}
    while pc < len(code):
        c = code[pc].split(); pc += 1; steps += 1
        if c[0] == "push": stack.append(int(c[2]) if c[1] == "constant" else local[int(c[2])])
        elif c[0] == "pop": local[int(c[2])] = stack.pop()
        elif c[0] in ops: b, a = stack.pop(), stack.pop(); stack.append(ops[c[0]](a, b))
        elif c[0] == "not": stack.append(int(not stack.pop()))
        elif c[0] == "if-goto":
            if stack.pop(): pc = labels[c[1]]
        elif c[0] == "goto": pc = labels[c[1]]
    return local, steps

src = "x = (2 + 3) * y - 4 * 2;"
print("tokens:", lex(src))
tree = Parser(lex(src)).program()
print("tree:  ", tree[0])
print("folded:", fold(tree[0]))
for label, t in (("unoptimised", tree), ("folded", [fold(s) for s in tree])):
    code = []; gen(t[0], code, {"y": 0}, [])
    print(f"{label:12} {len(code)} VM commands: {'; '.join(code)}")

program = """
sum = 0;
i = 1;
while i <= 100 {
    sum = sum + i;
    i = i + 1;
}
"""
ast = Parser(lex(program)).program()
code, slots = [], {}
for s in ast: gen(s, code, slots, [])
local, steps = run_vm(code, len(slots))
print(f"\nthe loop compiles to {len(code)} VM commands; running them leaves sum = {local[slots['sum']]} "
      f"after {steps:,} commands")
for line in code: print(f"   {line}")

tokens: ['x', '=', '(', '2', '+', '3', ')', '*', 'y', '-', '4', '*', '2', ';']
tree:   ('let', 'x', ('-', ('*', ('+', 2, 3), 'y'), ('*', 4, 2)))
folded: ('let', 'x', ('-', ('*', 5, 'y'), 8))
unoptimised  10 VM commands: push constant 2; push constant 3; add; push local 0; mul; push constant 4; push constant 2; mul; sub; pop local 1
folded       6 VM commands: push constant 5; push local 0; mul; push constant 8; sub; pop local 1

the loop compiles to 20 VM commands; running them leaves sum = 5050 after 1,511 commands
   push constant 0
   pop local 0
   push constant 1
   pop local 1
   label TOP0
   push local 1
   push constant 100
   le
   not
   if-goto END0
   push local 0
   push local 1
   add
   pop local 0
   push local 1
   push constant 1
   add
   pop local 1
   goto TOP0
   label END0

The compiled loop runs 1,511 VM commands, where chapter 8's hand-written version ran 1,411. The difference is the not the code generator emits before every loop test, 101 times, because it compiles "jump to the end if the condition is false" literally. A slightly smarter generator would test the inverse condition directly (exercise 16.3). Compilers are full of small decisions like that, and their accumulated effect is the difference between naive and optimised code.

Assembling, and beyond

Below the compiler, the VM translator turns each VM command into a fixed sequence of assembly instructions (chapter 8, exercise 8.3), and the assembler turns assembly into machine code with chapter 7's two passes. Real toolchains split the same work across separate programs. clang -S stops after code generation and shows the assembly, clang -c runs the assembler too and produces an object file, and the linker (chapter 17) finishes the job. Just-in-time compilers, in the JVM, in JavaScript engines such as V8, and in PyPy, run this pipeline while the program executes, compiling the hottest code using the types and values they actually observe.

Object files

A compiler and assembler turn each source file into an object file: machine code that isn't yet runnable, because it refers to things whose addresses aren't known. An object file contains sections. .text holds the code, .data initialised global variables, .rodata constants, and .bss zero-initialised globals, which take no space in the file, only a size. It has a symbol table listing the names it defines and the names it uses but doesn't define, and relocation entries marking each place in the code that refers to a symbol and must be patched once its address is known. The formats differ by platform: ELF on Linux, Mach-O on macOS and PE/COFF on Windows. The tools to inspect them, nm, objdump and readelf, are worth learning.

What the linker does

Linking happens in two steps, much like chapter 7's assembler. Symbol resolution matches every undefined symbol in every input to exactly one definition elsewhere. Relocation lays the sections out at final addresses, computes every symbol's address, and patches each relocation entry with the right value.

The two classic errors fall out of resolution. "Undefined reference" means some symbol has no definition in any input, usually a missing library on the command line, such as forgetting -lm for sqrt. "Duplicate symbol" or "multiple definition" means two inputs define the same name, often because a variable was defined, rather than declared, in a header included by several files. Static libraries, .a archives, are searched only for symbols still undefined at that point, which is why the order of libraries on a Unix linker command line matters.

Linked, by hand

The example's object files are lists of pseudo-instructions with symbol tables and relocation entries. The linker places the text sections from address 0x1000 and the data from 0x8000, resolves every reference, and patches the code. It then fails twice on purpose, and finally loads the result at three random base addresses.

import random

# Object files as an assembler would leave them: code, the symbols they define, the references to resolve
main_o = {"name": "main.o",
          "text": ["push 2", "push 3", "call add", "store result", "call print_int", "ret"],
          "data": {"result": 0},
          "defines": {"main": 0},
          "relocs": [(2, "add"), (3, "result"), (4, "print_int")]}       # (instruction index, symbol)
math_o = {"name": "math.o",
          "text": ["load arg0", "load arg1", "add", "ret"],
          "data": {},
          "defines": {"add": 0},
          "relocs": []}
libc_o = {"name": "libc.o", "text": ["syscall write", "ret"], "data": {}, "defines": {"print_int": 0}, "relocs": []}

def link(objects, text_base=0x1000, data_base=0x8000, instr_size=4):
    symbols, text, data, layout = {}, [], {}, []
    for obj in objects:                                        # pass 1: lay out sections, collect definitions
        start = text_base + instr_size * len(text)
        layout.append((obj["name"], start, len(obj["text"])))
        for name, off in obj["defines"].items():
            if name in symbols: raise ValueError(f"duplicate symbol {name}")
            symbols[name] = start + instr_size * off
        for name in obj["data"]:
            symbols[name] = data_base + 8 * len(data); data[name] = obj["data"][name]
        obj["start_index"] = len(text); text += obj["text"]
    patched = list(text)
    for obj in objects:                                        # pass 2: patch every reference with its address
        for idx, name in obj["relocs"]:
            if name not in symbols: raise ValueError(f"undefined reference to {name} in {obj['name']}")
            k = obj["start_index"] + idx
            op = patched[k].split()[0]
            patched[k] = f"{op} 0x{symbols[name]:X}"
    return patched, symbols, layout

exe, symbols, layout = link([main_o, math_o, libc_o])
print("layout:", ", ".join(f"{n} at 0x{s:X} ({c} instructions)" for n, s, c in layout))
print("symbols:", {k: hex(v) for k, v in symbols.items()})
print("linked text:")
for i, ins in enumerate(exe): print(f"   0x{0x1000 + 4 * i:X}: {ins}")
try:
    link([main_o, math_o])
except ValueError as e:
    print(f"\nlinking without libc.o: error: {e}")
try:
    link([main_o, math_o, libc_o, {"name": "dup.o", "text": ["ret"], "data": {}, "defines": {"add": 0}, "relocs": []}])
except ValueError as e:
    print(f"linking a second definition of add: error: {e}")

# Loading with address space layout randomisation: the same program at a different base each run
random.seed(17)
print("\nloaded at random bases (ASLR): absolute addresses move, relative offsets don't:")
for run in range(3):
    base = random.randrange(0x5550_0000_0000, 0x5600_0000_0000, 0x1000)       # page-aligned
    add_addr = base + (symbols["add"] - 0x1000)
    call_site = base + 4 * 2                                  # main's "call add" instruction
    print(f"   run {run + 1}: base 0x{base:X}, add at 0x{add_addr:X}, call-site-relative offset {add_addr - call_site:+d}")

layout: main.o at 0x1000 (6 instructions), math.o at 0x1018 (4 instructions), libc.o at 0x1028 (2 instructions)
symbols: {'main': '0x1000', 'result': '0x8000', 'add': '0x1018', 'print_int': '0x1028'}
linked text:
   0x1000: push 2
   0x1004: push 3
   0x1008: call 0x1018
   0x100C: store 0x8000
   0x1010: call 0x1028
   0x1014: ret
   0x1018: load arg0
   0x101C: load arg1
   0x1020: add
   0x1024: ret
   0x1028: syscall write
   0x102C: ret

linking without libc.o: error: undefined reference to print_int in main.o
linking a second definition of add: error: duplicate symbol add

loaded at random bases (ASLR): absolute addresses move, relative offsets don't:
   run 1: base 0x55D5A0BCC000, add at 0x55D5A0BCC018, call-site-relative offset +16
   run 2: base 0x55BA06E9A000, add at 0x55BA06E9A018, call-site-relative offset +16
   run 3: base 0x559DAD298000, add at 0x559DAD298018, call-site-relative offset +16

Static and dynamic linking

Static linking copies the library code a program uses into the executable. The result is self-contained and starts fast, but every program carries its own copy, and fixing a bug in the library means relinking every program. Dynamic linking leaves library references unresolved until the program runs. Shared libraries, .so on Linux, .dylib on macOS and .dll on Windows, are loaded at run time and their code pages shared between all the processes that use them. A security fix to a shared library reaches every program at once. The costs are a little indirection on every call, through a procedure linkage table (PLT) and a global offset table (GOT) that the dynamic linker fills in, some start-up work, and a class of version-mismatch problems known on Windows as "DLL hell". Go and Rust link their own code statically by default, while most C and C++ programs link the system's C library dynamically.

Loading

To start a program, the operating system creates a fresh virtual address space and maps the executable's segments into it: code as read-only and executable, data as read-write. It reserves the bss and a stack, places the arguments and environment variables on the stack, and, for a dynamically linked program, maps the dynamic linker, ld.so on Linux, which loads the shared libraries and resolves their symbols. Control finally passes to the entry point, usually _start in the C runtime, which initialises the library and calls main. The resulting layout has code and data at the bottom, the heap above them growing upward as the program allocates, shared libraries and other mappings in the middle, and the stack near the top growing downward (chapter 18).

Address randomisation

If code always loads at the same address, an attacker who can overwrite a return address (chapter 18) knows exactly where to jump. Address space layout randomisation (ASLR) loads the executable, libraries, heap and stack at random addresses on every run, so a hard-coded address works only by luck. It requires position-independent code, which refers to its own functions and data relative to the current instruction's address rather than by absolute address. In the example, the base address changes on each run while the distance from main's call site to add stays +16, so an instruction that encodes "call the function 16 bytes ahead" works wherever the code is loaded. Modern compilers produce position-independent executables (PIE) by default for exactly this reason.

Calls and frames

A call has to remember where to come back to. On x86 the call instruction pushes the return address onto the stack. On RISC-V, jal puts it in the register ra (chapter 6), and a function that makes calls of its own saves ra to the stack first. The function's prologue then saves the caller's frame pointer and any registers it promised to preserve, and allocates space for its locals by subtracting from the stack pointer. The epilogue undoes all of that, and ret jumps to the saved address. The rules for which registers hold arguments, which hold the return value, and which a function must preserve make up the calling convention. RISC-V passes the first eight arguments in a0 to a7 and returns in a0; on Linux and macOS, x86-64 uses rdi, rsi, rdx, rcx, r8 and r9, and returns in rax. Further arguments go on the stack.

Two consequences follow. Stack allocation is almost free compared with the heap, where malloc has to search for a free block, which is one reason short-lived locals are fast. And a local variable stops existing when its function returns. Its bytes stay in memory until the next call reuses them, so a pointer to a local that outlives the call reads whatever the next frame put there.

Overflowing a buffer

In C, strcpy(buf, input) copies until it finds the terminating zero byte, however big buf is. So do gets, which can't be used safely at all and was removed from C11, and sprintf. If the input comes from outside the program, its author decides what lands past the end of the buffer, and the return address starts only 8 bytes past its end. The example simulates a 64 KiB machine and runs the vulnerable function three times. A 5-byte input and a 16-byte one leave the frame intact. A 32-byte input fills the buffer, overwrites the saved frame pointer with the bytes BBBBBBBB, and replaces the return address with a value the attacker chose.

import struct, random

# A tiny machine: 64 KiB of memory, a stack growing down from the top, 8-byte words, little-endian
MEM = bytearray(65536)
def w64(addr, v): MEM[addr:addr + 8] = struct.pack("<Q", v)
def r64(addr): return struct.unpack("<Q", MEM[addr:addr + 8])[0]

def call_vulnerable(user_input, canary=None):
    """The caller pushes a return address; the callee saves the frame pointer, maybe a canary, and a 16-byte buffer."""
    sp = 0x10000
    sp -= 8; w64(sp, 0x401234); ret_slot = sp                  # return address into the caller
    sp -= 8; w64(sp, 0xFFF0); fp_slot = sp                     # saved frame pointer
    if canary is not None: sp -= 8; w64(sp, canary); canary_slot = sp
    sp -= 16; buf = sp                                         # char buf[16]
    MEM[buf:buf + len(user_input)] = user_input                # strcpy(buf, input): no length check
    layout = f"buf at 0x{buf:X}, " + (f"canary at 0x{canary_slot:X}, " if canary is not None else "") + \
             f"saved fp at 0x{fp_slot:X}, return address at 0x{ret_slot:X}"
    if canary is not None and r64(canary_slot) != canary:
        return layout, "stack smashing detected: the program aborts before returning"
    return layout, f"returns to 0x{r64(ret_slot):X}"

print("frame:", call_vulnerable(b"hello")[0])
print(f"input of  5 bytes: {call_vulnerable(b'hello')[1]}")
print(f"input of 16 bytes: {call_vulnerable(b'A' * 16)[1]}")
attack = b"A" * 16 + b"B" * 8 + struct.pack("<Q", 0xDEADBEEF)          # fill buf, overwrite fp, then the return address
print(f"input of 32 bytes: {call_vulnerable(attack)[1]}   <- the attacker chose this address")
random.seed(18)
canary = random.getrandbits(64) & ~0xFF                                # real canaries start with a zero byte
attack_c = b"A" * 16 + b"C" * 8 + b"B" * 8 + struct.pack("<Q", 0xDEADBEEF)
print(f"with a stack canary, the same attack: {call_vulnerable(attack_c, canary)[1]}")

# How deep can recursion go? Frame size times depth against the stack limit
for frame_bytes in (48, 256, 4096):
    print(f"frames of {frame_bytes:5,} bytes: an 8 MiB stack holds about {8 * 1024 * 1024 // frame_bytes:,} nested calls")

frame: buf at 0xFFE0, saved fp at 0xFFF0, return address at 0xFFF8
input of  5 bytes: returns to 0x401234
input of 16 bytes: returns to 0x401234
input of 32 bytes: returns to 0xDEADBEEF   <- the attacker chose this address
with a stack canary, the same attack: stack smashing detected: the program aborts before returning
frames of    48 bytes: an 8 MiB stack holds about 174,762 nested calls
frames of   256 bytes: an 8 MiB stack holds about 32,768 nested calls
frames of 4,096 bytes: an 8 MiB stack holds about 2,048 nested calls

In a real attack, the chosen address points at code the attacker supplied in the same input, or at existing code that does what they want. This is the oldest exploit technique in computing that still works. The Morris worm used it in 1988 against a gets call in the finger daemon, and Aleph One's 1996 article "Smashing the Stack for Fun and Profit" taught it to a generation.

Defences

A stack canary is a random value the prologue places between the locals and the saved registers, and that the epilogue checks before returning. An overflow from a buffer must pass through it to reach the return address, and the attacker doesn't know its value, so the check fails and the program aborts instead of jumping. GCC and Clang insert canaries with -fstack-protector, on by default in most Linux distributions. A non-executable stack, also called NX, DEP or W^X, makes the processor refuse to run instructions from stack pages, so injected code can't run. Attackers answered with return-oriented programming: chaining short fragments of the program's existing code, each ending in ret. That's where ASLR (chapter 17) comes in, since the fragments' addresses are no longer known in advance. The newest defences are in hardware. Intel's CET keeps a shadow stack of return addresses that ordinary stores can't write, and ARM's pointer authentication, used on Apple silicon, signs return addresses with a key held in the processor.

Each defence raises the cost of an attack, and none removes the bug. Microsoft and the Chromium project have each reported that about 70% of their serious security bugs are memory-safety errors. The lasting fix is code that can't write past the end of a buffer: bounds-checked languages such as Rust, Go, Java and Python, and in C and C++, functions that take the destination's size, such as snprintf, used correctly.

How deep can recursion go?

Each nested call adds a frame, and the stack has a fixed size. The main thread's default is 8 MiB on Linux and macOS, other threads often get less (512 KiB for secondary threads on macOS), and Windows defaults to 1 MiB. The example's last lines divide 8 MiB by the frame size: about 175,000 calls for a small 48-byte frame, but only 2,048 for a function with a 4 KiB local array. Below the stack sits an unmapped guard page, so running out is a crash, a segmentation fault, rather than silent corruption of the heap. Python sets its own recursion limit, 1,000 by default, well below the point where its interpreter's C stack would overflow. Recursion whose depth depends on the input, such as walking a long linked list or parsing deeply nested JSON, should be rewritten as a loop with an explicit stack on the heap.

Talking to devices

Most devices are reached by memory-mapped I/O. Their control and status registers appear at physical addresses, and ordinary loads and stores to those addresses go to the device instead of memory, just as the Hack computer's screen and keyboard did in chapter 7. A store to a network card's register might mean "send the packet described here", and a load from its status register reports whether one has arrived. Those addresses must never be cached, and accesses to them must not be reordered or optimised away, so the page tables mark them uncached and drivers access them through volatile pointers or helpers such as Linux's readl and writel. In a modern computer most devices sit on PCI Express, and the code that knows a particular device's registers is its driver.

Polling and interrupts

Polling means reading the status register in a loop until it says data is ready. Each check costs only tens of cycles, but the core does nothing else, so polling a keyboard that produces ten events a second wastes a whole core. With interrupts, the device raises a signal when it needs attention. The processor finishes its current instruction, saves the program counter and some state, switches to kernel mode, and jumps to the handler registered for that interrupt in a table of handlers, the interrupt vector table. The handler acknowledges the device, does the minimum, schedules any longer work for later, and returns, and the interrupted program continues as if nothing had happened. The same mechanism handles exceptions, such as a page fault or a division by zero, and system calls, where a program deliberately traps into the kernel. A timer interrupt, a few hundred or a thousand times a second, is what lets the operating system take the processor back from a running program and schedule another.

An interrupt isn't free. Saving state, switching modes and running the handler costs around a microsecond, roughly 3,000 cycles, and the handler's code and data push the program's out of the caches. Even with interrupts, if the processor copies every byte from the device itself, a fast device keeps it busy.

Direct memory access

With DMA, the device copies the data itself. The driver sets up a ring of descriptors in memory, each pointing at an empty buffer. The device writes each incoming packet or disk block into the next buffer, marks the descriptor as filled, and raises an interrupt only after a batch of them, or after a short timeout. This is interrupt coalescing. The processor never touches the data until it's ready to use it. Two practical details matter. On x86 machines, DMA is cache-coherent: the hardware makes sure the caches don't hold stale copies of buffers a device has written. On many ARM systems the driver must flush or invalidate the caches itself. And because a device that can write anywhere in memory can also overwrite the kernel, an IOMMU translates and restricts the addresses each device may use, the way page tables restrict programs.

The example prices one second of each device. Busy polling costs a whole core whatever the device, which is why it's worth it only when events never stop. With interrupts, the keyboard and mouse cost almost nothing, and their DMA column shows only that at low rates the choice doesn't matter; nobody batches keystrokes. The network card, with an interrupt and a copy per packet, takes 94% of a core. The SSD would need more than a whole core. DMA with one interrupt per 32 events brings both down to about 3%.

# How much CPU time does it take to move data in from a device? Three ways, for four devices.
GHZ = 3e9                                    # cycles per second of one core
INTERRUPT = 3_000                            # cycles to take an interrupt, run the handler and return (about 1 us)
COPY_PER_BYTE = 0.25                         # cycles per byte for the CPU to copy data itself

devices = [  # name, events per second, bytes per event
    ("keyboard", 10, 8),
    ("mouse", 1_000, 8),
    ("10 Gb/s network, 1500-byte packets", 10e9 / 8 / 1500, 1500),
    ("NVMe SSD, 4 KiB reads at 1M IOPS", 1_000_000, 4096),
]
def busy_polling(rate, size):     # a core spends all its time checking: the whole core, whatever the rate
    return 1.0
def interrupts(rate, size):       # each event interrupts the CPU, which then copies the data
    return rate * (INTERRUPT + size * COPY_PER_BYTE) / GHZ
def dma(rate, size, batch=32):    # the device copies into memory itself and interrupts once per batch
    return rate / batch * INTERRUPT / GHZ

print(f"{'device':38} {'events/s':>11}   busy polling   interrupts + copy   DMA, 1 interrupt per 32")
for name, rate, size in devices:
    irq = interrupts(rate, size)
    shown = f"{irq:.2%}" if irq <= 1 else f"{irq:.0%} (over 1 core)"
    print(f"{name:38} {rate:11,.0f}   {busy_polling(rate, size):>11.0%}   {shown:>16}   {dma(rate, size):>14.2%}")

# Interrupt storms: with one interrupt per packet, a core saturates; coalescing and polling under load help
for pps in (100_000, 1_000_000, 3_000_000):
    load = pps * INTERRUPT / GHZ
    print(f"{pps:>9,} packets/s with one interrupt each: {min(load, 1):.0%} of a core" + ("  (livelock: no time left for work)" if load >= 1 else ""))

device                                    events/s   busy polling   interrupts + copy   DMA, 1 interrupt per 32
keyboard                                        10          100%              0.00%            0.00%
mouse                                        1,000          100%              0.10%            0.00%
10 Gb/s network, 1500-byte packets         833,333          100%             93.75%            2.60%
NVMe SSD, 4 KiB reads at 1M IOPS         1,000,000          100%   134% (over 1 core)            3.12%
  100,000 packets/s with one interrupt each: 10% of a core
1,000,000 packets/s with one interrupt each: 100% of a core  (livelock: no time left for work)
3,000,000 packets/s with one interrupt each: 100% of a core  (livelock: no time left for work)

When interrupts are too many

The last lines of the output show the failure that made networking engineers rethink interrupts. At a million packets a second with one interrupt each, handling interrupts takes the whole core. The handler runs, receives the packet, and before the program can process it the next interrupt arrives. The machine is fully busy and gets nothing done. This is receive livelock, described by Mogul and Ramakrishnan in 1996. The answer was to go back to polling, but polling memory rather than device registers. Linux's NAPI takes one interrupt, switches it off, and polls the DMA ring until it's empty, switching interrupts back on only when traffic falls. Frameworks such as DPDK, for networking, and SPDK, for storage, go further: they give a device to a user-space program that polls its rings on dedicated cores and never takes an interrupt. Interrupts are best when events are rare, and polling a DMA ring is best when they never stop.

Coalescing trades latency for throughput. An interrupt per batch of 32 means the first packet waits for 31 more, or for the timeout. Network cards and storage drivers let the timeout and batch size be tuned, and latency-sensitive systems such as trading platforms set them low or poll.

The iron law

A program's running time is the product of three factors:

Different things change each factor. The instruction count depends on the algorithm, the compiler and the instruction set; SIMD (chapter 15) cuts it by doing several operations per instruction. Cycles per instruction, or CPI, depends on how well the program suits the microarchitecture: cache misses (chapters 9 to 11), branch mispredictions (chapter 13) and dependency chains (chapter 14) all raise it. The clock period is set by circuit design and power (chapters 3 and 12). The factors interact, which is why the law is worth writing down. In the example, a better compiler removes 20% of the instructions, but the remaining ones are slower on average, and the gain is 1.18 times rather than 1.25. A cache-friendly data layout that leaves the instruction count alone but cuts CPI from 1.6 to 0.9 gains 1.78 times, much more than a 20% faster clock.

Hardware people often quote the inverse, instructions per cycle or IPC. A wide out-of-order core running well-behaved code retires three or four instructions per cycle, and the same core chasing pointers through memory retires a fraction of one. On Linux, perf stat reports a program's IPC along with its cache and branch misses, and is the quickest way to see which factor is the problem. Comparing CPI or clock rates between different instruction sets or different programs says little, because the instruction counts differ.

import math

# 1. The iron law: time = instructions x cycles per instruction x seconds per cycle
def seconds(instructions, cpi, ghz): return instructions * cpi / (ghz * 1e9)
variants = [("original", 10e9, 1.6, 3.0), ("better compiler: 20% fewer instructions", 8e9, 1.7, 3.0),
            ("cache-friendly layout: lower CPI", 10e9, 0.9, 3.0), ("faster clock, same code", 10e9, 1.6, 3.6)]
print("the iron law of performance:")
base = None
for name, n, cpi, ghz in variants:
    t = seconds(n, cpi, ghz); base = base or t
    print(f"   {name:42} {n / 1e9:4.0f}G instructions x CPI {cpi} / {ghz} GHz = {t:5.2f} s  ({base / t:.2f}x)")

# 2. The roofline: attainable speed is limited by compute or by memory bandwidth, whichever binds first
PEAK, BW = 200e9, 50e9                       # 200 GFLOP/s of arithmetic, 50 GB/s of memory bandwidth
ridge = PEAK / BW
print(f"\nroofline for a machine with {PEAK / 1e9:.0f} GFLOP/s and {BW / 1e9:.0f} GB/s (ridge at {ridge:.0f} FLOP per byte):")
kernels = [("vector add  c = a + b", 1, 12), ("dot product", 2, 8), ("5-point stencil", 6, 16),
           ("matrix multiply, naive", 2, 16), ("matrix multiply, blocked", 2 * 64, 16)]
for name, flops, bytes_ in kernels:                         # per element: arithmetic and memory traffic
    ai = flops / bytes_
    attainable = min(PEAK, ai * BW)
    bound = "memory-bound" if ai < ridge else "compute-bound"
    print(f"   {name:26} {ai:7.3f} FLOP/byte -> at most {attainable / 1e9:6.1f} GFLOP/s ({bound})")

# 3. Back-of-the-envelope: how long does it take to read 1 GB?
print("\nreading 1 GB:")
for where, rate in (("from L3-resident data, ~200 GB/s", 200e9), ("from DRAM, ~50 GB/s", 50e9),
                    ("from an NVMe SSD, ~5 GB/s", 5e9), ("from a hard disk, ~200 MB/s", 200e6), ("over a 1 Gb/s network", 125e6)):
    s = 1e9 / rate
    print(f"   {where:36} {s * 1000:9,.1f} ms")

# 4. Speeding up one part: Amdahl again, applied to a profile
profile = {"parse input": 0.15, "compute": 0.70, "write output": 0.15}
for part, factor in (("compute", 4), ("compute", 1e9), ("parse input", 4)):
    new = sum(f / factor if p == part else f for p, f in profile.items())
    print(f"making '{part}' {'infinitely' if factor > 1e6 else f'{factor:g}x'} faster: whole program {1 / new:.2f}x faster")

the iron law of performance:
   original                                     10G instructions x CPI 1.6 / 3.0 GHz =  5.33 s  (1.00x)
   better compiler: 20% fewer instructions       8G instructions x CPI 1.7 / 3.0 GHz =  4.53 s  (1.18x)
   cache-friendly layout: lower CPI             10G instructions x CPI 0.9 / 3.0 GHz =  3.00 s  (1.78x)
   faster clock, same code                      10G instructions x CPI 1.6 / 3.6 GHz =  4.44 s  (1.20x)

roofline for a machine with 200 GFLOP/s and 50 GB/s (ridge at 4 FLOP per byte):
   vector add  c = a + b        0.083 FLOP/byte -> at most    4.2 GFLOP/s (memory-bound)
   dot product                  0.250 FLOP/byte -> at most   12.5 GFLOP/s (memory-bound)
   5-point stencil              0.375 FLOP/byte -> at most   18.8 GFLOP/s (memory-bound)
   matrix multiply, naive       0.125 FLOP/byte -> at most    6.2 GFLOP/s (memory-bound)
   matrix multiply, blocked     8.000 FLOP/byte -> at most  200.0 GFLOP/s (compute-bound)

reading 1 GB:
   from L3-resident data, ~200 GB/s           5.0 ms
   from DRAM, ~50 GB/s                       20.0 ms
   from an NVMe SSD, ~5 GB/s                200.0 ms
   from a hard disk, ~200 MB/s            5,000.0 ms
   over a 1 Gb/s network                  8,000.0 ms
making 'compute' 4x faster: whole program 2.11x faster
making 'compute' infinitely faster: whole program 3.33x faster
making 'parse input' 4x faster: whole program 1.13x faster

The roofline

A loop needs both arithmetic and data. Its arithmetic intensity $I$ is the number of floating-point operations it does per byte it moves to or from main memory. A machine has a peak arithmetic rate $P_{\text{peak}}$ and a memory bandwidth $B$, and the loop can go no faster than whichever limit it hits first:

Plotted on log-log axes, that's a sloped line, the bandwidth limit, meeting a flat one, the peak, at the ridge point $P_{\text{peak}}/B$. The example's machine, with 200 GFLOP/s and 50 GB/s, has its ridge at 4 FLOP per byte. Real CPUs have ridges between roughly 5 and 15, and GPUs often higher still, so most simple loops are on the slope. A vector add does one addition per 12 bytes moved, three 4-byte floats, and can't exceed 4.2 GFLOP/s on a machine that could do 200. Wider SIMD or more cores make no difference to a loop on the slope. Only reducing its memory traffic does: blocking (chapter 11), smaller data types, or fusing loops so that data is used several times while it's in the cache.

Matrix multiplication is the chapter 11 result seen on the roofline. The naive loop loads two values for every multiply-add, an intensity of 0.125. Blocking reuses each loaded value 64 times, which raises the intensity to 8 and moves the loop past the ridge, where it's limited by arithmetic. That's also why matrix multiplication is the workload GPUs and AI accelerators are built around: it's one of the few important computations with enough reuse to use all their arithmetic.

Numbers to know

Estimates need a few numbers, known to within a factor of two: chapter 9's latencies, and the bandwidths in the example's third section. Reading a gigabyte takes about 20 ms from memory, 200 ms from an NVMe SSD, 5 s from a hard disk and 8 s over a 1 Gb/s network. Multiplying such numbers out answers design questions in a minute. A request that must read 1 GB from memory can't be served more than about 50 times a second per memory system, and a full scan of a 1 TB table on one SSD takes over three minutes however clever the query is. Throughput and latency connect through Little's law (chapters 9 and 14): the number of operations in flight equals throughput times latency, so a disk with a 100 µs latency needs 100 outstanding requests to deliver a million operations a second.

Amdahl on a profile

Before speeding anything up, find out where the time goes. A sampling profiler such as perf record on Linux, Instruments on macOS or py-spy for Python interrupts the program thousands of times a second and records what it was running, which gives each function's share of the time with little overhead. Amdahl's law (chapter 15) then gives the ceiling. In the example's profile, computing takes 70% of the time. Making it four times faster speeds the whole program up 2.11 times, and making it infinitely fast only 3.33 times, $1/(1-0.7)$. Making parsing, 15% of the time, four times faster gains 1.13 times. Effort spent on a small part of the profile is mostly wasted, however good the optimisation.

Measurement has its own traps. Run several times and report the median, since the first run pays for cold caches and the rest vary with whatever else the machine is doing. Clock rates change with temperature and power: a laptop on battery or a core that has been busy for a minute runs slower than one that just woke up. Measure the work you care about at a realistic size, because a benchmark that fits in the cache tells you nothing about one that doesn't. The method that works is to estimate the bound first, measure, and compare. A loop running at 10% of its roofline has a problem worth finding, while one at 80% needs a different algorithm or a different machine, not more tuning.