Week 2 · Lesson 1

Buffers and views

Week 1 programs computed values from constants and call arguments. Real kernels read and write memory that lives outside the program: model weights, activations, the output you hand back. This week adds that memory, and this lesson starts with the two things you can name: buffers, and windows into them.

Memory lives outside the program

A buffer is a block of n elements that exists before your program runs and after it ends. The program can read it and write it. When your compiler renders C, each buffer becomes one pointer argument of the kernel.

%b = buffer 6 dtype=i32 slot=0 data=[10 20 30 40 50 60]
%w = buffer 3 dtype=f32 slot=1

The operand is the size, an integer literal.
dtype is the element type, and slot is the buffer's position in the kernel's argument list. Two buffers can't share a slot.
data=[...] gives exactly n starting values. Without it the buffer starts as zeros. In real use the data comes from outside, but in tests it's written into the file.

An alloc is the same shape of thing, but it's scratch space that belongs to the program, like a local float a[3]; in C. It always starts as zeros, and nothing outside sees it.

%a = alloc 3 dtype=f32

A view is a window

You rarely want a whole buffer. shrink makes a view: a window that starts some number of elements in and covers a fixed number of them. Nothing is copied. A view is just a buffer plus an offset plus a length.

%v = shrink %b 2 shape=[3]     # elements 2, 3, 4
%e = shrink %b 5 shape=[]      # just element 5

shape=[k] gives a rank-1 window of k elements. shape=[] gives a single element, a rank-0 view, which is what you load and store scalars through. Step through the picture: the window slides over the same six cells.

Views of views

A view can be shrunk again. The offsets add up, and the new window has to fit inside the view it was cut from, not just inside the buffer.

%v = shrink %b 2 shape=[3]     # elements 2..4 of %b
%w = shrink %v 1 shape=[]      # element 1 of %v, which is element 3 of %b

shrink %v 3 shape=[] would be invalid, even though %b has an element 5: %v only has three elements, numbered 0 to 2.

Resolve a view

Here views are an OCaml type: a Buffer n, a Shrink (parent, off, k) for shape=[k], or an Elem (parent, off) for shape=[]. Write resolve v, returning (start, len): where the view starts inside its buffer, and how many elements it covers.

Raise Invalid_argument "out of bounds" if any step in the chain doesn't fit inside its parent: a negative offset, or a window that runs past the end of the parent.

Memory is not a value

Every week 1 value lived in what we'll call the ALU address space: numbers your program computes with. Buffers, allocs and views live in GLOBAL: they're places, not numbers. (GLOBAL here just means "memory", not a C global variable.) You can't add a buffer to 1, compare it, stack it, or pass it to a call. You have to load it first.

%x = add %b 1          # invalid: memory can't be an operand of add
%e = shrink %b 0 shape=[]
%y = load %e           # 10, an i32 value
%z = add %y 1          # 11

A load takes the view's dtype and shape. Loading a shape=[] view gives a scalar. Loading a shape=[3] view, or a whole buffer, gives a rank-1 value, the same kind of value stack builds, so you can compare it with assert or pick from it with index.

%r = load %v           # the rank-1 value [30 40 50]
%s = stack 30 40 50
%t = assert %r %s      # passes

Why the split matters

Keeping places and values apart is what lets the compiler reason about memory later. A value can be copied, folded and shared freely. A place can't: reading it twice might give two answers if something wrote in between. The next lesson is about exactly that.

Does the view fit?

Write fits(n, off, k) in C: return 1 if a view of k elements starting at off fits inside a parent of n elements, else 0. n and k are at least 1, but off can be any int, including INT_MAX and INT_MIN.

Check yourself

Which element indices of %b does shrink %b 2 shape=[3] cover?

It starts at the offset and covers k elements.

Offset 2, three elements: indices 2, 3 and 4.

What does %x hold?

%b = buffer 6 dtype=i32 slot=0 data=[10 20 30 40 50 60]
%v = shrink %b 2 shape=[3]
%w = shrink %v 1 shape=[]
%x = load %w

Offsets add up: where does %v start, and how far into %v is %w?

%v starts at element 2, and %w is one further in: element 3 of %b, which holds 40.

On %b = buffer 6 ..., which view is invalid?

A window of k elements starting at off ends at index off + k - 1. The last valid index is 5.

Offset 4 with three elements would cover indices 4, 5 and 6, and there is no index 6. The others end exactly at index 5 or earlier.

What happens with %x = add %b 1, where %b is a buffer?

Is a buffer a value or a place?

A buffer is memory, not a value. ALU ops only take values, so you have to load first. The oracle reports "memory can't be an operand here (load it first)".

What does load %a give for %a = alloc 3 dtype=f32, before anything is stored?

The spec says what an alloc starts as. And loading a whole 3-element alloc keeps its shape.

Allocs start as zeros, and loading all three elements gives a rank-1 value. In C, a local array starts as garbage, so your renderer will have to initialize it.

Why is shrink %v 3 shape=[] invalid when %v = shrink %b 2 shape=[3] and %b has six elements?

Check the new window against the view it was cut from.

A view must fit inside its parent. %v has three elements, so offset 3 is past its end, even though it would land on element 5 of %b, which does exist.