From a loop to a reduction
You have a correct little program made of loops, and it runs slowly. Turning it into array operations without changing its answer takes three steps: pick one output, write its arithmetic, and decide which axis gets combined. An average, a distance table, and an image blur show how.
Start with [1,2,3]. A loop accumulates 0+1=1, then 1+2=3, then 3+3=6, and divides the total by three. The answer is 2. A reduction combines entries along an axis, as that sum does. It replaces several input entries with one result for the group it reduces.
A whole-list mean and a running average have different output shapes. The whole-list mean returns one number. The running average returns one number per prefix: [1,(1+2)/2,(1+2+3)/3]=[1,1.5,2]. A prefix is the opening portion of the list, ending at some position. The last entries agree, and the earlier outputs are extra information.
The loop’s changing accumulator puts the sequential dependency in plain sight. Addition allows another organization, as long as you account for floating-point rounding. A prefix scan computes the accumulated result for every opening portion of a list. It is a useful operation in its own right, and it is not an instruction to build a huge matrix full of zeros and ones.
A matrix that explains every prefix
Multiply the lower-triangular mask [[1,0,0],[1,1,0],[1,1,1]] by (1,2,3). The rows give 1, 1+2=3, and 1+2+3=6. Divide those entries by (1,2,3) entry by entry. The running averages are (1,1.5,2). The zeros say which later inputs each prefix leaves out.
The dense mask explains the index pattern, and it wastes storage as the list grows. A practical implementation uses a scan with far less temporary storage. That is the first split between a mathematical description and an implementation choice: writing an operation as a matrix doesn’t oblige a program to build every cell of that matrix.
One point against every other point
Now six points: A=(0,0), B=(1,0), C=(2,0), D=(0,1), E=(1,1), and F=(2,1). The job is the distance between every pair. Each output cell carries two point indices, a row point and a column point. Once the original coordinates are in hand, one cell’s answer doesn’t depend on any other.
To broadcast arrays is to line up compatible axes and repeat values across them in principle. The operation can often reuse storage instead of copying every repeated input. Here one copy of the point list supplies the row-point axis and another supplies the column-point axis. A third axis holds the two coordinate differences each pair needs.
If X has shape (6,2), the expression X[:,None,:] exposes shape (6,1,2), while X[None,:,:] exposes shape (1,6,2). A colon selects every entry along an existing axis. None inserts an axis of length one. Subtracting those two views gives the pair-and-coordinate shape (6,6,2).
Inspect A against E
The difference between (0,0) and (1,1) is (−1,−1). Squaring gives (1,1); adding gives squared distance 2; the square root gives distance √2. From A, the six squared distances are [0,1,4,1,2,5]. The table in the figure holds squared distances, which is why its entries are whole numbers.
Let Dᵢⱼ name the distance from point i to point j. The coordinate index k visits the two coordinates inside each pair. The point indices survive into the output table; the coordinate index disappears, because summing reduces it. Recognize that pattern before you reach for a library expression.
$$ D_{ij}=\sqrt{\sum_k(X_{ik}-X_{jk})^2} $$In words: subtract the coordinates, square the differences, add them, then take the square root.
A six-by-six-by-two temporary is small. The same pattern on a much larger point set builds an expensive intermediate. An algebraic alternative computes squared distances from dot products and squared norms, and never forms the full difference tensor. So the comparison is about arithmetic and memory together, not about which source file has fewer lines.
The image operation behind the loop
The third program slides a local average over an image. Use a five-by-five input whose every row is [0,0,3,0,0]. An image kernel is a shared local array of weights applied to patches. That is a different object from the device program called a kernel in the last chapter, sharing one word.
The averaging image kernel is three by three, with 1/9 in every entry. Padding adds border entries around the image; here there is none. Stride is how far the window moves between outputs; here it is one cell. A five-cell side leaves three valid positions for a three-cell window, so the output is three by three.
Each output reads its own patch of the original image. Neighboring outputs share many input pixels, and neither needs the other’s output. A program that overwrote the original image while sliding would change that: later windows would read already-blurred values. Keeping input and output separate preserves the operation.
The first two windows
The first sum is 0+0+3+0+0+3+0+0+3=9, divided by 9 to give 1. The next is 0+3+0+0+3+0+0+3+0=9, divided by 9 to give 1. The same central stripe sits inside every valid window, so all nine output cells equal 1.
Flatten each three-by-three patch into nine entries and stack the nine patches into rows. Each row’s dot product with the flattened averaging kernel gives one output. The repeated local computation is now a tensor operation. An efficient implementation may gather the patches implicitly; the conceptual stack doesn’t require copying every patch value into a new array.
Watch the same cell in both programs
To vectorize is to write a calculation as array operations instead of one interpreter-level operation per element. Contiguous memory means neighboring logical entries sit in neighboring storage locations under a stated layout. Both help a library process many entries efficiently, and neither on its own makes a rewritten program faster.
See it move
Start with blur. Step the loop and select the matching output cell. Read the full nine-term sum before you ask for all the independent outputs at once. Then switch to distances and look at the coordinate reduction inside one pair. In average mode, keep the whole-list reduction and the prefix output apart; they don’t return the same shape.
The editable examples are small enough to check by hand. We timed larger versions on the machine this book was written on: 100,000 values for the running average, 2,000 two-dimensional points for distances, and a 1024×1024 input for the valid three-by-three blur. Each time below is the median of five runs.
The transfer-inclusive result changes the reading. CUDA compute beats the NumPy blur here, while CUDA with transfer takes a little longer than NumPy. The two CUDA times cover different work: the second includes copying the image to the GPU and the result back.
Where this shows up when you train
A batch axis repeats examples; a feature axis holds the values inside one example. A reduction removes the axis whose entries it combines, and broadcasting exposes the axes a calculation repeats over. That vocabulary describes data preparation, layers, and losses in the same terms. It also makes a large temporary array easy to spot before it exhausts memory.
For each rewrite, name the surviving output axes, the reduced axes, and any intermediate arrays. Check that every output reads the original inputs. Then time the real workload with its copying and allocation boundary stated. A performance claim needs all three to stand on.
What you now know
- Vectorizing preserves the arithmetic while changing how work is scheduled.
- Broadcasting pairs compatible axes, and reductions combine an axis.
- A speedup is measured on a real workload, with the copying included or excluded on purpose.
Where we’re headed
Next: choosing the axes before you write the loop. Continue to the next chapter.