Week 0 study guide

Week 0 is the toolbox: C and memory, what an IR is, tensors as views of flat memory, matrix multiply, and enough Python or OCaml to write a compiler. Use this page to review before week 1, or to find the one idea that didn't stick.

The week in one page

0.1 C and pointers

Memory is a long row of numbered bytes, and a pointer is one of those numbers. An array is a base address plus an offset, so p[i] is just *(p + i), with the offset scaled by the element size. Signed overflow, INT_MIN / -1 and division by zero are undefined behavior in C, which is why your compiler will wrap integers through uint32_t.

0.2 Memory and caches

The CPU reads memory in 64-byte cache lines (128 on Apple M-series), and a cache miss costs roughly a hundred times a hit. Walking a row-major 2D array row by row uses every byte of each line. Walking it column by column touches a new line on almost every step. Loop order is a performance decision your compiler will make.

0.3 Compilers and IRs

A compiler turns text into tokens, tokens into a tree, the tree into an IR, and the IR into code. Sharing equal subtrees turns the tree into a DAG, which is what week 1's UOps are. Printing code from a DAG means visiting sources before the nodes that use them: a toposort.

0.4 Tensors and shapes

A tensor is a flat buffer plus a shape plus strides. The element at [i, j] lives at offset + i*stride0 + j*stride1. Reshape, permute, broadcast (stride 0) and shrink are all just different strides and offsets over the same buffer, and pad adds a validity mask.

0.5 Matrix multiply

Each output of A @ B is a dot product of a row of A with a column of B. For M×K times K×N, that's M·N outputs and 2·M·N·K floating-point operations. The syllabus writes it as a broadcast multiply followed by a sum over the shared axis.

0.6 OCaml crash course

Variants plus pattern matching are the heart of a compiler written in OCaml. OCaml's int is 63 bits, so the course's 32-bit integers need Int32 or explicit wrapping. Floats are doubles, so round to f32 with Int32.float_of_bits (Int32.bits_of_float x).

0.7 Python for this course

Dataclasses hold IR nodes, dicts do the hash consing, and match with class patterns branches on a node's shape. Python's ints never overflow, so i32 needs explicit wrapping, and // floors where C truncates. Floats are doubles, so round to f32 with struct.unpack("<f", struct.pack("<f", x))[0].

You only need the lesson for your track. The sidebar's Language picker chooses it, and Python and OCaml, deeper goes further in both.

Cheat sheet

