Language & library reference

Formal. A row of n bits, each 0 or 1, has exactly 2^n distinct patterns. Read as a whole number with no sign, those patterns are the values 0 through 2^n − 1, and each extra bit doubles the count.

In plain English. Every bit you add doubles how many different things you can label, because each old pattern now comes in a "0 in front" and a "1 in front" version. Eight bits give 256 patterns, so a byte can stand for any number from 0 to 255.

Example. 4 bits: 2^4 = 16 patterns, 0000 to 1111, the values 0 to 15. 16 bits: 65,536 patterns, 0 to 65,535. 64 bits: about 1.8 × 10^19.

Why this rule exists. It tells you, before writing any code, the largest value a type can hold and how many bits you need to label m different things (the smallest n with 2^n ≥ m).

Formal. Because 16 = 2^4, each base-16 digit corresponds to exactly one 4-bit group (a nibble). A binary number converts to hexadecimal by grouping its bits in fours from bit 0 and replacing each group by its hex digit, and back by expanding each hex digit to four bits.

In plain English. Hex is shorthand for binary. Split the bits into groups of four starting from the right, and write one hex digit per group; no arithmetic on the whole number is needed.

Example. 1011 0110 → B 6 → 0xB6. 0x3F → 0011 1111.

Why this rule exists. It is why debuggers, compilers and memory dumps print values in hex: two hex digits are one byte, and every bit is still visible at a glance.

Formal. For n-bit unsigned integers, the hardware's add, subtract and multiply produce the true result reduced modulo 2^n: only the low n bits are kept. In C++ this is the defined behaviour of unsigned types.

In plain English. A fixed-width unsigned number behaves like a car's odometer. Go one past the largest value and it rolls back to 0; go below 0 and it rolls up to the largest value.

Example. In 8 bits, 250 + 10 = 260, and 260 − 256 = 4, so a std::uint8_t holding 250 plus 10 holds 4. 0 − 1 gives 255.

Why this rule exists. The processor has a fixed number of bits in each register; whatever does not fit is simply not stored. Knowing the rule lets you predict the result instead of being surprised by it.

Formal. An n-bit pattern b_{n-1} … b_1 b_0 read as two's complement has the value −b_{n-1}·2^(n−1) + Σ_{i=0}^{n−2} b_i·2^i. The range is −2^(n−1) to 2^(n−1) − 1, and negation is (~x + 1) mod 2^n.

In plain English. Every bit keeps its usual place value except the top one, which counts as a big negative amount. That single change lets the same adder handle positive and negative numbers, and gives exactly one zero.

Example. In 8 bits, 1111 1101 is −128 + 64 + 32 + 16 + 8 + 4 + 1 = −3. Negating 3 (0000 0011): flip to 1111 1100, add 1 → 1111 1101.

Why this rule exists. It is the encoding every processor in this course uses for signed integers, so every signed instruction, flag and branch condition is defined in terms of it.

Formal. For n-bit two's-complement addition a + b, signed overflow occurs exactly when a and b have the same sign bit and the result's sign bit differs from it. Adding values of opposite sign never overflows. Unsigned wraparound (the carry out of bit n−1) is a separate condition.

In plain English. Two positives can't add up to a negative, and two negatives can't add up to a positive — if the stored answer says they did, it didn't fit. Carry asks a different question: did the unsigned answer wrap past the top?

Example. 8 bits: 100 + 100 = 200 doesn't fit in −128..127; the stored pattern 1100 1000 reads as −56 (overflow, no carry). −1 + 1: 1111 1111 + 0000 0001 = 1 0000 0000, carry out 1, result 0 — correct, no overflow.

Why this rule exists. Processors compute one sum and report both conditions; signed and unsigned code each check the one that matters to them.

Formal. The effective address of a memory operand is computed modulo 2^64 as follows.

