Vectorization — avoiding Python loops, speed comparison: Worked examples

This page is a drill. The parent note built the theory: a Python loop pays a big per-element overhead $τ_{py}$ , vectorized code pays a tiny $τ_{vec}$ , and the model is

$T = c_{setup} + N τ_{per-element}, Speedup = \frac{N τ _{py}}{c _{setup} + N τ _{vec}} .$

Here we hit every case that model can throw at you — big $N$ , tiny $N$ , the exact break-even point, the $O (N^{2})$ trap, memory-bound reality, and a word problem.

The scenario matrix

Every problem about vectorization lives in one of these cells. The examples below are labelled with the cell (C1…C8) they cover.

Cell	Case class	What changes	Who wins?
C1	Large $N$ (limit)	$N \to \infty$ , setup negligible	Vectorized, $\approx τ_{py} / τ_{vec}$
C2	Tiny $N$ (degenerate)	$N$ so small $c_{setup}$ dominates	Loop can win
C3	Break-even $N$	the exact $N$ where times are equal	Tie — solve for it
C4	$N = 0$ / $N = 1$ (edge)	empty or single element	Pure setup / almost pure setup
C5	$O (N^{2})$ trap	`np.append` in a loop	Neither — it's quadratic
C6	Memory-bound ceiling	arithmetic is free, data movement isn't	Speedup capped below $τ_{py} / τ_{vec}$
C7	Word problem	real timing from a benchmark	Forecast then check
C8	Exam twist	`np.vectorize` mislabelled as fast	It's a loop in disguise

Figure — Vectorization — avoiding Python loops, speed comparison

Worked examples

C1 — The large- $N$ limit

Worked example

C1. You process $N = 1 0^{7}$ floats. With $τ_{py} = 100$ , $τ_{vec} = 1$ , $c_{setup} = 1000$ (all ns), find the speedup.

Forecast: $N$ is huge — guess the speedup lands near the ceiling $τ_{py} / τ_{vec} = 100$ . Slightly under?

Loop time $T_{py} = N τ_{py} = 1 0^{7} \times 100 = 1 0^{9}$ ns $= 1.0$ s. Why this step? The loop has no meaningful setup term — its whole cost is $N$ slow ops.
Vector time $T_{vec} = c_{setup} + N τ_{vec} = 1000 + 1 0^{7} \times 1 = 10, 001, 000$ ns $\approx 10.001$ ms. Why this step? Setup is $1000$ ns; the real work is $1 0^{7}$ ns. Setup is $0.01%$ — negligible, exactly as the limit predicts.
Speedup $= T_{py} / T_{vec} = 1 0^{9} /10, 001, 000 \approx 99.99$ . Why this step? Dividing the two totals gives how many times faster.

Verify: $99.99 < 100$ and the gap is tiny — the setup shaves a hair off the ceiling. Units: ns/ns is dimensionless ✅. As $N \to \infty$ this creeps up to exactly $100$ .

C2 — Tiny $N$ , vectorization loses

C3 — The exact break-even point

C4 — Degenerate inputs: $N = 0$ and $N = 1$

C5 — The $O (N^{2})$ trap (`np.append` in a loop)

Worked example

C5. You build an array by np.append-ing one element at a time, $N$ times. Each append copies all elements present so far. How many total element-copies for $N = 1000$ , and how does that scale?

Forecast: Each append copies a growing array → sounds like $1 + 2 + 3 + \dots$ , the triangular number. Guess $\approx N^{2} /2$ .

Cost of the $k$ -th append: it copies the $k - 1$ existing elements (then adds one), so $\approx k$ copies. Why this step? np.append reallocates a fresh block and copies the old contents every call — see the parent mistake box.
Total copies $= \sum_{k = 1}^{N} k = \frac{N ( N + 1 )}{2}$ . Why? Sum the per-call costs. For $N = 1000$ : $\frac{1000 \cdot 1001}{2} = 500, 500$ .
Scaling: $\frac{N ( N + 1 )}{2} \sim \frac{N ^{2}}{2}$ , i.e. $O (N^{2})$ — see Big-O Complexity. Why? The $N^{2}$ term dominates; this is worse than a plain Python list append which is $O (N)$ total.

Verify: $500, 500 \approx \frac{1}{2} (1000)^{2} = 500, 000$ ✅. Fix: build a Python list then np.array(lst) once — a single $O (N)$ pass.

C6 — Memory-bound ceiling (the real-world cap)

Worked example

C6. Adding two big arrays should be $100 \times$ faster by C1. In practice you measure only $\approx 30 \times$ . Explain the gap using a memory model: reading/writing one $8$ -byte float costs $τ_{mem} = 3$ ns, while the add costs $τ_{vec} = 1$ ns.

Forecast: If moving data costs more than the arithmetic, the CPU waits on memory, not on adds. Guess: the real per-element cost is dominated by $τ_{mem}$ , capping the speedup.