C fact	value
`sizeof(char)`, `int`, `double`, pointer (64-bit)	1, 4, 8, 8 bytes
`int32_t` range	−2,147,483,648 to 2,147,483,647
signed overflow, `INT_MIN / -1`, `x / 0`, shift ≥ width	undefined behavior
unsigned overflow	defined: wraps modulo 2ⁿ
`-7 / 2`, `-7 % 2`	`-3`, `-1` (truncate toward zero, and the remainder takes the dividend's sign)

memory and tensors	rule
cache line	64 bytes (16 floats), or 128 on Apple M-series
row-major strides of shape `(d0, d1, d2)`	`(d1·d2, d2, 1)`: each stride is the product of the sizes after it
flat index of `[i, j, k]`	`i·d1·d2 + j·d2 + k`
unravel a flat index `f` in shape `(d0, d1)`	`[f / d1, f % d1]`
broadcast an axis	stride 0
`(M, K) @ (K, N)`	shape `(M, N)`, 2·M·N·K flops

Python	meaning
`@dataclass(frozen=True)`	an immutable record with generated `__init__`
`match e:` / `case Add(x, y):`	pattern matching on a value's class and fields
`d.get(k)`, `d[k] = v`, `d.setdefault(k, v)`	a dict lookup, store, and store if missing
`-7 // 2`, `-7 % 2`	`-4`, `1` (floors, unlike C)
`2**31 - 1 + 1`	`2147483648` (Python ints never wrap)
`ctypes.c_int32(2**31).value`	`-2147483648` (wraps, handy for checking your own wrap)
`x.hex()`	a float's exact value as a hex float

OCaml	meaning
`type t = A \| B of int * t`	a variant whose `B` carries a pair
`match e with A -> 0 \| B (n, _) -> n`	pattern matching
`let x = 3 in x + 1`, `fun x -> x + 1`	local name, anonymous function
`Some v \| None`	an option
`let r = ref 0 in r := !r + 1`	a mutable cell
`Hashtbl.replace t k v`, `Hashtbl.find_opt t k`	a hash table
`max_int`	4611686018427387903 (63-bit)
`Int32.add Int32.max_int 1l`	`-2147483648l` (wraps)

Mistakes people make

Adding two int32_t and expecting wraparound. Signed overflow is undefined, so the optimizer may assume it never happens. Add as uint32_t and convert back. The w0-01-wrap-add exercise is built around this.
Treating C's / like Python's //. C truncates toward zero (-7 / 2 == -3), Python floors (-4). Week 1's i32 division follows C, and the week 1 test i32_div_trunc catches the Python version.
Mixing up bytes and elements. Lesson 0.2 counts addresses in bytes, and lesson 0.4 counts strides in elements. A float at element 5 is at byte 20.
Computing a size in int before widening. 4 * n overflows before it reaches a long long. Write 4LL * n.
Forgetting the clamp on a padded read. Reading x[-1] is undefined even if you throw the value away. Check the index first.
Assuming OCaml's int is 32 bits. It's 63, so 2147483647 + 1 is 2147483648, not INT_MIN. Use Int32 or wrap by hand.
Assuming Python's int wraps somewhere. It never does, so 2147483647 + 1 is 2147483648, not INT_MIN. Wrap to 32 bits after every i32 op.
Comparing floats with = and expecting NaN to equal itself. nan = nan is false in OCaml and C, and nan == nan is false in Python. Week 1's assert deliberately treats two NaNs as equal, and your own code has to do the same on purpose.

Stuck on an exercise?

Read the examples under the prompt first. They show the exact call and the expected output. Run your code on them with Run before Submit.
A C exercise crashes or times out on one test. The runner traps undefined behavior, so a crash usually means signed overflow, INT_MIN / -1, or reading past an array. On Windows, a naive INT_MIN / -1 can hang instead of crashing.
An exercise says "keep the function name and type". The tests call your function by name. If you renamed it or changed its arguments, the harness can't compilecall it.
A hidden test fails and you can't see why. Submit shows the input and expected value of the first failing hidden test. Re-create that case by hand and trace your code on it.
Still stuck. Each exercise has hints that build up one at a time, and Show answer explains the reference solution. Try one hint, then one more attempt, before looking.

Check yourself

In C, unsigned char c = 250; c += 10; leaves what in c?

An unsigned char holds 0 to 255, and unsigned arithmetic wraps.

260 wraps modulo 256 to 4. Unsigned overflow is defined in C, unlike signed overflow.

For int a[3][4];, how many ints apart are &a[2][1] and &a[0][0]?

Each row is 4 ints. Count whole rows, then the column.

2 rows of 4 plus 1: 2·4 + 1 = 9. Pointer subtraction counts elements, not bytes.

In a row-major tensor of shape (2, 3, 4), which index [i j k] is at flat position 17?

The strides are 12, 4 and 1. Take out as many 12s as fit, then 4s.

17 = 1·12 + 1·4 + 1, so [1 1 1].

A loop reads 1024 floats that sit back to back, starting at the beginning of a cache line. How many 64-byte cache lines does it touch?

How many floats fit in one line?

A line holds 16 floats (64 bytes / 4), so 1024 / 16 = 64 lines.

How many floating-point operations does a (2, 3) @ (3, 4) matrix multiply take, counting each multiply and each add?

The rule of thumb is 2·M·N·K.

M=2, K=3, N=4: 2·2·4·3 = 48. (Strictly each output needs K multiplies and K−1 adds, but the 2·M·N·K count is the standard convention.)

In C, what is -9 % 4?

C's remainder takes the sign of the left operand.

-9 / 4 truncates to -2, and -9 - (-2)·4 = -1.

In OCaml, what does Int32.to_int (Int32.add Int32.max_int 1l) evaluate to?

In Python, with wrap = lambda x: (x + 2**31) % 2**32 - 2**31, what does wrap(2147483647 + 1) evaluate to?

Int32 arithmetic wraps at 32 bits, exactly like the course's i32.The sum is 2³¹, one past INT_MAX. wrap maps any int into the 32-bit range.

Int32.add wraps, so max_int + 1 becomes min_int, which converts to -2147483648 as a native int. Plain int would give 2147483648.Python computes 2147483648 exactly, then wrap gives (2**32) % 2**32 - 2**31 = -2147483648. Without wrap you'd get 2147483648.

More practice: the week 0 quiz review has every quiz from this week's lessons, or only the ones you missed.

Go deeper

What Every Programmer Should Know About Memory (Ulrich Drepper). The long version of lesson 0.2: caches, TLBs and why access order matters.
A Guide to Undefined Behavior in C and C++ (John Regehr). Why compilers exploit undefined behavior, with examples that will surprise you.
cppreference: undefined behavior. The precise list of what C leaves undefined.
Real World OCaml. A free book that goes well past the crash course: modules, functors, and the standard library you'll lean on.
OCaml documentation. The standard library reference for Int32, Hashtbl and Printf.
The Python tutorial. The official tour, worth a skim for classes, dicts, and the standard library if your Python is rusty.
The Python standard library. The reference for struct, dataclasses, functools and subprocess, the modules a Python compiler leans on.
Python and OCaml, deeper. Idioms, traps, and reading for each language, week by week.
Row- and column-major order. Short, with pictures of how the same array is laid out both ways.

Challenges

Time the cache effect yourself. Write a C program that sums a 4096×4096 float array row by row, then column by column, and time both with clock(). Predict the ratio before you run it.
Strides for any view. Extend view_at so it also handles a negative stride (a flipped axis). Check by hand that flipping twice gives the original.
A tiny expression evaluator in your language. Define a varianta dataclass per node kind for +, * and integer constants, write a function that evaluates it, and another that counts nodes. This is the shape of week 1, on a toy you control.