Making Python Fast

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Big-O

A way to describe how work grows as the input grows, such as linear (n) or constant (1).

Cache (memoise)

Store a result so the same input never has to be computed again.

Vectorise

Replace a Python loop over numbers by one operation on a whole array.

Lazy

Computing a value only when it is asked for.

Hot loop

A loop that runs so often that it dominates the run time.

Native extension

A compiled module (C, C++, Rust) that Python can import.

JIT

Just-in-time compiler: compiles hot code to machine code while running.

Constant factor

The fixed cost of each step. Big-O ignores it, but it still decides speed once the algorithm is right.

1. 1

   Double the input

   In the first example change range(300) to range(600). Predict the two step counts before running: the slow one should be about four times bigger, the fast one twice.

2. 2

   Look at the cache

   Call fib(60) and then fib(61) and print fib.cache_info() again. How many new misses did fib(61) cause?

3. 3

   Find the hot loop

   Take any loop you wrote earlier in this course that touches a list item by item. Ask three questions: can a set or dict replace a scan, can a built-in do the loop, and is any value inside the loop the same on every pass?

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

from functools import lru_cache


@lru_cache(maxsize=None)
def total(values):
    return sum(values)


print(total((1, 2, 3)))
print(total([1, 2, 3]))

1. 1

   The right data structure comes first. (Recall Topics 4.5, 4.10 and 4.11 for hashing, deque and the cost of each structure.) Membership tests: a set or dict answers x in s in constant time, a list scans (linear). Queue operations: collections.deque pops from the left in constant time, list.pop(0) moves everything. Sorted data: bisect finds a position in logarithmic time. Counting: Counter. This changes the growth of the run time, so it beats every micro-trick. The example counts 44,850 steps for a nested loop against 300 for a set on 300 items.

2. 2

   Avoid repeated work. Move calculations that do not change out of loops. Cache results of pure functions with functools.lru_cache or cache (Topic 9.5): the cached recursive fib(60) makes 61 real calls instead of trillions. Read a file once, not once per line of another file. Build strings with "".join(parts) instead of += in a loop. Batch many small database or API calls into fewer large ones.

3. 3

   Use the C code that already ships with Python. Built-ins such as sum, min, max, sorted, any, all, zip, map and the methods of str, list and dict run their loops in C. sum(data) and max(data) beat a hand-written loop by a wide margin, and str.join, str.split and slicing beat character-by-character code. (A generator expression inside sum is not as fast: each item still runs Python bytecode, so the win comes from the C-level loop, not from the generator.) A list comprehension is usually faster than the same for loop with append, because it avoids repeated method lookups.

4. 4

   Stay lazy. A generator or generator expression produces one item at a time and never builds the whole list, so memory stays flat: a list of 100,000 squares is hundreds of times larger than the generator that makes them. Streaming a big file line by line, or an LLM response token by token, uses the same idea (Topic 9.2).

5. 5

   Micro-tricks, last. Reading a local variable is faster than a global or attribute lookup, so inside a very hot loop binding append = items.append or sqrt = math.sqrt can help a little. The specialising interpreter (Topic 13.3) has narrowed the gap, so measure (Topic 13.7). Avoid creating objects in the hot loop, avoid exceptions as normal flow, and keep functions small and monomorphic (a function that always gets the same types in and gives the same types out, so the specialising interpreter can stay specialised).

6. 6

   Vectorise. For numeric work, move the loop out of Python entirely: NumPy applies an operation to a whole array in compiled C (Topic 13.9, Topic 14.3), often tens to hundreds of times faster than a Python loop over the same numbers. When no library does the job, the next steps are: Cython, Numba (compiles numeric Python functions with a JIT), a C or Rust extension (PyO3), or running on PyPy, an alternative interpreter with a mature JIT. For parallel work see Phase 12. The order is always: algorithm, built-ins, caching, vectorise, then native code.

• ↔

  Speed versus readability. Clever tricks make code harder to read. Spend them only on measured hot spots and leave a comment saying what was measured.

• ↔

  Memory versus time. Caches and look-up tables trade memory for speed, and generators trade a little speed for flat memory. State the budget you are optimising for.

• ↔

  Rewriting in a faster language versus a faster design. A C or Rust extension is the biggest gain for a tight numeric kernel, but it adds a build step, packaging work and a second language to maintain.

• Done when you can choose a better data structure for a slow lookup or queue and explain the growth difference.

• Done when you can cache a pure function and check the hit rate.

• Done when you can replace a list-building loop with a generator where the data is used once.

• Done when you can explain why np.vectorize is not vectorisation.

• Done when you can list the order of speed-up steps and say when to stop.