True vector per-element cost $= max (τ_{vec}, τ_{mem}) = max (1, 3) = 3$ ns. Why this step? For a+b you must read a[i], read b[i], write out[i] — the pipeline stalls on memory bandwidth, not arithmetic. See Memory Layout and Cache.
Realistic speedup $= \frac{τ _{py}}{τ _{mem}} = \frac{100}{3} \approx 33.3$ . Why? Replace the idealized $τ_{vec}$ with the actual bottleneck.
Interpretation: the $100 \times$ ceiling assumed arithmetic was the bottleneck; when data movement dominates, the real ceiling drops to $\approx 33 \times$ .

Verify: $33.3 < 100$ ✅ and matches the measured $\approx 30 \times$ order of magnitude. This is why the parent said large vectorized ops are "memory-bandwidth bound."

C7 — Word problem: forecast a benchmark

Worked example

C7. A colleague's loop over $N = 2 \times 1 0^{6}$ floats runs in 0.30 s. You'll vectorize it. Using the memory-bound cost $τ_{mem} = 3$ ns/elem plus $c_{setup} = 1000$ ns, forecast the vectorized time and the speedup.

Forecast: $2 \times 1 0^{6}$ elements at a few ns each → a handful of milliseconds. Big win.

Vector time $T_{vec} = c_{setup} + N τ_{mem} = 1000 + 2 \times 1 0^{6} \times 3 = 6, 001, 000$ ns $\approx 6.001$ ms. Why this step? Use the realistic per-element cost from C6, since a plain a+b is memory-bound.
Speedup $= \frac{0.30 s}{6.001 \times 1 0 ^{- 3} s} \approx 49.99$ . Why? Divide the measured loop time by the forecast vector time. Convert everything to seconds first: $6.001$ ms $= 0.006001$ s.
Report: "Expect roughly 50× faster, landing near 6 ms."

Verify: $0.30/0.006001 \approx 50.0$ ✅. Units: s/s dimensionless. The forecast sits between the C6 ceiling ( $33 \times$ for pure add) and the ideal $100 \times$ — sensible because the loop here was already relatively slow at $150$ ns/elem.

C8 — Exam twist: `np.vectorize` is a decoy

Worked example

C8. An exam claims: "Wrapping f with np.vectorize(f) gives the $100 \times$ speedup." If np.vectorize still runs f once per element in Python at $τ_{py} = 100$ ns (plus a small $c_{setup} = 1000$ ns), compute its real speedup over a hand-written loop for $N = 1 0^{6}$ . True or false?

Forecast: The name lies — if it's still a Python-level loop, the per-element cost is $τ_{py}$ , so no real speedup. Guess: $\approx 1 \times$ , claim false.

Hand loop time $= N τ_{py} = 1 0^{6} \times 100 = 1 0^{8}$ ns. Why? Baseline: the straightforward loop.
np.vectorize time $= c_{setup} + N τ_{py} = 1000 + 1 0^{8} = 100, 001, 000$ ns. Why this step? np.vectorize does not compile f; it merely loops in Python — so it also pays $τ_{py}$ per element (see Universal Functions (ufuncs) for what real speed needs).
Speedup $= 1 0^{8} /100, 001, 000 \approx 0.99999$ . Why? Essentially $1 \times$ — the extra setup even makes it a whisker slower.

Verify: $0.99999 < 1$ ✅ → the claim is FALSE. True speed needs a real ufunc or Numba and Cython compilation, whose per-element cost is $τ_{vec}$ , not $τ_{py}$ .

Case-coverage checklist

Recall Did we hit every cell of the matrix?

Which example covers the large- $N$ limit? ::: C1 ( $\approx 99.99 \times$ ). Which shows vectorization losing? ::: C2 (tiny $N = 5$ , speedup $\approx 0.498$ ). Where is the exact break-even $N$ ? ::: C3 ( $N^{⋆} = 1000/99 \approx 10.10$ ). What happens at $N = 0$ ? ::: C4 — loop costs $0$ , vector still pays $1000$ ns setup. Which example exposes the $O (N^{2})$ trap? ::: C5 (np.append, $500, 500$ copies for $N = 1000$ ). Why is real speedup below $100 \times$ ? ::: C6 — memory-bound, ceiling $\approx 33 \times$ . The word-problem forecast? ::: C7 — $\approx 6$ ms, $\approx 50 \times$ . The np.vectorize decoy result? ::: C8 — $\approx 1 \times$ , claim false.

Connections

Parent — the speed model these examples exercise.
NumPy Arrays vs Python Lists — why the $O (N^{2})$ append trap (C5) exists.
Big-O Complexity — the $N^{2}$ scaling in C5.
Universal Functions (ufuncs) / Numba and Cython — the real fix for C8.
Memory Layout and Cache — the bandwidth ceiling in C6.
Broadcasting Rules — vectorizing multi-dimensional cases.