← All Base Form Math projects
BM-02NOT STARTEDBASE FORM · LINEAR ALGEBRAMATHPYTHON

Matmul speed ladder in Python

Make matrix multiplication 50× faster than a naive Python loop without calling np.matmul, and chart every step on the way.

EST.6 h
REWARD+100 XP
AFTERSimon Boehm

ML-ARENA BENCHMARKS

YOUR NUMBER VS THE INDUSTRY'S
METRICINDUSTRYMINE
speedup over your naive loop, 512 × 512 float32
GOAL · ≥ 50× with no np.matmul, np.dot, @, einsum or tensordot
NumPy ~7,900× (measured on one machine; mlarena bench measures yours)—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

Every neural network is mostly matrix multiplication. NumPy hands the work to a BLAS library that experts have tuned for decades, so A @ B is absurdly fast. In this project you climb the same ladder they did, one rung at a time, and measure every step.

You start with three nested Python loops. Then you change the loop order, rewrite the product as a sum of outer products so NumPy can do most of the work, and try blocking. You'll get a big speedup and still see why the library wins by a mile: it runs compiled C with SIMD instructions and many threads.

The maths you need: entry (i,j)(i, j) of C=ABC = AB is Cij=∑kAikBkjC_{ij} = \sum_k A_{ik} B_{kj}, and the same product can be written as C=∑kakbk⊤C = \sum_k a_k b_k^\top, where aka_k is column kk of AA and bk⊤b_k^\top is row kk of BB.

OVERVIEWFig. 1
RUNG 1Naive loopthree loops,pure Python RUNG 2Loop ordersame maths,friendlier access RUNG 3Outer productsone loop; NumPydoes the rest RUNG 4Blockingtiles that fitin cache INDUSTRYNumPy / BLASC, SIMD, threads:the Cracked follow-up
The ladder: one rung per objective. Why it's here: See the whole climb before you write the first loop.
VISUALFig. 2
A B C = A·B
Blocking computes C one tile at a time from bands of A and B that fit in cache. Why it's here: Objective 4 asks whether blocking helps in NumPy. See what it changes before you measure it.
EXPECTEDFig. 3
1×10× 100×1k× 10k× 1×98× 60×~7,900× naiveouter prod. blockedNumPy
Speedups measured on one machine at 512 × 512. Blocking was slower than plain outer products there. Why it's here: A sanity check for your own chart, and a reminder that 'should be faster' isn't 'is faster'.
HINT · OBJECTIVE 3
Stuck? Hints stay hidden until you ask.

DATA · random matrices

Objectives

0 / 5 CLEARED

Read-only. Log in to update progress.

VICTORY CONDITIONS

  1. At least 50× faster than your naive loop at 512 × 512, measured with `python tools/mlarena.py bench BM-02 your_file.py`.
  2. No np.matmul, np.dot, @, einsum or tensordot anywhere in your solution.
  3. Matches NumPy to a relative error under 1e-4, and the README has the chart and one paragraph per rung.

Side quests

Repeat the ladder at 1024 × 1024 and explain why the gaps change.
Read how BLAS libraries use SIMD and threads, then sketch what a C version would do differently (that's the Cracked follow-up).

Terms in plain words

Matrix multiplication
Each entry of C = A·B is the dot product of a row of A with a column of B.
Outer product
A column vector times a row vector gives a whole matrix; C is the sum of n of them.
Broadcasting
NumPy stretches arrays of different shapes so one expression works on whole blocks at once, without a Python loop.
Cache
Small, fast memory next to the CPU. Code that reuses nearby data stays in cache and runs much faster.