Module 4 ended with a promise: we now know how to choose the right algorithm, but between that choice and a fast program there is still a craft to learn. This lesson teaches the first part of that craft: how to make a given implementation run faster without changing what it does. And it starts with the rule that governs everything else: you don't optimize what you believe is slow, you optimize what you have measured to be slow. On that foundation we will build a four-level hierarchy — from the data structure change that multiplies speed by a hundred to the micro-optimization that scrapes out 20% — and, just as important as knowing how to optimize, we will learn to recognize when to stop.
Contents
- The golden rule: measure, don't guess
- The measurement tools:
perf_counter,timeit, andcProfile - The optimization hierarchy
- Level 1 — A better algorithm or data structure
- Level 2 — Hoisting invariant work out of loops
- Level 3 — Don't repeat work:
lru_cache - Level 4 — Idiomatic Python micro-optimizations
- Leaving early: early exit and short-circuiting
- When to stop optimizing
The golden rule: measure, don't guess
In 1974 Donald Knuth wrote the most quoted (and worst quoted) sentence in software engineering: "premature optimization is the root of all evil". The full quote is more nuanced and more useful:
"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%."
Knuth is not saying "don't optimize": he is saying that 97% of the code deserves no optimization and the remaining 3% deserves all of it. The problem is that intuition is terrible at locating that 3%. Developers systematically point at the "ugly-looking" loop while the actual time is being spent on an innocent line — an in on a list, a string concatenation — the kind we already unmasked in 02-01. Hence this module's golden rule:
- Measure first (with data of realistic size, not with 10 test elements).
- Optimize only what the measurement points at.
- Measure again to confirm the improvement exists and to quantify it.
Optimizing without measuring has two possible endings: complicating code that was never the problem (maintenance cost with no benefit) or, worse, "optimizing" blindly and making the program slower.
The measurement tools: perf_counter, timeit, and cProfile
Timing a snippet: time.perf_counter
The basic stopwatch. perf_counter() returns a high-resolution instant; subtracting two instants gives the elapsed time:
import time
start = time.perf_counter()
result = assign_trips(requests, buses) # the code being measured
end = time.perf_counter()
print(f"assign_trips: {end - start:.4f} s")It is perfect for measuring operations that take tenths of a second or more. For very fast snippets (microseconds), a single run is pure noise: the operating system, the cache, or the garbage collector distort the measurement.
Measuring fast snippets: timeit
timeit fixes that noise by running the snippet thousands of times and averaging:
import timeit
# How much does it cost to look up a stop in a list versus a set?
t_list = timeit.timeit("'University' in stops",
setup="stops = ['Stop %d' % i for i in range(5000)] + ['University']",
number=10_000)
t_set = timeit.timeit("'University' in stops",
setup="stops = set('Stop %d' % i for i in range(5000)) | {'University'}",
number=10_000)
print(f"list: {t_list:.4f} s set: {t_set:.4f} s")
# list: 0.5410 s set: 0.0004 s (ballpark: ~1000x difference)setupprepares the data (it is not timed).numberis how many times the statement runs; the result is the total time.
Locating the bottleneck: cProfile
When you don't know what to measure, cProfile measures everything: it runs the whole program and splits the time across functions.
Typical output (trimmed):
2.847 seconds
ncalls tottime cumtime filename:lineno(function)
1 0.002 2.847 planner.py:12(plan_day)
10000 0.011 2.790 planner.py:31(validate_tap_record)
10000000 2.779 2.779 {built-in method 'in' on list}
10000 0.041 0.055 planner.py:48(compute_fare)How to read it:
- ncalls: how many times the function was called.
- tottime: time spent inside the function, not counting the functions it calls.
- cumtime: cumulative time, including what it calls.
The reading is a complete diagnosis: plan_day hogs all the cumtime but has almost no tottime — it's not the culprit, it's someone it calls. That someone is validate_tap_record, and inside it the ten million calls to in on a list eat 2.78 of the 2.85 seconds: 97% of the time is on a single line. compute_fare, the function that "looked slow" because of its formulas, costs 55 thousandths of a second: irrelevant. Without the profile, admit it — you would have started with that one, wouldn't you?
The optimization hierarchy
Not all optimizations are worth the same. They are best attacked in descending order of impact:
| Level | What changes | Typical gain | Example |
|---|---|---|---|
| 1 | Algorithm or data structure | 10x – 1000x or more | list → set, linear → binary (M4) |
| 2 | Invariant work moved out of loops | 2x – 50x | hoisting repeated computations |
| 3 | Don't repeat work (result caching) | 2x – 100x | lru_cache on pure functions |
| 4 | Idiomatic micro-optimizations | 1.1x – 3x | comprehensions, join, built-ins |
The practical consequence: never start at level 4. Polishing microseconds in a loop that shouldn't exist is buffing the chrome on a car with no engine.
Level 1 — A better algorithm or data structure
This is the territory of Modules 2–4, so here we merely place it in the hierarchy using the case from the profile above. Every night RutaBus validates 10,000 tap records by checking that each pass is in the list of valid passes:
def validate_tap_records(tap_records, valid_passes): # valid_passes: list of 5,000
valid_records = []
for tap_record in tap_records: # 10,000 iterations
if tap_record["pass"] in valid_passes: # 'in' on a list: O(m) — 02-01!
valid_records.append(tap_record)
return valid_recordsCost: 10,000 × O(5,000) = 50 million comparisons. The fix is one line:
def validate_tap_records(tap_records, valid_passes):
valid = set(valid_passes) # O(m), just once
return [r for r in tap_records if r["pass"] in valid] # 'in' on a set: O(1)From O(n·m) to O(n + m): from 2.8 seconds to 4 thousandths of a second on the profiled machine. No optimization at the levels below comes anywhere near this — that is why level 1 comes first, and why the analysis and design modules came before this one.
Level 2 — Hoisting invariant work out of loops
A computation is loop-invariant if it produces the same result on every iteration. Inside the loop you pay for it n times; outside, once. Moving it out is called hoisting:
# BEFORE — report of tap records at stops currently in service
def tap_records_in_service(tap_records, stops):
result = []
for r in tap_records: # n iterations
active = {s["name"] for s in stops # rebuilt n times!
if s["in_service"]}
if r["stop"] in active and r["minute"] < len(tap_records) - 1:
result.append(r)
return resultThe set active doesn't depend on r: it is identical across all n iterations. And len(tap_records) - 1 doesn't change either. Both get hoisted:
# AFTER
def tap_records_in_service(tap_records, stops):
active = {s["name"] for s in stops if s["in_service"]} # once
last = len(tap_records) - 1 # once
return [r for r in tap_records if r["stop"] in active and r["minute"] < last]From O(n·p) to O(n + p). The most common camouflaged forms of the invariant: compiling a regular expression inside the loop (re.compile goes outside), opening/querying a resource per iteration, sorting a list that doesn't change, or calling a pure function with the same arguments inside the loop — which is exactly the level 3 case.
Level 3 — Don't repeat work: lru_cache
In 03-03 we wrote memoization by hand with a memo dictionary, and a note anticipated that Python ships it out of the box. The time has come to use it. RutaBus's fare function computes the price between two stops, and to do so it launches a Dijkstra (04-05) that is far from cheap:
from functools import lru_cache
@lru_cache(maxsize=None)
def fare(origin, destination):
dist, _ = dijkstra(network, origin) # expensive: paid only the FIRST time
minutes = dist[destination]
return 100 + 15 * minutes # cents: flat fee + per-minute charge
fare("Main Square", "Central Hospital") # computes: runs dijkstra → 235
fare("Main Square", "Central Hospital") # cache: returns 235 without running ANYTHING
print(fare.cache_info())
# CacheInfo(hits=1, misses=1, maxsize=None, currsize=1)The @lru_cache decorator wraps the function with an arguments → result dictionary: the first call with a given set of arguments runs the body and stores the result; subsequent calls return it in O(1). With thousands of users querying the same popular pairs of stops, the savings are massive. Three conditions for using it safely:
- The function must be pure: same result for the same arguments, no side effects. If fares change at midnight, you must invalidate with
fare.cache_clear(). - The arguments must be hashable (strings, numbers, and tuples yes; lists and dicts no).
maxsize=Nonemeans an unbounded cache — memory in exchange for time, the trade-off from 02-02. Amaxsize=1024bounds the memory by discarding the least recently used entries (that is what LRU, Least Recently Used, means); both sides of that coin will be analyzed in 05-02.
Level 4 — Idiomatic Python micro-optimizations
When the algorithm is already the right one and the profile still points at a hot loop, what remains is squeezing the interpreter. These improvements are modest but real, and they share something: the fast version is usually also the most idiomatic one.
| Slow pattern | Idiomatic alternative | Ballpark improvement* |
|---|---|---|
loop + append |
list comprehension | 1.2x – 1.5x |
s = s + chunk in a loop |
"".join(chunks) |
2x – 100x (grows with n, 02-01) |
| manual loop to sum/find the maximum | sum(), max(), min() |
2x – 5x |
| sorting with manual comparisons | sorted(data, key=...) |
2x – 10x |
| attribute/global looked up in a hot loop | copy into a local variable | 1.1x – 1.3x |
* Measured with timeit on CPython 3.12 over lists of 10⁵–10⁶ elements; yours will differ — which is why you measure.
The four patterns on RutaBus:
# 1) Comprehension: the loop runs in C, not in Python bytecode
times = [r["minute"] for r in tap_records if r["line"] == "L1"]
# 2) join: one single memory allocation instead of n copies (the O(n²) from 02-01)
report = "\n".join(f"{r['stop']};{r['minute']}" for r in tap_records)
# 3) Built-ins and sorted with key: traversals in C, with Timsort (04-03) thrown in
earliest_riser = min(tap_records, key=lambda r: r["minute"])
by_stop = sorted(tap_records, key=lambda r: r["stop"])
# 4) Local variable in a hot loop: locals resolve faster than
# attributes (obj.method) or globals, and the alias is looked up only once
def count_by_line(tap_records):
counter = {}
get = counter.get # local alias for the method
for r in tap_records:
line = r["line"]
counter[line] = get(line, 0) + 1
return counterPattern 4 is the only one that sacrifices some naturalness: reserve it for loops the profile has flagged. The other three should be your default style — they perform better and read better.
Leaving early: early exit and short-circuiting
The fastest operation is the one that never runs. Early exit means returning the result as soon as it is known, instead of completing the traversal:
# BEFORE: sweeps all 3,000 stops even if it finds the problem at the first one
def has_overcrowded_stop(stops):
overcrowded = False
for s in stops:
if s["occupancy"] > 0.9:
overcrowded = True
return overcrowded
# AFTER: leaves at the first hit — and any() says it in one line
def has_overcrowded_stop(stops):
return any(s["occupancy"] > 0.9 for s in stops)any() returns True as soon as one element qualifies; all() returns False as soon as one fails. With a generator as the argument (no square brackets), the list is never even materialized. This doesn't change the worst case — it is still O(n), as we saw in 02-03 — but it transforms the average case.
Its close relative is the short-circuit of and/or: in A and B, if A is false, B is not evaluated. Order the conditions from cheap to expensive:
# The O(1) check first; Dijkstra only fires if needed
if stop in network and fare("Main Square", stop) < 300:
quote_route(stop)When to stop optimizing
Optimization has diminishing returns and rising costs. Stopping criteria:
- When the requirement is met. If the nightly report must be ready in under 5 minutes and it takes 40 seconds, you're done. Optimizing further is cost with no benefit.
- When the next improvement costs readability. Optimized code tends to be code that is harder to understand, test, and modify. A 15% speedup in exchange for the next developer (you, in six months) needing an afternoon to understand the function almost never pays off.
- When the profile flattens out. If no function dominates the time anymore (everything shares 5–10%), the easy wins are gone; what remains are the memory (05-02) and parallelization (05-03) levels, or accepting the current performance.
- Document the non-obvious. If an optimization forces you to write strange code, a comment with the measurement that justifies it (
# join: from 12 s to 0.3 s with 10⁶ tap records) prevents someone from "cleaning it up" back into the slow version.
Common Mistakes and Tips
- Optimizing without a profile. The number-one mistake, from which all the others descend. Intuition points at the complex code; the time is usually in the simple code executed millions of times.
- Measuring with toy data. With 10 tap records, list and set take the same time and the O(n²) is invisible. Measure with sizes on the order of real production data.
- Measuring a single run of something fast. System noise dominates. For microseconds,
timeit; for seconds,perf_counterwith several repetitions. lru_cacheon impure functions. If the function depends on state that changes (updatable fares, the current time), the cache will serve stale results. Purity first, decorator second.- Mistaking the exception for the rule. Level 4 exists, but a program is not saved by micro-optimizations: if the profile shows a structural problem, go back to levels 1–3.
- Tip: keep the before/after measurements next to the change (in the commit or in a comment). An optimization without numbers is an anecdote; with numbers, it's engineering.
Exercises
Exercise 1. This snippet generates RutaBus's daily report. Identify — without running it — the performance problems it contains, classify them by hierarchy level (1–4), and rewrite it applying the fixes:
def daily_report(tap_records, vip_stops): # vip_stops: list of 200 names
report = ""
for r in tap_records: # ~100,000 tap records
if r["stop"] in vip_stops: # ??
line = r["stop"] + ";" + str(r["minute"]) + "\n"
report = report + line # ??
return reportExercise 2. The fare(origin, destination) function from the lru_cache section has a subtle efficiency defect even with the cache: every new (origin, destination) pair launches a full Dijkstra, even if a Dijkstra from that same origin has already been launched for another destination. Redesign the cache so that Dijkstra runs at most once per origin. Hint: cache a different function.
Exercise 3. Using timeit, write a measurement that compares "".join(...) against concatenation with += for building a string from 10,000 chunks. Before running it, write down your prediction of the difference; afterwards, compare it with the result and with the corresponding row of the level 4 table.
Solutions
Solution 1. Three problems: (a) in on the vip_stops list inside the loop — level 1, switch to a set; (b) the set must be built outside the loop — level 2, hoisting (building it inside would fall right back into the problem); (c) string concatenation in a loop, the O(n²) from 02-01 — level 4, join:
def daily_report(tap_records, vip_stops):
vip = set(vip_stops) # levels 1+2: a set, and outside the loop
return "\n".join(f"{r['stop']};{r['minute']}" # level 4: join + generator
for r in tap_records if r["stop"] in vip)With 100,000 tap records and 200 VIP stops, you go from ~20 million comparisons plus quadratic copies to a linear traversal. Note the order of the fix: structure first (1), then placement (2), the idiom last (4).
Solution 2. The unit of expensive work is "Dijkstra from one origin", not "one pair". Cache that unit:
@lru_cache(maxsize=None)
def distances_from(origin):
dist, _ = dijkstra(network, origin)
return dist # dict destination → minutes, computed ONCE per origin
def fare(origin, destination):
return 100 + 15 * distances_from(origin)[destination]With V stops, up to V² Dijkstras were run before (one per pair); now, at most V. The general lesson: cache at the granularity of the expensive work, not at the granularity of the query. (Sound familiar? It is the Dijkstra-per-origin vs. Floyd-Warshall discussion from 04-06 reappearing as a caching policy.)
Solution 3.
import timeit
t_concat = timeit.timeit(
"s = ''\nfor x in chunks:\n s = s + x",
setup="chunks = ['segment;%d\\n' % i for i in range(10_000)]",
number=100)
t_join = timeit.timeit(
"''.join(chunks)",
setup="chunks = ['segment;%d\\n' % i for i in range(10_000)]",
number=100)
print(f"concatenation: {t_concat:.3f} s join: {t_join:.3f} s ratio: {t_concat/t_join:.0f}x")
# Ballpark on CPython 3.12: concatenation ~0.9 s, join ~0.02 s → ~40xThe exact ratio depends on the machine and the Python version (CPython optimizes some += cases), and it grows with the number of chunks: concatenation is O(n²) and join is O(n). If your prediction was way off, that is precisely the lesson: this is why we measure.
Conclusion
This lesson has established the method that governs the whole module: measure first (perf_counter for slow things, timeit for fast ones, cProfile to know where to look), and optimize afterwards following the hierarchy — data structure (the 1000x jump of the tap-record set), hoisting invariants, result caching with lru_cache, and only at the end the idiomatic micro-optimizations with join, comprehensions, and any/all. And it has set limits: you stop when the requirement is met, when readability starts footing the bill, or when the profile flattens out. There is, however, a resource we have spent freely today: lru_cache(maxsize=None), the auxiliary set, the materialized list of the report... everything saves time by paying with memory. The next lesson flips the counter around: what to do when memory is the scarce resource — how to actually measure it, and how a RutaBus nightly job can process millions of tap records without ever holding them all in RAM at once.