• x86-64: base + index × scale + displacement, where base and index are 64-bit registers (index may not be rsp), scale ∈ {1, 2, 4, 8} and displacement is a signed 8- or 32-bit constant; any part may be absent. rip-based form: address of the next instruction + signed 32-bit displacement. Written [rdi + rsi*4 + 16], [rip + label].
• ARM64: base xn (or sp) plus one of: an immediate ([x0, #8], unsigned and scaled by the access size, or signed 9-bit unscaled), a register shifted left by 0 or log2(access size) ([x0, x1, lsl #3]), or a 32-bit register sign- or zero-extended ([x0, w1, sxtw #2]). Pre-index [x0, #16]! uses x0 + 16 and writes it back to x0 first; post-index [x0], #16 uses x0, then adds 16 to x0.
• RISC-V: base register + signed 12-bit immediate (−2048 to 2047), written imm(rs1), e.g. 8(sp). There is no index register; a scaled index is built with slli and add first.

In plain English. Every ISA starts from an address held in a register and adds a little to it. x86-64 lets one operand add a second register multiplied by 1, 2, 4 or 8 and a fixed number. ARM64 lets you add a fixed number or a second register multiplied by the item size, and can update the register as it goes. RISC-V only adds a small fixed number; anything more takes extra instructions.

Example. rdi = 0x1000 holds an int array and rsi = 3: x86-64 mov eax, [rdi + rsi*4] reads 0x100C. ARM64 with x0 = 0x1000, x1 = 3: ldr w2, [x0, x1, lsl #2] reads 0x100C. RISC-V: slli t0, a1, 2, add t0, a0, t0, lw a2, 0(t0) reads 0x100C.

Why this rule exists. Array elements, struct fields and local variables are all "a base address plus a computed distance". Building that arithmetic into the memory operand saves instructions; RISC-V keeps it minimal so every instruction stays simple to decode.

Formal. For an n-bit flag-setting add r = a + b or subtract r = a − b:

x86-64 add, sub, neg and the logic instructions set flags; mov and lea never do; inc/dec leave CF alone. ARM64 sets NZCV only from the S forms (adds, subs, ands) and the compares built on them (Chapter 9). RISC-V has no flags: comparisons write a register (slt, sltu) or branch directly.

In plain English. After arithmetic the processor answers four yes/no questions about the result: is it zero, is its top bit set, did the unsigned answer wrap, and did the signed answer come out with the wrong sign. One trap: when subtracting, ARM64's carry means "no borrow", the opposite of x86-64's.

Example. 8-bit 0x7F + 0x01 = 0x80: Z 0, N 1, C 0, V 1 (127 + 1 overflowed as signed; no unsigned wrap). 8-bit 0x01 − 0x02 = 0xFF: x86-64 CF = 1 (borrow), ARM64 C = 0; both report negative and no signed overflow.

Why this rule exists. The adder computes one bit pattern for signed and unsigned values alike. The flags record both readings, and the conditional instructions that follow choose the one that matches the program's types.

Formal. For n-bit two's-complement addition a + b, signed overflow occurs exactly when a and b have the same sign bit and the result's sign bit differs from it. Adding values of opposite sign never overflows. Unsigned wraparound (the carry out of bit n−1) is a separate condition.

In plain English. Two positives can't add up to a negative, and two negatives can't add up to a positive — if the stored answer says they did, it didn't fit. Carry asks a different question: did the unsigned answer wrap past the top?

Example. 8 bits: 100 + 100 = 200 doesn't fit in −128..127; the stored pattern 1100 1000 reads as −56 (overflow, no carry). −1 + 1: 1111 1111 + 0000 0001 = 1 0000 0000, carry out 1, result 0 — correct, no overflow.

Why this rule exists. Processors compute one sum and report both conditions; signed and unsigned code each check the one that matters to them.

Formal. After a compare of a with b (a − b):

Signed conditions use the words less/greater (l, g, lt, gt); unsigned ones use below/above (b, a) on x86-64 and lower/higher (lo, hi, ls, hs) on ARM64. RISC-V's bgt, ble, bgtu, bleu are pseudo-instructions that swap the operands.

In plain English. The compare is the same either way; the branch decides whether the bits are read as signed or unsigned numbers. "Less" and "greater" mean signed; "below", "above", "lower" and "higher" mean unsigned. Equal and not-equal don't care.

Example. Compare −1 with 1. As signed, −1 < 1, so jl / b.lt / blt are taken. As unsigned, −1's pattern is the largest value, so jb / b.lo / bltu are not taken.

Why this rule exists. Two's complement lets one subtractor serve both kinds of number, so the ISA moves the signed-or-unsigned choice to the condition. The compiler picks it from the C++ types being compared.

Formal.

• x86-64: call target does rsp ← rsp − 8, [rsp] ← address of the next instruction, rip ← target. ret does rip ← [rsp], rsp ← rsp + 8.
• ARM64: bl target (or blr xn) does x30 ← address of the next instruction, pc ← target; memory is not touched. ret does pc ← x30.
• RISC-V: jal ra, target (written call or jal target) does ra ← address of the next instruction, pc ← target. ret is jalr zero, 0(ra): pc ← ra.

So a function's return address is at [rsp] on entry on x86-64, and in x30 or ra on ARM64 and RISC-V; a function that makes calls of its own must save x30 or ra (usually at its start) before the first one.

In plain English. A call is a jump that first remembers where to come back to. x86-64 writes that place on the stack; ARM64 and RISC-V put it in a register. Return just jumps back to the remembered place, the instruction after the call.

Example. At 0x1000, call f (5 bytes) with rsp = 0x7FF0 leaves rsp = 0x7FE8 holding 0x1005 at [0x7FE8]; ret in f jumps to 0x1005 and restores rsp = 0x7FF0. On ARM64, bl f at 0x4000 sets x30 = 0x4004.

Why this rule exists. The same function is called from many places, so the way back must be recorded at run time. Keeping it in a register is faster for functions that call nothing else; keeping it on the stack makes nested calls automatic.

Formal. Across a call, a callee-saved register must hold the same value on return as on entry (the callee saves and restores it if it uses it); a caller-saved register may hold anything on return (a caller that needs its value afterwards saves it before the call).

Every register not listed as callee-saved (and not reserved, like ARM64's x18 on Apple and Windows) is caller-saved, including all argument and result registers and the return-address register x30 / ra.

In plain English. Some registers are promised to survive a call, and any function that borrows one has to put it back. The rest may be wiped by any call, so if you still need one, keep a copy somewhere safe first.

Example. On x86-64 Linux, a value kept in rbx survives call f; one kept in rcx may not. A function that uses r12 starts with push r12 and ends with pop r12 before ret.

Why this rule exists. Splitting the registers lets short functions use the caller-saved ones with no saving at all, while long-lived values sit in callee-saved ones and cost a save only in functions that need them.

Formal. For an array of type T whose first element is at address base, element i is at base + i × sizeof(T). In C++, for T* p, the expression p + i means exactly that address, and p[i] is *(p + i).

In plain English. Elements sit side by side, each taking the same number of bytes, so finding element i is a multiplication and an addition — no searching.

Example. An int array starting at 0x1000: element 3 is at 0x1000 + 3 × 4 = 0x100C. A std::int16_t array at the same place: element 3 is at 0x1000 + 3 × 2 = 0x1006.

Why this rule exists. It is why array indexing is fast, why indexes start at 0, and why the addressing modes in Chapter 7 have a "scale" part.

Formal. For a C/C++ struct (standard layout, no packing directives) with fields f₁ … fₖ in declaration order:

1. offset(f₁) = 0;
2. offset(fᵢ) = the smallest multiple of alignof(fᵢ) that is ≥ offset(fᵢ₋₁)
   • sizeof(fᵢ₋₁);
3. alignof(struct) = the largest alignof(fᵢ);
4. sizeof(struct) = offset(fₖ) + sizeof(fₖ) rounded up to a multiple of alignof(struct).

The bytes skipped in step 2 and step 4 are padding.

In plain English. Place the fields in order, sliding each one forward until it starts on a multiple of its own alignment. Then round the total up so that the next struct in an array starts properly aligned too.

Example. struct S { char c; int i; char d; };: c at 0, i at 4 (after 3 padding bytes), d at 8, then 3 bytes of tail padding: sizeof 12, alignof 4. Reordered as { int i; char c; char d; }: offsets 0, 4, 5, sizeof 8.

Why this rule exists. Aligned values can be loaded in one access and some instructions require it; the ABI fixes this rule so that separately compiled C++ and assembly agree on every field's offset.

Formal. For a call p->f(args) to the virtual function in vtable slot k, through a pointer p to a polymorphic object (vptr at offset 0, 8-byte slots):

1. vptr ← [p] (load the object's vtable pointer);
2. target ← [vptr + 8k] (load slot k);
3. call target indirectly, with p passed as the hidden this argument.

x86-64 (System V): mov rax, [rdi] then call [rax + 8*k]. ARM64: ldr x8, [x0], ldr x8, [x8, #8*k], blr x8. RISC-V: ld t0, 0(a0), ld t0, 8*k(t0), jalr t0.

In plain English. Each object carries a hidden pointer to its class's table of function addresses. A virtual call reads that pointer, reads the right entry from the table, and calls whatever address it finds, so the object's real class decides which function runs.

Example. Base Shape declares virtual area() in slot 0 and virtual name() in slot 1. For s->name() with s in rdi, the compiler emits mov rax, [rdi] and call [rax + 8]. A Circle and a Square share this code but hold different vptrs, so different functions run.

Why this rule exists. The compiler cannot know an object's real class at a call through a base pointer. One table per class plus one pointer per object makes the run-time choice cost two loads and an indirect call.

Formal. A binary32 (binary64) pattern has a sign bit s, a w-bit exponent field E (w = 8, bias 127; w = 11, bias 1023) and a fraction field f of 23 (52) bits. When 0 < E < 2^w − 1, its value is

(−1)^s × 1.f × 2^(E − bias).

The two remaining exponent patterns, E = 0 and E = 2^w − 1, are reserved for special values with their own decoding rules (Section 15.4).

In plain English. A float is binary scientific notation. One bit says plus or minus. The exponent field says which power of two to scale by, stored with a fixed number added so it is never negative. The fraction field holds the digits after the point, and a 1 sits in front of them without being stored. Two exponent patterns, all zeros and all ones, are set aside for special cases.

Example. The float pattern 0xC0A00000 is 1 10000001 01000000000000000000000. s = 1, E = 129, so the power is 129 − 127 = 2; f = .01 in binary, so the significand is 1.01₂ = 1.25. The value is −1.25 × 2² = −5.0.

Why this rule exists. A fixed number of bits must cover values from about 10^−38 to 10^38 (float) with the same relative precision everywhere. Storing a power of two separately from the significant digits does that, and the hidden 1 and the bias each buy one more useful bit or an easy unsigned comparison.

Formal. Under the default IEEE 754 rounding mode, the result of +, −, ×, ÷ and √ is the exact real result rounded to the nearest representable value; when the exact result lies exactly halfway between two representable values, the one whose least significant significand bit is 0 is chosen. Consequently |fl(x) − x| ≤ ½ ulp(x), and for normal results the relative error is at most ε/2, where ε is machine epsilon (2^−23 for binary32, 2^−52 for binary64).

In plain English. The hardware works out the true answer, then keeps the closest number it can store. If the true answer is exactly in the middle, it picks the neighbour whose last bit is 0. So every single operation is off by at most half a step of the last bit.

Example. At 2^24 a float's step is 2, so 16,777,216 and 16,777,218 are neighbours. 16,777,217 is exactly between them; 16,777,216 has the even last bit, so float(16777217) is 16,777,216. 16,777,219 lies between 16,777,218 (odd) and 16,777,220 (even), so it rounds up to 16,777,220.

Why this rule exists. Always rounding halves up would push long sums steadily upward. Choosing the even neighbour sends ties up half the time and down half the time, and fixing one rule makes every conforming processor give bit-identical results for the same operation.

Formal. With p significand bits (24 for binary32, 53 for binary64), every normal x with 2^e ≤ |x| < 2^(e+1) has neighbours a distance

ulp(x) = 2^(e − p + 1)

away. Machine epsilon is ε = ulp(1) = 2^(1 − p): 2^−23 ≈ 1.19 × 10^−7 for float, 2^−52 ≈ 2.22 × 10^−16 for double (std::numeric_limits<T>::epsilon()). Subnormals are all evenly spaced 2^(2 − bias − p) apart, the same gap as the smallest normal numbers (2^−149 for float, 2^−1074 for double).

In plain English. Between two powers of two, floats are evenly spaced. Each time you cross a power of two, the spacing doubles. So small numbers are packed tightly and large numbers are far apart, while the gap stays about the same size relative to the number itself.

Example. A double near 1.0 has neighbours 2^−52 apart. Near 10^16, which lies between 2^53 and 2^54, the gap is 2^(53 − 52) = 2, so 1e16 + 1.0 rounds back to 1e16 and the 1.0 is lost.

Why this rule exists. The exponent field scales the same p-bit significand by a power of two, so the step of the last bit is scaled too. This is what lets one format span tiny and huge values with a fixed number of significant digits.

Formal. Comparing two floating-point values has four mutually exclusive outcomes: less, equal, greater, unordered. The outcome is unordered exactly when at least one operand is a NaN. Then <, <=, ==, >= and > are all false and != is true. In hardware: x86-64 ucomisd sets ZF = PF = CF = 1; ARM64 fcmp sets NZCV = 0011; RISC-V feq.d, flt.d and fle.d write 0.

In plain English. A NaN means "no sensible number", so it is not less than, equal to, or greater than anything, not even itself. Every comparison that asks "is it less / equal / greater?" answers no, and "is it different?" answers yes.

Example. For double x = 0.0 / 0.0;, x == x is false and x != x is true. Clang -O2 on x86-64 compiles if (a == b) g(); as ucomisd xmm0, xmm1, jne skip, jp skip, then a jump to g: the branch to g needs ZF = 1 (equal) and PF = 0 (not unordered).

Why this rule exists. If a NaN compared equal to something, an invalid result could pass a check meant for real numbers. Making every ordered comparison false lets code detect NaNs (with x != x or std::isnan) and keeps them from silently satisfying a test.

Formal. Floating-point addition is commutative (a ⊕ b = b ⊕ a for non-NaN a, b) but not associative: in general (a ⊕ b) ⊕ c ≠ a ⊕ (b ⊕ c), because each ⊕ rounds its exact result. The same holds for multiplication. A conforming compiler therefore may not reassociate FP expressions unless explicitly permitted (for example -ffast-math or -fassociative-math).

In plain English. For floats, the order you add things in can change the answer, because every addition rounds a little. Swapping the two sides of one addition is safe; regrouping three or more numbers is not.

Example. In double precision, (0.1 + 0.2) + 0.3 gives 0.6000000000000001, while 0.1 + (0.2 + 0.3) gives 0.6. And (1e16 + 1.0) − 1e16 is 0.0, while (1e16 − 1e16) + 1.0 is 1.0.

Why this rule exists. Rounding happens after every operation, and the rounding error depends on the size of the intermediate result. Different groupings produce different intermediates, so they lose different bits. This is why compilers keep FP sums in source order, and why splitting a float sum into several partial sums needs permission.

Formal. A C++ implementation may transform a program in any way, provided that, for every program execution without undefined behaviour, the observable behaviour is that of the abstract machine: the sequence of accesses through volatile glvalues, the data written to files by termination, and the prompting and input/output of interactive devices. For an execution that has undefined behaviour, no requirement applies.

In plain English. The compiler may rewrite, reorder, merge or delete your code however it likes, as long as what the outside world can see — the output, the files, any volatile accesses — comes out the same. If the program does something undefined, the compiler owes it nothing at all.

Example. int f() { int s = 0; for (int i = 1; i <= 100; ++i) s += i; return s; } compiles at -O2 to the equivalent of return 5050;. The loop is gone, but nothing observable changed: f still returns 5050.

Why this rule exists. Without it, every optimization would need its own permission in the language standard. One rule — keep the visible behaviour — licenses constant folding, inlining, dead-code elimination and the rest, and explains why a benchmark whose result is unused may measure nothing.

Formal. An x86-64 instruction is 1 to 15 bytes made of these parts, always in this order; every part except the opcode may be absent:

1. instruction prefixes, 0 to 4 bytes (e.g. 66 operand size 16, f0 lock, f2/f3);
2. REX prefix, 0 or 1 byte, 0100WRXB, immediately before the opcode: W = 1 selects 64-bit operands; R, X and B add a fourth (high) bit to the ModRM reg field, the SIB index and the ModRM r/m (or SIB base) field;
3. opcode, 1 to 3 bytes;
4. ModRM byte, 0 or 1: mod (2 bits) | reg (3) | r/m (3). mod = 11 means r/m is a register; otherwise r/m names a memory form, with mod = 01 adding an 8-bit and mod = 10 a 32-bit displacement. r/m = 100 with a memory mod means a SIB byte follows; mod = 00 with r/m = 101 means rip + 32-bit displacement;
5. SIB byte, 0 or 1: scale (2 bits: ×1, ×2, ×4, ×8) | index (3) | base (3);
6. displacement, 0, 1 or 4 bytes, signed, little-endian (8 only for the movabs forms that load or store at a full 64-bit address);
7. immediate, 0, 1, 2 or 4 bytes (8 only for mov r64, imm64), little-endian.

Register numbers: rax 0, rcx 1, rdx 2, rbx 3, rsp 4, rbp 5, rsi 6, rdi 7, r8 to r15 are 8 to 15 (the REX bit supplies the 8).

In plain English. Read an x86-64 instruction from left to right: optional bytes that adjust it, an optional byte that means "64-bit" or "one of the new registers", the byte or bytes saying which operation, a byte saying which registers (or what kind of memory address), maybe a byte for an index register and scale, then the fixed number in the address, then the constant. Because each part may or may not be there, the length changes from instruction to instruction.

Example. mov rax, [rdi + rsi*4 + 8] encodes as 48 8b 44 b7 08: 48 is REX with W = 1 (64-bit); 8b is the opcode "load a register from r/m"; ModRM 44 = 01 000 100: mod 01 (8-bit displacement), reg 000 (rax), r/m 100 (a SIB byte follows); SIB b7 = 10 110 111: scale ×4, index 110 (rsi), base 111 (rdi); the displacement byte is 08. Five bytes in all.

Why this rule exists. x86-64 descends from the 8086, whose instructions were already 1 to 6 bytes long. Each later extension added parts in front (prefixes, then REX) rather than changing the existing bytes, so old encodings stayed valid and the lengths grew more varied. The processor and every disassembler must work out each length by decoding the parts in order.

Formal. For a direct jump, conditional branch or call at address A, with signed branch offset k stored in its instruction encoding:

• x86-64: target = A + L + k, where L is the branch's own length in bytes (so A + L is the address of the next instruction). k is stored in 1 byte (rel8, range −128 to 127) or 4 bytes (rel32).
• ARM64: target = A + 4k. b and bl store k in 26 bits (±128 MiB); b.cond, cbz/cbnz store it in 19 bits (±1 MiB).
• RISC-V: target = A + k, where k is always even. jal stores it in 20 bits (±1 MiB); beq, bne and the other branches in 12 bits (±4 KiB).

Since only the distance A-to-target is stored, moving the branch and its target together by the same amount leaves the encoding unchanged.

In plain English. A branch doesn't store where to go. It stores how far to go from where it is. x86-64 counts the distance from the end of the branch; ARM64 and RISC-V count from the branch itself, and ARM64 counts in whole 4-byte instructions. Because it is a distance, the same bytes work wherever the code ends up in memory.

Example. A 2-byte x86-64 jmp at 0x1000 encoded eb 10 lands at 0x1000 + 2 + 0x10 = 0x1012. An ARM64 b at 0x1000 with k = 4 lands at 0x1000 + 16 = 0x1010. A RISC-V beq at 0x1000 with k = 16 lands at 0x1010 when taken. eb fe (k = −2) is an x86-64 jump to itself.

Why this rule exists. Most branches stay inside one function, so a small distance fits in a few bits where a full 64-bit address never could. Counting from the branch also means code can be placed at any address without rewriting its jumps.

Formal. A relocation entry names a place in a section (offset), a relocation type, a symbol and an addend (stored in the entry for ELF RELA; in the patched bytes for Mach-O and COFF). Once final addresses are chosen, let S = the symbol's address, A = the addend, and P = the address of the place being patched. Then

• a PC-relative relocation type writes S + A − P;
• an absolute relocation type writes S + A;

truncated to the field width the type names (e.g. 32 bits for ELF R_X86_64_PC32, 64 bits for R_X86_64_64), and it is an error if the value doesn't fit. ELF x86-64 and ARM64 objects store A in the entry; Mach-O and COFF objects store it in the bytes being patched.

In plain English. The assembler leaves blank bytes and a note: "put the address of this symbol here, plus a small adjustment". When the final addresses are known, the blank is filled in either with the address itself or, for PC-relative instructions, with the distance from the blank to the symbol.

Example. lea rax, [rip + msg] sits at .text offset 0x20 as 48 8d 05 00 00 00 00; its 4-byte field starts at offset 0x23, with an R_X86_64_PC32 entry for msg and addend −4 (rip already points 4 bytes past the field's start when the instruction runs). If .text is placed at 0x401000 and msg at 0x402010: P = 0x401023, and S + A − P = 0x402010 − 4 − 0x401023 = 0xfe9, written e9 0f 00 00. Check: the next instruction starts at 0x401027, and 0x401027 + 0xfe9 = 0x402010.

Why this rule exists. One formula covers every unfinished place: the note says which symbol, the type says which formula and how many bits, and the addend absorbs details like "measured from the end of the instruction". The tool that finally places the code needs nothing else.

Formal. Across all the object files being linked, consider each global symbol name:

• referenced (undefined in some file) and defined in exactly one file: every reference is resolved to that definition;
• referenced but defined in no file: an undefined-symbol error;
• defined in two or more files: a duplicate-symbol error,

with two sanctioned exceptions. A weak definition (ELF, Mach-O) yields to a normal one, and if all are weak the linker keeps one. Definitions the compiler marks as mergeable (C++ inline functions, template instances and vtables: COMDAT on ELF and COFF, coalesced weak definitions on Mach-O) are expected to repeat, and one copy is kept. Local symbols never take part: they are visible only inside their own file.

In plain English. Every public name must have exactly one home. If a file uses a name nobody provides, the link fails with "undefined". If two files both provide it, the link fails with "duplicate", unless the compiler marked the copies as interchangeable (as it does for inline functions and templates), in which case the linker keeps one.

Example. main.o lists total as U and sum.o lists it as T: resolved. Drop sum.o and the link stops with an undefined symbol total. Add a second file that also defines long total = 0; and the link stops with a duplicate symbol. Make one of them static and it becomes local, out of the contest.

Why this rule exists. A call or load in one file must reach exactly one place in the finished program. Zero homes leaves an instruction with nowhere to go; two homes would make the program's meaning depend on which one the linker happened to pick.

Formal. A relocation entry names a place in a section (offset), a relocation type, a symbol and an addend (stored in the entry for ELF RELA; in the patched bytes for Mach-O and COFF). Once final addresses are chosen, let S = the symbol's address, A = the addend, and P = the address of the place being patched. Then

• a PC-relative relocation type writes S + A − P;
• an absolute relocation type writes S + A;

truncated to the field width the type names (e.g. 32 bits for ELF R_X86_64_PC32, 64 bits for R_X86_64_64), and it is an error if the value doesn't fit. ELF x86-64 and ARM64 objects store A in the entry; Mach-O and COFF objects store it in the bytes being patched.

In plain English. The assembler leaves blank bytes and a note: "put the address of this symbol here, plus a small adjustment". When the final addresses are known, the blank is filled in either with the address itself or, for PC-relative instructions, with the distance from the blank to the symbol.

Example. lea rax, [rip + msg] sits at .text offset 0x20 as 48 8d 05 00 00 00 00; its 4-byte field starts at offset 0x23, with an R_X86_64_PC32 entry for msg and addend −4 (rip already points 4 bytes past the field's start when the instruction runs). If .text is placed at 0x401000 and msg at 0x402010: P = 0x401023, and S + A − P = 0x402010 − 4 − 0x401023 = 0xfe9, written e9 0f 00 00. Check: the next instruction starts at 0x401027, and 0x401027 + 0xfe9 = 0x402010.

Why this rule exists. One formula covers every unfinished place: the note says which symbol, the type says which formula and how many bits, and the addend absorbs details like "measured from the end of the instruction". The tool that finally places the code needs nothing else.

Formal. A linker keeps a set U of currently undefined symbols while it reads its inputs.

• An object file named on the command line is always included; its undefined symbols join U and its definitions leave it.
• From a static library (archive), only a member that defines some symbol currently in U is included, and its own undefined symbols join U in turn.
• GNU ld (BFD) and gold read inputs left to right and search each archive only at its position, repeating within that archive until it adds nothing, then never return to it (unless the archives are grouped with --start-group … --end-group).
• lld, Apple's ld64 and MSVC link.exe remember every archive's symbols, so a symbol needed later can still be found in an archive named earlier.

In plain English. The linker only pulls a piece out of a library if something already needs it. The traditional Linux linker looks into each library once, when it reaches it on the command line, so a library has to come after the files that use it. Newer linkers, and the macOS and Windows ones, look back, so order rarely matters there.

Example. main.o calls square, which lives in libmath.a. With GNU ld, cc main.o -L. -lmath links: when -lmath is reached, square is in U and its member is pulled in. cc -L. -lmath main.o fails with an undefined reference to square: when the archive was searched, U was still empty. The same second command links with lld or on macOS.

Why this rule exists. Pulling in only needed members keeps programs small, and a single left-to-right pass kept early Unix linkers fast and simple. The cost is the order dependence, which newer linkers removed by indexing all archives first.

Formal. On Linux, a system call puts its system call number and up to six arguments in registers, executes the system call instruction, and receives one result:

A result from −4095 to −1 is an error: the negated error code (−errno). On x86-64, syscall overwrites rcx (with the return address) and r11 (with the flags), which is why argument 4 uses r10 instead of rcx. Numbers are fixed per ISA: write is 1 and exit is 60 on x86-64; write is 64 and exit is 93 on ARM64 and RISC-V.

In plain English. To ask the Linux kernel for something, put the number of the service in one register and the details in the next few, then run the one special instruction that switches into kernel mode. The answer comes back in a register, and a small negative answer means it failed. The registers are almost the function-call ones; on x86-64 the fourth detail moves from rcx to r10.

Example. Write 6 bytes from msg to standard output (file 1) on x86-64 Linux: mov eax, 1 / mov edi, 1 / lea rsi, [rip + msg] / mov edx, 6 / syscall. Afterwards rax holds 6, the number of bytes written. On ARM64 the same call is mov x8, #64, mov x0, #1, the address in x1, mov x2, #6, svc #0.

Why this rule exists. The kernel can't trust the program's stack or its calling convention, so it takes everything in registers it reads the moment it is entered. Linux promises never to renumber its system calls, so programs that use these numbers keep working on every later kernel. That promise is Linux's own; the other operating systems this course covers make no such promise.

Formal. Split an instruction's work into k pipeline stages of equal length, starting one instruction per clock cycle. Then n instructions take k + (n − 1) cycles instead of the n × k cycles they would take one at a time. That gives the speedup below.

The limit k is reached only in the ideal case. Real stages are unequal, and the cycle must fit the slowest one. Each pipeline register also adds a fixed delay to every stage. Say the total work t is split into k stages, the slowest takes t_max ≥ t / k, and r is the register overhead. Then the cycle time is t_max + r, and the speedup over a single-cycle design is at most t / (t_max + r) < k.

In plain English. If every instruction goes through k steps and a new one can start every tick, then once the pipeline is full one instruction finishes every tick, instead of one every k ticks. So k steps can make a long run of instructions up to k times faster, never more. Steps that aren't the same size, and the small cost of passing work from one step to the next, keep the real gain below k. No single instruction gets faster: each one still passes through all k steps.

Example. A five-stage pipeline runs 100 instructions in 5 + 99 = 104 cycles, against 500 one at a time: a speedup of about 4.8. Now say the single-cycle design needed 5 ns per instruction. If the slowest stage needs 1.2 ns and each pipeline register adds 0.1 ns, the cycle is 1.3 ns. The best speedup is then 5 / 1.3 ≈ 3.8, not 5.

Why this formula exists. Pipelining is the first and largest reason modern processors finish far more than one instruction per cycle time of their slowest step, and this bound says exactly what it can and can't buy. It is why designers balance their stages, and why adding stages eventually stops paying.

Formal. In the five-stage pipeline (fetch, decode, execute, memory, write-back) with full forwarding:

• An ALU result is ready at the end of the execute stage, so the very next instruction can use it in its own execute stage: 0 stall cycles.
• A loaded value is ready only at the end of the memory stage. An instruction that uses it immediately after the load reaches execute one cycle too early, so it must stall 1 cycle; if one independent instruction sits between the load and its use, there is no stall.
• Without forwarding, a dependent instruction waits until the producer's write-back: 2 stall cycles after an ALU instruction (with the register file written in the first half of a cycle and read in the second), 2 after a load as well.

In plain English. Forwarding hands a result straight to the next instruction as soon as it exists. An addition's result exists right after the arithmetic step, so the next instruction gets it in time. A load's value exists only after the memory step, one step later, so an instruction that needs it straight away has to wait one tick: nothing can hand over a value that hasn't arrived yet.

Example. RISC-V: ld a1, 0(a0) then add a2, a1, a3 stalls 1 cycle. Reordering to ld a1, 0(a0) / addi a0, a0, 8 / add a2, a1, a3 puts an independent instruction in the gap and removes the stall; compilers schedule loads early for exactly this reason.

Why this rule exists. The memory step comes after the execute step because a load must first compute its address. That ordering is what makes the loaded value one stage later than an ALU result, and why this one data hazard survives forwarding in any pipeline of this shape.

Formal. For one program on one processor,

where CPI (cycles per instruction) is total cycles divided by instructions executed. For a pipeline that can start one instruction per cycle,

with ideal CPI = 1 and the stall term summing the structural, data (load-use) and control (branch penalty) cycles averaged over all instructions: for example, branch fraction × fraction of those that flush × branch penalty.

In plain English. How long a program takes is: how many instructions it runs, times how many ticks each one needs on average, times how long one tick lasts. A simple pipeline would need exactly one tick per instruction if nothing ever had to wait; every wait adds a little to that average.

Example. 10⁹ instructions at 2 GHz. 20% are loads, and half of those are followed straight away by an instruction that uses the value (1 stall cycle each); 15% are branches, a third of them flush 2 instructions. CPI = 1 + 0.20 × 0.5 × 1 + 0.15 × (1/3) × 2 = 1 + 0.10 + 0.10 = 1.20. Time = 10⁹ × 1.20 / (2 × 10⁹ per second) = 0.6 s; with no stalls it would be 0.5 s.

Why this formula exists. The three factors come from different places: the program and compiler set the instruction count, the microarchitecture sets CPI, and the circuits and power budget set the clock rate. The equation shows why no one factor settles speed, and lets you check a claimed improvement for what it costs the other two.

Formal. A two-bit saturating counter holds a state c ∈ {0, 1, 2, 3}: 0 strongly not taken, 1 weakly not taken, 2 weakly taken, 3 strongly taken.

• Predict taken if c ≥ 2, not taken if c ≤ 1.
• Update after the branch resolves: taken → c = min(c + 1, 3); not taken → c = max(c − 1, 0).

A prediction changes only after two outcomes in a row disagree with it from a strong state. For a loop branch taken N − 1 times and then not taken once per run, the counter mispredicts once per run in steady state, where a one-bit predictor (which predicts the last outcome) mispredicts twice.

In plain English. Keep a score from 0 to 3. Add one when the branch jumps, subtract one when it doesn't, and never go past 0 or 3. Guess "jumps" when the score is 2 or 3. Because it takes two surprises in a row to change the guess, one odd outcome, such as a loop ending, doesn't make the predictor forget what the branch usually does.

Example. A loop branch runs T T T N (taken three times, then the exit), and the loop runs again. Starting at 3: T, T, T predicted taken, counter stays 3; N mispredicted, counter drops to 2; the next run's first T is predicted taken (2 ≥ 2), correct, back to 3. One misprediction per run. A one-bit predictor mispredicts the N and then the next run's first T: two per run.

Why this rule exists. Most branches lean strongly one way with occasional exceptions. A counter with hysteresis keeps its lean through an exception and costs only two bits per entry, which is why it is the building block of real predictors, which pick the counter using the branch's address and recent history.

Formal. Between an earlier instruction I and a later instruction J in program order:

• Read after write (true): J reads a register I writes. J needs I's value; it must wait for it.
• Write after read (anti, WAR): J writes a register I reads.
• Write after write (output, WAW): J writes a register I also writes.

If every write is given a newly allocated physical register, and every read uses the physical register mapped to its architectural register at that point in program order, then every WAR and WAW dependence disappears; only true dependences constrain execution order.

In plain English. Two instructions are really tied together only when one uses a value the other makes. If they merely reuse the same register name, the processor gives the new value a fresh hidden register of its own, and the old value stays put for whoever still needs it. Then neither has to wait for the other.

Example. x86-64: mov eax, [rdi] / add eax, 1 / mov [rsi], eax / mov eax, [rdx] / add eax, 2 / mov [rcx], eax. The second group reuses eax: its first mov has a WAR dependence on the store above and a WAW dependence on the earlier writes. After renaming, the first group's eax is, say, p17 and p18, the second group's is p40 and p41, and the two groups can run at the same time; within each group, the true dependences still order the load, the add and the store.

Why this rule exists. An instruction set has only 16 or 31 general-purpose registers, so compilers must reuse names constantly. Without renaming, a wide core would spend its time waiting on name clashes rather than on real data; with it, a few hundred physical registers let it overlap independent work.

Formal. For a loop of n iterations on an out-of-order core, the time in cycles is at least the larger of two bounds:

Here L_chain is the total latency of the loop-carried dependency chain in one iteration. For each resource r (issue width, each group of execution units), u_r is the work one iteration puts on it, and c_r is how much of that work it can accept per cycle. Splitting a loop-carried chain across k independent accumulators divides the first bound by k, until the throughput bound takes over: the best k is about latency × (operations per cycle the units accept).

In plain English. A loop can't run faster than its slowest requirement. If each step needs the previous step's result, the steps form a chain and the loop takes at least one chain-length per step, no matter how wide the processor is. If the steps are independent, the limit is instead how many operations the hardware can start per tick. Splitting one running total into several makes the chain shorter until the hardware itself becomes the limit.

Example. Summing doubles with one accumulator: each addsd (or fadd) waits for the previous one, so with a 4-cycle add latency the loop takes about 4 cycles per element. With two add units, each accepting one add per cycle, the throughput bound is 0.5 cycles per element, so about 4 × 2 = 8 accumulators approach it. Because this reassociates floating-point addition, the result can differ in the last bits, and compilers make this change only when allowed.

Why this formula exists. Out-of-order hardware finds independent work but cannot shorten a chain of true dependences. Knowing which bound applies tells you whether to restructure the computation (latency-bound) or reduce the operations (throughput-bound).

Formal. For one cache level,

In a hierarchy the miss penalty of one level is the average access time of the level below it, so for an L1 cache backed by an L2 cache and memory,

where each t is a hit time (or memory's access time) and each m is a local miss rate: the fraction of the accesses reaching that level that miss there.

In plain English. Every access pays the time to look in the fast cache. Only the accesses that miss also pay for the trip further down, so you add that trip's cost weighted by how often it happens. If the next level is itself a cache, its own cost is worked out the same way first.

Example. L1: hit time 4 cycles, miss rate 5%. L2: hit time 14 cycles, local miss rate 20%. Memory: 300 cycles. The L2 average is 14 + 0.20 × 300 = 74 cycles, so AMAT = 4 + 0.05 × 74 = 7.7 cycles. With no L2 it would be 4 + 0.05 × 300 = 19 cycles. These are model figures of the size published for current cores, not measurements.

Why this formula exists. A cache's worth depends on both how fast its hits are and how often it misses, and a small change in miss rate can matter more than a faster hit. AMAT puts both in one number, so two designs, or two versions of a loop, can be compared.

Formal. Take a cache of C bytes with lines of B bytes and N lines in each group that an index selects (N = 1 for a direct-mapped cache). All three are powers of two. The number of groups is S = C / (B × N). An m-bit address splits into three fields, from the high end down:

The line offset is address mod B. The index is ⌊address / B⌋ mod S, and the tag is ⌊address / (B × S)⌋.

In plain English. The lowest bits say which byte inside a line you want; there must be enough of them to count every byte in a line. The next bits say where in the cache to look; there must be enough of them to count every place. Whatever bits are left over are the tag, kept so the cache can tell which of the many lines that share that place is the one sitting there.

Example. A 1 KiB direct-mapped cache with 64-byte lines has 1024 / 64 = 16 places, so b = 6 and s = 4. For the 32-bit address 0x00001234: line offset = 0x1234 & 0x3F = 0x34, index = (0x1234 >> 6) & 0xF = 0x8, tag = 0x1234 >> 10 = 0x4. The address 0x00001634 has the same offset and index but tag 0x5, so in this cache the two lines compete for place 8.

Why this formula exists. Every cache lookup is this split done in hardware with wires instead of arithmetic. Knowing it lets you predict which addresses share a place in the cache, and so which access patterns will keep throwing each other out.

Formal. Classify each miss in an address trace against a given cache:

1. Compulsory if it is the first reference to that cache line in the trace (it would miss in an infinitely large cache).
2. Otherwise capacity if a fully associative LRU cache with the same total number of lines would also miss it.
3. Otherwise conflict: only the restricted placement (too many lines competing for one set) caused it.

Remedies follow the class: compulsory misses fall with larger lines or prefetching, capacity misses with a larger cache or with code that keeps less data in use at once, conflict misses with higher associativity or a different stride or layout.

In plain English. Ask three questions about each miss. Was this the first time the line was ever used? Then nothing could have saved it. Would a cache of the same size that could put anything anywhere also have missed? Then the data simply doesn't fit. If not, the miss happened only because too many lines wanted the same few slots.

Example. A direct-mapped cache with 4 lines of 16 bytes (index = (address >> 4) & 3). The trace 0x000, 0x040, 0x000, 0x040: both addresses have index 0. The first two accesses are compulsory misses. The third and fourth also miss, but a 4-line fully associative cache would hold both lines and hit, so they are conflict misses. A loop cycling through five different lines in a 4-line fully associative LRU cache misses on every access after the first five: capacity misses.

Why this rule exists. Each kind of miss has a different cure, and the wrong cure (more ways for a capacity problem, a bigger cache for compulsory misses) costs hardware or effort and fixes nothing.

Formal. With pages of 2^p bytes, a virtual address VA splits into a page number VPN and an offset:

In bits, VPN is VA >> p and the offset is VA & (2^p − 1). Suppose the page table entry for VPN holds page frame number PFN. Then the physical address is

Translation replaces the page number and never changes the offset.

In plain English. Cut the address in two. The low part, enough bits to count every byte in a page (12 bits for 4 KiB), says where inside the page you are, and it stays the same. The high part says which page; look it up in the page table to learn which slot of real memory holds that page, and put that slot's number in front of the unchanged low part.

Example. 4 KiB pages, so p = 12. VA 0x7f3a1c48 gives VPN 0x7f3a1 and offset 0xc48. If the page table maps page 0x7f3a1 to frame 0x2b04, then PA = 0x2b04 × 0x1000 + 0xc48 = 0x2b04c48. With 16 KiB pages (p = 14) the same VA would split differently: VPN 0x1fce8, offset 0x1c48.

Why this formula exists. It is the whole contract between a program's addresses and real memory. The program keeps its own consistent numbering, and the operating system chooses where each page really lives. The low bits pass straight through, so translation only has to be done once per page, not once per byte.

Formal. With 4 KiB pages and 48-bit virtual addresses (x86-64 four-level paging; ARM64 with a 4 KiB granule), each table holds 512 eight-byte entries, so each level consumes 9 bits:

index_k = (VA >> (12 + 9(k − 1))) & 0x1FF. The walk starts at the table whose physical address is in the page-table base register (cr3, TTBR0_EL1), and each entry read gives the physical address of the next table, so a full walk is four dependent memory reads. On x86-64, bits 63–48 must all equal bit 47 (a canonical address). Five-level paging adds a 9-bit level above (bits 56–48) for 57-bit addresses; RISC-V Sv39/Sv48 use the same 9-bit, 4 KiB scheme with three or four levels.

In plain English. One giant table would need an entry for every page a program could possibly have, mostly empty. Instead the page number is cut into four 9-bit pieces, each choosing one of 512 slots in a small table that points to the next table. Tables only exist for the parts of the address space a program uses.

Example. VA 0x00007f3a1c2b5c48: level-4 index 0xfe (254), level-3 index 0xe8 (232), level-2 index 0xe1 (225), level-1 index 0xb5 (181), offset 0xc48. A program using only a few megabytes needs one table at each of the top three levels and a handful of level-1 tables, a few pages in all, rather than a table covering all 2^36 possible pages.

Why this formula exists. It shows exactly what a page walk does, why a miss in the translation cache costs up to four extra memory reads, and why ending the walk one level early (a bigger page) saves work.

Formal.

A working set larger than the reach of a TLB level causes TLB misses at that level even when its data fits in the caches.

In plain English. Each remembered translation covers one page, so the TLB as a whole covers its number of entries times the page size. Use more memory than that, scattered over many pages, and the processor keeps having to look translations up again.

Example. A second-level TLB of 2048 entries with 4 KiB pages reaches 2048 × 4 KiB = 8 MiB. If the same entries hold 2 MiB huge pages, it reaches 2048 × 2 MiB = 4 GiB. A program whose working set is 64 MiB misses the TLB often with 4 KiB pages and almost never with huge pages. (Entry counts and which page sizes each level can hold vary by core; these numbers are illustrative.)

Why this formula exists. The caches are measured in bytes but the TLB in pages, and comparing the two explains why a program can slow down from translation alone, and why huge pages help large working sets.

Formal. The kernel's handler returns to the address the processor saved when the exception was taken:

• Fault (a page fault, x86-64 divide error, a general protection fault): the saved address is the faulting instruction itself, which had no effect; after the kernel fixes the cause, it runs again.
• Trap (a system call, an x86-64 int3 breakpoint): the event is reported after the instruction, and execution resumes at the next instruction. (RISC-V records the address of ecall itself, and the kernel adds 4 before returning.)
• Abort (a machine check, a double fault): the state can't be trusted, there is no restart, and the program or the machine stops.
• External interrupt: taken between two instructions, unrelated to either; the program resumes at the first instruction not yet done.

In plain English. A fault means "this instruction could not run", so once the problem is fixed the same instruction is tried again. A trap means "this instruction asked to stop here", so it carries on after it. An abort means something is too broken to carry on. An interrupt just slots in between two instructions and then lets the program carry on.

Example. A store to a page that hasn't been given memory yet faults; the kernel supplies the page and the same store runs again, this time successfully. A syscall instruction traps; the kernel does the work and returns to the instruction after syscall. An integer divide by zero also faults, but re-running the division would fault again, so instead the kernel reports it to the program (Linux and macOS send SIGFPE).

Why this rule exists. Restarting the exact instruction is what lets the operating system fill memory in lazily and invisibly, while continuing after a trap is what makes a system call behave like a function call.

Formal. A SIMD register of width W bits split into lanes of width w bits holds

lanes. A loop over n independent elements needs about ⌊n / L⌋ passes of the vector body plus (n mod L) passes of a remainder loop. Its speed-up S over the scalar loop, which does one element per instruction, obeys

when the SIMD loop does the same instructions per element, L at a time. A rewrite that also removes branches or table lookups can beat L: the extra gain comes from doing less work, not from the lanes.

In plain English. Divide the register's width by the size of one value to get how many values fit side by side. One instruction can then do at most that many values' worth of work, so the loop can be at most that many times faster, and only if nothing else holds it back.

Example. A 256-bit SIMD register holds 256 / 32 = 8 floats or 256 / 8 = 32 bytes. A loop adding two float arrays of n = 1003 elements needs 125 vector passes (1000 elements) and 3 remainder passes. Its speed-up over the scalar loop is at most 8; streaming arrays far larger than the caches, it is usually much less, because the loads wait on memory bandwidth, not on the adds.

Why this formula exists. It turns "SIMD makes code faster" into a number to check against: if a measured speed-up is far below L, the remaining limit is somewhere else (memory, a dependency chain, the tail).

Formal. For n-bit lanes, saturating addition returns the exact sum clamped to the type's range:

and saturating subtraction likewise clamps at 0 (unsigned) or at the signed limits. Ordinary lane-wise addition instead returns (a + b) mod 2^n. Each lane is clamped on its own.

In plain English. A saturating add gives the true answer if it fits; if it doesn't, it gives the closest value that does fit, the biggest or the smallest. It never wraps around to the other end of the range.

Example. Unsigned bytes: 250 + 10 is 260, too big, so the result is 255 (x86-64 paddusb, ARM64 uqadd); the plain add (paddb, add .16b) gives 4. Unsigned 5 − 9 saturates to 0 (psubusb, uqsub). Signed bytes: 100 + 100 is 200, above 127, so the result is 127 (paddsb, sqadd), where the plain add gives −56.

Why this rule exists. Pixels, audio samples and other measured values should get brighter or louder up to a limit, not jump to the opposite extreme, and saturating instructions do that without a compare and a select per value.

Formal. A SIMD register of width W bits split into lanes of width w bits holds

lanes. A loop over n independent elements needs about ⌊n / L⌋ passes of the vector body plus (n mod L) passes of a remainder loop. Its speed-up S over the scalar loop, which does one element per instruction, obeys

when the SIMD loop does the same instructions per element, L at a time. A rewrite that also removes branches or table lookups can beat L: the extra gain comes from doing less work, not from the lanes.

In plain English. Divide the register's width by the size of one value to get how many values fit side by side. One instruction can then do at most that many values' worth of work, so the loop can be at most that many times faster, and only if nothing else holds it back.

Example. A 256-bit SIMD register holds 256 / 32 = 8 floats or 256 / 8 = 32 bytes. A loop adding two float arrays of n = 1003 elements needs 125 vector passes (1000 elements) and 3 remainder passes. Its speed-up over the scalar loop is at most 8; streaming arrays far larger than the caches, it is usually much less, because the loads wait on memory bandwidth, not on the adds.

Why this formula exists. It turns "SIMD makes code faster" into a number to check against: if a measured speed-up is far below L, the remaining limit is somewhere else (memory, a dependency chain, the tail).

Formal. CAS(p, expected, desired) performs, as one atomic step with respect to every other core:

1. Read v = *p.
2. If v = expected, store *p = desired and report success.
3. Otherwise leave *p unchanged and report failure, returning v.

On x86-64, lock cmpxchg [p], desired takes the expected value in rax (eax for 32 bits), sets ZF = 1 on success, and on failure loads the value it found into rax. C++ std::atomic<T>::compare_exchange_strong(expected, desired) returns true or false and, on failure, writes the found value into expected.

In plain English. "If the value is still what I last saw, replace it with my new one; if somebody changed it, don't touch it and tell me what it is now." No other thread can change the value between the check and the write.

Example. A counter holds 5. Thread A runs CAS(p, 5, 6) and succeeds: the counter is 6. Thread B, which also read 5, then runs CAS(p, 5, 6) and fails, because the value is now 6; B gets 6 back and can try CAS(p, 6, 7) instead. Both increments survive.

Why this rule exists. Compare-and-swap is the general atomic step: any update that can be computed from the old value can be made atomic with it, by retrying until the value it was computed from is still current.

Formal. At any moment, each cache line is either

1. writable by exactly one core (MESI state Modified or Exclusive in that core's cache, Invalid everywhere else), or
2. readable by any number of cores (Shared or Invalid everywhere),

and a read returns the value of the most recent write to that location in the single order of writes to it. A core that wants to write a line it holds Shared must first invalidate every other copy.

In plain English. Many cores may read a line at once, but only one may write it, and while it writes, nobody else has a copy. Every core therefore agrees on the history of each memory location.

Example. Cores 0 and 1 both read x: the line is Shared in both caches. Core 1 writes x: it sends an invalidation, core 0's copy becomes Invalid and core 1's becomes Modified. Core 0 reads x again: it misses (a coherence miss), core 1 supplies the new value, and both copies become Shared.

Why this rule exists. It is what lets private per-core caches act like one memory for each location. It also predicts the cost: every write to a line that other cores hold moves the line, even when the cores are using different bytes of it.

Formal. False sharing occurs when two or more cores access different bytes of the same cache line, at least one of them writes, and the accesses repeat often. Because coherence works per line, each write invalidates the other cores' copies and the line moves between caches although no byte is shared. It disappears when each core's written data occupies lines no other core touches: align or pad to the line size B (64 bytes on most x86-64 and ARM64 cores, 128 on Apple M-series), or keep per-thread copies and combine them at the end.

In plain English. Two threads that never touch each other's variables can still fight over them if the variables sit in the same cache line. Give each thread's frequently written data a line of its own.

Example. long counts[4] takes 32 bytes, all in one 64-byte line. Four threads each incrementing their own counts[t] a hundred million times make that line bounce on almost every increment. Declaring struct alignas(64) Slot { long n; }; Slot counts[4]; puts each counter on its own line (use 128 on Apple M-series), and the threads no longer interfere. The totals are identical either way; only the time changes.

Why this rule exists. False sharing makes correct parallel code slower than serial code without any visible bug, and the source code gives no hint of it; only the data layout and the line size do.

Formal. Under x86-TSO, for memory operations of one core to different addresses, as observed by other cores:

All stores become visible to all other cores in one total order, a core reads its own stores early through store-to-load forwarding, and a locked instruction or mfence forbids the store → load case across it.

In plain English. On x86-64, other cores see a core's loads in order and its stores in order. The one exception: a store can sit in the store buffer while a later load to a different address goes ahead.

Example. The store-buffering litmus test, x = y = 0 at the start: thread 1 runs mov [x], 1 then mov eax, [y]; thread 2 runs mov [y], 1 then mov eax, [x]. Under sequential consistency at least one thread must read 1. Under x86-TSO both may read 0, because each store can still be in its core's store buffer when the other core's load runs. An mfence between the store and the load in each thread forbids that outcome.

Why this rule exists. It is the whole difference between x86-64 and sequential consistency, so it tells exactly which x86-64 code needs a barrier: code that stores one shared variable and then loads a different one and relies on the order.

Formal. If thread A performs a release store to a location f, and thread B performs an acquire load of f that reads the value A stored, then every memory write A performed before its release store (in A's program order) is visible to every read B performs after its acquire load. A release store keeps all earlier loads and stores before it; an acquire load keeps all later loads and stores after it.

In plain English. Write the data first, then set the flag with a release store. Read the flag with an acquire load, and if it is set, the data is guaranteed to be there. Each side only keeps order in one direction, which is cheaper than a full barrier.

Example. A: data = 42; ready.store(1, std::memory_order_release); B: while (!ready.load(std::memory_order_acquire)) {} use(data); — B always sees 42. With both operations relaxed, ARM64 may let B see ready == 1 and still read the old data; on x86-64 the hardware keeps this order anyway, but the compiler may not, so the C++ orders are still required.

Why this rule exists. Publishing data from one thread to another is the most common pattern in concurrent code, and acquire/release is the cheapest ordering that makes it correct on every ISA.

Formal. In a function compiled with a stack protector, the prologue copies a per-process random guard value G into a canary slot placed between the frame's local buffers (at lower addresses) and its saved registers and return address (at higher addresses). Before returning, the epilogue reloads the slot and compares it with G:

1. If slot = G, the function restores its saved registers and returns.
2. If slot ≠ G, a failure handler ends the process without returning (__stack_chk_fail on Linux and macOS; on Windows the comparison itself is a call to __security_check_cookie, which reports the failure).

Because the stack grows down and an overflow writes upward through consecutive addresses, any contiguous overflow of a local buffer that reaches the saved registers or the return address must overwrite the canary slot first, and is detected at step 2 unless it rewrote the slot with exactly G.

In plain English. The compiler puts a secret number between your arrays and the address the function will return to, and checks it on the way out. Writing far enough past an array to reach the return address means writing over the secret number, so the program notices and stops before the bad return happens.

Example. On Linux x86-64, clang -O1 -fstack-protector-strong compiles a function with a local char buf[16] into a prologue that loads the guard from fs:0x28 (thread-local storage) and stores it in a slot above buf, and an epilogue that compares that slot with fs:0x28 and calls __stack_chk_fail if they differ. A copy that runs far enough past the end of buf to reach the saved return address changes the slot on the way, so the process is ended at the check, with the C library's "stack smashing detected" message (SIGABRT), instead of returning to a damaged address.

Why this rule exists. It says exactly what the protection covers, and so what it doesn't: the check runs only at return, only catches contiguous overwrites that cross the slot, and says nothing about heap memory, out-of-bounds reads, or locals and pointers corrupted and used before the function returns.

Formal. If a region's base address is chosen uniformly from N possible positions (the randomization range divided by the required alignment), its entropy is

and a single guess of the base, made without other information, is right with probability

Every address inside the region moves with its base, so learning any one of them determines the base and reduces the region's remaining entropy to 0.

In plain English. Randomization picks one of 2^k places. More bits means more places and a smaller chance that a guess is right. But a whole library or stack moves as one block, so a single leaked address gives away where all of it is.

Example. A region placed at a random page-aligned (4 KiB = 2^12) address within a 2^40-byte range has N = 2^40 / 2^12 = 2^28 positions. That is k = 28 bits, so one guess succeeds with probability 2^-28, about 1 in 268 million. A 32-bit system with only 8 bits of randomization gives 1 in 256. (Actual bit counts depend on the OS, its version and settings, and the region; these numbers are illustrative.)

Why this formula exists. It turns "the addresses are random" into a number that can be compared across systems and regions. It shows why 64-bit address spaces made ASLR much stronger. It also shows why keeping addresses secret matters as much as the bit count: once an address is known, all k bits of protection are gone.

Formal. If a fraction p of a task's original running time is sped up by a factor s, and the remaining fraction 1 − p is unchanged, the overall speed-up is

and for any s,

For N cores running the parallel part perfectly, s = N.

In plain English. Only the part you speed up gets faster. The part you can't speed up still takes as long as it did, and soon it is most of the time that's left. If a tenth of the work must run on one core, no number of cores makes the whole job more than ten times faster.

Example. A program spends 90% of its time in a loop that splits perfectly across cores (p = 0.9). On 8 cores, S = 1 / (0.1 + 0.9/8) = 1 / 0.2125 ≈ 4.7, not 8. On 64 cores, S = 1 / (0.1 + 0.9/64) ≈ 8.8; the limit is 1 / 0.1 = 10. The same arithmetic applies when the fast part is moved to a GPU instead of more cores, before counting the cost of moving the data.

Why this formula exists. It explains why adding cores or accelerators gives diminishing returns, and why the part of a program that stays serial (setup, synchronization, data transfer) decides how much parallel hardware can help.

Formal. The power a CMOS chip spends switching transistors is

where a is the activity factor (the fraction of the capacitance switched per cycle), C the switched capacitance, V the supply voltage and f the clock frequency. Static (leakage) power is added on top of it. Over the upper part of a chip's operating range, a higher f needs a roughly proportionally higher V, so P_dynamic grows roughly with f³ there.

In plain English. Every tick of the clock charges and discharges millions of tiny wires. Running faster means more ticks per second, and it also needs a higher voltage, which counts twice because it is squared. So the last bit of speed costs far more power than the first.

Example. Raising a core's clock by 20% with a 10% voltage increase multiplies dynamic power by 1.2 × 1.1² ≈ 1.45: 45% more power for 20% more speed. Lowering the clock by 20% with 10% less voltage multiplies it by 0.8 × 0.9² ≈ 0.65. (Real voltage-frequency curves differ by chip; these numbers are illustrative.)

Why this formula exists. It explains the power wall that stopped clock rates rising in the mid-2000s, why chips use many slower cores and efficiency cores, and why turbo frequencies last only while there is power and cooling to spare.

Formal. For a direct jump, conditional branch or call at address A, with signed branch offset k stored in its instruction encoding:

• x86-64: target = A + L + k, where L is the branch's own length in bytes (so A + L is the address of the next instruction). k is stored in 1 byte (rel8, range −128 to 127) or 4 bytes (rel32).
• ARM64: target = A + 4k. b and bl store k in 26 bits (±128 MiB); b.cond, cbz/cbnz store it in 19 bits (±1 MiB).
• RISC-V: target = A + k, where k is always even. jal stores it in 20 bits (±1 MiB); beq, bne and the other branches in 12 bits (±4 KiB).

Since only the distance A-to-target is stored, moving the branch and its target together by the same amount leaves the encoding unchanged.

In plain English. A branch doesn't store where to go. It stores how far to go from where it is. x86-64 counts the distance from the end of the branch; ARM64 and RISC-V count from the branch itself, and ARM64 counts in whole 4-byte instructions. Because it is a distance, the same bytes work wherever the code ends up in memory.

Example. A 2-byte x86-64 jmp at 0x1000 encoded eb 10 lands at 0x1000 + 2 + 0x10 = 0x1012. An ARM64 b at 0x1000 with k = 4 lands at 0x1000 + 16 = 0x1010. A RISC-V beq at 0x1000 with k = 16 lands at 0x1010 when taken. eb fe (k = −2) is an x86-64 jump to itself.

Why this rule exists. Most branches stay inside one function, so a small distance fits in a few bits where a full 64-bit address never could. Counting from the branch also means code can be placed at any address without rewriting its jumps.

Formal. On Linux, a system call puts its system call number and up to six arguments in registers, executes the system call instruction, and receives one result:

A result from −4095 to −1 is an error: the negated error code (−errno). On x86-64, syscall overwrites rcx (with the return address) and r11 (with the flags), which is why argument 4 uses r10 instead of rcx. Numbers are fixed per ISA: write is 1 and exit is 60 on x86-64; write is 64 and exit is 93 on ARM64 and RISC-V.

In plain English. To ask the Linux kernel for something, put the number of the service in one register and the details in the next few, then run the one special instruction that switches into kernel mode. The answer comes back in a register, and a small negative answer means it failed. The registers are almost the function-call ones; on x86-64 the fourth detail moves from rcx to r10.

Example. Write 6 bytes from msg to standard output (file 1) on x86-64 Linux: mov eax, 1 / mov edi, 1 / lea rsi, [rip + msg] / mov edx, 6 / syscall. Afterwards rax holds 6, the number of bytes written. On ARM64 the same call is mov x8, #64, mov x0, #1, the address in x1, mov x2, #6, svc #0.

Why this rule exists. The kernel can't trust the program's stack or its calling convention, so it takes everything in registers it reads the moment it is entered. Linux promises never to renumber its system calls, so programs that use these numbers keep working on every later kernel. That promise is Linux's own; the other operating systems this course covers make no such promise.

Formal.

• x86-64: call target does rsp ← rsp − 8, [rsp] ← address of the next instruction, rip ← target. ret does rip ← [rsp], rsp ← rsp + 8.
• ARM64: bl target (or blr xn) does x30 ← address of the next instruction, pc ← target; memory is not touched. ret does pc ← x30.
• RISC-V: jal ra, target (written call or jal target) does ra ← address of the next instruction, pc ← target. ret is jalr zero, 0(ra): pc ← ra.

So a function's return address is at [rsp] on entry on x86-64, and in x30 or ra on ARM64 and RISC-V; a function that makes calls of its own must save x30 or ra (usually at its start) before the first one.

In plain English. A call is a jump that first remembers where to come back to. x86-64 writes that place on the stack; ARM64 and RISC-V put it in a register. Return just jumps back to the remembered place, the instruction after the call.

Example. At 0x1000, call f (5 bytes) with rsp = 0x7FF0 leaves rsp = 0x7FE8 holding 0x1005 at [0x7FE8]; ret in f jumps to 0x1005 and restores rsp = 0x7FF0. On ARM64, bl f at 0x4000 sets x30 = 0x4004.

Why this rule exists. The same function is called from many places, so the way back must be recorded at run time. Keeping it in a register is faster for functions that call nothing else; keeping it on the stack makes nested calls automatic.

Formal. For one program on one processor,

where CPI (cycles per instruction) is total cycles divided by instructions executed. For a pipeline that can start one instruction per cycle,

with ideal CPI = 1 and the stall term summing the structural, data (load-use) and control (branch penalty) cycles averaged over all instructions: for example, branch fraction × fraction of those that flush × branch penalty.

In plain English. How long a program takes is: how many instructions it runs, times how many ticks each one needs on average, times how long one tick lasts. A simple pipeline would need exactly one tick per instruction if nothing ever had to wait; every wait adds a little to that average.

Example. 10⁹ instructions at 2 GHz. 20% are loads, and half of those are followed straight away by an instruction that uses the value (1 stall cycle each); 15% are branches, a third of them flush 2 instructions. CPI = 1 + 0.20 × 0.5 × 1 + 0.15 × (1/3) × 2 = 1 + 0.10 + 0.10 = 1.20. Time = 10⁹ × 1.20 / (2 × 10⁹ per second) = 0.6 s; with no stalls it would be 0.5 s.

Why this formula exists. The three factors come from different places: the program and compiler set the instruction count, the microarchitecture sets CPI, and the circuits and power budget set the clock rate. The equation shows why no one factor settles speed, and lets you check a claimed improvement for what it costs the other two.